Module `SET.Enum`

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

type enum

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

An enumeration represents an increasing sequence of elements. It can also be thought of as a set.

Enumerations and sets represent the same abstract object (namely, a mathematical set), 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 t = enum

The type t is a synonym for the type enum.

val empty : enum

empty is the empty enumeration.

val is_empty : enum -> bool

is_empty e determines whether the enumeration e is empty.

Time complexity: $O(1)$ .

val enum : set -> enum

enum s returns an enumeration of the set s. This enumeration can be thought of as an increasing sequence whose elements are the elements of the set s.

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

val from_enum : elt -> set -> enum

from_enum x s returns an enumeration whose elements are the elements of the set s that are greater than or equal to x. It is equivalent to from x (enum s).

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

val head : enum -> elt

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

Time complexity: $O(1)$ .

val tail : enum -> enum

If the enumeration e is nonempty, then tail e returns this enumeration, deprived of its first element (that is, its least element). 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 elements of a set of size $n$ , using head and tail, is only $O(n)$ .

val head_opt : enum -> elt option

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

Time complexity: $O(1)$ .

val tail_opt : enum -> enum option

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

val from : elt -> enum -> enum

from x e returns the enumeration obtained from the enumeration e by skipping (removing) the elements that are less than x.

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

val to_seq : enum -> elt 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 : enum -> set

elements e returns a set whose elements are the elements of the enumeration e.

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

val length : 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

Module SET.Enum

Module `SET.Enum`