Module Assocext

module Assocext: sig  end

An assocext object is used to keep associations between non-overlapping extents of integers and values.

An associative extent should be seen as a null array and an ordered list of extent, each extent possessing a value and covering a certain part of the array. Single extents are contiguous, and can not overlap. An extent can have zero length. Many extents of zero length can fit between the same two elements of the array - they are not said to overlap. They can also fit between two non-zero-length extents. However, they won't fit inside an extent. The ordering is maintained among zero-length extent.

A range in the list above is also called a reserved extent. The complement of the union of all the reserved ranges can be written as a disjoint union of non-overlapping non-empty contiguous intervals of the array, called free intervals.

The functionality of assocexts is driven by the functionality desired of ligands. For instance, zero-length reserved extents are important because we can collapse any given non-empty extent to an empty one. Also, there is currently no way to reserve an empty extent between, say, two other given extent, since the reserve function below always reserves the leftmost possible extent. But this functionality is not needed.

This type is not thread-safe.
See also testing/test_assocext.ml for simple examples of how to use this module.

An opaque type which represents an extent in the list of associative extents.

The length can be zero. For instance, a string of length one has three extents: the strict beginning of the string {start = 0; length = 0}; the entire string {start = 0; length = 1}; and the strict end of the string {start = 1; length = 0}.

val get_interval : 'a extent -> interval

Get the interval of an opaque extent type.

val get_value : 'a extent -> 'a

Get the value attached to an opaque extent type.

The type of associative extents which associate elements of type 'a to extents.

val create : int -> 'a t

create n creates a new associative extent of length n. It originally has a single interval in it, which is free and whose range is {start = 0; length = n}.

val get_length : 'a t -> int

get_length q returns the total length of the assocext q. It was set at the beginning by the create command, and may be changed through the use of the change_length function below.

exception Illegal_range

Raised by some operations when a passed range is illegal.

val check : 'a t -> int -> int -> bool

check e start len returns true if the range of length len starting at start does not overlap with any reserved range, false otherwise. In other words, it returns true if and only if reserve (see below) with the same parameters does not raise an exception.

If start + len is greater than the length of the original extent, exception Illegal_range will be raised.

This also applies to a range of length zero.

exception Extent_occupied

Raised when attempting to reserve an interval which overlaps with an already reserved extent.

val reserve : 'a t -> 'a -> int -> int -> 'a extent

reserve q v start len will allocate value v to a new reserved extent ranging from start to start + len and return that extent, if that range does not overlap with an existing reserved extent. If not, it will raise Extent_occupied.

If start + len is greater than the length of the original extent, exception Illegal_range will be raised.

If the range has length zero, the reserved range will be the leftmost (that is, first) in the ordering.

exception Extent_illegal

Raised by certain operations when using a stale extent.

val free : 'a extent -> 'a t -> unit

free e q returns the previously reserved extent e in the associative extent queue q to the free state. e must correspond exactly to a reserved extent, otherwise exception Extent_illegal is raised.

val list_extents : 'a t -> 'a extent list

Returns the list of reserved extents. FIXME: Should be sorted.

val list_free_intervals : 'a t -> interval list

Returns a list of free intervals. FIXME: Should be sorted.

exception Illegal_position

Raised by get_pos_extent below.

val get_pos_extent : 'a t -> int -> 'a holder

get_pos_extent q pos returns either the reserved extent or the free interval which contains the array entry (of length one!) at position pos, or throws Illegal_position if the position does not fit within the extent. The range returned is either free or reserved, but necessarily non-empty.

val change_length : 'a extent -> 'a t -> int -> unit

change_length e q n sets the length of the reserved extend e in the assocext q to n, shifting all the other extents if necessary (if the length changes). e must be reserved, otherwise exception Extent_illegal is raised. The length may be set to zero. The validity of all the other extents is unaffected.

exception Out_of_bounds

Raised by some operations when attempting to get to an extent which is beyond the legal range.

exception Empty

Raised by first and last if the assocexts are empty.

val first : 'a t -> 'a extent

Returns the first extent in the assocext.

val last : 'a t -> 'a extent

Returns the last extent in the assocext.

val next_extent : 'a extent -> 'a extent

next_extent e q returns the extent which follows e in the assocext q. Raises Out_of_bounds if e is the last extent.

val prev_extent : 'a extent -> 'a extent

Assocext.next_extent.

val iter : ('a extent -> unit) -> 'a t -> unit

iter f q applies the function f to each extent e of q, in the order in which they appear, starting from the first to the last. f must have type 'a extent -> unit.