public class IntervalAntichains extends AbstractDistributiveLattice
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.
| Modifier and Type | Class and Description |
|---|---|
static class |
IntervalAntichains.Antichain
A class representing elements of this lattice (antichains of intervals).
|
| Modifier and Type | Field and Description |
|---|---|
int |
n
Number of elements used to generate intervals.
|
| Constructor and Description |
|---|
IntervalAntichains(int n) |
| Modifier and Type | Method and Description |
|---|---|
boolean |
comp(Element x,
Element y)
Return whether the two provided elements are comparable.
|
Collection<Element> |
elements()
Generate iteratively all elements of this lattice.
|
Collection<Element> |
generators()
Return a collection of generators for the lattice.
|
IntervalAntichains.Antichain |
join(Element... element)
Return the join of the provided elements.
|
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.
|
IntervalAntichains.Antichain |
meet(Element... element)
Return the meet of the provided elements.
|
IntervalAntichains.Antichain |
one()
Return a singleton representing the zero of this lattice (the antichain formed by the empty interval).
|
IntervalAntichains.Antichain |
pscomp(Element x,
Element y)
Enumerate all elements of this lattice to compute explicitly the
pseudocomplement using the definition given in
Lattice.pscomp(Element, Element). |
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.
|
IntervalAntichains.Antichain |
symdiff(Element x,
Element y)
Return the symmetric difference of the arguments, that is,
psdiff(x,y).join(psdiff(y,x)). |
IntervalAntichains.Antichain |
valueOf(String name)
Parse an antichain, returning the corresponding element.
|
IntervalAntichains.Antichain |
zero()
Return a singleton representing the zero of this lattice (the empty antichain).
|
isDistributivecoveringRelation, ensureElementsInLattice, ensureElementsInLattice, ensureElementsInLattice, valueOfZeroOrOnepublic IntervalAntichains.Antichain meet(Element... element)
Latticeone, and upon a singleton list the only specified element.element - the elements whose meet has to be computed.public IntervalAntichains.Antichain join(Element... element)
Latticezero, and upon a singleton list the only specified element.element - the elements whose join has to be computed.public Collection<Element> generators()
Latticezero or
one. There is no guarantee of freeness or minimality.public IntervalAntichains.Antichain valueOf(String name)
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.
name - the description of an antichain.public IntervalAntichains.Antichain zero()
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().
public IntervalAntichains.Antichain one()
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().
public boolean comp(Element x, Element y)
comp in interface Latticecomp in class AbstractLatticex - an element.y - another element.public boolean leq(Element x, Element y)
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).
leq in interface Latticeleq in class AbstractLatticex - an element.y - another element.x ≤ y.public IntervalAntichains.Antichain psdiff(Element x, Element y)
In the case of this lattice, the difference assumes the simple form above, and it can be easily computed with a linear greedy algorithm.
psdiff in interface Latticepsdiff in class AbstractLatticex - an element.y - another element.x with intervals
containing some interval of y removed.Lattice.psdiff(Element, Element)public IntervalAntichains.Antichain pscomp(Element x, Element y)
AbstractLatticeLattice.pscomp(Element, Element).
It is expected that concrete subclasses will override this method
with an ad hoc, more efficient implementation.pscomp in interface Latticepscomp in class AbstractLatticex - an element.y - another element.x ⇒ y.Lattice.pscomp(Element, Element)public IntervalAntichains.Antichain symdiff(Element x, Element y)
AbstractLatticepsdiff(x,y).join(psdiff(y,x)).symdiff in interface Latticesymdiff in class AbstractLatticex - an element.y - another element.x Δ y.Element.join(Element),
Lattice.psdiff(Element, Element)public Collection<Element> elements()
This methods uses the CAT enumeration algorithm for interval antichains by Boldi and Vigna.
elements in interface Latticeelements in class AbstractLattice