src/utils/lib/bitv.mli

   1 (*
   2  * Bit vectors.
   3  * Copyright (C) 1999 Jean-Christophe FILLIATRE
   4  *
   5  * This software is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License version 2, as published by the Free Software Foundation.
   8  *
   9  * This software is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12  *
  13  * See the GNU Library General Public License version 2 for more details
  14  * (enclosed in the file LGPL).
  15  *)
  16
  17 (*i $Id$ i*)
  18
  19 (*s {\bf Module Bitv}.
  20     This module implements bit vectors, as an abstract datatype [t].
  21     Since bit vectors are particular cases of arrays, this module provides
  22     the same operations as the module [Array] (Sections~\ref{barray}
  23     up to \ref{earray}). It also provides bitwise operations
  24     (Section~\ref{bitwise}). In the following, [false] stands for the bit 0
  25     and [true] for the bit 1. *)
  26
  27 type t
  28
  29 (*s {\bf Creation, access and assignment.} \label{barray}
  30     [(Bitv.create n b)] creates a new bit vector of length [n],
  31     initialized with [b].
  32     [(Bitv.init n f)] returns a fresh vector of length [n],
  33     with bit number [i] initialized to the result of [(f i)].
  34     [(Bitv.set v n b)] sets the [n]th bit of [v] to the value [b].
  35     [(Bitv.get v n)] returns the [n]th bit of [v].
  36     [Bitv.length] returns the length (number of elements) of the given
  37     vector. *)
  38
  39 val create : int -> bool -> t
  40
  41 val init : int -> (int -> bool) -> t
  42
  43 val set : t -> int -> bool -> unit
  44
  45 val get : t -> int -> bool
  46
  47 val length : t -> int
  48
  49 (*s [max_length] is the maximum length of a bit vector (System dependent). *)
  50
  51 val max_length : int
  52
  53 (*s {\bf Copies and concatenations.}
  54    [(Bitv.copy v)] returns a copy of [v],
  55    that is, a fresh vector containing the same elements as
  56    [v]. [(Bitv.append v1 v2)] returns a fresh vector containing the
  57    concatenation of the vectors [v1] and [v2]. [Bitv.concat] is
  58    similar to [Bitv.append], but catenates a list of vectors. *)
  59
  60 val copy : t -> t
  61
  62 val append : t -> t -> t
  63
  64 val concat : t list -> t
  65
  66 (*s {\bf Sub-vectors and filling.}
  67     [(Bitv.sub v start len)] returns a fresh
  68     vector of length [len], containing the bits number [start] to
  69     [start + len - 1] of vector [v].  Raise [Invalid_argument
  70     "Bitv.sub"] if [start] and [len] do not designate a valid
  71     subvector of [v]; that is, if [start < 0], or [len < 0], or [start
  72     + len > Bitv.length a].
  73
  74     [(Bitv.fill v ofs len b)] modifies the vector [v] in place,
  75     storing [b] in elements number [ofs] to [ofs + len - 1].  Raise
  76     [Invalid_argument "Bitv.fill"] if [ofs] and [len] do not designate
  77     a valid subvector of [v].
  78
  79     [(Bitv.blit v1 o1 v2 o2 len)] copies [len] elements from vector
  80     [v1], starting at element number [o1], to vector [v2], starting at
  81     element number [o2]. It {\em does not work} correctly if [v1] and [v2] are
  82     the same vector with the source and destination chunks overlapping.
  83     Raise [Invalid_argument "Bitv.blit"] if [o1] and [len] do not
  84     designate a valid subvector of [v1], or if [o2] and [len] do not
  85     designate a valid subvector of [v2]. *)
  86
  87 val sub : t -> int -> int -> t
  88
  89 val fill : t -> int -> int -> bool -> unit
  90
  91 val blit : t -> int -> t -> int -> int -> unit
  92
  93 (*s {\bf Iterators.} \label{earray}
  94     [(Bitv.iter f v)] applies function [f] in turn to all
  95     the elements of [v]. Given a function [f], [(Bitv.map f v)] applies
  96     [f] to all
  97     the elements of [v], and builds a vector with the results returned
  98     by [f]. [Bitv.iteri] and [Bitv.mapi] are similar to [Bitv.iter]
  99     and [Bitv.map] respectively, but the function is applied to the
 100     index of the element as first argument, and the element itself as
 101     second argument.
 102
 103     [(Bitv.fold_left f x v)] computes [f (... (f (f x (get v 0)) (get
 104     v 1)) ...) (get v (n-1))], where [n] is the length of the vector
 105     [v].
 106
 107     [(Bitv.fold_right f a x)] computes [f (get v 0) (f (get v 1)
 108     ( ... (f (get v (n-1)) x) ...))], where [n] is the length of the
 109     vector [v]. *)
 110
 111 val iter : (bool -> unit) -> t -> unit
 112 val map : (bool -> bool) -> t -> t
 113
 114 val iteri : (int -> bool -> unit) -> t -> unit
 115 val mapi : (int -> bool -> bool) -> t -> t
 116
 117 val fold_left : ('a -> bool -> 'a) -> 'a -> t -> 'a
 118 val fold_right : (bool -> 'a -> 'a) -> t -> 'a -> 'a
 119 val foldi_left : ('a -> int -> bool -> 'a) -> 'a -> t -> 'a
 120 val foldi_right : (int -> bool -> 'a -> 'a) -> t -> 'a -> 'a
 121
 122 val iteri_true : (int -> unit) -> t -> unit
 123
 124 (*s [gray_iter f n] iterates function [f] on all bit vectors
 125     of length [n], once each, using a Gray code. The order in which
 126     bit vectors are processed is unspecified. *)
 127
 128 val gray_iter : (t -> unit) -> int -> unit
 129
 130 (*s {\bf Bitwise operations.} \label{bitwise} [bwand], [bwor] and
 131     [bwxor] implement logical and, or and exclusive or.  They return
 132     fresh vectors and raise [Invalid_argument "Bitv.xxx"] if the two
 133     vectors do not have the same length (where \texttt{xxx} is the
 134     name of the function).  [bwnot] implements the logical negation.
 135     It returns a fresh vector.
 136     [shiftl] and [shiftr] implement shifts. They return fresh vectors.
 137     [shiftl] moves bits from least to most significant, and [shiftr]
 138     from most to least significant (think [lsl] and [lsr]).
 139     [all_zeros] and [all_ones] respectively test for a vector only
 140     containing zeros and only containing ones. *)
 141
 142 val bw_and : t -> t -> t
 143 val bw_or  : t -> t -> t
 144 val bw_xor : t -> t -> t
 145 val bw_not : t -> t
 146
 147 val shiftl : t -> int -> t
 148 val shiftr : t -> int -> t
 149
 150 val all_zeros : t -> bool
 151 val all_ones  : t -> bool
 152
 153 (*s {\bf Conversions to and from strings.}
 154     Least significant bit comes first. *)
 155
 156 val to_string : t -> string
 157 val of_string : string -> t
 158 val print : Format.formatter -> t -> unit
 159
 160 (*s {\bf Conversions to and from lists of integers.}
 161     The list gives the indices of bits which are set (ie [true]). *)
 162
 163 val to_list : t -> int list
 164 val of_list : int list -> t
 165 val of_list_with_length : int list -> int -> t
 166
 167 (*s Interpretation of bit vectors as integers. Least significant bit
 168     comes first (ie is at index 0 in the bit vector).
 169     [to_xxx] functions truncate when the bit vector is too wide,
 170     and raise [Invalid_argument] when it is too short.
 171     Suffix [_s] indicates that sign bit is kept,
 172     and [_us] that it is discarded. *)
 173
 174 (* type [int] (length 31/63 with sign, 30/62 without) *)
 175 val of_int_s : int -> t
 176 val to_int_s : t -> int
 177 val of_int_us : int -> t
 178 val to_int_us : t -> int
 179 (* type [Int32.t] (length 32 with sign, 31 without) *)
 180 val of_int32_s : Int32.t -> t
 181 val to_int32_s : t -> Int32.t
 182 val of_int32_us : Int32.t -> t
 183 val to_int32_us : t -> Int32.t
 184 (* type [Int64.t] (length 64 with sign, 63 without) *)
 185 val of_int64_s : Int64.t -> t
 186 val to_int64_s : t -> Int64.t
 187 val of_int64_us : Int64.t -> t
 188 val to_int64_us : t -> Int64.t
 189 (* type [Nativeint.t] (length 32/64 with sign, 31/63 without) *)
 190 val of_nativeint_s : Nativeint.t -> t
 191 val to_nativeint_s : t -> Nativeint.t
 192 val of_nativeint_us : Nativeint.t -> t
 193 val to_nativeint_us : t -> Nativeint.t
 194
 195 (*s Only if you know what you are doing... *)
 196
 197 val unsafe_set : t -> int -> bool -> unit
 198 val unsafe_get : t -> int -> bool