Package 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

Fields

Modifier and Type	Field	Description
protected final BitVector	bitVector
static final long	MSBS_STEP_4
static final long	MSBS_STEP_8
static final long	ONES_STEP_4
static final long	ONES_STEP_8

Constructor Summary

Constructors

Constructor	Description
JacobsonBalancedParentheses(long[] bits, long length)
JacobsonBalancedParentheses(BitVector bv)
JacobsonBalancedParentheses(BitVector bitVector, boolean findOpen, boolean findClose, boolean enclose)

Method Summary

Modifier and Type	Method	Description
static String	binary(long l, boolean reverse)
BitVector	bitVector()	Returns the bit vector indexed by this structure.
static final int	countFarClose(long word, int l)
static final 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 final int	findFarClose(long word, int k)
static final int	findFarClose2(long word, int k)
static final int	findFarOpen(long word, int l, int k)
static final int	findNearClose(long word)
static final int	findNearClose2(long word)
static final 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 Details

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 Details

JacobsonBalancedParentheses

public JacobsonBalancedParentheses(BitVector bv)

JacobsonBalancedParentheses

public JacobsonBalancedParentheses(long[] bits,
 long length)

JacobsonBalancedParentheses

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

Method Details

binary

public static String binary(long l,
 boolean reverse)

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.