Package mondrian.util

Class 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 Detail

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

      • isValid

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

      • 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:
        getDescendants(E)

      • 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:
        getAncestors(E)

      • getNonChildren

        public List<E> getNonChildren()

      • getNonParents

        public List<E> getNonParents()

      • 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