Package org.apache.druid.extendedset.intset

Class ConciseSetUtils

java.lang.Object
org.apache.druid.extendedset.intset.ConciseSetUtils
public class ConciseSetUtils extends Object

  • Field Details

    • MAX_ALLOWED_INTEGER

      public static final int MAX_ALLOWED_INTEGER
      The highest representable integer.

      Its value is computed as follows. The number of bits required to represent the longest sequence of 0's or 1's is ceil(log2((Integer.MAX_VALUE - 31) / 31)) = 27. Indeed, at least one literal exists, and the other bits may all be 0's or 1's, that is Integer.MAX_VALUE - 31. If we use:

      • 2 bits for the sequence type;
      • 5 bits to indicate which bit is set;
      then 32 - 5 - 2 = 25 is the number of available bits to represent the maximum sequence of 0's and 1's. Thus, the maximal bit that can be set is represented by a number of 0's equals to 31 * (1 << 25), followed by a literal with 30 0's and the MSB (31st bit) equal to 1
      See Also:

    • MIN_ALLOWED_SET_BIT

      public static final int MIN_ALLOWED_SET_BIT
      The lowest representable integer.
      See Also:

    • MAX_LITERAL_LENGTH

      public static final int MAX_LITERAL_LENGTH
      Maximum number of representable bits within a literal
      See Also:

    • ALL_ONES_LITERAL

      public static final int ALL_ONES_LITERAL
      Literal that represents all bits set to 1 (and MSB = 1)
      See Also:

    • ALL_ZEROS_LITERAL

      public static final int ALL_ZEROS_LITERAL
      Literal that represents all bits set to 0 (and MSB = 1)
      See Also:

    • ALL_ONES_WITHOUT_MSB

      public static final int ALL_ONES_WITHOUT_MSB
      All bits set to 1 and MSB = 0
      See Also:

    • SEQUENCE_BIT

      public static final int SEQUENCE_BIT
      Sequence bit
      See Also:

  • Constructor Details

    • ConciseSetUtils

      public ConciseSetUtils()

  • Method Details

    • maxLiteralLengthModulus

      public static int maxLiteralLengthModulus(int n)
      Calculates the modulus division by 31 in a faster way than using n % 31

      This method of finding modulus division by an integer that is one less than a power of 2 takes at most O(lg(32)) time. The number of operations is at most 12 + 9 * ceil(lg(32)).

      See http://graphics.stanford.edu/~seander/bithacks.html

      Parameters:
      n - number to divide
      Returns:
      n % 31

    • maxLiteralLengthMultiplication

      public static int maxLiteralLengthMultiplication(int n)
      Calculates the multiplication by 31 in a faster way than using n * 31
      Parameters:
      n - number to multiply
      Returns:
      n * 31

    • maxLiteralLengthDivision

      public static int maxLiteralLengthDivision(int n)
      Calculates the division by 31
      Parameters:
      n - number to divide
      Returns:
      n / 31

    • isLiteral

      public static boolean isLiteral(int word)
      Checks whether a word is a literal one
      Parameters:
      word - word to check
      Returns:
      true if the given word is a literal word

    • isOneSequence

      public static boolean isOneSequence(int word)
      Checks whether a word contains a sequence of 1's
      Parameters:
      word - word to check
      Returns:
      true if the given word is a sequence of 1's

    • isZeroSequence

      public static boolean isZeroSequence(int word)
      Checks whether a word contains a sequence of 0's
      Parameters:
      word - word to check
      Returns:
      true if the given word is a sequence of 0's

    • isSequenceWithNoBits

      public static boolean isSequenceWithNoBits(int word)
      Checks whether a word contains a sequence of 0's with no set bit, or 1's with no unset bit.
      Parameters:
      word - word to check
      Returns:
      true if the given word is a sequence of 0's or 1's but with no (un)set bit

    • getSequenceCount

      public static int getSequenceCount(int word)
      Gets the number of blocks of 1's or 0's stored in a sequence word
      Parameters:
      word - word to check
      Returns:
      the number of blocks that follow the first block of 31 bits

    • getSequenceNumWords

      public static int getSequenceNumWords(int word)

    • getLiteral

      public static int getLiteral(int word, boolean simulateWAH)
      Gets the literal word that represents the first 31 bits of the given the word (i.e. the first block of a sequence word, or the bits of a literal word).

      If the word is a literal, it returns the unmodified word. In case of a sequence, it returns a literal that represents the first 31 bits of the given sequence word.

      Parameters:
      word - word to check
      Returns:
      the literal contained within the given word, with the most significant bit set to 1.

    • getLiteralFromZeroSeqFlipBit

      public static int getLiteralFromZeroSeqFlipBit(int word)

    • getLiteralFromOneSeqFlipBit

      public static int getLiteralFromOneSeqFlipBit(int word)

    • getFlippedBit

      public static int getFlippedBit(int word)
      Gets the position of the flipped bit within a sequence word. If the sequence has no set/unset bit, returns -1.

      Note that the parameter must a sequence word, otherwise the result is meaningless.

      Parameters:
      word - sequence word to check
      Returns:
      the position of the set bit, from 0 to 31. If the sequence has no set/unset bit, returns -1.

    • flipBitAsBinaryString

      public static int flipBitAsBinaryString(int flipBit)

    • getLiteralBitCount

      public static int getLiteralBitCount(int word)
      Gets the number of set bits within the literal word
      Parameters:
      word - literal word
      Returns:
      the number of set bits within the literal word

    • getLiteralBits

      public static int getLiteralBits(int word)
      Gets the bits contained within the literal word
      Parameters:
      word - literal word
      Returns:
      the literal word with the most significant bit cleared

    • isAllOnesLiteral

      public static boolean isAllOnesLiteral(int word)

    • isAllZerosLiteral

      public static boolean isAllZerosLiteral(int word)

    • isLiteralWithSingleZeroBit

      public static boolean isLiteralWithSingleZeroBit(int word)

    • isLiteralWithSingleOneBit

      public static boolean isLiteralWithSingleOneBit(int word)

    • clearBitsAfterInLastWord

      public static int clearBitsAfterInLastWord(int lastWord, int lastSetBit)

    • onesUntil

      public static int onesUntil(int bit)