<!-- bit-array.mldoc -->
<!-- Entities.sgml entry 
<!ENTITY BitArray SDATA "bit-array-sig.sml">
 -->

<!DOCTYPE ML-DOC SYSTEM>

<COPYRIGHT OWNER="Bell Labs, Lucent Technologies" YEAR=1998>
<VERSION VERID="1.0" YEAR=1998 MONTH=6 DAY=9>
<TITLE>The BitArray structure</TITLE>

<INTERFACE>
<HEAD>The <CD/BitArray/ structure</HEAD>
<SEEALSO>
    <STRREF/BitVector/
    <SIGREF DOCUMENT=SML-BASIS-DOC/MONO_ARRAY/
</SEEALSO>

<PP>
The <STRREF NOLINK/BitArray/ structure  
provides compacted arrays of booleans,
with one bit for each boolean value. A 0 (1) bit corresponds
to the boolean value <CD/false/ (<CD/true/), respectively. These arrays can be
used to implement sets of integers. Member testing takes constant time and, 
since a <CD/bitarray/ is mutable, adding and deleting elements are also constant
time operations. In addition, the structure provides a complementary set 
of applicative operations.


<STRUCTURE STRID="BitArray">
  <SIGBODY SIGID="BIT_ARRAY" FILE=BIT-ARRAY>
    <SPEC>
      <INCLUDE><SIGREF DOCUMENT=SML-BASIS-DOC>MONO_ARRAY</SIGREF>
        <WHERETYPE><ID>elem<TY>bool</WHERETYPE>
    <SPEC>
      <VAL>fromString<TY>string -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Fail/
        <COMMENT>
          <PROTOTY>
          fromString <ARG/s/
          </PROTOTY>
          creates an array from the string argument <ARG/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, 
          <CD/fromString "1af8" = 0001101011111000/. (By convention, 0 
          corresponds to <CD/false/ and 1 corresponds to <CD/true/, 
          bit 0 appears on the right, and indices increase to the left.) 
          The length of the array will be <CD/4*(size <ARG/s/)/. 
          Raises <EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Fail/ if a non-hexadecimal character 
          appears in the string.
    <SPEC>
      <VAL>bits<TY>(int * int list) -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Subscript/
        <COMMENT>
          <PROTOTY>
          bits (<ARG/sz/, <ARG/l/)
          </PROTOTY>
          creates an array of length <ARG/sz/ with the indices of its set bits  
          given by <ARG/l/. Raises <EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Subscript/ 
          if a list item is less than 0, or greater than or equal to <ARG/sz/.
    <SPEC>
      <VAL>getBits<TY>array -> int list
        <COMMENT>
          <PROTOTY>
          getBits <ARG/arr/
          </PROTOTY>
          returns a list of indices of the bits set in <ARG/arr/, 
          in increasing order.
    <SPEC>
      <VAL>toString<TY>array -> string
        <COMMENT>
          <PROTOTY>
          toString <ARG/arr/
          </PROTOTY>
          encodes a bit array as a string. The bit array is zero-padded to 
          the next length that is a multiple of 4.
    <SPEC>
      <VAL>isZero<TY>array -> bool
        <COMMENT>
          <PROTOTY>
          isZero <ARG/arr/
          </PROTOTY>
          returns true if and only if no bits are set.
    <SPEC>
      <VAL>extend0<TY>(array * int) -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Size/
      <VAL>extend1<TY>(array * int) -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Size/
        <COMMENT>
          <PROTOTY>
          extend0 (<ARG/arr/, <ARG/len/)
          <PROTO>
          extend1 (<ARG/arr/, <ARG/len/)
          </PROTOTY>
          create a new arrays by extending the argument bit array 
          by 0's or 1's to given length. If <ARG/arr/ 
          is already as long as <ARG/len/, return a copy of the bit array. 
          Raise <EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Size/
	  if <ARG/len/ is negative.
    <SPEC>
      <VAL>eqBits<TY>(array * array) -> bool
        <COMMENT>
          <PROTOTY>
          eqBits (<ARG/arr/, <ARG/arr2/)
          </PROTOTY>
          returns true if the set bits in the two arrays are the same. This
          is equivalent to:
          <CODE>
            getBits <ARG/arr/ = getBits <ARG/arr2/
          </CODE>
    <SPEC>
      <VAL>equal<TY>(array * array) -> bool
        <COMMENT>
          <PROTOTY>
          equal (<ARG/arr/, <ARG/arr2/)
          </PROTOTY>
          returns true if the two arrays are equivalent, i.e., have the
          same length and set bits.
    <SPEC>
      <VAL>andb<TY>(array * array * int) -> array
      <VAL>orb<TY>(array * array * int) -> array
      <VAL>xorb<TY>(array * array * int) -> array
        <COMMENT>
          <PROTOTY>
          andb (<ARG/arr/, <ARG/arr2/, <ARG/len/)
          <PROTO>
          orb (<ARG/arr/, <ARG/arr2/, <ARG/len/)
          <PROTO>
          xorb (<ARG/arr/, <ARG/arr2/, <ARG/len/)
          </PROTOTY>
          creates a new array of length <ARG/len/ by logically combining the 
          bits of <ARG/arr/ and <ARG/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.
    <SPEC>
      <VAL>notb<TY>array -> array
        <COMMENT>
          <PROTOTY>
          notb <ARG/arr/
          </PROTOTY>
          creates a new array with all bits of original array inverted.
    <SPEC>
      <VAL>lshift<TY>(array * int) -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Fail/
        <COMMENT>
          <PROTOTY>
          lshift (<ARG/arr/, <ARG/n/)
          </PROTOTY>
          creates a new array by inserting <ARG/n/ 0's on the right 
          of <ARG/arr/. The new array has 
          length <MATH/<ARG/n/ + <CD/length/ <ARG/arr//.
          Raises <EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Fail/ if <ARG/n/ is negative.
    <SPEC>
      <VAL>rshift<TY>(array * int) -> array
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Fail/
        <COMMENT>
          <PROTOTY>
          rshift (<ARG/arr/, <ARG/n/)
          </PROTOTY>
          creates a new array of 
          length <MATH/max(0,<CD/length/ <ARG/arr/ - <ARG/n/)/ consisting 
          of bits <MATH/n,n+1,...,<CD/length/ <ARG/arr/ - 1/ of <ARG/arr/. 
          If <MATH/<ARG/n/ &GREATEREQ; <CD/length/ <ARG/arr//, the new array 
          has length 0.
    <SPEC>
      <VAL>setBit<TY>(array * int) -> unit
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Subscript/
      <VAL>clrBit<TY>(array * int) -> unit
      <RAISES><EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Subscript/
        <COMMENT>
          <PROTOTY>
          setBit (<ARG/arr/, <ARG/i/)
          <PROTO>
          clrBit (<ARG/arr/, <ARG/i/)
          </PROTOTY>
          updates the value at index <ARG/i/ to new value, true and false,
          respectively. These are equivalent to:
          <CODE>
          update(arr,i,true)
          update(arr,i,false)
          </CODE>
          respectively. Raises <EXNREF STRID="General" DOCUMENT=SML-BASIS-DOC/Subscript/ if 
          <ARG/i/ is negative 
          or <MATH/<ARG/i/ $GREATEREQ; <CD/length/ <ARG/arr//. 
    <SPEC>
      <VAL>union<TY>array -> array -> unit
      <VAL>intersection<TY>array -> array -> unit
        <COMMENT>
          <PROTOTY>
          union <ARG/arr/ <ARG/arr2/
          <PROTO>
          intersection <ARG/arr/ <ARG/arr2/
          </PROTOTY>
          Or (respectively, and) <ARG/arr2/ into <ARG/arr/. The array <ARG/arr2/
          is implicitly truncated or extended by 0's to match the length 
          of the <ARG/arr/.
    <SPEC>
      <VAL>complement<TY>array -> unit
        <COMMENT>
          <PROTOTY>
          complement <ARG/arr/
          </PROTOTY>
          inverts all the bits in <ARG/arr/.
</STRUCTURE>

</INTERFACE>
