it.unimi.dsi.sux4j.bits
Interface BalancedParentheses

All Superinterfaces:
Serializable
All Known Implementing Classes:
JacobsonBalancedParentheses, TrivialBalancedParentheses

public interface BalancedParentheses
extends Serializable

A data structure providing primitives for balanced parentheses represented in a bit array.

A bit array of viewed by implementations of this class as a string of open (=one) and closed (=zero) parentheses, which must be nested correctly. All operations are optional, but by contract at least one of findOpen(long) and findClose(long) must be provided.


Method Summary
 BitVector bitVector()
          Returns the bit vector indexed by this structure.
 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).
 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.
 

Method Detail

findOpen

long findOpen(long pos)
Returns the position of the matching open parenthesis (optional operation).

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

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

findClose

long findClose(long pos)
Returns the position of the matching closed parenthesis (optional operation).

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

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

enclose

long enclose(long pos)
Returns the position of the open parenthesis of the pair the most tightly encloses the given position (optional operation).

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.

bitVector

BitVector bitVector()
Returns the bit vector indexed by this structure.

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

Returns:
the bit vector indexed by this structure.

numBits

long numBits()
Returns the overall number of bits allocated by this structure.

Returns:
the overall number of bits allocated by this structure (not including the bits of the indexed vector).