<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="next" href="Reins.Sets.MonoSetSig.html">
<link rel="Up" href="Reins.Sets.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Reins" rel="Chapter" href="Reins.html"><title>Reins.Sets.Set_</title>
</head>
<body>
<div class="navbar"> <a href="Reins.Sets.html">Up</a>
<a href="Reins.Sets.MonoSetSig.html">Next</a>
</div>
<center><h1>Module type <a href="type_Reins.Sets.Set_.html">Reins.Sets.Set_</a></h1></center>
<br>
<pre><span class="keyword">module type</span> Set_ = <code class="code">sig</code> <a href="Reins.Sets.Set_.html">..</a> <code class="code">end</code></pre>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 <a href="Reins.Sets.MonoSetSig.html"><code class="code">Reins.Sets.MonoSetSig</code></a>.<br>
<hr width="100%">
<pre><span id="TYPEelt_"><span class="keyword">type</span> <code class="type">'a</code> elt_</span> </pre>
<div class="info">
The type of elements in the set<br>
</div>
<pre><span id="TYPEset"><span class="keyword">type</span> <code class="type">'a</code> set</span> </pre>
<div class="info">
The type of sets<br>
</div>
<pre><span id="TYPEresult_"><span class="keyword">type</span> <code class="type">('a, 'b)</code> result_</span> </pre>
<div class="info">
The <code class="code">result_</code> 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)<br>
</div>
<pre><span id="VALempty"><span class="keyword">val</span> empty</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
The empty set<br>
</div>
<pre><span id="VALis_empty"><span class="keyword">val</span> is_empty</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> bool</code></pre><div class="info">
Returns true if the set is empty<br>
</div>
<pre><span id="VALmem"><span class="keyword">val</span> mem</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -><br> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> (bool, 'a) <a href="Reins.Sets.Set_.html#TYPEresult_">result_</a></code></pre><div class="info">
<code class="code">mem x t</code> Returns true if <code class="code">x</code> is contained in the set <code class="code">t</code>.
More precisely, there exists an element <code class="code">y</code> in <code class="code">t</code> such that
<code class="code">compare x y = 0</code>.<br>
</div>
<pre><span id="VALadd"><span class="keyword">val</span> add</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">add x t</code> Return the set <code class="code">t</code> with the element <code class="code">x</code>.<br>
</div>
<pre><span id="VALsingleton"><span class="keyword">val</span> singleton</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">singleton x</code> Return the set consisting of only the element
<code class="code">x</code><br>
</div>
<pre><span id="VALremove"><span class="keyword">val</span> remove</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">remove x t</code> Return the set <code class="code">t</code> with the element <code class="code">x</code> removed.
Does <b>not</b> raise an exception if <code class="code">t</code> does not contain <code class="code">x</code>.<br>
</div>
<pre><span id="VALmin_elt"><span class="keyword">val</span> min_elt</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -><br> ('a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a>, 'a) <a href="Reins.Sets.Set_.html#TYPEresult_">result_</a></code></pre><div class="info">
Return the smallest element in the set. If the set is empty,
raises <code class="code">Not_found</code><br>
</div>
<pre><span id="VALmax_elt"><span class="keyword">val</span> max_elt</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -><br> ('a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a>, 'a) <a href="Reins.Sets.Set_.html#TYPEresult_">result_</a></code></pre><div class="info">
Return the largest element in the set. If the set is empty,
raises <code class="code">Not_found</code><br>
</div>
<pre><span id="VALchoose"><span class="keyword">val</span> choose</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -><br> ('a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a>, 'a) <a href="Reins.Sets.Set_.html#TYPEresult_">result_</a></code></pre><div class="info">
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
<code class="code">Not_found</code>.<br>
</div>
<pre><span id="VALcardinal"><span class="keyword">val</span> cardinal</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> int</code></pre><div class="info">
Returns the number of elements in the set.<br>
</div>
<pre><span id="VALcompare"><span class="keyword">val</span> compare</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> int</code></pre><div class="info">
<code class="code">compare t1 t2</code> Compares the sets <code class="code">t1</code> and <code class="code">t2</code> and returns
<code class="code">0</code> if they are equal. Returns <code class="code"><0</code> if <code class="code">t1</code> is less than <code class="code">t2</code>
and <code class="code">>0</code> otherwise.<br>
</div>
<pre><span id="VALequal"><span class="keyword">val</span> equal</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> bool</code></pre><div class="info">
<code class="code">equal t1 t2</code> Returns true if <code class="code">t1</code> and <code class="code">t2</code> contain the same
elements.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -> unit) -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> unit</code></pre><div class="info">
<code class="code">iter f t</code> Apply <code class="code">f</code> to each element in list <code class="code">t</code>. The
elements are always visited in increasing order.<br>
</div>
<pre><span id="VALfold"><span class="keyword">val</span> fold</span> : <code class="type">('a -> 'b <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a> -> 'a) -> 'a -> 'b <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a</code></pre><div class="info">
<code class="code">fold f acc t</code> Accumulates the result <code class="code">acc</code> by applying <code class="code">f acc
x</code> for each element <code class="code">x</code> in <code class="code">t</code>. 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.<br>
</div>
<pre><span id="VALunion"><span class="keyword">val</span> union</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">union t1 t2</code> Returns a set containing all of the elements in
<code class="code">t1</code> and <code class="code">t2</code><br>
</div>
<pre><span id="VALinter"><span class="keyword">val</span> inter</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">inter t1 t2</code> Returns a set containing only the elements
contained in both <code class="code">t1</code> and <code class="code">t2</code><br>
</div>
<pre><span id="VALdiff"><span class="keyword">val</span> diff</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">diff t1 t2</code> Returns a set containing only the elements
contained in <code class="code">t1</code> and not <code class="code">t2</code><br>
</div>
<pre><span id="VALgen1"><span class="keyword">val</span> gen1</span> : <code class="type">(?size:int -> Random.State.t -> 'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a>) -><br> ?size:int -> Random.State.t -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
<code class="code">gen1 f ?size rs</code> Generates a random set whose size is bounded
by <code class="code">size</code>. Each element in the set is computed by calling <code class="code">f
?size rs</code>.<br>
</div>
<pre><span id="VALwell_formed"><span class="keyword">val</span> well_formed</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> bool</code></pre><div class="info">
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.<br>
</div>
<pre><span id="VALof_result"><span class="keyword">val</span> of_result</span> : <code class="type">('a, 'b) <a href="Reins.Sets.Set_.html#TYPEresult_">result_</a> -> 'a</code></pre><div class="info">
Returns the result part of a <code class="code">result_</code> value. This is only
useful when treating a collection of sets abstractly, as most
clients should deconstruct the values of type <code class="code">result_</code> for
maximal efficiency<br>
</div>
<br>
The cursor interface to sets<br>
<pre><span id="TYPEcursor_"><span class="keyword">type</span> <code class="type">'a</code> cursor_</span> </pre>
<div class="info">
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.<br>
</div>
<pre><span id="VALto_cursor"><span class="keyword">val</span> to_cursor</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEset">set</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a></code></pre><div class="info">
Create a cursor from a tree. The cursor initially points to
the top of the tree.<br>
</div>
<pre><span id="VALfrom_cursor"><span class="keyword">val</span> from_cursor</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEset">set</a></code></pre><div class="info">
Return the tree pointed to by the cursor. This operation may
require re-balancing the tree depending on the implementation.<br>
</div>
<pre><span id="VALat_top"><span class="keyword">val</span> at_top</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor is at the top of the tree. The
<a href="Reins.Sets.Set_.html#VALmove_up"><code class="code">Reins.Sets.Set_.move_up</code></a> operation only succeeds when this
returns <code class="code">false</code>.<br>
</div>
<pre><span id="VALat_left"><span class="keyword">val</span> at_left</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor is at the left most element in the
current subtree. The <a href="Reins.Sets.Set_.html#VALmove_down_left"><code class="code">Reins.Sets.Set_.move_down_left</code></a>
operation only succeeds when this returns <code class="code">false</code>.<br>
</div>
<pre><span id="VALat_right"><span class="keyword">val</span> at_right</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor is at the right most element in the
current subtree. The <a href="Reins.Sets.Set_.html#VALmove_down_right"><code class="code">Reins.Sets.Set_.move_down_right</code></a>
operation only succeeds when this returns <code class="code">false</code>.<br>
</div>
<pre><span id="VALmove_up"><span class="keyword">val</span> move_up</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a></code></pre><div class="info">
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
<a href="Reins.Sets.Set_.html#VALat_top"><code class="code">Reins.Sets.Set_.at_top</code></a>), it raises <code class="code">Failure "move_up"</code>.<br>
</div>
<pre><span id="VALmove_down_left"><span class="keyword">val</span> move_down_left</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a></code></pre><div class="info">
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 <a href="Reins.Sets.Set_.html#VALat_left"><code class="code">Reins.Sets.Set_.at_left</code></a>), it raises <code class="code">Failure
"move_down_left"</code>.<br>
</div>
<pre><span id="VALmove_down_right"><span class="keyword">val</span> move_down_right</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a></code></pre><div class="info">
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 <a href="Reins.Sets.Set_.html#VALat_right"><code class="code">Reins.Sets.Set_.at_right</code></a>), it raises <code class="code">Failure
"move_down_right"</code>.<br>
</div>
<pre><span id="VALwent_left"><span class="keyword">val</span> went_left</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor points to an element that is the
left sibling of its parent.<br>
</div>
<pre><span id="VALwent_right"><span class="keyword">val</span> went_right</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor points to an element that is the
right sibling of its parent.<br>
</div>
<pre><span id="VALhas_value"><span class="keyword">val</span> has_value</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> bool</code></pre><div class="info">
Returns true if the cursor points to a node that contains a
value.<br>
</div>
<pre><span id="VALget_value"><span class="keyword">val</span> get_value</span> : <code class="type">'a <a href="Reins.Sets.Set_.html#TYPEcursor_">cursor_</a> -> 'a <a href="Reins.Sets.Set_.html#TYPEelt_">elt_</a></code></pre><div class="info">
Extracts the value from the current node. If the node does
not contain a value (as determined by
<a href="Reins.Sets.Set_.html#VALhas_value"><code class="code">Reins.Sets.Set_.has_value</code></a>, then it raises <code class="code">Failure
"get_value"</code>.<br>
</div>
</body></html>
