it.unimi.dsi.sux4j.bits
Class JacobsonBalancedParentheses

java.lang.Object
  extended by it.unimi.dsi.sux4j.bits.JacobsonBalancedParentheses
All Implemented Interfaces:
BalancedParentheses, Serializable

public class JacobsonBalancedParentheses
extends Object
implements BalancedParentheses

An implementation of Jacobson's balanced parentheses data structure. Warning: this class is a stub implementing just those method needed by a HollowTrieMonotoneMinimalPerfectHashFunction.

Author:
Sebastiano Vigna
See Also:
Serialized Form

Field Summary
protected  BitVector bitVector
           
static long MSBS_STEP_4
           
static long MSBS_STEP_8
           
static long ONES_STEP_4
           
static long ONES_STEP_8
           
 
Constructor Summary
JacobsonBalancedParentheses(BitVector bv)
           
JacobsonBalancedParentheses(BitVector bitVector, boolean findOpen, boolean findClose, boolean enclose)
           
JacobsonBalancedParentheses(long[] bits, long length)
           
 
Method Summary
 BitVector bitVector()
          Returns the bit vector indexed by this structure.
static int countFarClose(long word, int l)
           
static int countFarOpen(long word, int l)
           
 long enclose(long pos)
          Returns the position of the open parenthesis of the pair the most tightly encloses the given position (optional operation).
 long findClose(long pos)
          Returns the position of the matching closed parenthesis (optional operation).
static int findFarClose(long word, int k)
           
static int findFarClose2(long word, int k)
           
static int findFarOpen(long word, int l, int k)
           
static int findNearClose(long word)
           
static int findNearClose2(long word)
           
static int findNearCloseAlt(long word)
           
 long findOpen(long pos)
          Returns the position of the matching open parenthesis (optional operation).
 long numBits()
          Returns the overall number of bits allocated by this structure.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

bitVector

protected final BitVector bitVector

ONES_STEP_4

public static final long ONES_STEP_4
See Also:
Constant Field Values

MSBS_STEP_4

public static final long MSBS_STEP_4
See Also:
Constant Field Values

ONES_STEP_8

public static final long ONES_STEP_8
See Also:
Constant Field Values

MSBS_STEP_8

public static final long MSBS_STEP_8
See Also:
Constant Field Values
Constructor Detail

JacobsonBalancedParentheses

public JacobsonBalancedParentheses(BitVector bv)

JacobsonBalancedParentheses

public JacobsonBalancedParentheses(long[] bits,
                                   long length)

JacobsonBalancedParentheses

public JacobsonBalancedParentheses(BitVector bitVector,
                                   boolean findOpen,
                                   boolean findClose,
                                   boolean enclose)
Method Detail

countFarOpen

public static final int countFarOpen(long word,
                                     int l)

findFarOpen

public static final int findFarOpen(long word,
                                    int l,
                                    int k)

countFarClose

public static final int countFarClose(long word,
                                      int l)

findFarClose2

public static final int findFarClose2(long word,
                                      int k)

findFarClose

public static final int findFarClose(long word,
                                     int k)

findNearClose2

public static final int findNearClose2(long word)

findNearClose

public static final int findNearClose(long word)

findNearCloseAlt

public static final int findNearCloseAlt(long word)

enclose

public long enclose(long pos)
Description copied from interface: BalancedParentheses
Returns the position of the open parenthesis of the pair the most tightly encloses the given position (optional operation).

Specified by:
enclose in interface BalancedParentheses
Parameters:
pos - a position in the bit vector.
Returns:
the position of the open parenthesis of the pair the most tightly encloses the given position.

findClose

public long findClose(long pos)
Description copied from interface: BalancedParentheses
Returns the position of the matching closed parenthesis (optional operation).

Note that if you do not implement this method you must implement BalancedParentheses.findOpen(long).

Specified by:
findClose in interface BalancedParentheses
Parameters:
pos - a position in the bit vector containing an open parenthesis (a one).
Returns:
the position of the matching open parenthesis.

findOpen

public long findOpen(long pos)
Description copied from interface: BalancedParentheses
Returns the position of the matching open parenthesis (optional operation).

Note that if you do not implement this method you must implement BalancedParentheses.findClose(long).

Specified by:
findOpen in interface BalancedParentheses
Parameters:
pos - a position in the bit vector containing a closed parenthesis (a zero).
Returns:
the position of the matching open parenthesis.

numBits

public long numBits()
Description copied from interface: BalancedParentheses
Returns the overall number of bits allocated by this structure.

Specified by:
numBits in interface BalancedParentheses
Returns:
the overall number of bits allocated by this structure (not including the bits of the indexed vector).

bitVector

public BitVector bitVector()
Description copied from interface: BalancedParentheses
Returns the bit vector indexed by this structure.

Note that you are not supposed to modify the returned vector.

Specified by:
bitVector in interface BalancedParentheses
Returns:
the bit vector indexed by this structure.