it.unimi.dsi.lama4j

Class AbstractLattice

java.lang.Object

it.unimi.dsi.lama4j.AbstractLattice

All Implemented Interfaces:

Lattice

Direct Known Subclasses:

AbstractDistributiveLattice, Flat, Product

public abstract class AbstractLattice
extends Object
implements Lattice

An abstract implementation of Lattice providing obvious implementations of order-related operators and an implementation of elements() based on exhaustive generation.

The additional methods ensureElementsInLattice(Element[]) and valueOfZeroOrOne(String) can be used to simplify concrete implementing subclasses.

Field Summary

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

RING, UTF8

Constructor Summary

Constructors

Constructor and Description
AbstractLattice()

Method Summary

Modifier and Type	Method and Description
boolean	comp(Element x, Element y) Check whether two elements are comparable using Lattice.meet(Element[]).
Map<Element,Set<Element>>	coveringRelation() Return the covering relation of this lattice.
Collection<Element>	elements() Generate iteratively all elements of this lattice.
protected void	ensureElementsInLattice(Element... element) Ensure that the provided elements belong to this lattice, throwing an ElementLatticeMismatchException otherwise.
protected void	ensureElementsInLattice(Element x) Ensure that the provided element belong to this lattice, throwing an ElementLatticeMismatchException otherwise.
protected void	ensureElementsInLattice(Element x, Element y) Ensure that the provided elements belong to this lattice, throwing an ElementLatticeMismatchException otherwise.
boolean	isDistributive() Return true if this lattice is distributive.
boolean	leq(Element x, Element y) Check whether an element is smaller than or equal to another element using Lattice.meet(Element[]).
Element	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).
Element	psdiff(Element x, Element y) Enumerate all elements of this lattice to compute explicitly the difference using the definition given in Lattice.psdiff(Element, Element).
Element	symdiff(Element x, Element y) Return the symmetric difference of the arguments, that is, psdiff(x,y).join(psdiff(y,x)).
protected Element	valueOfZeroOrOne(String s) A simple support method to make it easy to parse zero and one.

Methods inherited from class java.lang.Object

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

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

generators, join, meet, one, valueOf, zero

Constructor Detail

AbstractLattice

public AbstractLattice()

Method Detail

isDistributive

public boolean isDistributive()

Description copied from interface: Lattice

Return true if this lattice is distributive.

Specified by:

isDistributive in interface Lattice

Returns:

true if this lattice is distributive.

ensureElementsInLattice

protected void ensureElementsInLattice(Element x)

Ensure that the provided element belong to this lattice, throwing an ElementLatticeMismatchException otherwise.

Parameters:

x - an element.

ensureElementsInLattice

protected void ensureElementsInLattice(Element x,
                                       Element y)

Ensure that the provided elements belong to this lattice, throwing an ElementLatticeMismatchException otherwise.

Parameters:

x - an element.

y - another element.

ensureElementsInLattice

protected void ensureElementsInLattice(Element... element)

Ensure that the provided elements belong to this lattice, throwing an ElementLatticeMismatchException otherwise.

Parameters:

element - some elements.

valueOfZeroOrOne

protected Element valueOfZeroOrOne(String s)

A simple support method to make it easy to parse zero and one.

Parameters:

s - a string.

Returns:

Lattice.zero() or Lattice.one() is s is 0 or 1, respectively; null otherwise.

elements

public Collection<Element> elements()

Generate iteratively all elements of this lattice.

This methods uses Lattice.generators() to obtain an initial set of elements, and then computes joins and meets of all available elements until no new elements are generated. It is expected that concrete subclasses will override this method with an ad hoc, more efficient implementation.

It is strongly suggested that concrete subclasses that do not override this method cache its result internally.

Specified by:

elements in interface Lattice

Returns:

the set of elements of this lattice.

comp

public boolean comp(Element x,
                    Element y)

Check whether two elements are comparable using Lattice.meet(Element[]).

Specified by:

comp in interface Lattice

Parameters:

x - an element.

y - another element.

Returns:

true iff x.meet(y) equals x or y.

leq

public boolean leq(Element x,
                   Element y)

Check whether an element is smaller than or equal to another element using Lattice.meet(Element[]).

Specified by:

leq in interface Lattice

Parameters:

x - an element.

y - another element.

Returns:

true iff x.meet(y) equals x.

psdiff

public Element psdiff(Element x,
                      Element y)

Enumerate all elements of this lattice to compute explicitly the difference using the definition given in Lattice.psdiff(Element, Element). It is expected that concrete subclasses will override this method with an ad hoc, more efficient implementation.

Specified by:

psdiff in interface Lattice

Parameters:

x - an element.

y - another element.

Returns:

x − y.

See Also:

Lattice.psdiff(Element, Element)

pscomp

public Element 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). It is expected that concrete subclasses will override this method with an ad hoc, more efficient implementation.

Specified by:

pscomp in interface Lattice

Parameters:

x - an element.

y - another element.

Returns:

x ⇒ y.

See Also:

Lattice.pscomp(Element, Element)

symdiff

public Element symdiff(Element x,
                       Element y)

Return the symmetric difference of the arguments, that is, psdiff(x,y).join(psdiff(y,x)).

Specified by:

symdiff in interface Lattice

Parameters:

x - an element.

y - another element.

Returns:

x Δ y.

See Also:

Element.join(Element), Lattice.psdiff(Element, Element)

coveringRelation

public Map<Element,Set<Element>> coveringRelation()

Return the covering relation of this lattice.

This method examines exhaustively all pairs of elements x, y such that there is no element strictly between x and y. In the worst case, this requires cubic time. It is expected that concrete subclasses will override this method with an ad hoc, more efficient implementation.

Specified by:

coveringRelation in interface Lattice

Returns:

a map from elements to set of elements representing the covering relation.