# 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

[ Top | Parent | Contents | Index | Root ]

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