Package org.apache.calcite.util

Class PartiallyOrderedSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
org.apache.calcite.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. It 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.

  • Field Details

    • BIT_SET_INCLUSION_ORDERING

      public static final PartiallyOrderedSet.Ordering<ImmutableBitSet> BIT_SET_INCLUSION_ORDERING
      Ordering that orders bit sets by inclusion.

      For example, the children of 14 (1110) are 12 (1100), 10 (1010) and 6 (0110).

  • 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, Function<E,Iterable<E>> childFunction, Function<E,Iterable<E>> parentFunction)
      Creates a partially-ordered set with a parent-generating function.
      Parameters:
      ordering - Ordering relation
      parentFunction - Function to compute parents of a node; may be null

    • PartiallyOrderedSet

      @Deprecated public PartiallyOrderedSet(PartiallyOrderedSet.Ordering<E> ordering, com.google.common.base.Function<E,Iterable<E>> childFunction, com.google.common.base.Function<E,Iterable<E>> parentFunction)
      Deprecated.

    • 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(@Nullable 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(@Nullable 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 @Nullable 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 null.

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

    • getChildren

      public @Nullable List<E> getChildren(E e, boolean hypothetical)
      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 null if hypothetical is false.

      Parameters:
      e - Value
      hypothetical - Whether to generate a list if value is not in the set
      Returns:
      List of values in this set that are directly less than the given value
      See Also:

    • getParents

      public @Nullable 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 null.

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

    • getParents

      public @Nullable List<E> getParents(E e, boolean hypothetical)
      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 null if hypothetical is false.

      Parameters:
      e - Value
      hypothetical - Whether to generate a list if value is not in the set
      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

    • strip

      public static <E> List<E> strip(List<org.apache.calcite.util.PartiallyOrderedSet.Node<E>> list)
      Returns a list, backed by a list of PartiallyOrderedSet.Nodes, that strips away the node and returns the element inside.
      Type Parameters:
      E - Element type

    • 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