(*                                                                        *)
(*  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        *)
(*                                                                        *)

(*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

    [(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

(* With most significant bits first. *)

module M : sig
  val to_string : t -> string
  val of_string : string -> t
  val print : Format.formatter -> t -> unit

(*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