SML/NJ Library Manual

The BitArray structure

Synopsis

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.

Interface

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


Description

fromString s

creates an array from the string argument s, which should contain a hexadecimal representation of the bits set in the array. Characters 0-9, a-f and A-F are allowed. For example, 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)

creates an array of length sz with the indices of its set bits given by l. Raises Subscript if a list item is less than 0, or greater than or equal to sz.

getBits arr

returns a list of indices of the bits set in arr, in increasing order.

toString arr

encodes a bit array as a string. The bit array is zero-padded to the next length that is a multiple of 4.

isZero arr

returns true if and only if no bits are set.

extend0 (arr, len)

extend1 (arr, len)

create a new arrays by extending the argument bit array by 0's or 1's to given length. If arr is already as long as len, return a copy of the bit array. Raise Size if len is negative.

eqBits (arr, arr2)

returns true if the set bits in the two arrays are the same. This is equivalent to:

            getBits arr = getBits arr2
          

equal (arr, arr2)

returns true if the two arrays are equivalent, i.e., have the same length and set bits.

andb (arr, arr2, len)

orb (arr, arr2, len)

xorb (arr, arr2, len)

creates a new array of length len by logically combining the bits of arr and arr2 using and, or and xor, respectively. If necessary, the arrays are implicitly extended by 0 to be the same length as the new array.

notb arr

creates a new array with all bits of original array inverted.

lshift (arr, n)

creates a new array by inserting n 0's on the right of arr. The new array has length n + length arr. Raises Fail if n is negative.

rshift (arr, n)

creates a new array of length max(0,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)

updates the value at index i to new value, true and false, respectively. These are equivalent to:

          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

Or (respectively, and) arr2 into arr. The array arr2 is implicitly truncated or extended by 0's to match the length of the arr.

complement arr

inverts all the bits in arr.

See Also

BitVector, MONO_ARRAY

Last Modified June 9, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies