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

  • Constructor Details

  • Method Details

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