Package mondrian.util

Class PartiallyOrderedSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
mondrian.util.PartiallyOrderedSet<E>
Type Parameters:
E - Element type
All Implemented Interfaces:
Iterable<E>, Collection<E>, Set<E>
public class PartiallyOrderedSet<E> extends AbstractSet<E>
Partially-ordered set.

When you create a partially-ordered set ('poset' for short) you must provide an PartiallyOrderedSet.Ordering that determines the order relation. The ordering must be:

  • reflexive: e.lte(e) returns true;
  • anti-symmetric: if e.lte(f) returns true, then f.lte(e) returns false only if e = f;
  • transitive: if e.lte(f) returns true and f.lte(g) returns true, then e.lte(g) must return true.

Note that not all pairs of elements are related. If is OK if e.lte(f) returns false and f.lte(e) returns false also.

In addition to the usual set methods, there are methods to determine the immediate parents and children of an element in the set, and method to find all elements which have no parents or no children (i.e. "root" and "leaf" elements).

A lattice is a special kind of poset where there is a unique top and bottom element. You can use a PartiallyOrderedSet for a lattice also. It may be helpful to add the top and bottom elements to the poset on construction.

Author:
Julian Hyde

  • Constructor Details

    • PartiallyOrderedSet

      public PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering)
      Creates a partially-ordered set.
      Parameters:
      ordering - Ordering relation

    • PartiallyOrderedSet

      public PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering, Collection<E> collection)
      Creates a partially-ordered set, and populates it with a given collection.
      Parameters:
      ordering - Ordering relation
      collection - Initial contents of partially-ordered set

  • Method Details

    • iterator

      public Iterator<E> iterator()
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface Set<E>
      Specified by:
      iterator in class AbstractCollection<E>

    • size

      public int size()
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface Set<E>
      Specified by:
      size in class AbstractCollection<E>

    • contains

      public boolean contains(Object o)
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface Set<E>
      Overrides:
      contains in class AbstractCollection<E>

    • remove

      public boolean remove(Object o)
      Specified by:
      remove in interface Collection<E>
      Specified by:
      remove in interface Set<E>
      Overrides:
      remove in class AbstractCollection<E>

    • add

      public boolean add(E e)
      Adds an element to this lattice.
      Specified by:
      add in interface Collection<E>
      Specified by:
      add in interface Set<E>
      Overrides:
      add in class AbstractCollection<E>

    • isValid

      public boolean isValid(boolean fail)
      Checks internal consistency of this lattice.
      Parameters:
      fail - Whether to throw an assertion error
      Returns:
      Whether valid

    • out

      public void out(StringBuilder buf)

    • getChildren

      public List<E> getChildren(E e)
      Returns the values in this partially-ordered set that are less-than a given value and there are no intervening values.

      If the value is not in this set, returns the empty list.

      Parameters:
      e - Value
      Returns:
      List of values in this set that are directly less than the given value
      See Also:

    • getParents

      public List<E> getParents(E e)
      Returns the values in this partially-ordered set that are greater-than a given value and there are no intervening values.

      If the value is not in this set, returns the empty list.

      Parameters:
      e - Value
      Returns:
      List of values in this set that are directly greater than the given value
      See Also:

    • getNonChildren

      public List<E> getNonChildren()

    • getNonParents

      public List<E> getNonParents()

    • clear

      public void clear()
      Specified by:
      clear in interface Collection<E>
      Specified by:
      clear in interface Set<E>
      Overrides:
      clear in class AbstractCollection<E>

    • getDescendants

      public List<E> getDescendants(E e)
      Returns a list of values in the set that are less-than a given value. The list is in topological order but order is otherwise non-deterministic.
      Parameters:
      e - Value
      Returns:
      Values less than given value

    • getAncestors

      public List<E> getAncestors(E e)
      Returns a list of values in the set that are less-than a given value. The list is in topological order but order is otherwise non-deterministic.
      Parameters:
      e - Value
      Returns:
      Values less than given value