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 Summary

int	n Number of elements used to generate intervals.

Fields inherited from interface it.unimi.dsi.lama4j.Lattice

RING, UTF8

Constructor Summary

IntervalAntichains(int n)

Method Summary

boolean	comp(Element x, Element y) Returns whether the two provided elements are comparable.
Set<Element>	generators() Returns a set of generators for the lattice.
Element	join(Element... element) Returns the join of the provided elements.
boolean	leq(Element x, Element y) Returns whether an element is less than or equal to another element in the natural order of this lattice.
Element	meet(Element... element) Returns the meet of the provided elements.
Element	minus(Element x, Element y) Returns an antichain equal to the first element from which all intervals containing some interval of the second element have been eliminated.
Element	one() Returns the one of this lattice.
Element	valueOf(String name) Parses an antichain, returning the corresponding element.
Element	zero() Returns the zero of this lattice.

Methods inherited from class it.unimi.dsi.lama4j.AbstractDistributiveLattice

isDistributive

Methods inherited from class it.unimi.dsi.lama4j.AbstractLattice

coveringRelation, elements, ensureElementsInLattice, ensureElementsInLattice, ensureElementsInLattice, pscomp, valueOfZeroOrOne

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

n

public final int n

Number of elements used to generate intervals.

Constructor Detail

IntervalAntichains

public IntervalAntichains(int n)

Method Detail

meet

public Element meet(Element... element)

Description copied from interface: Lattice

Returns 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 Element join(Element... element)

Description copied from interface: Lattice

Returns 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 Set<Element> generators()

Description copied from interface: Lattice

Returns a set of generators for the lattice. The set will not include zero or one. There is no guarantee of freeness or minimality.

Returns:

a set of generators.

valueOf

public Element valueOf(String name)

Parses 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 Element zero()

Description copied from interface: Lattice

Returns the zero of this lattice.

Note that there is no guarantee that the returned element is the only element representing zero in this lattice. Other zeroes may arise from computations, but they will always be equal to the element returned by this method.

Returns:

the zero of this lattice.

one

public Element one()

Description copied from interface: Lattice

Returns the one of this lattice.

Note that there is no guarantee that the returned element is the only element representing one in this lattice. Other ones may arise from computations, but they will always be equal to the element returned by this method.

Returns:

the one of this lattice.

comp

public boolean comp(Element x,
                    Element y)

Returns 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)

Returns 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.

minus

public Element minus(Element x,
                     Element y)

Returns 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:

minus in interface Lattice

Overrides:

minus 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.minus(Element, Element)