# Module `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.

`type region`

The type of regions.

`type point`

The type of points.

`val create : unit -> point`

`create()` creates both a new region and a new point `p` in this region. It returns `p`.

`val capacity : int`

`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.

`val after : point -> point`

`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.

`val before : point -> point`

`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.

`val compare : point -> point -> int`

`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.

`val region : point -> region`

`region p` returns the region that the point `p` inhabits.

`val same : region -> region -> bool`

`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.

`val invalidate_open_interval : point -> point -> unit`

`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.

`val invalidate_semi_open_interval : point -> point -> unit`

`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).