<!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.DoubleList.html">
<link rel="next" href="Reins.SList.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.DoubleQueue</title>
</head>
<body>
<div class="navbar"><a href="Reins.DoubleList.html">Previous</a>
<a href="Reins.html">Up</a>
<a href="Reins.SList.html">Next</a>
</div>
<center><h1>Module <a href="type_Reins.DoubleQueue.html">Reins.DoubleQueue</a></h1></center>
<br>
<pre><span class="keyword">module</span> DoubleQueue: <code class="code">sig</code> <a href="Reins.DoubleQueue.html">..</a> <code class="code">end</code></pre><hr width="100%">
<br>
Double ended queues<br>
<pre><span id="TYPEt"><span class="keyword">type</span> <code class="type">'a</code> t</span> </pre>
<div class="info">
The type of double ended queues. Access to both the front and
the back of the queue take amortized O(1) time.<br>
</div>
<pre><span id="VALempty"><span class="keyword">val</span> empty</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
The empty queue<br>
</div>
<pre><span id="VALis_empty"><span class="keyword">val</span> is_empty</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> bool</code></pre><div class="info">
Returns true is the queue is empty<br>
</div>
<pre><span id="VALhd"><span class="keyword">val</span> hd</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">hd q</code> Return the element at the front of the queue. If the
queue is empty, it raises <code class="code">Failure "hd"</code><br>
</div>
<pre><span id="VALtl"><span class="keyword">val</span> tl</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">tl t</code> Return the queue <code class="code">t</code> with the element at the front of the
queue removed. Runs in O(1) time and stack space. If the queue
is empty, it raises <code class="code">Failure "tl"</code>.<br>
</div>
<pre><span id="VALpop"><span class="keyword">val</span> pop</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.DoubleQueue.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 O(1) time and stack space. If the queue is empty, it
raises <code class="code">Failure "pop"</code>.<br>
</div>
<pre><span id="VALcons"><span class="keyword">val</span> cons</span> : <code class="type">'a -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">cons x t</code> Adds <code class="code">x</code> to the front of queue <code class="code">t</code> so that a
subsequent call to <code class="code">hd</code> returns <code class="code">x</code>. Runs in O(1) time and
stack space.<br>
</div>
<pre><span id="VALhd_back"><span class="keyword">val</span> hd_back</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">hd_back q</code> Return the element at the back of the queue. If the
queue is empty, it raises <code class="code">Failure "hd_back"</code>. Runs in
amortized O(1) time and O(1) stack space.<br>
</div>
<pre><span id="VALtl_back"><span class="keyword">val</span> tl_back</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">tl t</code> Return the queue <code class="code">t</code> with the element at the back of the
queue removed. Runs in amortized O(1) time and O(1) stack
space. If the queue is empty, it raises <code class="code">Failure "tl_back"</code>.<br>
</div>
<pre><span id="VALpop_back"><span class="keyword">val</span> pop_back</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> * 'a</code></pre><div class="info">
<code class="code">pop_back t</code> Equivalent to <code class="code">(hd_back t), (tl_back t)</code> but is
more efficient. Runs in amortized O(1) time and O(1) stack
space. If the queue is empty, it raises <code class="code">Failure "pop_back"</code>.<br>
</div>
<pre><span id="VALcons_back"><span class="keyword">val</span> cons_back</span> : <code class="type">'a -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">cons_back x t</code> Adds <code class="code">x</code> to the back of queue <code class="code">t</code> so that a
subsequent call to <code class="code">hd_back</code> returns <code class="code">x</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.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">snoc x t</code> is an alias for <a href="Reins.DoubleQueue.html#VALcons_back"><code class="code">Reins.DoubleQueue.cons_back</code></a> <code class="code">x t</code>,
adding <code class="code">x</code> to the back of <code class="code">t</code>.<br>
</div>
<pre><span id="VALlast"><span class="keyword">val</span> last</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">last q</code> is an alias for <code class="code">hd_back q</code><br>
</div>
<pre><span id="VALenqueue"><span class="keyword">val</span> enqueue</span> : <code class="type">'a -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">enqueue x t</code> is an alias for <a href="Reins.DoubleQueue.html#VALcons_back"><code class="code">Reins.DoubleQueue.cons_back</code></a> <code class="code">x t</code>,
adding <code class="code">x</code> to the back of <code class="code">t</code>.<br>
</div>
<pre><span id="VALdequeue"><span class="keyword">val</span> dequeue</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a * 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">dequeue x t</code> is an alias for <a href="Reins.DoubleQueue.html#VALhd"><code class="code">Reins.DoubleQueue.hd</code></a> <code class="code">x t</code>, removing
the first element from the front of <code class="code">t</code>.<br>
</div>
<pre><span id="VALlength"><span class="keyword">val</span> length</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">length t</code> Returns the number of elements in the queue <code class="code">t</code><br>
</div>
<pre><span id="VALrev"><span class="keyword">val</span> rev</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev t</code> Reverses the order of the queue <code class="code">t</code>. e.g., <code class="code">hd t ==
hd_back (rev t)</code><br>
</div>
<pre><span id="VALappend"><span class="keyword">val</span> append</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">append t1 t2</code> Appends all of the elements in queue <code class="code">t2</code> onto
the back of <code class="code">t1</code>. That is, in the resulting queue,
<a href="Reins.DoubleQueue.html#VALhd"><code class="code">Reins.DoubleQueue.hd</code></a> returns the first element of <code class="code">t1</code> and
<a href="Reins.DoubleQueue.html#VALhd_back"><code class="code">Reins.DoubleQueue.hd_back</code></a> returns the last element of <code class="code">t2</code>. Runs
in O(n+m) time where n and m are the number of elements in <code class="code">t1</code>
and <code class="code">t2</code> respectively.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a -> unit) -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">iter f t</code> Iterates over each element in the queue <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.DoubleQueue.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.DoubleQueue.html#TYPEt">t</a> -> 'b <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">rev_map f t</code> Creates a new queue by applying <code class="code">f</code> to each element
of <code class="code">t</code>. The resulting queue 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.DoubleQueue.html#TYPEt">t</a> -> 'b <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">map f t</code> Creates a new queue by applying <code class="code">f</code> to each element of
<code class="code">t</code>. The resulting queue 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) stack space where fs is
the stack space required by <code class="code">f</code>. This function is just as
efficient as <a href="Reins.DoubleQueue.html#VALrev_map"><code class="code">Reins.DoubleQueue.rev_map</code></a> (yielding a different
ordering) and more efficient than <code class="code">DoubleQueue.rev
(DoubleQueue.rev_map t)</code>.<br>
</div>
<pre><span id="VALto_list"><span class="keyword">val</span> to_list</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a list</code></pre><div class="info">
<code class="code">to_list t</code> Convert the DoubleQueue <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>. The resulting list has the same ordering as
<code class="code">t</code>. That is, <code class="code">DoubleQueue.hd t == List.hd (DoubleQueue.to_list
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.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">from_list l</code> Convert the standard list l into a DoubleQueue.t.
Runs in O(n) time and O(1) stack space where n is the number of
elements in <code class="code">l</code>. The resulting queue has the same order as the
original list. That is <code class="code">List.hd l == DoubleQueue.hd
(DoubleQueue.from_list l)</code>.<br>
</div>
<pre><span id="VALflatten"><span class="keyword">val</span> flatten</span> : <code class="type">'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">flatten l</code> Appends all of the elements of <code class="code">l</code> into a new queue.
The current implementation is not very efficient and runs in
greater than O(n) time uses a O(n) stack space.<br>
</div>
<pre><span id="VALto_string"><span class="keyword">val</span> to_string</span> : <code class="type">('a -> string) -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> string</code></pre><div class="info">
<code class="code">to_string to_s t</code> Convert the queue <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) -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> 'a <a href="Reins.DoubleQueue.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">compare f t1 t2</code> Compares the queues <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.DoubleQueue.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">gen f ?size rs</code> Generates a random queue whose length is
bounded by <code class="code">size</code>. Each element in the queue 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>
</body></html>
