org.apache.lucene.util
Class BroadWord

java.lang.Object
  extended by org.apache.lucene.util.BroadWord

public final class BroadWord
extends Object

Methods and constants inspired by the article "Broadword Implementation of Rank/Select Queries" by Sebastiano Vigna, January 30, 2012:

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Field Summary
static long H16_L
           
static long H8_L
          Hk = Lk << (k-1) .
static long L16_L
           
static long L8_L
          Lk denotes the constant whose ones are in position 0, k, 2k, .
static long L9_L
           
 
Method Summary
static long notEquals0_8(long x)
          An unsigned bytewise not equals 0 operator.
static int select(long x, int r)
          Select a 1-bit from a long.
static int selectNaive(long x, int r)
          Naive implementation of select(long,int), using Long.numberOfTrailingZeros(long) repetitively.
static long smalleru_8(long x, long y)
          An unsigned bytewise smaller <8 operator.
static long smallerUpto15_16(long x, long y)
          A bytewise smaller <16 operator.
static long smallerUpTo7_8(long x, long y)
          A signed bytewise smaller <8 operator, for operands 0L<= x, y <=0x7L.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

L8_L

public static final long L8_L
Lk denotes the constant whose ones are in position 0, k, 2k, . . . These contain the low bit of each group of k bits. The suffix _L indicates the long implementation.

See Also:
Constant Field Values

L9_L

public static final long L9_L
See Also:
Constant Field Values

L16_L

public static final long L16_L
See Also:
Constant Field Values

H8_L

public static final long H8_L
Hk = Lk << (k-1) . These contain the high bit of each group of k bits. The suffix _L indicates the long implementation.

See Also:
Constant Field Values

H16_L

public static final long H16_L
See Also:
Constant Field Values
Method Detail

select

public static int select(long x,
                         int r)
Select a 1-bit from a long.

Returns:
The index of the r-th 1 bit in x, or if no such bit exists, 72.

smallerUpTo7_8

public static long smallerUpTo7_8(long x,
                                  long y)
A signed bytewise smaller <8 operator, for operands 0L<= x, y <=0x7L. This uses the following numbers of basic long operations: 1 or, 2 and, 2 xor, 1 minus, 1 not.

Returns:
A long with bits set in the H8_L positions corresponding to each input signed byte pair that compares smaller.

smalleru_8

public static long smalleru_8(long x,
                              long y)
An unsigned bytewise smaller <8 operator. This uses the following numbers of basic long operations: 3 or, 2 and, 2 xor, 1 minus, 1 not.

Returns:
A long with bits set in the H8_L positions corresponding to each input unsigned byte pair that compares smaller.

notEquals0_8

public static long notEquals0_8(long x)
An unsigned bytewise not equals 0 operator. This uses the following numbers of basic long operations: 2 or, 1 and, 1 minus.

Returns:
A long with bits set in the H8_L positions corresponding to each unsigned byte that does not equal 0.

smallerUpto15_16

public static long smallerUpto15_16(long x,
                                    long y)
A bytewise smaller <16 operator. This uses the following numbers of basic long operations: 1 or, 2 and, 2 xor, 1 minus, 1 not.

Returns:
A long with bits set in the H16_L positions corresponding to each input signed short pair that compares smaller.

selectNaive

public static int selectNaive(long x,
                              int r)
Naive implementation of select(long,int), using Long.numberOfTrailingZeros(long) repetitively. Works relatively fast for low ranks.

Returns:
The index of the r-th 1 bit in x, or if no such bit exists, 72.


Copyright © 2000-2014 Apache Software Foundation. All Rights Reserved.