SML/NJ Library Manual

The BitVector structure

Synopsis

signature BIT_VECTOR
structure BitVector : BIT_VECTOR


The BitVector structure provides compacted vectors of booleans, with one bit for each boolean value. A 0 (1) bit corresponds to the boolean value false (true), respectively. These vectors can be used to implement sets of integers. Member testing takes constant time.

Interface

include MONO_VECTOR
  where type elem = bool
val fromString : string -> vector
val bits : (int * int list) -> vector
val getBits : vector -> int list
val toString : vector -> string
val isZero : vector -> bool
val extend0 : (vector * int) -> vector
val extend1 : (vector * int) -> vector
val eqBits : (vector * vector) -> bool
val equal : (vector * vector) -> bool
val andb : (vector * vector * int) -> vector
val orb : (vector * vector * int) -> vector
val xorb : (vector * vector * int) -> vector
val notb : vector -> vector
val lshift : (vector * int) -> vector
val rshift : (vector * int) -> vector


Description

fromString s

creates a vector from the string argument s, which should contain a hexadecimal representation of the bits set in the vector. 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 vector will be 4*(size s). Raises Fail if a non-hexadecimal character appears in the string.

bits (sz, l)

creates a vector 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 vec

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

toString vec

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

isZero vec

returns true if and only if no bits are set.

extend0 (vec, len)

extend1 (vec, len)

create a new vectors by extending the argument bit vector by 0's or 1's to given length. If vec is already as long as len, return a copy of the bit vector. Raises Size if len is negative.

eqBits (vec, vec2)

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

            getBits vec = getBits vec2
          

equal (vec, vec2)

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

andb (vec, vec2, len)

orb (vec, vec2, len)

xorb (vec, vec2, len)

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

notb vec

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

lshift (vec, i)

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

rshift (vec, i)

creates a new vector of length max(0,length vec - n) consisting of bits n,n+1,...,length vec - 1 of vec. If n >= length vec, the new vector has length 0.

See Also

BitArray, MONO_VECTOR

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