Package org.apache.calcite.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.

    • Field Detail

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

      • parentFunction

        private final java.util.function.Function<E,​java.lang.Iterable<E>> parentFunction

      • childFunction

        private final java.util.function.Function<E,​java.lang.Iterable<E>> childFunction

      • topNode

        private final PartiallyOrderedSet.Node<E> topNode
        Synthetic node to hold all nodes that have no parents. It does not appear in the set.

      • DEBUG

        private static final boolean DEBUG
        Whether to check internal consistency all the time. False unless you specify "-Dcalcite.debug" on the command line.

    • 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.function.Function<E,​java.lang.Iterable<E>> childFunction,
                           java.util.function.Function<E,​java.lang.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,​java.lang.Iterable<E>> childFunction,
                           com.google.common.base.Function<E,​java.lang.Iterable<E>> parentFunction)
        Deprecated.

      • 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

      • PartiallyOrderedSet

        private PartiallyOrderedSet​(PartiallyOrderedSet.Ordering<E> ordering,
                            java.util.Map<E,​PartiallyOrderedSet.Node<E>> map,
                            java.util.function.Function<E,​java.lang.Iterable<E>> childFunction,
                            java.util.function.Function<E,​java.lang.Iterable<E>> parentFunction)
        Internal constructor.
        Parameters:
        ordering - Ordering relation
        map - Map from values to nodes
        parentFunction - Function to compute parents of a node; may be null

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

      • isDescendantOfAny

        private boolean isDescendantOfAny​(PartiallyOrderedSet.Node<E> node,
                                  java.util.Set<PartiallyOrderedSet.Node<E>> nodeSet)
        Returns whether node's value is a descendant of any of the values in nodeSet.
        Parameters:
        node - Node
        nodeSet - Suspected ancestors
        Returns:
        Whether node is a descendant of any of the nodes

      • replace

        private <T> void replace​(java.util.List<T> list,
                         T remove,
                         T add)

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

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

      • getChildren

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

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

      • getParents

        public java.util.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:
        getAncestors(E)

      • closure

        private void closure​(java.util.function.Function<E,​java.lang.Iterable<E>> generator,
                     E e,
                     java.util.List<E> list,
                     java.util.Set<E> set)

      • 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

      • strip

        public static <E> java.util.List<E> strip​(java.util.List<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

      • strip

        private static <E> com.google.common.collect.ImmutableList<E> strip​(java.lang.Iterable<PartiallyOrderedSet.Node<E>> iterable)
        Converts an iterable of nodes into the list of the elements inside. If there is one node whose element is null, it represents a list containing either the top or bottom element, so we return the empty list.
        Type Parameters:
        E - Element type

      • 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

      • descendants

        private java.util.List<E> descendants​(E e,
                                      boolean up)