oma 20240619 (latest) · OCaml Package

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

package oma