An optimized representation for sets, i.e. maps to unit: we do not store a reference to unit (note that you can further optimize when you know the representation of the key). This is the node used in MakeHeterogeneousSet and MakeSet.
We use a uniform type 'map view to pattern match on maps and sets The actual types 'map t can be a bit different from 'map view to allow for more efficient representations, but view should be a constant time operation for quick conversions.
module Key : sig ... endtype 'a key = 'a Key.tThe type of keys.
The type of value, which depends on the type of the key and the type of the map.
val empty : 'map tThe empty map
A singleton leaf, similar to BASE_MAP.singleton
A branch node. This shouldn't be called externally unless you know what you're doing! Doing so could easily break the data structure's invariants.
When called, it assumes that:
tree0 nor tree1 should be empty.branching_bit should have a single bit setprefix should be normalized (bits below branching_bit set to zero)tree0 should have their to_int start by prefix followed by 0 at position branching_bit).tree1 should have their to_int start by prefix followed by 0 at position branching_bit).type 'map view = private | Empty : 'map viewCan happen only at the toplevel: there is no empty interior node.
*)| Branch : {} -> 'map viewSame constraints as branch:
branching_bit contains only one bit set; the corresponding mask is (branching_bit - 1).prefix is normalized: the bits below the branching_bit are set to zero (i.e. prefix & (branching_bit - 1) = 0).tree0 should have their to_int start by prefix followed by 0 at position branching_bit).tree1 should have their to_int start by prefix followed by 0 at position branching_bit).| Leaf : {} -> 'map viewA key -> value mapping.
*)This makes the map nodes accessible to the pattern matching algorithm; this corresponds 1:1 to the SimpleNode implementation. This just needs to be copy-and-pasted for every node type.
val is_empty : 'map t -> boolCheck if the map is empty. Should be constant time.