`Oma`

This library implements an order maintenance data structure.

It is based on Section 3 of the paper "Two Simplified Algorithms for Maintaining Order in a List", by Bender, Cole, Demaine, Farach-Colton, and Zito (2002).

An order maintenance data structure represents a collection of points, organized in a strict total order relation. In other words, the points can be arranged along a straight line. The main operations offered by the data structure include `before`

and `after`

, which insert a new point before or after an existing point, and `compare`

, which determines the relative order of two points.

Such a totally ordered collection of points is known as a region. Several independent regions can of course co-exist; each call to `create`

creates a fresh region.

`val create : unit -> point`

`create()`

creates both a new region and a new point `p`

in this region. It returns `p`

.

`capacity`

is the maximum number of points that can be created within a single region. On a 64-bit machine, this number is so large that it is effectively impossible to exceed this capacity.

`after p`

creates a new point `p'`

, in the same region as the point `p`

, and inserts `p'`

immediately after the point `p`

in the total order. The point `p`

must be valid. The point `p'`

is returned.

`before p`

creates a new point `p'`

, in the same region as the point `p`

, and inserts `p'`

immediately before the point `p`

in the total order. The point `p`

must be valid. The point `p'`

is returned.

`compare p1 p2`

requires the points `p1`

and `p2`

to be valid and to inhabit the same region. It determines which of these points comes first in the total order. It returns -1, 0, or +1 to indicate which of the conditions `p1 < p2`

, `p1 = p2`

, and `p1 > p2`

holds.

`same r1 r2`

determines whether the regions `r1`

and `r2`

are the same region.

`val invalidate : point -> unit`

`invalidate p`

destroys the point `p`

. This point is removed from the total order and is no longer part of the data structure. An invalidated point must not be used any more: that is, it must not be supplied as an argument to any operation, except `is_valid`

and `region`

.

`val is_valid : point -> bool`

`is_valid p`

determines whether the point `p`

is currently valid or has been invalidated.

`invalidate_open_interval p1 p2`

invalidates all points in the open interval comprised between the points `p1`

and `p2`

. The points `p1`

and `p2`

are excluded: they are not part of this open interval. If the interval is empty, nothing happens. The points `p1`

and `p2`

must be valid and must inhabit the same region.

`invalidate_semi_open_interval p1 p2`

invalidates all points in the semi-open interval comprised between the points `p1`

and `p2`

. The point `p1`

is included in this semi-open interval, whereas the point `p2`

is excluded. If the interval is empty, nothing happens. The points `p1`

and `p2`

must be valid and must inhabit the same region.

`module Unsafe : sig ... end`

The operations in the submodule `Unsafe`

are deemed unsafe because they expose unstable information, that is, information that will become out of date when further operations are performed. This unstable information includes a point's current tag, predecessor, and successor, as well as a region's current sequence of points. Unsafe operations can be useful in some situations (e.g., when debugging).