(**************************************************************************) (* *) (* Copyright (C) Jean-Christophe Filliatre *) (* *) (* This software is free software; you can redistribute it and/or *) (* modify it under the terms of the GNU Library General Public *) (* License version 2, with the special exception on linking *) (* described in file LICENSE. *) (* *) (* This software is distributed in the hope that it will be useful, *) (* but WITHOUT ANY WARRANTY; without even the implied warranty of *) (* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *) (* *) (**************************************************************************) (*i $Id: bitv.mli,v 1.19 2012/08/14 07:26:00 filliatr Exp $ i*) (*s {\bf Module Bitv}. 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] (Sections~\ref{barray} up to \ref{earray}). It also provides bitwise operations (Section~\ref{bitwise}) and conversions to/from integer types. In the following, [false] stands for bit 0 and [true] for bit 1. *) type t (*s {\bf Creation, access and assignment.} \label{barray} [(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.set v n b)] sets the [n]th bit of [v] to the value [b]. [(Bitv.get v n)] returns the [n]th bit of [v]. [Bitv.length] returns the length (number of elements) of the given vector. *) val create : int -> bool -> t val init : int -> (int -> bool) -> t val set : t -> int -> bool -> unit val get : t -> int -> bool val length : t -> int (*s [max_length] is the maximum length of a bit vector (System dependent). *) val max_length : int (*s {\bf 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. *) val copy : t -> t val append : t -> t -> t val concat : t list -> t (*s {\bf 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 {\em 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]. *) val sub : t -> int -> int -> t val fill : t -> int -> int -> bool -> unit val blit : t -> int -> t -> int -> int -> unit (*s {\bf Iterators.} \label{earray} [(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]. *) val iter : (bool -> unit) -> t -> unit val map : (bool -> bool) -> t -> t val iteri : (int -> bool -> unit) -> t -> unit val mapi : (int -> bool -> bool) -> t -> t val fold_left : ('a -> bool -> 'a) -> 'a -> t -> 'a val fold_right : (bool -> 'a -> 'a) -> t -> 'a -> 'a val foldi_left : ('a -> int -> bool -> 'a) -> 'a -> t -> 'a val foldi_right : (int -> bool -> 'a -> 'a) -> t -> 'a -> 'a (*s Population count, i.e., number of 1 bits *) val pop: t -> int (*s [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. *) val iteri_true : (int -> unit) -> t -> unit (*s [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. *) val gray_iter : (t -> unit) -> int -> unit (*s {\bf Bitwise operations.} \label{bitwise} [bwand], [bwor] and [bwxor] implement logical and, or and exclusive or. They return fresh vectors and raise [Invalid_argument "Bitv.xxx"] if the two vectors do not have the same length (where \texttt{xxx} is the name of the function). [bwnot] implements the logical negation. It returns a fresh vector. [shiftl] and [shiftr] implement shifts. They return fresh vectors. [shiftl] moves bits from least to most significant, and [shiftr] from most to least significant (think [lsl] and [lsr]). [all_zeros] and [all_ones] respectively test for a vector only containing zeros and only containing ones. *) val bw_and : t -> t -> t val bw_or : t -> t -> t val bw_xor : t -> t -> t val bw_not : t -> t val shiftl : t -> int -> t val shiftr : t -> int -> t val all_zeros : t -> bool val all_ones : t -> bool (*s {\bf Conversions to and from strings.} *) (* With least significant bits first. *) module L : sig val to_string : t -> string val of_string : string -> t val print : Format.formatter -> t -> unit end (* With most significant bits first. *) module M : sig val to_string : t -> string val of_string : string -> t val print : Format.formatter -> t -> unit end (*s {\bf Input/output in a machine-independent format.} The following functions export/import a bit vector to/from a channel, 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 4+ceil(n/8) on a 32-bit machine and 8+ceil(n/8) on a 64-bit machine. *) val output_bin: out_channel -> t -> unit val input_bin: in_channel -> t (*s {\bf Conversions to and from lists of integers.} The list gives the indices of bits which are set (ie [true]). *) val to_list : t -> int list val of_list : int list -> t val of_list_with_length : int list -> int -> t (*s 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, and raise [Invalid_argument] when it is too short. Suffix [_s] means that sign bit is kept, and [_us] that it is discarded. *) (* type [int] (length 31/63 with sign, 30/62 without) *) val of_int_s : int -> t val to_int_s : t -> int val of_int_us : int -> t val to_int_us : t -> int (* type [Int32.t] (length 32 with sign, 31 without) *) val of_int32_s : Int32.t -> t val to_int32_s : t -> Int32.t val of_int32_us : Int32.t -> t val to_int32_us : t -> Int32.t (* type [Int64.t] (length 64 with sign, 63 without) *) val of_int64_s : Int64.t -> t val to_int64_s : t -> Int64.t val of_int64_us : Int64.t -> t val to_int64_us : t -> Int64.t (* type [Nativeint.t] (length 32/64 with sign, 31/63 without) *) val of_nativeint_s : Nativeint.t -> t val to_nativeint_s : t -> Nativeint.t val of_nativeint_us : Nativeint.t -> t val to_nativeint_us : t -> Nativeint.t (*s Only if you know what you are doing... *) val unsafe_set : t -> int -> bool -> unit val unsafe_get : t -> int -> bool
This document was generated using caml2html