Class BitArray

  • All Implemented Interfaces:
    java.lang.Cloneable

    public final class BitArray
    extends java.lang.Object
    implements java.lang.Cloneable

    A simple, fast array of bits, represented compactly by an array of ints internally.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[] bits  
      private static int[] EMPTY_BITS  
      private static float LOAD_FACTOR  
      private int size  
    • Constructor Summary

      Constructors 
      Constructor Description
      BitArray()  
      BitArray​(int size)  
      BitArray​(int[] bits, int size)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void appendBit​(boolean bit)  
      void appendBitArray​(BitArray other)  
      void appendBits​(int value, int numBits)
      Appends the least-significant bits, from value, in order from most-significant to least-significant.
      void clear()
      Clears all bits (sets to false).
      BitArray clone()  
      private void ensureCapacity​(int newSize)  
      boolean equals​(java.lang.Object o)  
      void flip​(int i)
      Flips bit i.
      boolean get​(int i)  
      int[] getBitArray()  
      int getNextSet​(int from)  
      int getNextUnset​(int from)  
      int getSize()  
      int getSizeInBytes()  
      int hashCode()  
      boolean isRange​(int start, int end, boolean value)
      Efficient method to check if a range of bits is set, or not set.
      private static int[] makeArray​(int size)  
      void reverse()
      Reverses all bits in the array.
      void set​(int i)
      Sets bit i.
      void setBulk​(int i, int newBits)
      Sets a block of 32 bits, starting at bit i.
      void setRange​(int start, int end)
      Sets a range of bits.
      void toBytes​(int bitOffset, byte[] array, int offset, int numBytes)  
      java.lang.String toString()  
      void xor​(BitArray other)  
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • EMPTY_BITS

        private static final int[] EMPTY_BITS
      • bits

        private int[] bits
      • size

        private int size
    • Constructor Detail

      • BitArray

        public BitArray()
      • BitArray

        public BitArray​(int size)
      • BitArray

        BitArray​(int[] bits,
                 int size)
    • Method Detail

      • getSize

        public int getSize()
      • getSizeInBytes

        public int getSizeInBytes()
      • ensureCapacity

        private void ensureCapacity​(int newSize)
      • get

        public boolean get​(int i)
        Parameters:
        i - bit to get
        Returns:
        true iff bit i is set
      • set

        public void set​(int i)
        Sets bit i.
        Parameters:
        i - bit to set
      • flip

        public void flip​(int i)
        Flips bit i.
        Parameters:
        i - bit to set
      • getNextSet

        public int getNextSet​(int from)
        Parameters:
        from - first bit to check
        Returns:
        index of first bit that is set, starting from the given index, or size if none are set at or beyond this given index
        See Also:
        getNextUnset(int)
      • getNextUnset

        public int getNextUnset​(int from)
        Parameters:
        from - index to start looking for unset bit
        Returns:
        index of next unset bit, or size if none are unset until the end
        See Also:
        getNextSet(int)
      • setBulk

        public void setBulk​(int i,
                            int newBits)
        Sets a block of 32 bits, starting at bit i.
        Parameters:
        i - first bit to set
        newBits - the new value of the next 32 bits. Note again that the least-significant bit corresponds to bit i, the next-least-significant to i+1, and so on.
      • setRange

        public void setRange​(int start,
                             int end)
        Sets a range of bits.
        Parameters:
        start - start of range, inclusive.
        end - end of range, exclusive
      • clear

        public void clear()
        Clears all bits (sets to false).
      • isRange

        public boolean isRange​(int start,
                               int end,
                               boolean value)
        Efficient method to check if a range of bits is set, or not set.
        Parameters:
        start - start of range, inclusive.
        end - end of range, exclusive
        value - if true, checks that bits in range are set, otherwise checks that they are not set
        Returns:
        true iff all bits are set or not set in range, according to value argument
        Throws:
        java.lang.IllegalArgumentException - if end is less than start or the range is not contained in the array
      • appendBit

        public void appendBit​(boolean bit)
      • appendBits

        public void appendBits​(int value,
                               int numBits)
        Appends the least-significant bits, from value, in order from most-significant to least-significant. For example, appending 6 bits from 0x000001E will append the bits 0, 1, 1, 1, 1, 0 in that order.
        Parameters:
        value - int containing bits to append
        numBits - bits from value to append
      • appendBitArray

        public void appendBitArray​(BitArray other)
      • xor

        public void xor​(BitArray other)
      • toBytes

        public void toBytes​(int bitOffset,
                            byte[] array,
                            int offset,
                            int numBytes)
        Parameters:
        bitOffset - first bit to start writing
        array - array to write into. Bytes are written most-significant byte first. This is the opposite of the internal representation, which is exposed by getBitArray()
        offset - position in array to start writing
        numBytes - how many bytes to write
      • getBitArray

        public int[] getBitArray()
        Returns:
        underlying array of ints. The first element holds the first 32 bits, and the least significant bit is bit 0.
      • reverse

        public void reverse()
        Reverses all bits in the array.
      • makeArray

        private static int[] makeArray​(int size)
      • equals

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • clone

        public BitArray clone()
        Overrides:
        clone in class java.lang.Object