Associate a unique number to each node, so they can be used as keys in sets or maps.
include NODEThe 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.
val to_int : 'a t -> intUnique number for each node.
This is not hash-consing. Equal nodes created separately will have different identifiers. On the flip side, nodes with equal identifiers will always be physically equal.