oma 20240106 · 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 check : point -> unit

check p has no effect. It is used while testing this library.

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