baby 20240619 · OCaml Package

The functor Baby.Make constructs balanced binary search trees based on a user-supplied balancing scheme. The main operation that the user is expected to provide is join.

Parameters

module E : OrderedType

module _ : CORE with type key = E.t

Signature

type elt = E.t

The type of elements.

type set

The abstract type of sets. A set is an immutable data structure.

type t = set

A synonym for the type set.

Constructing sets

val empty : set

empty is the empty set.

val singleton : elt -> t

singleton x returns a set whose sole element is x.

val add : elt -> set -> set

add x s returns a set that contains all elements of the set s, plus x. Thus, it is logically equal to union (singleton x) s.

If the result is logically equal to s, then the result is physically equal to s.

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

val remove : elt -> set -> set

remove x s returns a set that contains all elements of the set s, except x. It is equivalent to diff s (singleton x).

If the result is logically equal to s, then the result is physically equal to s.

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

val remove_min_elt : set -> set

If the set s is nonempty, then remove_min_elt s returns the set s, deprived of its minimum element. Otherwise, it raises Not_found.

It is equivalent to remove (min_elt s) s.

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

val remove_max_elt : set -> set

If the set s is nonempty, then remove_max_elt s returns the set s, deprived of its maximum element. Otherwise, it raises Not_found.

It is equivalent to remove (max_elt s) s.

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

val union : set -> set -> set

union s1 s2 returns the union of the sets s1 and s2, that is, a set that contains all elements of the set s1 and all elements of the set s2.

The weight-balanced-tree implementation (Baby.W) offers the following guarantee: if the result is logically equal to s1 or to s2, then the result is physically equal to s1 or to s2. The height-balanced tree implementation (Baby.H) does not offer this guarantee.

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val inter : set -> set -> set

inter s1 s2 returns the intersection of the sets s1 and s2, that is, a set that contains the common elements of the sets s1 and s2.

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val diff : set -> set -> set

diff s1 s2 returns the difference of the sets s1 and s2, that is, a set that contains the elements of the set s1 that do not appear in the set s2.

if the result is logically equal to s1, then the result is physically equal to s1.

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val xor : set -> set -> set

xor s1 s2 returns the symmetric difference of the sets s1 and s2, that is, a set that contains the elements of the set s1 that do not appear in the set s2 and the elements of the set s2 that do not appear in the set s1.

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val split : elt -> set -> set * bool * set

split x s returns a triple (l, present, r), where l is the set of the elements of s that are strictly less than x, r is the set of the elements of s that are strictly greater than x, and present is true if and only if x is a member of the set s.

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

Querying sets

val is_empty : set -> bool

is_empty s determines whether the set s is the empty set.

Time complexity: $O(1)$ .

val min_elt : set -> elt

If the set s is nonempty, min_elt s returns the minimum element of this set. Otherwise, it raises Not_found.

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

val min_elt_opt : set -> elt option

If the set s is nonempty, min_elt_opt s returns Some x, where x is the minimum element of this set. Otherwise, it returns None.

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

val max_elt : set -> elt

If the set s is nonempty, max_elt s returns the maximum element of this set. Otherwise, it raises Not_found.

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

val max_elt_opt : set -> elt option

If the set s is nonempty, max_elt_opt s returns Some x, where x is the maximum element of this set. Otherwise, it returns None.

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

val choose : set -> elt

If the set s is nonempty, choose s returns an arbitrary element of this set. Otherwise, it raises Not_found.

choose respects equality: if the sets s1 and s2 are equal then choose s1 and choose s2 are equal.

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

val choose_opt : set -> elt option

If the set s is nonempty, choose_opt s returns Some x, where x is an arbitrary element of this set. Otherwise, it returns None.

choose_opt respects equality: if the sets s1 and s2 are equal then choose_opt s1 and choose_opt s2 are equal.

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

val mem : elt -> set -> bool

mem x s determines whether the element x is a member of the set s.

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

val find : elt -> set -> elt

If x is a member of the set s, then find x s returns the unique element x' of the set s such that x and x' are equivalent. (We say that x and x' are equivalent if compare x x' = 0 holds.) Otherwise, it raises Not_found.

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

val find_opt : elt -> set -> elt option

If x is a member of the set s, then find_opt x s returns Some x', where x' is the unique element of the set s such that x and x' are equivalent. (We say that x and x' are equivalent if compare x x' = 0 holds.) Otherwise, it returns None.

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

val disjoint : set -> set -> bool

disjoint s1 s2 determines whether the sets s1 and s2 are disjoint, that is, whether their intersection is empty. It is equivalent to is_empty (inter s1 s2).

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val subset : set -> set -> bool

subset s1 s2 determines whether the set s1 is a subset of the set s2, that is, whether their difference is empty. It is equivalent to is_empty (diff s1 s2).

Time complexity: $O(m.\log (\frac{n}{m}))$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val equal : set -> set -> bool

equal s1 s2 determines whether the sets s1 and s2 are equal, that is, whether their symmetric difference is empty. It is equivalent to is_empty (xor s1 s2).

Time complexity: $O(m)$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val compare : set -> set -> int

compare is a total ordering function over sets. (Which specific ordering is used is unspecified.)

Time complexity: $O(m)$ , where $m$ is the size of the smaller set and $n$ is the size of the larger set.

val cardinal : set -> int

cardinal s returns the cardinal of the set s, that is, the number of its elements.

Time complexity: in the weight-balanced-tree implementation (Baby.W), $O(1)$ ; in the height-balanced-tree implementation (Baby.H), $O(n)$ , where $n$ is the size of the set s.

Conversions to and from sets

val of_list : elt list -> set

of_list xs constructs a set whose elements are the elements of the list xs.

This function has adaptive time complexity. In the worst case, its complexity is $O(n.\log n)$ , where $n$ is the length of the list xs. However, if the list xs is sorted, then its complexity is only $O(n)$ . In between these extremes, its complexity degrades gracefully.

val to_list : set -> elt list

to_list s constructs a list whose elements are the elements of the set s, in increasing order.

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

val elements : set -> elt list

elements is a synonym for to_list.

val of_array : elt array -> set

of_array xs constructs a set whose elements are the elements of the array xs.

This function has adaptive time complexity. In the worst case, its complexity is $O(n.\log n)$ , where $n$ is the length of the array xs. However, if the array xs is sorted, then its complexity is only $O(n)$ . In between these extremes, its complexity degrades gracefully.

val to_array : set -> elt array

to_array s constructs an array whose elements are the elements of the set s, in increasing order.

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

val of_seq : elt Seq.t -> set

of_seq xs constructs a set whose elements are the elements of the sequence xs. (The whole sequence is immediately consumed.)

This function has adaptive time complexity. In the worst case, its complexity is $O(n.\log n)$ , where $n$ is the length of the list xs. However, if the sequence xs is sorted, then its complexity is only $O(n)$ . In between these extremes, its complexity degrades gracefully.

val add_seq : elt Seq.t -> set -> set

add_seq xs s constructs a set whose elements are the elements of the sequence xs and the elements of the set s.

It is equivalent to union (of_seq xs) s.

Its time complexity is the combined time complexity of of_seq and union.

val to_seq : set -> elt Seq.t

to_seq s constructs a (persistent) increasing sequence whose elements are the elements of the set s.

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

val to_seq_from : elt -> set -> elt Seq.t

to_seq_from x s constructs a (persistent) increasing sequence whose elements are the elements of the set s that are greater than or equal to x.

The time complexity of consuming the entire sequence is $O(n)$ , where $n$ is the size of the set s. The time complexity of demanding one element is $O(\log n)$ .

val to_rev_seq : set -> elt Seq.t

to_rev_seq s constructs a (persistent) decreasing sequence whose elements are the elements of the set s.

The time complexity of consuming the entire sequence is $O(n)$ , where $n$ is the size of the set s. The time complexity of demanding one element is $O(\log n)$ .

Iterating, searching, transforming sets

val iter : (elt -> unit) -> set -> unit

iter yield s produces an increasing sequence whose elements are the elements of the set s.

This is achieved by applying the function yield in turn to each element of the sequence.

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

val fold : (elt -> 'a -> 'a) -> set -> 'a -> 'a

fold yield s accu produces an increasing sequence whose elements are the elements of the set s.

This is achieved by applying the function yield in turn to each element of the sequence. An accumulator, whose initial value is accu, is threaded through this sequence of function invocations.

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

val for_all : (elt -> bool) -> set -> bool

for_all p s tests whether all elements x of the set s satisfy p x = true.

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

val exists : (elt -> bool) -> set -> bool

exists p s tests whether at least one element x of the set s satisfies p x = true.

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

val find_first : (elt -> bool) -> t -> elt

find_first f s requires the function f to be a monotonically increasing function of elements to Boolean values. It returns the least element x of the set s such that f x is true, if there is such an element. If there is none, it raises Not_found.

In other words, when the elements of the set are enumerated as an increasing sequence, find_first f s returns the first element of the sequence that follows the threshold of the function f.

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

val find_first_opt : (elt -> bool) -> t -> elt option

find_first_opt f s requires the function f to be a monotonically increasing function of elements to Boolean values. It returns Some x, where x is the least element of the set s such that f x is true, if there is such an element. If there is none, it returns None.

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

val find_last : (elt -> bool) -> t -> elt

find_last f s requires the function f to be a monotonically decreasing function of elements to Boolean values. It returns the greatest element x of the set s such that f x is true, if there is such an element. If there is none, it raises Not_found.

In other words, when the elements of the set are enumerated as an increasing sequence, find_last f s returns the last element of the sequence that precedes the threshold of the function f.

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

val find_last_opt : (elt -> bool) -> t -> elt option

find_last_opt f s requires the function f to be a monotonically decreasing function of elements to Boolean values. It returns Some x, where x is the greatest element of the set s such that f x is true, if there is such an element. If there is none, it returns None.

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

val map : (elt -> elt) -> set -> set

map f s computes the image of the set s through the function f, that is, in mathematical notation, the set $\{ y \mid y = f(x) \wedge x \in s \}$ .

If, for every element x of the set s, f x is x, then the result is physically equal to s.

If the function f is monotonically increasing, then the time complexity is $O(n)$ , where $n$ is the size of the set s; otherwise, it is $O(n.\log n)$ .

val filter : (elt -> bool) -> set -> set

filter p s returns the set of the elements x of the set s such that p x is true.

If, for every element x of the set s, p x is true, then the result of filter p s is physically equal to s.

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

val filter_map : (elt -> elt option) -> set -> set

filter_map f s computes the set $\{ y \mid \mathit{Some}\; y = f(x) \wedge x \in s \}$ .

If, for every element x of the set s, f x is Some x, then the result is physically equal to s.

If the function f (restricted to the elements that it retains) is monotonically increasing, then the time complexity is $O(n)$ , where $n$ is the size of the set s; otherwise, it is $O(n.\log n)$ .

val partition : (elt -> bool) -> set -> set * set

partition p s returns a pair (s1, s2), where s1 is the set of the elements x of s such that p x is true, and s2 is the set of the elements of s such that p x is false.

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

Random access

Caution: the following functions exist only in the weight-balanced-tree implementation (Baby.W). In the height-balanced tree implementation (Baby.H), they raise an exception of the form Failure _.

In the following descriptions, a set is viewed as an increasing sequence of elements. Thus, the index of an element is its index in the sequence. The valid indices in a set s are the integers in the semi-open interval of 0 to cardinal s.

val get : set -> int -> elt

get s i requires 0 <= i && i < cardinal s. It returns the element that lies at index i in the set s.

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

val index : elt -> set -> int

If x is a member of the set s, then index x s returns the index i where this element lies in the set s. (Thus, get s i is x.) Otherwise, it raises Not_found.

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

val cut : set -> int -> set * set

cut s i requires 0 <= i && i <= cardinal s. It returns a pair (s1, s2), where s1 is the set of the elements of s whose index is less than i, and s2 is the set of the elements of s whose index is greater than or equal to i.

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

val cut_and_get : set -> int -> set * elt * set

cut_and_get s i requires 0 <= i && i < cardinal s. It returns a triple (s1, x, s2), where s1 is the set of the elements of s whose index is less than i, x is the element of s at index i, and s2 is the set of the elements of s whose index is greater than i.

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

Enumerations

module Enum : sig ... end

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

package baby

Parameters

Signature

Constructing sets

Querying sets

Conversions to and from sets

Iterating, searching, transforming sets

Random access

Enumerations