it.unimi.dsi.sux4j.bits
Class JacobsonBalancedParentheses

java.lang.Object
  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.