Module Base__.Avltree

A low-level, mutable AVL tree.

It is not intended to be used directly by casual users. It is used for implementing other data structures. The interface is somewhat ugly, and it's that way for a reason. The goal of this module is minimum memory overhead, and maximum performance.

Points of Ugliness

After all this, you're probably asking yourself whether all these hacks are worth it. Yes! They are! With them, we built a hash table that is faster than INRIA's (no small feat actually), with the same memory overhead, with sane add semantics (the add semantics they used were a performance hack), and with worst case log(N) insertion, lookup, and removal. I'd say that's worth it. But for those of you who will feel morally compelled to put in a CR about this interface. I challenge you to write a better interface, implement a hash table with it, and show that your table has better performance than Hashtbl.

type ('k, 'v) t = private
| Empty
| Node of {
mutable left : ('k'vt;
key : 'k;
mutable value : 'v;
mutable height : int;
mutable right : ('k'vt;
}
| Leaf of {
key : 'k;
mutable value : 'v;
}

We expose t to allow an optimization in Hashtbl that makes iter and fold more than twice as fast. We keep the type private to reduce opportunities for external code to violate avltree invariants.

val empty : ('k'vt
val invariant : ('k'vt ‑> compare:('k ‑> 'k ‑> int) ‑> unit

check invariants, raise an exception if any invariants fail

val add : ('k'vt ‑> replace:bool ‑> compare:('k ‑> 'k ‑> int) ‑> added:bool Base__.Import.ref ‑> key:'k ‑> data:'v ‑> ('k'vt

adds the specified key and data to the tree destructively (previous t's are no longer valid) using the specified comparison function. O(log(N)) time, O(1) space. The returned t is the new root node of the tree, and should be used on all further calls to any other function in this module. The bool ref, added, will be set to true if a new node is added to the tree, or false if an existing node is replaced (in the case that the key already exists). If replace (default true) is true then add will overwrite any existing mapping for key. If replace is false, and there is an existing mapping for key then add has no effect.

val first : ('k'vt ‑> ('k * 'v) option

Returns the first (leftmost) or last (rightmost) element in the tree

val last : ('k'vt ‑> ('k * 'v) option
val find : ('k'vt ‑> compare:('k ‑> 'k ‑> int) ‑> 'k ‑> 'v option

if the specified key exists in the tree, return the corresponding value. O(log(N)) time and O(1) space.

val find_and_call : ('k'vt ‑> compare:('k ‑> 'k ‑> int) ‑> 'k ‑> if_found:('v ‑> 'a) ‑> if_not_found:('k ‑> 'a) ‑> 'a

find_and_call t ~compare k ~if_found ~if_not_found

is equivalent to:

match find t ~compare k with Some v -> if_found v | None -> if_not_found k

except that it doesn't allocate the option.

val mem : ('k'vt ‑> compare:('k ‑> 'k ‑> int) ‑> 'k ‑> bool

return true if key is present in the tree, otherwise return false.

val remove : ('k'vt ‑> removed:bool Base__.Import.ref ‑> compare:('k ‑> 'k ‑> int) ‑> 'k ‑> ('k'vt

remove key destructively from the tree if it exists, return the new root node. Previous root nodes are not usable anymore, do so at your peril. the removed ref will be set to true if a node was actually removed, or false otherwise.

val fold : ('k'vt ‑> init:'a ‑> f:(key:'k ‑> data:'v ‑> 'a ‑> 'a) ‑> 'a

fold over the tree

val iter : ('k'vt ‑> f:(key:'k ‑> data:'v ‑> unit) ‑> unit

iterate over the tree