module type Set_ = sig .. end
This module represents the core functionality of Sets. It defines
a few extra types to abstract over exact implement details of its
operations. Also, it defines the elements and the set type to be
polymorphic, although this can later be refined to a monomorphic
type (as is done bye Reins.Sets.MonoSetSig.
type 'a elt_
The type of elements in the set
type 'a set
The type of sets
type ('a, 'b) result_
The result_ type is used for operations that may either
return just a result or a result a something else. Most trees
conform to the former, while splay trees use the latter
(e.g. the mem function may modify the tree)
val empty : 'a set
The empty set
val is_empty : 'a set -> bool
Returns true if the set is empty
val mem : 'a elt_ ->
'a set -> (bool, 'a) result_
mem x t Returns true if x is contained in the set t.
More precisely, there exists an element y in t such that
compare x y = 0.
val add : 'a elt_ -> 'a set -> 'a set
add x t Return the set t with the element x.
val singleton : 'a elt_ -> 'a set
singleton x Return the set consisting of only the element
x
val remove : 'a elt_ -> 'a set -> 'a set
remove x t Return the set t with the element x removed.
Does not raise an exception if t does not contain x.
val min_elt : 'a set ->
('a elt_, 'a) result_
Return the smallest element in the set. If the set is empty,
raises Not_found
val max_elt : 'a set ->
('a elt_, 'a) result_
Return the largest element in the set. If the set is empty,
raises Not_found
val choose : 'a set ->
('a elt_, 'a) result_
Choose an arbitrary element from the set. It is
implementation dependent whether or not the same element is
chosen for equal sets. If the set is empty, it raises
Not_found.
val cardinal : 'a set -> int
Returns the number of elements in the set.
val compare : 'a set -> 'a set -> int
compare t1 t2 Compares the sets t1 and t2 and returns
0 if they are equal. Returns <0 if t1 is less than t2
and >0 otherwise.
val equal : 'a set -> 'a set -> bool
equal t1 t2 Returns true if t1 and t2 contain the same
elements.
val iter : ('a elt_ -> unit) -> 'a set -> unit
iter f t Apply f to each element in list t. The
elements are always visited in increasing order.
val fold : ('a -> 'b elt_ -> 'a) -> 'a -> 'b set -> 'a
fold f acc t Accumulates the result acc by applying f acc
x for each element x in t. The elements are always
visited in increasing order. Note that this is a slightly
different signature than the fold from the standard library,
however, it is the same signature as the lists modules use.
val union : 'a set -> 'a set -> 'a set
union t1 t2 Returns a set containing all of the elements in
t1 and t2
val inter : 'a set -> 'a set -> 'a set
inter t1 t2 Returns a set containing only the elements
contained in both t1 and t2
val diff : 'a set -> 'a set -> 'a set
diff t1 t2 Returns a set containing only the elements
contained in t1 and not t2
val gen1 : (?size:int -> Random.State.t -> 'a elt_) ->
?size:int -> Random.State.t -> 'a set
gen1 f ?size rs Generates a random set whose size is bounded
by size. Each element in the set is computed by calling f
?size rs.
val well_formed : 'a set -> bool
A predicate to test if the set is well-formed. All sets
exposed by this API should always be well-formed. This is
only useful for debugging an implementation.
val of_result : ('a, 'b) result_ -> 'a
Returns the result part of a result_ value. This is only
useful when treating a collection of sets abstractly, as most
clients should deconstruct the values of type result_ for
maximal efficiency
The cursor interface to sets
type 'a cursor_
The type of Set cursors. A cursor can be thought of a
pointer to a node in the middle of a tree. Cursors support
navigating the tree in arbitrary ways. Depending on the
implementation, not every node in the tree may have a value
associated with it.
val to_cursor : 'a set -> 'a cursor_
Create a cursor from a tree. The cursor initially points to
the top of the tree.
val from_cursor : 'a cursor_ -> 'a set
Return the tree pointed to by the cursor. This operation may
require re-balancing the tree depending on the implementation.
val at_top : 'a cursor_ -> bool
Returns true if the cursor is at the top of the tree. The
Reins.Sets.Set_.move_up operation only succeeds when this
returns
false.
val at_left : 'a cursor_ -> bool
Returns true if the cursor is at the left most element in the
current subtree. The
Reins.Sets.Set_.move_down_left
operation only succeeds when this returns
false.
val at_right : 'a cursor_ -> bool
Returns true if the cursor is at the right most element in the
current subtree. The
Reins.Sets.Set_.move_down_right
operation only succeeds when this returns
false.
val move_up : 'a cursor_ -> 'a cursor_
Move the cursor up the tree from a sibling to a parent. If
the cursor is already at the top of the tree (as determined by
Reins.Sets.Set_.at_top), it raises
Failure "move_up".
val move_down_left : 'a cursor_ -> 'a cursor_
Move the cursor down the tree to the left child. If the
cursor is already at the bottom left of the tree (as
determined by
Reins.Sets.Set_.at_left), it raises
Failure
"move_down_left".
val move_down_right : 'a cursor_ -> 'a cursor_
Move the cursor down the tree to the right child. If the
cursor is already at the bottom right of the tree (as
determined by
Reins.Sets.Set_.at_right), it raises
Failure
"move_down_right".
val went_left : 'a cursor_ -> bool
Returns true if the cursor points to an element that is the
left sibling of its parent.
val went_right : 'a cursor_ -> bool
Returns true if the cursor points to an element that is the
right sibling of its parent.
val has_value : 'a cursor_ -> bool
Returns true if the cursor points to a node that contains a
value.
val get_value : 'a cursor_ -> 'a elt_
Extracts the value from the current node. If the node does
not contain a value (as determined by
Reins.Sets.Set_.has_value, then it raises
Failure
"get_value".