Package mondrian.util

Class PartiallyOrderedSet<E>

  • Type Parameters:
    E - Element type
    All Implemented Interfaces:
    java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>

    public class PartiallyOrderedSet<E>
    extends java.util.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
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E e)
      Adds an element to this lattice.
      void clear()  
      boolean contains​(java.lang.Object o)  
      java.util.List<E> getAncestors​(E e)
      Returns a list of values in the set that are less-than a given value.
      java.util.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.
      java.util.List<E> getDescendants​(E e)
      Returns a list of values in the set that are less-than a given value.
      java.util.List<E> getNonChildren()  
      java.util.List<E> getNonParents()  
      java.util.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.
      boolean isValid​(boolean fail)
      Checks internal consistency of this lattice.
      java.util.Iterator<E> iterator()  
      void out​(java.lang.StringBuilder buf)  
      boolean remove​(java.lang.Object o)  
      int size()  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll
      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
      • Methods inherited from interface java.util.Set

        addAll, containsAll, isEmpty, retainAll, spliterator, toArray, toArray
    • 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,
                                   java.util.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

      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Set<E>
        Specified by:
        size in class java.util.AbstractCollection<E>
      • contains

        public boolean contains​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Set<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>
      • remove

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.Set<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>
      • add

        public boolean add​(E e)
        Adds an element to this lattice.
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.Set<E>
        Overrides:
        add in class java.util.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​(java.lang.StringBuilder buf)
      • getChildren

        public java.util.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 java.util.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 java.util.List<E> getNonChildren()
      • getNonParents

        public java.util.List<E> getNonParents()
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.Set<E>
        Overrides:
        clear in class java.util.AbstractCollection<E>
      • getDescendants

        public java.util.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 java.util.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