Package it.unimi.dsi.sux4j.bits

Interface BalancedParentheses

All Superinterfaces:
Serializable
All Known Implementing Classes:
JacobsonBalancedParentheses
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

    Modifier and Type
    Method
    Description
    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 Details

    • 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).