mirror of
https://github.com/c-cube/ocaml-containers.git
synced 2025-12-06 03:05:28 -05:00
18 lines
No EOL
16 KiB
HTML
18 lines
No EOL
16 KiB
HTML
<!DOCTYPE html>
|
|
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>CCBV (containers.data.CCBV)</title><link rel="stylesheet" href="../../odoc.css"/><meta charset="utf-8"/><meta name="viewport" content="width=device-width,initial-scale=1.0"/><meta name="generator" content="doc-ock-html v1.0.0-1-g1fc9bf0"/></head><body><nav id="top"><a href="../index.html">Up</a> — <span class="package">package <a href="../index.html">containers.data</a></span></nav><header><h1><span class="keyword">Module</span> <span class="module-path">CCBV</span></h1></header><h3>Imperative Bitvectors</h3><p><b>BREAKING CHANGES</b> since 1.2:
|
|
size is now stored along with the bitvector. Some functions have
|
|
a new signature.</p><p>The size of the bitvector used to be rounded up to the multiple of 30 or 62.
|
|
In other words some functions such as <a href="index.html#val-iter">iter</a> would iterate on more
|
|
bits than what was originally asked for. This is not the case anymore.</p><div class="spec type" id="type-t"><a href="#type-t" class="anchor"></a><div class="def type"><code><span class="keyword">type </span>t</code><code></code><code></code></div><div class="doc"><p>A resizable bitvector</p></div></div><div class="spec val" id="val-empty"><a href="#val-empty" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>empty : unit <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p>Empty bitvector.</p></div></div><div class="spec val" id="val-create"><a href="#val-create" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>create : size:int <span class="keyword">‑></span> bool <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p>Create a bitvector of given size, with given default value.</p></div></div><div class="spec val" id="val-copy"><a href="#val-copy" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>copy : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p>Copy of bitvector.</p></div></div><div class="spec val" id="val-cardinal"><a href="#val-cardinal" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>cardinal : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int</code></div><div class="doc"><p>Number of bits set to one, seen as a set of bits.</p></div></div><div class="spec val" id="val-length"><a href="#val-length" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>length : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int</code></div><div class="doc"><p>Size of underlying bitvector.
|
|
This is not related to the underlying implementation.
|
|
Changed at 1.2</p></div></div><div class="spec val" id="val-capacity"><a href="#val-capacity" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>capacity : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int</code></div><div class="doc"><p>The number of bits this bitvector can store without resizing.</p><ul class="at-tag"><li><span class="at-tag since">Since</span>: 1.2</li></ul></div></div><div class="spec val" id="val-resize"><a href="#val-resize" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>resize : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Resize the BV so that it has the specified length. This can grow or shrink
|
|
the underlying bitvector.</p><ul class="at-tag"><li><span class="at-tag raise">Raises</span> <span class="module-path">Invalid_arg</span>: on negative sizes.</li></ul></div></div><div class="spec val" id="val-is_empty"><a href="#val-is_empty" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>is_empty : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> bool</code></div><div class="doc"><p>Are there any true bits?</p></div></div><div class="spec val" id="val-set"><a href="#val-set" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>set : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Set i-th bit, extending the bitvector if needed.</p></div></div><div class="spec val" id="val-get"><a href="#val-get" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>get : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <span class="keyword">‑></span> bool</code></div><div class="doc"><p>Is the i-th bit true? Returns false if the index is too high.</p></div></div><div class="spec val" id="val-reset"><a href="#val-reset" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>reset : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Set i-th bit to 0, extending the bitvector if needed.</p></div></div><div class="spec val" id="val-flip"><a href="#val-flip" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>flip : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Flip i-th bit, extending the bitvector if needed.</p></div></div><div class="spec val" id="val-clear"><a href="#val-clear" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>clear : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Set every bit to 0.</p></div></div><div class="spec val" id="val-iter"><a href="#val-iter" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>iter : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> (int <span class="keyword">‑></span> bool <span class="keyword">‑></span> unit) <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Iterate on all bits.</p></div></div><div class="spec val" id="val-iter_true"><a href="#val-iter_true" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>iter_true : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> (int <span class="keyword">‑></span> unit) <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Iterate on bits set to 1.</p></div></div><div class="spec val" id="val-to_list"><a href="#val-to_list" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>to_list : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int list</code></div><div class="doc"><p>List of indexes that are true.</p></div></div><div class="spec val" id="val-to_sorted_list"><a href="#val-to_sorted_list" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>to_sorted_list : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int list</code></div><div class="doc"><p>Same as <a href="index.html#val-to_list">to_list</a>, but also guarantees the list is sorted in
|
|
increasing order.</p></div></div><div class="spec val" id="val-of_list"><a href="#val-of_list" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>of_list : int list <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p>From a list of true bits.</p><p>The bits are interpreted as indices into the returned bitvector, so the final
|
|
bitvector will have <code class="code">length t</code> equal to 1 more than max of list indices.</p></div></div><div class="spec val" id="val-first"><a href="#val-first" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>first : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int option</code></div><div class="doc"><p>First set bit, or return None.
|
|
changed type at 1.2</p></div></div><div class="spec val" id="val-first_exn"><a href="#val-first_exn" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>first_exn : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int</code></div><div class="doc"><p>First set bit, or</p><ul class="at-tag"><li><span class="at-tag raise">Raises</span> <span class="module-path">Not_found</span>: if all bits are 0.</li><li><span class="at-tag since">Since</span>: 1.2</li></ul></div></div><div class="spec val" id="val-filter"><a href="#val-filter" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>filter : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> (int <span class="keyword">‑></span> bool) <span class="keyword">‑></span> unit</code></div><div class="doc"><p><code class="code">filter bv p</code> only keeps the true bits of <code class="code">bv</code> whose <code class="code">index</code>
|
|
satisfies <code class="code">p index</code>.</p></div></div><div class="spec val" id="val-negate_self"><a href="#val-negate_self" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>negate_self : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p><code class="code">negate_self t</code> flips all of the bits in <code class="code">t</code>.</p><ul class="at-tag"><li><span class="at-tag since">Since</span>: 1.2</li></ul></div></div><div class="spec val" id="val-negate"><a href="#val-negate" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>negate : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p><code class="code">negate t</code> returns a copy of <code class="code">t</code> with all of the bits flipped.</p></div></div><div class="spec val" id="val-union_into"><a href="#val-union_into" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>union_into : into:<a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p><code class="code">union_into ~into bv</code> sets <code class="code">into</code> to the union of itself and <code class="code">bv</code>.
|
|
Also updates the length of <code class="code">into</code> to be at least <code class="code">length bv</code>.</p></div></div><div class="spec val" id="val-inter_into"><a href="#val-inter_into" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>inter_into : into:<a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p><code class="code">inter_into ~into bv</code> sets <code class="code">into</code> to the intersection of itself and <code class="code">bv</code>.
|
|
Also updates the length of <code class="code">into</code> to be at most <code class="code">length bv</code>.</p></div></div><div class="spec val" id="val-union"><a href="#val-union" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>union : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p><code class="code">union bv1 bv2</code> returns the union of the two sets.</p></div></div><div class="spec val" id="val-inter"><a href="#val-inter" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>inter : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p><code class="code">inter bv1 bv2</code> returns the intersection of the two sets.</p></div></div><div class="spec val" id="val-diff_into"><a href="#val-diff_into" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>diff_into : into:<a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p><code class="code">diff_into ~into t</code> modifies <code class="code">into</code> with only the bits set but not in <code class="code">t</code>.</p><ul class="at-tag"><li><span class="at-tag since">Since</span>: 1.2</li></ul></div></div><div class="spec val" id="val-diff"><a href="#val-diff" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>diff : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"><p><code class="code">diff t1 t2</code> returns those bits found in <code class="code">t1</code> but not in <code class="code">t2</code>.</p><ul class="at-tag"><li><span class="at-tag since">Since</span>: 1.2</li></ul></div></div><div class="spec val" id="val-select"><a href="#val-select" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>select : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <span class="type-var">'a</span> array <span class="keyword">‑></span> <span class="type-var">'a</span> list</code></div><div class="doc"><p><code class="code">select arr bv</code> selects the elements of <code class="code">arr</code> whose index
|
|
corresponds to a true bit in <code class="code">bv</code>. If <code class="code">bv</code> is too short, elements of <code class="code">arr</code>
|
|
with too high an index cannot be selected and are therefore not
|
|
selected.</p></div></div><div class="spec val" id="val-selecti"><a href="#val-selecti" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>selecti : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> <span class="type-var">'a</span> array <span class="keyword">‑></span> (<span class="type-var">'a</span><span class="keyword"> * </span>int) list</code></div><div class="doc"><p>Same as <a href="index.html#val-select">select</a>, but selected elements are paired with their indexes.</p></div></div><div class="spec type" id="type-sequence"><a href="#type-sequence" class="anchor"></a><div class="def type"><code><span class="keyword">type </span>'a sequence</code><code><span class="keyword"> = </span>(<span class="type-var">'a</span> <span class="keyword">‑></span> unit) <span class="keyword">‑></span> unit</code><code></code></div><div class="doc"></div></div><div class="spec val" id="val-to_seq"><a href="#val-to_seq" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>to_seq : <a href="index.html#type-t">t</a> <span class="keyword">‑></span> int <a href="index.html#type-sequence">sequence</a></code></div><div class="doc"></div></div><div class="spec val" id="val-of_seq"><a href="#val-of_seq" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>of_seq : int <a href="index.html#type-sequence">sequence</a> <span class="keyword">‑></span> <a href="index.html#type-t">t</a></code></div><div class="doc"></div></div><div class="spec val" id="val-pp"><a href="#val-pp" class="anchor"></a><div class="def val"><code><span class="keyword">val </span>pp : Format.formatter <span class="keyword">‑></span> <a href="index.html#type-t">t</a> <span class="keyword">‑></span> unit</code></div><div class="doc"><p>Print the bitvector as a string of bits.</p><ul class="at-tag"><li><span class="at-tag since">Since</span>: 0.13</li></ul></div></div></body></html> |