BitArray
structure
signature BIT_ARRAY
structure BitArray
: BIT_ARRAY
The BitArray structure provides compacted arrays of booleans, with one bit for each boolean value. A 0 (1) bit corresponds to the boolean value false
(true
), respectively. These arrays can be used to implement sets of integers. Member testing takes constant time and, since a bitarray
is mutable, adding and deleting elements are also constant time operations. In addition, the structure provides a complementary set of applicative operations.
include MONO_ARRAY
where type elem = bool
val fromString : string -> array
val bits : (int * int list) -> array
val getBits : array -> int list
val toString : array -> string
val isZero : array -> bool
val extend0 : (array * int) -> array
val extend1 : (array * int) -> array
val eqBits : (array * array) -> bool
val equal : (array * array) -> bool
val andb : (array * array * int) -> array
val orb : (array * array * int) -> array
val xorb : (array * array * int) -> array
val notb : array -> array
val lshift : (array * int) -> array
val rshift : (array * int) -> array
val setBit : (array * int) -> unit
val clrBit : (array * int) -> unit
val union : array -> array -> unit
val intersection : array -> array -> unit
val complement : array -> unit
fromString s
fromString "1af8" = 0001101011111000
. (By convention, 0 corresponds to false
and 1 corresponds to true
, bit 0 appears on the right, and indices increase to the left.) The length of the array will be 4*(size s)
. Raises Fail if a non-hexadecimal character appears in the string.
bits (sz, l)
getBits arr
toString arr
isZero arr
extend0 (arr, len)
extend1 (arr, len)
eqBits (arr, arr2)
getBits arr = getBits arr2
equal (arr, arr2)
andb (arr, arr2, len)
orb (arr, arr2, len)
xorb (arr, arr2, len)
notb arr
lshift (arr, n)
length
arr. Raises Fail if n is negative.
rshift (arr, n)
length
arr - n) consisting of bits n,n+1,...,length
arr - 1 of arr. If n >= length
arr, the new array has length 0.
setBit (arr, i)
clrBit (arr, i)
update(arr,i,true) update(arr,i,false)respectively. Raises Subscript if i is negative or i $GREATEREQ;
length
arr.
union arr arr2
intersection arr arr2
complement arr
BitVector, MONO_ARRAY
Last Modified June 9, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies