<!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="previous" href="Reins.SList.html">
<link rel="next" href="Reins.Maps.html">
<link rel="Up" href="Reins.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.SkewBinaryList</title>
</head>
<body>
<div class="navbar"><a href="Reins.SList.html">Previous</a>
<a href="Reins.html">Up</a>
<a href="Reins.Maps.html">Next</a>
</div>
<center><h1>Module <a href="type_Reins.SkewBinaryList.html">Reins.SkewBinaryList</a></h1></center>
<br>
<pre><span class="keyword">module</span> SkewBinaryList: <code class="code">sig</code> <a href="Reins.SkewBinaryList.html">..</a> <code class="code">end</code></pre><hr width="100%">
<br>
Random access lists based on skew binary numbers
<p>
This module implements random access lists with O(1) <code class="code">hd</code> and <code class="code">tl</code>
operations and O(log n) <code class="code">lookup</code> and <code class="code">update</code> operations.<br>
<pre><span id="TYPEt"><span class="keyword">type</span> <code class="type">'a</code> t</span> </pre>
<div class="info">
The type of random access lists<br>
</div>
<pre><span id="VALempty"><span class="keyword">val</span> empty</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
The empty list<br>
</div>
<pre><span id="VALis_empty"><span class="keyword">val</span> is_empty</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> bool</code></pre><div class="info">
Returns tree if the list is emtpy.<br>
</div>
<pre><span id="VALlength"><span class="keyword">val</span> length</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">length t</code> returns the lenth of the list <code class="code">t</code>. Runs in O(log n)
time and O(1) stack space where n is the number of elements in
the list.<br>
</div>
<pre><span id="VALrev"><span class="keyword">val</span> rev</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev t</code> Reverse the list <code class="code">t</code>. Runs in O(n) run and O(1) stack
space where n is the number of elements in the list.<br>
</div>
<pre><span id="VALcons"><span class="keyword">val</span> cons</span> : <code class="type">'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">cons x t</code> Adds the element <code class="code">x</code> to the front of the list <code class="code">t</code>.
Runs in O(1) time and stack space.<br>
</div>
<pre><span id="VALsnoc"><span class="keyword">val</span> snoc</span> : <code class="type">'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">snoc x t</code> Adds the element <code class="code">x</code> to the back of the list <code class="code">t</code>.
Runs in O(n) time and O(1) stack space where n is the length of
the list.<br>
</div>
<pre><span id="VALlast"><span class="keyword">val</span> last</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">last t</code> Returns the element at the back of the list. If the
list is empty, it raises <code class="code">Failure "last"</code>. Runs in O(1) stack
and O(log n) time.<br>
</div>
<pre><span id="VALhd"><span class="keyword">val</span> hd</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">hd t</code> Returns the element at the front of the list <code class="code">t</code>. Runs
in O(1) time and stack space. Raises <code class="code">Failure "hd"</code> if the list is
empty.<br>
</div>
<pre><span id="VALtl"><span class="keyword">val</span> tl</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">tl t</code> Returns the list <code class="code">t</code> with the first element removed.
Runs in O(1) time and stack space. Raises <code class="code">Failure "tl"</code> if the
list is empty.<br>
</div>
<pre><span id="VALpop"><span class="keyword">val</span> pop</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">pop t</code> Equivalent to <code class="code">(hd t), (tl t)</code> but is more efficient.
Runs in amortized O(1) time and stack space. If the list is
empty, it raises <code class="code">Failure "pop"</code>.<br>
</div>
<pre><span id="VALappend"><span class="keyword">val</span> append</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -><br> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">append t1 t2</code> Appends the list <code class="code">t2</code> onto the back of list <code class="code">t1</code>.
Runs in O(n) time and O(1) stack space where n is the number of
elements in <code class="code">t1</code>.<br>
</div>
<pre><span id="VALflatten"><span class="keyword">val</span> flatten</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">flatten t</code> Appends all of the elements of <code class="code">t</code> into a new list.
Runs in O(n) time and O(1) stack space where n is the sum of
each of the lists in <code class="code">t</code>.<br>
</div>
<pre><span id="VALfrom_list"><span class="keyword">val</span> from_list</span> : <code class="type">'a list -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">from_list l</code> Convert the standard list l into a SkewBinaryList.
Runs in O(n) time and O(1) stack space where n is the number of
elements in <code class="code">l</code>.<br>
</div>
<pre><span id="VALto_list"><span class="keyword">val</span> to_list</span> : <code class="type">'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a list</code></pre><div class="info">
<code class="code">to_list t</code> Convert the SkewBinaryList <code class="code">t</code> into a standard list.
Runs in O(n) time and O(1) stack space where n is the number of
elements in <code class="code">t</code>.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a -> unit) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">iter f t</code> Iterates over each element in the list <code class="code">t</code> in order
and applies <code class="code">f</code> to that element. Runs in O(n*ft) where ft is
the running time of <code class="code">f</code> and uses O(fs) stack space where fs is
the stack space required by <code class="code">f</code>.<br>
</div>
<pre><span id="VALfold"><span class="keyword">val</span> fold</span> : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="Reins.SkewBinaryList.html#TYPEt">t</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>. Runs in O(n*ft) where ft is the
running time of <code class="code">f</code> and uses O(fs) stack space where fs is the
stack space required by <code class="code">f</code>.<br>
</div>
<pre><span id="VALrev_map"><span class="keyword">val</span> rev_map</span> : <code class="type">('a -> 'b) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'b <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev_map f t</code> Creates a new list by applying <code class="code">f</code> to each element
of <code class="code">t</code>. The resulting list is in reverse order of <code class="code">t</code>. Runs in
O(n*ft) time where n is the number of elements in <code class="code">t</code> and ft is
the running time of <code class="code">f</code>. It uses O(fs) stack space where fs is
the stack space required by <code class="code">f</code>.<br>
</div>
<pre><span id="VALmap"><span class="keyword">val</span> map</span> : <code class="type">('a -> 'b) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'b <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">map f t</code> Creates a new list by applying <code class="code">f</code> to each element of
<code class="code">t</code>. The resulting list is in the same order as <code class="code">t</code>. Runs in
O(n*ft) time where n is the number of elements in <code class="code">t</code> and ft is
the running time of <code class="code">f</code>. It uses O((fs * log n) stack space
where fs is the stack space required by <code class="code">f</code>. This function is
slightly more efficient than <a href="Reins.SkewBinaryList.html#VALrev_map"><code class="code">Reins.SkewBinaryList.rev_map</code></a> (yielding
a different ordering) and significantly more efficient (by a
constant factor) than <code class="code">SkewBinaryList.rev
(SkewBinaryList.rev_map t)</code>.<br>
</div>
<pre><span id="VALto_string"><span class="keyword">val</span> to_string</span> : <code class="type">('a -> string) -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> string</code></pre><div class="info">
<code class="code">to_string to_s t</code> Convert the list <code class="code">t</code> into a string using
<code class="code">to_s</code> to individually convert each element into a string. Runs
in O(n*st) where st is the running time of <code class="code">to_s</code> and uses O(ss)
stack space where ss is the amount of stack required by <code class="code">to_s</code>.<br>
</div>
<pre><span id="VALcompare"><span class="keyword">val</span> compare</span> : <code class="type">('a -> 'a -> int) -><br> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">compare f t1 t2</code> Compares the lists <code class="code">t1</code> and <code class="code">t2</code> using <code class="code">f</code> to
compare individual elements. Returns 0 if <code class="code">t1</code> and <code class="code">t2</code> are
equal (under f). Returns <code class="code"><0</code> if <code class="code">t1</code> is less than <code class="code">t2</code> and
returns <code class="code">>0</code> otherwise.<br>
</div>
<pre><span id="VALgen"><span class="keyword">val</span> gen</span> : <code class="type">(?size:int -> Random.State.t -> 'a) -><br> ?size:int -> Random.State.t -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">gen f ?size rs</code> Generates a random list whose length is bounded
by <code class="code">size</code>. Each element in the list is computed by calling <code class="code">f
?size rs</code>. Runs in time O(<code class="code">size</code> * ft) where ft is the running
time of <code class="code">f</code> and uses O(fs) stack space where fs is the stack space
of <code class="code">f</code>.<br>
</div>
<pre><span id="VALlookup"><span class="keyword">val</span> lookup</span> : <code class="type">int -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">lookup i t</code> Returns the element at position <code class="code">i</code> (O-indexed) in
the list <code class="code">t</code>. Raises <code class="code">Not_found</code> if the list contains fewer
than <code class="code">i-1</code> elements. Runs in O(min(i,log n)) time and O(1)
stack space where n is the number of elements in <code class="code">t</code>.<br>
</div>
<pre><span id="VALupdate"><span class="keyword">val</span> update</span> : <code class="type">int -> 'a -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a> -> 'a <a href="Reins.SkewBinaryList.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">update i v t</code> Returns a new list where the element in position
<code class="code">i</code> (0-indexed) has been replaced by <code class="code">v</code>. Raises <code class="code">Not_found</code> if
the list contains fewer than <code class="code">i-1</code> elements. Runs in
O(min(i,log n)) time and O(1) stack space where n is the number
of elements in <code class="code">t</code>.<br>
</div>
</body></html>
