Package io.github.abductcows.bitarray

Class BitArray

  • All Implemented Interfaces:
    Cloneable, Iterable<Boolean>, Collection<Boolean>, List<Boolean>, RandomAccess
    public final class BitArray
extends AbstractList<Boolean>
implements RandomAccess, Cloneable

    Random access List<Boolean> that uses a long primitive array to store its elements. Each element occupies a single bit in its corresponding long

    This class is superior to ArrayList in terms of CRUD performance and memory usage. Its limitation is its inability to store null values.

    Read only operations such as get(int) and iterator traversals run at about the same time. Add and remove at the tail also have similar performance. The most significant gains come from element copy and move operations. This includes random index add and remove, array resizes etc. You can find my benchmarks and their results from my machine here

    This class is NOT synchronized. For a synchronized version, use Collections.SynchronizedList


    Caveats

    No nulls. As mentioned above, the array will not accept null values, and throw a NullPointerException instead.

    Whole list copies. Note that methods which return a copy of the elements will probably not follow the one bit per entry principle. SubList and SynchronizedList are safe to use of course.

    Version:
    2.0.0

    • Field Detail

      • DEFAULT_CAPACITY

        public static final int DEFAULT_CAPACITY
        Default array capacity in bit entries
        See Also:
        Constant Field Values

    • Constructor Detail

      • BitArray

        public BitArray()
        Default constructor; sets initial capacity to DEFAULT_CAPACITY

      • BitArray

        public BitArray​(int initialCapacity)
        Initialises the array to store at least initialCapacity elements before resizing.

        Actual memory size of the array in bits is rounded up to the next multiple of BITS_PER_LONG.

        Parameters:
        initialCapacity - initial capacity of the array in bit entries

      • BitArray

        public BitArray​(Collection<? extends Boolean> other)
        Builds the array from the specified collection in the order specified by its iterator
        Parameters:
        other - the collection supplying the elements
        Throws:
        NullPointerException - if the collection is null

    • Method Detail

      • add

        public void add​(int index,
                Boolean bit)
        Inserts the boolean value at the argument index.
        Specified by:
        add in interface List<Boolean>
        Overrides:
        add in class AbstractList<Boolean>
        Parameters:
        index - array index to insert the element in
        bit - the boolean value to be inserted
        Throws:
        IndexOutOfBoundsException - if index is out of array insertion bounds
        IllegalStateException - if array size is Integer.MAX_VALUE at the time of insertion

      • add

        public boolean add​(Boolean bit)
        Inserts the boolean value at the tail of the array.
        Specified by:
        add in interface Collection<Boolean>
        Specified by:
        add in interface List<Boolean>
        Overrides:
        add in class AbstractList<Boolean>
        Parameters:
        bit - the boolean value to be inserted
        Returns:
        success / failure of the add operation
        Throws:
        IllegalStateException - if array size is Integer.MAX_VALUE at the time of insertion

      • get

        public Boolean get​(int index)
        Returns the boolean value of the bit at the selected array index.
        Specified by:
        get in interface List<Boolean>
        Specified by:
        get in class AbstractList<Boolean>
        Parameters:
        index - index of the element in the array
        Returns:
        boolean value of the bit entry
        Throws:
        IndexOutOfBoundsException - if index is out of array bounds

      • set

        public Boolean set​(int index,
                   Boolean bit)
        Sets the value of the element at the specified index to the desired value and returns the old value.
        Specified by:
        set in interface List<Boolean>
        Overrides:
        set in class AbstractList<Boolean>
        Parameters:
        index - index of the array element to be changed
        bit - the new value of the array element
        Returns:
        boolean value of the previous bit at that index
        Throws:
        IndexOutOfBoundsException - if index is out of array bounds

      • countOnes

        public int countOnes()
        Counts the number of true elements in the array
        Returns:
        number of true elements in the array

      • countZeros

        public int countZeros()
        Counts the number of false elements in the array
        Returns:
        number of false elements in the array

      • indexOfNeedle

        public int indexOfNeedle​(boolean needle)
        Finds the index of the first occurrence of needle by skipping multiple occurrences of !needle

        This method should be used when needle is indeed a needle in a haystack of !needle elements. In other cases, it will most likely run slower than indexOf. It skips ahead of multiples of 64, starting at element 0. Meaning it will skip 0-63, 64-127 etc, using a single long comparison for each.

        Parameters:
        needle - the boolean element
        Returns:
        index of the first occurrence of needle or -1 if not found

      • clone

        @Contract(" -> new")
public BitArray clone()
        Returns a deep copy of this object
        Returns:
        deep copy of this

      • toString

        public String toString()
        Serializes the array into a string.

        The string consists of the number of elements in the array and a list of the elements in a human readable format. Exact representation is "Size = SIZE, [(((0 | 1) + ' ')* (0 | 1))?]" where SIZE is a non negative integer and '+' is the concatenation operator. The list of elements consists of opening square brackets ([), zero or more bits (single digit ones or zeros) separated by spaces and closing square brackets.

        Examples:
        Size = 7, [1 1 1 0 1 1 1]
        Size = 4, [0 0 0 0]
        Size = 0, []

        Overrides:
        toString in class AbstractCollection<Boolean>
        Returns:
        String representation of the array and its elements

      • fromString

        public static BitArray fromString​(String stringArray)
        Constructs the BitArray from the serialized String representation given
        Parameters:
        stringArray - array in String format as returned by toString()
        Returns:
        new BitArray instance with the String array's contents
        Throws:
        UnknownFormatConversionException - if string parsing fails