Package it.unimi.dsi.lama4j

Class IntervalAntichains

java.lang.Object
it.unimi.dsi.lama4j.AbstractLattice
it.unimi.dsi.lama4j.AbstractDistributiveLattice
it.unimi.dsi.lama4j.IntervalAntichains
All Implemented Interfaces:
Lattice
public class IntervalAntichains
extends AbstractDistributiveLattice
The distributive lattice of antichains of intervals of a linear finite order. It is isomorphic to the order-ideal completion of intervals ordered by reverse inclusion, the isomorphism being given by taking the union of all principal ideals generated by the elements of an antichain.

Given an integer n, this class represents the lattice of interval antichains of the linear order { 0, 1, …, n − 1 }.

This lattice plays a prominent rôle in “An algebra for structured text search and a framework for its implementation”, by Charles L.A. Clarke, Gordon V. Cormack, and Forbes J. Burkowski, Comput. J., 38(1):43−56, 1995, where it is used to denote regions of text satisfying a query (albeit the authors do not remark that their lattice is actually an order-ideal completion). The algorithms used in this implementation are described in “Efficient lazy algorithms for minimal-interval semantics”, by Paolo Boldi and Sebastiano Vigna, Proc. SPIRE 2006, number 4209 in Lecture Notes in Computer Science, pages 134−149. Springer–Verlag, 2006, where a more mathematically oriented description of the lattice can be found.

  • Field Details

    • n

      public final int n
      Number of elements used to generate intervals.

  • Constructor Details

  • Method Details

    • meet

      public IntervalAntichains.Antichain meet​(Element... element)
      Description copied from interface: Lattice
      Return the meet of the provided elements. In particular, upon the empty list of arguments returns one, and upon a singleton list the only specified element.
      Parameters:
      element - the elements whose meet has to be computed.
      Returns:
      the meet of the provided elements.

    • join

      public IntervalAntichains.Antichain join​(Element... element)
      Description copied from interface: Lattice
      Return the join of the provided elements. In particular, upon the empty list of arguments returns zero, and upon a singleton list the only specified element.
      Parameters:
      element - the elements whose join has to be computed.
      Returns:
      the join of the provided elements.

    • generators

      public Collection<Element> generators()
      Description copied from interface: Lattice
      Return a collection of generators for the lattice. The set will not include zero or one. There is no guarantee of freeness or minimality.
      Returns:
      a collection of generators.

    • valueOf

      public IntervalAntichains.Antichain valueOf​(String name)
      Parse an antichain, returning the corresponding element.

      An interval is described (using Hoare's notation) by a pair of integers, separated by two dots and surrounded by square brackets. Thus, [1..3] denotes the interval containing the integers 1, 2, and 3. The shortcut [x] can be used to denote the singleton interval containing x.

      An interval antichain is described by a list of intervals separated by commas. Of course, no interval in the list must contain another interval. Intervals can be in any order. For instance, [1..3], [2..4], [0] is a legal antichain.

      Spaces are not significative, but the two dots in an interval must be consecutive.

      Parameters:
      name - the description of an antichain.
      Returns:
      the corresponding element of this lattice.

    • zero

      public IntervalAntichains.Antichain zero()
      Return a singleton representing the zero of this lattice (the empty antichain).

      The element returned by this method is a singleton: it has a single instance. All lattice scomputation methods will return this object when they have to return zero. As a consequence, it is possible to test for zero using == instead of equals().

      Returns:
      a singleton representing the zero of this lattice (the empty antichain).

    • one

      public IntervalAntichains.Antichain one()
      Return a singleton representing the zero of this lattice (the antichain formed by the empty interval).

      The element returned by this method is a singleton: it has a single instance. All lattice computation methods will return this object when they have to return one. As a consequence, it is possible to test for one using == instead of equals().

      Returns:
      a singleton representing the zero of this lattice (the antichain formed by the empty interval).

    • comp

      public boolean comp​(Element x, Element y)
      Return whether the two provided elements are comparable.
      Specified by:
      comp in interface Lattice
      Overrides:
      comp in class AbstractLattice
      Parameters:
      x - an element.
      y - another element.
      Returns:
      true if x ≤ y or y ≤ x, false otherwise.

    • leq

      public boolean leq​(Element x, Element y)
      Return whether an element is less than or equal to another element in the natural order of this lattice.

      This implementation is based on a simple linear greedy algorithm that uses an explicit definition (an antichain A is smaller than or equal to an antichain B iff for every interval in A there is a corresponding smaller interval in B).

      Specified by:
      leq in interface Lattice
      Overrides:
      leq in class AbstractLattice
      Parameters:
      x - an element.
      y - another element.
      Returns:
      true iff x ≤ y.

    • psdiff

      public IntervalAntichains.Antichain psdiff​(Element x, Element y)
      Return an antichain equal to the first element from which all intervals containing some interval of the second element have been eliminated.

      In the case of this lattice, the difference assumes the simple form above, and it can be easily computed with a linear greedy algorithm.

      Specified by:
      psdiff in interface Lattice
      Overrides:
      psdiff in class AbstractLattice
      Parameters:
      x - an element.
      y - another element.
      Returns:
      an antichain equal to x with intervals containing some interval of y removed.
      See Also:
      Lattice.psdiff(Element, Element)

    • pscomp

      public IntervalAntichains.Antichain pscomp​(Element x, Element y)
      Description copied from class: AbstractLattice
      Enumerate all elements of this lattice to compute explicitly the pseudocomplement using the definition given in Lattice.pscomp(Element, Element). It is expected that concrete subclasses will override this method with an ad hoc, more efficient implementation.
      Specified by:
      pscomp in interface Lattice
      Overrides:
      pscomp in class AbstractLattice
      Parameters:
      x - an element.
      y - another element.
      Returns:
      x ⇒ y.
      See Also:
      Lattice.pscomp(Element, Element)

    • symdiff

      public IntervalAntichains.Antichain symdiff​(Element x, Element y)
      Description copied from class: AbstractLattice
      Return the symmetric difference of the arguments, that is, psdiff(x,y).join(psdiff(y,x)).
      Specified by:
      symdiff in interface Lattice
      Overrides:
      symdiff in class AbstractLattice
      Parameters:
      x - an element.
      y - another element.
      Returns:
      x Δ y.
      See Also:
      Element.join(Element), Lattice.psdiff(Element, Element)

    • elements

      public Collection<Element> elements()
      Generate iteratively all elements of this lattice.

      This methods uses the CAT enumeration algorithm for interval antichains by Boldi and Vigna.

      Specified by:
      elements in interface Lattice
      Overrides:
      elements in class AbstractLattice
      Returns:
      the set of elements of this lattice.