baltree: basic balanced binary trees

This module implements balanced ordered binary trees. All operations over binary trees are applicative (no side-effects). The set and map modules are based on this module. This modules gives a more direct access to the internals of the binary tree implementation than the set and map abstractions, but is more delicate to use and not as safe. For advanced users only.

type 'a t = Empty | Node of 'a t * 'a * 'a t * int

The type of trees containing elements of type 'a. Empty is the empty tree (containing no elements).

type 'a contents = Nothing | Something of 'a

Used with the functions modify and split, to represent the presence or the absence of an element in a tree.

value add: ('a -> int) -> 'a -> 'a t -> 'a t

add f x t inserts the element x into the tree t. f is an ordering function: f y must return 0 if x and y are equal (or equivalent), a negative integer if x is smaller than y, and a positive integer if x is greater than y. The tree t is returned unchanged if it already contains an element equivalent to x (that is, an element y such that f y is 0). The ordering f must be consistent with the orderings used to build t with add, remove, modify or split operations.

value contains: ('a -> int) -> 'a t -> bool

contains f t checks whether t contains an element satisfying f, that is, an element x such that f x is 0. f is an ordering function with the same constraints as for add. It can be coarser (identify more elements) than the orderings used to build t, but must be consistent with them.

value find: ('a -> int) -> 'a t -> 'a

Same as contains, except that find f t returns the element x such that f x is 0, or raises Not_found if none has been found.

value remove: ('a -> int) -> 'a t -> 'a t

remove f t removes one element x of t such that f x is 0. f is an ordering function with the same constraints as for add. t is returned unchanged if it does not contain any element satisfying f. If several elements of t satisfy f, only one is removed.

value modify: ('a -> int) -> ('a contents -> 'a contents) -> 'a t -> 'a t

General insertion/modification/deletion function. modify f g t searchs t for an element x satisfying the ordering function f. If one is found, g is applied to Something x; if g returns Nothing, the element x is removed; if g returns Something y, the element y replaces x in the tree. (It is assumed that x and y are equivalent, in particular, that f y is 0.) If the tree does not contain any x satisfying f, g is applied to Nothing; if it returns Nothing, the tree is returned unchanged; if it returns Something x, the element x is inserted in the tree. (It is assumed that f x is 0.) The functions add and remove are special cases of modify, slightly more efficient.

value split: ('a -> int) -> 'a t -> 'a t * 'a contents * 'a t

split f t returns a triple (less, elt, greater) where less is a tree containing all elements x of t such that f x is negative, greater is a tree containing all elements x of t such that f x is positive, and elt is Something x if t contains an element x such that f x is 0, and Nothing otherwise.

value compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int

Compare two trees. The first argument f is a comparison function over the tree elements: f e1 e2 is zero if the elements e1 and e2 are equal, negative if e1 is smaller than e2, and positive if e1 is greater than e2. compare f t1 t2 compares the fringes of t1 and t2 by lexicographic extension of f.