Basic ordering operations

type t

An element of an ordering.

val root : unit -> t

Create a new ordering with a single element. O(1)

val after : t -> t

after t inserts a new element to the ordering, greater than t but less than all existing elements greater than t.

O(1) amortized.

val before : t -> t

before t inserts a new element to the ordering, less than t but greater than all existing elements less than t.

O(1) amortized.

val inside : t -> t

val outside : t -> t

val same_order : t -> t -> bool

Check if two elements belong to the same order. O(1)

type rel =

| Before
| Inside
| Equal
| Outside
| After

Compare two elements. O(1)

val compare : t -> t -> rel

val cardinal : t -> int

How many elements are ordered. O(1)

Memory management

val forget : t -> unit

When you know you are not going to use an element any longer, forget it to release memory. It makes operations slightly faster to not have to wait for the GC to release elements.

val is_valid : t -> bool

After calling forget, an element should not be used. You can check if it is the case with is_valid.

Algorithm due to: Two Simplified Algorithms for Maintaining Order in a List Bender et al., 2002

val unsafe_check : t -> string -> unit