package bitv
Install
dune-project
Dependency
Authors
Maintainers
Sources
md5=03cac56cec6a26321bad06e519cc3847
sha512=ae52e352b35486d7f990dbabcb3a0a78201cfb8f16c7273dbc520bb59f326c3aaedd64fd0ad84a99b686089329ad7f0a9a84e87ba766dafa3431883202ecc087
doc/bitv/Bitv/index.html
Module Bitv
Source
This module implements bit vectors, as an abstract datatype t
. Since bit vectors are particular cases of arrays, this module provides the same operations as module Array
. It also provides bitwise operations and conversions to/from integer types.
In the following, false
stands for bit 0 and true
for bit 1.
the type of bit vectors
Creation, access and assignment.
(Bitv.create n b)
creates a new bit vector of length n
, initialized with b
.
(Bitv.init n f)
returns a fresh vector of length n
, with bit number i
initialized to the result of (f i)
.
Bitv.random n
returns a fresh vector of length n
with random bits. This is equivalent to Bitv.init n (fun _ -> Random.bool ())
, but much faster.
Returns true
if two bit vectors are of the same length and with the same bits.
Bitv.tanimoto v1 v2
is |inter(v1,v2)| / |union(v1,v2)|. Also called the Jaccard score. (1 - tanimoto) is a proper distance. raises Invalid_argument
if the two vectors do not have the same length
This is typically Sys.max_string_length * 8
but may be smaller on small platform (e.g. Javascript).
Returns true if the argument exceeds the maximum length of a bit vector (System dependent).
Copies and concatenations.
(Bitv.copy v)
returns a copy of v
, that is, a fresh vector containing the same elements as v
.
(Bitv.append v1 v2)
returns a fresh vector containing the concatenation of the vectors v1
and v2
.
Bitv.concat
is similar to Bitv.append
, but catenates a list of vectors.
Sub-vectors and filling.
(Bitv.sub v start len)
returns a fresh vector of length len
, containing the bits number start
to start + len - 1
of vector v
. Raise Invalid_argument "Bitv.sub"
if start
and len
do not designate a valid subvector of v
; that is, if start < 0
, or len < 0
, or start + len > Bitv.length a
.
(Bitv.fill v ofs len b)
modifies the vector v
in place, storing b
in elements number ofs
to ofs + len - 1
. Raise Invalid_argument "Bitv.fill"
if ofs
and len
do not designate a valid subvector of v
.
(Bitv.blit v1 o1 v2 o2 len)
copies len
elements from vector v1
, starting at element number o1
, to vector v2
, starting at element number o2
. It does not work correctly if v1
and v2
are the same vector with the source and destination chunks overlapping. Raise Invalid_argument "Bitv.blit"
if o1
and len
do not designate a valid subvector of v1
, or if o2
and len
do not designate a valid subvector of v2
.
Iterators
(Bitv.iter f v)
applies function f
in turn to all the elements of v
.
Given a function f
, (Bitv.map f v)
applies f
to all the elements of v
, and builds a vector with the results returned by f
.
Bitv.iteri
and Bitv.mapi
are similar to Bitv.iter
and Bitv.map
respectively, but the function is applied to the index of the element as first argument, and the element itself as second argument.
(Bitv.fold_left f x v)
computes f (... (f (f x (get v 0)) (get v 1)) ...) (get v (n-1))
, where n
is the length of the vector v
.
(Bitv.fold_right f a x)
computes f (get v 0) (f (get v 1) ( ... (f (get v (n-1)) x) ...))
, where n
is the length of the vector v
.
Pop count and other iterations
iteri_true f v
applies function f
in turn to all indexes of the elements of v
which are set (i.e. true
); indexes are visited from least significant to most significant.
gray_iter f n
iterates function f
on all bit vectors of length n
, once each, using a Gray code. The order in which bit vectors are processed is unspecified.
Bitwise operations.
All the bitwise operations return fresh vectors.
bitwise AND; raises Invalid_argument
if the two vectors do not have the same length
bitwise OR; raises Invalid_argument
if the two vectors do not have the same length
bitwise XOR; raises Invalid_argument
if the two vectors do not have the same length
Bitwise in place operations.
This part of the API extends some bitwise operations by making them operate in place, that is mutating a destination bit vector supplied as a labeled argument dst
, rather than returning a fresh one.
These in place operations support being called with dst
being one of the operands supplied to the function call.
For example bw_and_in_place ~dst:a a b
will store in a
the result of the operation bw_and a b
.
bitwise AND in place into dst
; raises Invalid_argument
if the three vectors do not have the same length
bitwise OR in place into dst
; raises Invalid_argument
if the three vectors do not have the same length
bitwise XOR in place into dst
; raises Invalid_argument
if the three vectors do not have the same length
bitwise NOT in place into dst
; raises Invalid_argument
if the two vectors do not have the same length
Test functions
Conversions to and from strings
Input/output in a machine-independent format
The following functions export/import a bit vector to/from a channel or bytes, in a way that is compact, independent of the machine architecture, and independent of the OCaml version. For a bit vector of length n
, the number of bytes of this external representation is 8+ceil(n/8).
Conversions to and from lists of integers
The list gives the indices of bits which are set (i.e. true
).
Interpretation of bit vectors as integers
Least significant bit comes first (ie is at index 0 in the bit vector). to_xxx
functions truncate when the bit vector is too wide. Suffix _s
means that sign bit is kept, and _us
that it is discarded.
type int
(length 31/63 with sign, 30/62 without)
type Int32.t
(length 32 with sign, 31 without)
type Int64.t
(length 64 with sign, 63 without)
type Nativeint.t
(length 32/64 with sign, 31/63 without)
Only if you know what you are doing...
- Creation, access and assignment.
- Copies and concatenations.
- Sub-vectors and filling.
- Iterators
- Pop count and other iterations
- Bitwise operations.
- Test functions
- Conversions to and from strings
- Input/output in a machine-independent format
- Conversions to and from lists of integers
- Interpretation of bit vectors as integers
- Only if you know what you are doing...