baby 20241204 · OCaml Package

The submodule Enum offers an abstract data type of enumerations, which allow efficient iteration over a map.

type 'a enum

The type of enumerations. An enumeration is an immutable data structure.

An enumeration represents an increasing sequence of bindings (that is, a sequence of bindings, sorted by increasing order of keys). It can also be thought of as a map.

Enumerations and maps represent the same abstract object (namely, a mathematical map), but have different internal representations, and support a different array of operations. In particular, enumerations support head, tail, and from, which allow efficient iteration.

type 'a t = 'a enum

The type 'a t is a synonym for the type 'a enum.

val empty : 'a enum

empty is the empty enumeration.

val is_empty : 'a enum -> bool

is_empty e determines whether the enumeration e is empty.

Time complexity: $O(1)$ .

val enum : 'a map -> 'a enum

enum m returns an enumeration of the map m. This enumeration can be thought of as an increasing sequence whose elements are the bindings of the map m.

Time complexity: $O(\log n)$ , where $n$ is the size of the map m.

val from_enum : key -> 'a map -> 'a enum

from_enum x m returns an enumeration whose elements are the bindings of the map m whose key is greater than or equal to x. It is equivalent to from x (enum m).

Time complexity: $O(\log n)$ , where $n$ is the size of the map m.

val head : 'a enum -> 'a binding

If the enumeration e is nonempty, then head e returns its first element (that is, the binding whose key is the least key). Otherwise, it raises Not_found.

Time complexity: $O(1)$ .

val tail : 'a enum -> 'a enum

If the enumeration e is nonempty, then tail e returns this enumeration, deprived of its first element (that is, deprived of the binding whose key is the least key). Otherwise, it raises Not_found.

The worst-case time complexity of this operation is $O(\log n)$ , where $n$ is the size of the enumeration e. However, its amortized time complexity is only $O(1)$ : that is, the cost of enumerating all bindings of a map of size $n$ , using head and tail, is only $O(n)$ .

val head_opt : 'a enum -> 'a binding option

If the enumeration e is nonempty, then head_opt e returns its first element (that is, the binding whose key is the least key). Otherwise, it returns None.

Time complexity: $O(1)$ .

val tail_opt : 'a enum -> 'a enum option

If the enumeration e is nonempty, then tail_opt e returns this enumeration, deprived of its first element (that is, deprived of the binding whose key is the least key). Otherwise, it returns None.

val from : key -> 'a enum -> 'a enum

from x e returns the enumeration obtained from the enumeration e by skipping (removing) the bindings whose key is less than x.

Time complexity: $O(\log k)$ , where $k$ is the number of bindings that are skipped.

val to_seq : 'a enum -> 'a binding Seq.t

to_seq e constructs a (persistent) increasing sequence whose elements are the elements of the enumeration e.

The time complexity of consuming the entire sequence is $O(n)$ , where $n$ is the size of the enumeration e. The worst-case time complexity of demanding one element is $O(\log n)$ .

val elements : 'a enum -> 'a map

elements e returns a map whose bindings are the elements of the enumeration e.

Time complexity: $O(\log n)$ , where $n$ is the size of the enumeration e.

val length : 'a enum -> int

length e returns the length of the enumeration e, that is, the number of its elements.

Time complexity: in the weight-balanced-tree implementation (Baby.W), $O(\log n)$ , where $n$ is the size of the enumeration e; in the height-balanced-tree implementation (Baby.H), $O(n)$ .

package baby