ConciseSetUtils (io.druid:druid 0.10.0 API)

java.lang.Object
- io.druid.extendedset.intset.ConciseSetUtils

public class ConciseSetUtils
extends Object

Field Summary

Fields
Modifier and Type	Field and Description
`static int`	`ALL_ONES_LITERAL` Literal that represents all bits set to 1 (and MSB = 1)
`static int`	`ALL_ONES_WITHOUT_MSB` All bits set to 1 and MSB = 0
`static int`	`ALL_ZEROS_LITERAL` Literal that represents all bits set to 0 (and MSB = 1)
`static int`	`MAX_ALLOWED_INTEGER` The highest representable integer.
`static int`	`MAX_LITERAL_LENGTH` Maximum number of representable bits within a literal
`static int`	`MIN_ALLOWED_SET_BIT` The lowest representable integer.
`static int`	`SEQUENCE_BIT` Sequence bit

Constructor Summary

Constructors
Constructor and Description

ConciseSetUtils()

Constructors
Constructor and Description
`ConciseSetUtils()`

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method and Description
`static int`	`clearBitsAfterInLastWord(int lastWord, int lastSetBit)`
`static int`	`flipBitAsBinaryString(int flipBit)`
`static int`	`getFlippedBit(int word)` Gets the position of the flipped bit within a sequence word.
`static int`	`getLiteral(int word, boolean simulateWAH)` Gets the literal word that represents the first 31 bits of the given the word (i.e.
`static int`	`getLiteralBitCount(int word)` Gets the number of set bits within the literal word
`static int`	`getLiteralBits(int word)` Gets the bits contained within the literal word
`static int`	`getLiteralFromOneSeqFlipBit(int word)`
`static int`	`getLiteralFromZeroSeqFlipBit(int word)`
`static int`	`getSequenceCount(int word)` Gets the number of blocks of 1's or 0's stored in a sequence word
`static int`	`getSequenceNumWords(int word)`
`static int`	`getSequenceWithNoBits(int word)` Clears the (un)set bit in a sequence
`static boolean`	`isAllOnesLiteral(int word)`
`static boolean`	`isAllZerosLiteral(int word)`
`static boolean`	`isLiteral(int word)` Checks whether a word is a literal one
`static boolean`	`isLiteralWithSingleOneBit(int word)`
`static boolean`	`isLiteralWithSingleZeroBit(int word)`
`static boolean`	`isOneSequence(int word)` Checks whether a word contains a sequence of 1's
`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.
`static boolean`	`isZeroSequence(int word)` Checks whether a word contains a sequence of 0's
`static int`	`maxLiteralLengthDivision(int n)` Calculates the division by 31
`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.
`static int`	`maxLiteralLengthMultiplication(int n)` Calculates the multiplication by 31 in a faster way than using `n * 31`
`static int`	`onesUntil(int bit)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - 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(log₂((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 (31^st bit) equal to 1
    See Also:
    
    Constant Field Values
  - MIN_ALLOWED_SET_BIT
```
public static final int MIN_ALLOWED_SET_BIT
```
    The lowest representable integer.
    
    See Also:
    
    Constant Field Values
  - MAX_LITERAL_LENGTH
```
public static final int MAX_LITERAL_LENGTH
```
    Maximum number of representable bits within a literal
    
    See Also:
    
    Constant Field Values
  - ALL_ONES_LITERAL
```
public static final int ALL_ONES_LITERAL
```
    Literal that represents all bits set to 1 (and MSB = 1)
    
    See Also:
    
    Constant Field Values
  - ALL_ZEROS_LITERAL
```
public static final int ALL_ZEROS_LITERAL
```
    Literal that represents all bits set to 0 (and MSB = 1)
    
    See Also:
    
    Constant Field Values
  - ALL_ONES_WITHOUT_MSB
```
public static final int ALL_ONES_WITHOUT_MSB
```
    All bits set to 1 and MSB = 0
    
    See Also:
    
    Constant Field Values
  - SEQUENCE_BIT
```
public static final int SEQUENCE_BIT
```
    Sequence bit
    
    See Also:
    
    Constant Field Values
- Constructor Detail
  - ConciseSetUtils
```
public ConciseSetUtils()
```
- Method Detail
  - 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.
    NOTE: when #simulateWAH is true, it is equivalent to (and as fast as) !isLiteral(int)
    
    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)
```
  - getSequenceWithNoBits
```
public static int getSequenceWithNoBits(int word)
```
    Clears the (un)set bit in a sequence
    
    Parameters:
    
    word - word to check
    
    Returns:
    
    the sequence corresponding to the given sequence and with no (un)set bits
  - 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)
```

Class ConciseSetUtils

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

MAX_ALLOWED_INTEGER

MIN_ALLOWED_SET_BIT

MAX_LITERAL_LENGTH

ALL_ONES_LITERAL

ALL_ZEROS_LITERAL

ALL_ONES_WITHOUT_MSB

SEQUENCE_BIT

Constructor Detail

ConciseSetUtils

Method Detail

maxLiteralLengthModulus

maxLiteralLengthMultiplication

maxLiteralLengthDivision

isLiteral

isOneSequence

isZeroSequence

isSequenceWithNoBits

getSequenceCount

getSequenceNumWords

getSequenceWithNoBits

getLiteral

getLiteralFromZeroSeqFlipBit

getLiteralFromOneSeqFlipBit

getFlippedBit

flipBitAsBinaryString

getLiteralBitCount

getLiteralBits

isAllOnesLiteral

isAllZerosLiteral

isLiteralWithSingleZeroBit

isLiteralWithSingleOneBit

clearBitsAfterInLastWord

onesUntil