mirror of
https://github.com/c-cube/ocaml-containers.git
synced 2025-12-06 03:05:28 -05:00
2 lines
No EOL
18 KiB
HTML
2 lines
No EOL
18 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>CCDeque (containers.CCDeque)</title><link rel="stylesheet" href="../../odoc.css"/><meta charset="utf-8"/><meta name="viewport" content="width=device-width,initial-scale=1.0"/><script src="../../highlight.pack.js"></script><script>hljs.initHighlightingOnLoad();</script></head><body><div class="content"><header><nav><a href="../index.html">Up</a> – <a href="../index.html">containers</a> » CCDeque</nav><h1>Module <code>CCDeque</code></h1><h2 id="imperative-deque"><a href="#imperative-deque" class="anchor"></a>Imperative deque</h2><p>This structure provides fast access to its front and back elements, with O(1) operations.</p><nav class="toc"><ul><li><a href="#conversions">Conversions</a></li><li><a href="#print">print</a></li></ul></nav></header><dl><dt class="spec type" id="type-t"><a href="#type-t" class="anchor"></a><code><span class="keyword">type</span> 'a t</code></dt><dd><p>Contains 'a elements, queue in both ways</p></dd></dl><dl><dt class="spec exception" id="exception-Empty"><a href="#exception-Empty" class="anchor"></a><code><span class="keyword">exception</span> </code><code><span class="exception">Empty</span></code></dt></dl><dl><dt class="spec value" id="val-create"><a href="#val-create" class="anchor"></a><code><span class="keyword">val</span> create : unit <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p>New deque.</p></dd></dl><dl><dt class="spec value" id="val-clear"><a href="#val-clear" class="anchor"></a><code><span class="keyword">val</span> clear : <span class="type-var">_</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p>Remove all elements.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-is_empty"><a href="#val-is_empty" class="anchor"></a><code><span class="keyword">val</span> is_empty : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> bool</code></dt><dd><p>Is the deque empty?</p></dd></dl><dl><dt class="spec value" id="val-equal"><a href="#val-equal" class="anchor"></a><code><span class="keyword">val</span> equal : eq:(<span class="type-var">'a</span> <span>-></span> <span class="type-var">'a</span> <span>-></span> bool) <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> bool</code></dt><dd><p><code>equal a b</code> checks whether <code>a</code> and <code>b</code> contain the same sequence of elements.</p><dl><dt>parameter eq</dt><dd><p>comparison function for elements.</p></dd></dl><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-compare"><a href="#val-compare" class="anchor"></a><code><span class="keyword">val</span> compare : cmp:(<span class="type-var">'a</span> <span>-></span> <span class="type-var">'a</span> <span>-></span> int) <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> int</code></dt><dd><p><code>compare a b</code> compares lexicographically <code>a</code> and <code>b</code>.</p><dl><dt>parameter cmp</dt><dd><p>comparison function for elements.</p></dd></dl><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-length"><a href="#val-length" class="anchor"></a><code><span class="keyword">val</span> length : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> int</code></dt><dd><p>Number of elements. Used to be linear time, now constant time.</p></dd></dl><dl><dt class="spec value" id="val-push_front"><a href="#val-push_front" class="anchor"></a><code><span class="keyword">val</span> push_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <span>-></span> unit</code></dt><dd><p>Push value at the front.</p></dd></dl><dl><dt class="spec value" id="val-push_back"><a href="#val-push_back" class="anchor"></a><code><span class="keyword">val</span> push_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <span>-></span> unit</code></dt><dd><p>Push value at the back.</p></dd></dl><dl><dt class="spec value" id="val-peek_front"><a href="#val-peek_front" class="anchor"></a><code><span class="keyword">val</span> peek_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span></code></dt><dd><p>First value.</p><dl><dt>raises Empty</dt><dd><p>if empty.</p></dd></dl></dd></dl><dl><dt class="spec value" id="val-peek_front_opt"><a href="#val-peek_front_opt" class="anchor"></a><code><span class="keyword">val</span> peek_front_opt : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> option</code></dt><dd><p>First value.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-peek_back"><a href="#val-peek_back" class="anchor"></a><code><span class="keyword">val</span> peek_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span></code></dt><dd><p>Last value.</p><dl><dt>raises Empty</dt><dd><p>if empty.</p></dd></dl></dd></dl><dl><dt class="spec value" id="val-peek_back_opt"><a href="#val-peek_back_opt" class="anchor"></a><code><span class="keyword">val</span> peek_back_opt : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> option</code></dt><dd><p>Last value.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-remove_back"><a href="#val-remove_back" class="anchor"></a><code><span class="keyword">val</span> remove_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p>Remove last value. If the deque is empty do nothing</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-remove_front"><a href="#val-remove_front" class="anchor"></a><code><span class="keyword">val</span> remove_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p>Remove first value. If the deque is empty do nothing</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-take_back"><a href="#val-take_back" class="anchor"></a><code><span class="keyword">val</span> take_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span></code></dt><dd><p>Take last value.</p><dl><dt>raises Empty</dt><dd><p>if empty.</p></dd></dl></dd></dl><dl><dt class="spec value" id="val-take_back_opt"><a href="#val-take_back_opt" class="anchor"></a><code><span class="keyword">val</span> take_back_opt : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> option</code></dt><dd><p>Take last value.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-take_front"><a href="#val-take_front" class="anchor"></a><code><span class="keyword">val</span> take_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span></code></dt><dd><p>Take first value.</p><dl><dt>raises Empty</dt><dd><p>if empty.</p></dd></dl></dd></dl><dl><dt class="spec value" id="val-take_front_opt"><a href="#val-take_front_opt" class="anchor"></a><code><span class="keyword">val</span> take_front_opt : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> option</code></dt><dd><p>Take first value.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-update_back"><a href="#val-update_back" class="anchor"></a><code><span class="keyword">val</span> update_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> (<span class="type-var">'a</span> <span>-></span> <span class="type-var">'a</span> option) <span>-></span> unit</code></dt><dd><p>Update last value. If the deque is empty do nothing. If the function returns <code>None</code>, remove last element; if it returns <code>Some x</code>, replace last element with <code>x</code>.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-update_front"><a href="#val-update_front" class="anchor"></a><code><span class="keyword">val</span> update_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> (<span class="type-var">'a</span> <span>-></span> <span class="type-var">'a</span> option) <span>-></span> unit</code></dt><dd><p>Update first value. If the deque is empty do nothing. Similar to <a href="index.html#val-update_back"><code>update_back</code></a> but for the first value.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-append_front"><a href="#val-append_front" class="anchor"></a><code><span class="keyword">val</span> append_front : into:<span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p><code>append_front ~into q</code> adds all elements of <code>q</code> at the front of <code>into</code>. <code>O(length q)</code> in time.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-append_back"><a href="#val-append_back" class="anchor"></a><code><span class="keyword">val</span> append_back : into:<span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p><code>append_back ~into q</code> adds all elements of <code>q</code> at the back of <code>into</code>. <code>O(length q)</code> in time.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-iter"><a href="#val-iter" class="anchor"></a><code><span class="keyword">val</span> iter : (<span class="type-var">'a</span> <span>-></span> unit) <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> unit</code></dt><dd><p>Iterate on elements.</p></dd></dl><dl><dt class="spec value" id="val-fold"><a href="#val-fold" class="anchor"></a><code><span class="keyword">val</span> fold : (<span class="type-var">'b</span> <span>-></span> <span class="type-var">'a</span> <span>-></span> <span class="type-var">'b</span>) <span>-></span> <span class="type-var">'b</span> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'b</span></code></dt><dd><p>Fold on elements.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><section><header><h3 id="conversions"><a href="#conversions" class="anchor"></a>Conversions</h3></header><dl><dt class="spec type" id="type-gen"><a href="#type-gen" class="anchor"></a><code><span class="keyword">type</span> 'a gen</code><code> = unit <span>-></span> <span class="type-var">'a</span> option</code></dt><dt class="spec type" id="type-sequence"><a href="#type-sequence" class="anchor"></a><code><span class="keyword">type</span> 'a sequence</code><code> = (<span class="type-var">'a</span> <span>-></span> unit) <span>-></span> unit</code></dt></dl><dl><dt class="spec value" id="val-of_seq"><a href="#val-of_seq" class="anchor"></a><code><span class="keyword">val</span> of_seq : <span class="type-var">'a</span> <a href="index.html#type-sequence">sequence</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p>Create a deque from the sequence. Optional argument <code>deque</code> disappears, use <a href="index.html#val-add_seq_back"><code>add_seq_back</code></a> instead.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-to_seq"><a href="#val-to_seq" class="anchor"></a><code><span class="keyword">val</span> to_seq : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-sequence">sequence</a></code></dt><dd><p>Iterate on the elements.</p></dd></dl><dl><dt class="spec value" id="val-of_gen"><a href="#val-of_gen" class="anchor"></a><code><span class="keyword">val</span> of_gen : <span class="type-var">'a</span> <a href="index.html#type-gen">gen</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p><code>of_gen g</code> makes a deque containing the elements of <code>g</code>.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-to_gen"><a href="#val-to_gen" class="anchor"></a><code><span class="keyword">val</span> to_gen : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-gen">gen</a></code></dt><dd><p>Iterate on the elements of the deque.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-add_seq_front"><a href="#val-add_seq_front" class="anchor"></a><code><span class="keyword">val</span> add_seq_front : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-sequence">sequence</a> <span>-></span> unit</code></dt><dd><p><code>add_seq_front q seq</code> adds elements of <code>seq</code> into the front of <code>q</code>, in reverse order. <code>O(n)</code> in time, where <code>n</code> is the number of elements to add.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-add_seq_back"><a href="#val-add_seq_back" class="anchor"></a><code><span class="keyword">val</span> add_seq_back : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-sequence">sequence</a> <span>-></span> unit</code></dt><dd><p><code>add_seq_back q seq</code> adds elements of <code>seq</code> into the back of <code>q</code>, in order. <code>O(n)</code> in time, where <code>n</code> is the number of elements to add.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-copy"><a href="#val-copy" class="anchor"></a><code><span class="keyword">val</span> copy : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p>Fresh copy, <code>O(n)</code> in time.</p></dd></dl><dl><dt class="spec value" id="val-of_list"><a href="#val-of_list" class="anchor"></a><code><span class="keyword">val</span> of_list : <span class="type-var">'a</span> list <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p>Conversion from list, in order.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-to_list"><a href="#val-to_list" class="anchor"></a><code><span class="keyword">val</span> to_list : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> list</code></dt><dd><p>List of elements, in order. Less efficient than <a href="index.html#val-to_rev_list"><code>to_rev_list</code></a>.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-to_rev_list"><a href="#val-to_rev_list" class="anchor"></a><code><span class="keyword">val</span> to_rev_list : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> list</code></dt><dd><p>Efficient conversion to list, in reverse order.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl><dl><dt class="spec value" id="val-filter"><a href="#val-filter" class="anchor"></a><code><span class="keyword">val</span> filter : (<span class="type-var">'a</span> <span>-></span> bool) <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a></code></dt><dd><p>Filter into a new copy.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-filter_map"><a href="#val-filter_map" class="anchor"></a><code><span class="keyword">val</span> filter_map : (<span class="type-var">'a</span> <span>-></span> <span class="type-var">'b</span> option) <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> <span class="type-var">'b</span> <a href="index.html#type-t">t</a></code></dt><dd><p>Filter map into a new copy</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl><dl><dt class="spec value" id="val-filter_in_place"><a href="#val-filter_in_place" class="anchor"></a><code><span class="keyword">val</span> filter_in_place : <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <span>-></span> (<span class="type-var">'a</span> <span>-></span> bool) <span>-></span> unit</code></dt><dd><p>Keep only elements that satisfy the predicate.</p><dl><dt>since</dt><dd>2.7</dd></dl></dd></dl></section><section><header><h3 id="print"><a href="#print" class="anchor"></a>print</h3></header><dl><dt class="spec type" id="type-printer"><a href="#type-printer" class="anchor"></a><code><span class="keyword">type</span> 'a printer</code><code> = Stdlib.Format.formatter <span>-></span> <span class="type-var">'a</span> <span>-></span> unit</code></dt></dl><dl><dt class="spec value" id="val-pp"><a href="#val-pp" class="anchor"></a><code><span class="keyword">val</span> pp : <span class="type-var">'a</span> <a href="index.html#type-printer">printer</a> <span>-></span> <span class="type-var">'a</span> <a href="index.html#type-t">t</a> <a href="index.html#type-printer">printer</a></code></dt><dd><p>Print the elements.</p><dl><dt>since</dt><dd>0.13</dd></dl></dd></dl></section></div></body></html> |