Package org.wikidata.wdtk.storage.datastructures

Class RankedBitVectorImpl

java.lang.Object
org.wikidata.wdtk.storage.datastructures.RankedBitVectorImpl
All Implemented Interfaces:
Iterable<Boolean>, BitVector, RankedBitVector
public class RankedBitVectorImpl extends Object implements RankedBitVector, Iterable<Boolean>
Default implementation of RankedBitVector. This implementation uses auxiliary classes to have efficient performance for the methods of a ranked bit vector. Hence, countBits(boolean, long) uses an instance of CountBitsArray and findPosition(boolean, long) uses two instances of FindPositionArray.
Author:
Julian Mendez
See Also:
  • CountBitsArray
  • FindPositionArray

  • Field Summary

    Fields inherited from interface org.wikidata.wdtk.storage.datastructures.RankedBitVector

    NOT_FOUND

  • Constructor Summary

    Constructors
    Constructor
    Description
    RankedBitVectorImpl()
    Constructor of a ranked bit vector of size 0.
    RankedBitVectorImpl(long initialSize)
    Constructor of a ranked bit vector of size initialSize.
    RankedBitVectorImpl(long initialSize, int countBlockSize, int findPositionBlockSize)
    Constructor of a ranked bit vector of size initialSize and block size blockSize.
    RankedBitVectorImpl(BitVector bitVector)
    Copy constructor of a ranked bit vector.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    addBit(boolean bit)
    Appends a bit to this bit vector.
    long
    countBits(boolean bit, long position)
    This is the "rank" method of bit vectors.
    boolean
    equals(Object obj)
    Returns true if and only if the specified object is also a BitVector and both contain the same bits in the same order.
    long
    findPosition(boolean bit, long nOccurrence)
    This is the "select" method of bit vectors.
    boolean
    getBit(long position)
    This is the "access" method of bit vectors.
    int
    hashCode()
     
    Iterator<Boolean>
    iterator()
     
    void
    setBit(long position, boolean bit)
    Sets a bit at a particular position.
    long
    size()
     
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • RankedBitVectorImpl

      public RankedBitVectorImpl()
      Constructor of a ranked bit vector of size 0.

    • RankedBitVectorImpl

      public RankedBitVectorImpl(BitVector bitVector)
      Copy constructor of a ranked bit vector.
      Parameters:
      bitVector - bit vector

    • RankedBitVectorImpl

      public RankedBitVectorImpl(long initialSize)
      Constructor of a ranked bit vector of size initialSize. The bit vector contains false at all indexes.
      Parameters:
      initialSize - initial size of this ranked bit vector

    • RankedBitVectorImpl

      public RankedBitVectorImpl(long initialSize, int countBlockSize, int findPositionBlockSize)
      Constructor of a ranked bit vector of size initialSize and block size blockSize. The bit vector contains false at all indexes.
      Parameters:
      initialSize - initial size of this ranked bit vector
      countBlockSize - block size to count number of occurrences of a value; this value must be a positive number
      findPositionBlockSize - block size to find the position of the n-th occurrence of a value; this value must be greater than or equal to 64
      Throws:
      IllegalArgumentException - if any of the block sizes is too small

  • Method Details

    • addBit

      public boolean addBit(boolean bit)
      Description copied from interface: BitVector
      Appends a bit to this bit vector.
      Specified by:
      addBit in interface BitVector
      Returns:
      true if the element was successfully added

    • countBits

      public long countBits(boolean bit, long position)
      Description copied from interface: RankedBitVector
      This is the "rank" method of bit vectors. This method returns the number of occurrences of bit up to position.
      Specified by:
      countBits in interface RankedBitVector
      Parameters:
      bit - bit
      position - position
      Returns:
      number of occurrences of bit at position

    • equals

      public boolean equals(Object obj)
      Description copied from interface: BitVector
      Returns true if and only if the specified object is also a BitVector and both contain the same bits in the same order.
      Specified by:
      equals in interface BitVector
      Overrides:
      equals in class Object
      Parameters:
      obj - the object to be compared with this BitVector
      Returns:
      true if and only if the specified object is also a BitVector and both contain the same bits in the same order

    • findPosition

      public long findPosition(boolean bit, long nOccurrence)
      Description copied from interface: RankedBitVector
      This is the "select" method of bit vectors. This method returns the position of the n-th occurrence (nOccurrence) of bit or NOT_FOUND if there are not enough occurrences.
      Specified by:
      findPosition in interface RankedBitVector
      Parameters:
      bit - bit
      nOccurrence - number of occurrences
      Returns:
      position of the n-th occurrence (nOccurrence) of bit or NOT_FOUND if there are not enough occurrences

    • getBit

      public boolean getBit(long position)
      Description copied from interface: BitVector
      This is the "access" method of bit vectors.
      Specified by:
      getBit in interface BitVector
      Returns:
      value of a bit at position

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • iterator

      public Iterator<Boolean> iterator()
      Specified by:
      iterator in interface BitVector
      Specified by:
      iterator in interface Iterable<Boolean>
      Returns:
      an iterator for this bit vector

    • setBit

      public void setBit(long position, boolean bit)
      Description copied from interface: BitVector
      Sets a bit at a particular position.
      Specified by:
      setBit in interface BitVector
      Parameters:
      position - position
      bit - bit

    • size

      public long size()
      Specified by:
      size in interface BitVector
      Returns:
      size of this bit vector

    • toString

      public String toString()
      Overrides:
      toString in class Object