PartiallyOrderedSet.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to you under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.calcite.util;
import org.apache.calcite.config.CalciteSystemProperty;
import com.google.common.collect.ImmutableList;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.util.AbstractSet;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import static org.apache.calcite.linq4j.Nullness.castNonNull;
import static java.util.Objects.requireNonNull;
/**
* Partially-ordered set.
*
* <p>When you create a partially-ordered set ('poset' for short) you must
* provide an {@link Ordering} that determines the order relation. The
* ordering must be:
*
* <ul>
* <li>reflexive: e.lte(e) returns true;</li>
* <li>anti-symmetric: if e.lte(f) returns true,
* then f.lte(e) returns false only if e = f;</li>
* <li>transitive: if e.lte(f) returns true and
* f.lte(g) returns true, then e.lte(g) must return true.</li>
* </ul>
*
* <p>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.
*
* <p>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).
*
* <p>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.
*
* @param <E> Element type
*/
public class PartiallyOrderedSet<E> extends AbstractSet<E> {
/** Ordering that orders bit sets by inclusion.
*
* <p>For example, the children of 14 (1110) are 12 (1100), 10 (1010) and
* 6 (0110).
*/
public static final Ordering<ImmutableBitSet> BIT_SET_INCLUSION_ORDERING =
ImmutableBitSet::contains;
private final Map<E, Node<E>> map;
private final @Nullable Function<E, Iterable<E>> parentFunction;
@SuppressWarnings("unused")
private final @Nullable Function<E, Iterable<E>> childFunction;
private final Ordering<E> ordering;
/**
* Synthetic node to hold all nodes that have no parents. It does not appear
* in the set.
*/
private final Node<E> topNode;
/**
* Synthetic node to hold all nodes that have no children. It does not appear
* in the set.
*/
private final Node<E> bottomNode;
/**
* Creates a partially-ordered set.
*
* @param ordering Ordering relation
*/
public PartiallyOrderedSet(Ordering<E> ordering) {
this(ordering, new HashMap<>(), null, null);
}
/**
* Creates a partially-ordered set with a parent-generating function.
*
* @param ordering Ordering relation
* @param parentFunction Function to compute parents of a node; may be null
*/
public PartiallyOrderedSet(Ordering<E> ordering,
Function<E, Iterable<E>> childFunction,
Function<E, Iterable<E>> parentFunction) {
this(ordering, new HashMap<>(), childFunction, parentFunction);
}
@SuppressWarnings({"Guava", "UnnecessaryMethodReference"})
@Deprecated // to be removed before 2.0
public PartiallyOrderedSet(Ordering<E> ordering,
com.google.common.base.Function<E, Iterable<E>> childFunction,
com.google.common.base.Function<E, Iterable<E>> parentFunction) {
//noinspection FunctionalExpressionCanBeFolded
this(ordering, (Function<E, Iterable<E>>) childFunction::apply,
parentFunction::apply);
}
/**
* Creates a partially-ordered set, and populates it with a given
* collection.
*
* @param ordering Ordering relation
* @param collection Initial contents of partially-ordered set
*/
@SuppressWarnings("method.invocation.invalid")
public PartiallyOrderedSet(Ordering<E> ordering, Collection<E> collection) {
this(ordering, new HashMap<>(collection.size() * 3 / 2), null, null);
addAll(collection);
}
/**
* Internal constructor.
*
* @param ordering Ordering relation
* @param map Map from values to nodes
* @param parentFunction Function to compute parents of a node; may be null
*/
private PartiallyOrderedSet(Ordering<E> ordering, Map<E, Node<E>> map,
@Nullable Function<E, Iterable<E>> childFunction,
@Nullable Function<E, Iterable<E>> parentFunction) {
this.ordering = ordering;
this.map = map;
this.childFunction = childFunction;
this.parentFunction = parentFunction;
this.topNode = new TopBottomNode<>(true);
this.bottomNode = new TopBottomNode<>(false);
this.topNode.childList.add(bottomNode);
this.bottomNode.parentList.add(topNode);
}
@SuppressWarnings("NullableProblems")
@Override public Iterator<E> iterator() {
final Iterator<E> iterator = map.keySet().iterator();
return new Iterator<E>() {
@Nullable E previous;
@Override public boolean hasNext() {
return iterator.hasNext();
}
@Override public E next() {
return previous = iterator.next();
}
@Override public void remove() {
if (!PartiallyOrderedSet.this.remove(previous)) {
// Object was not present.
// Maybe they have never called 'next'?
// Maybe they called 'remove' twice?
// Either way, something is screwy.
throw new IllegalStateException();
}
}
};
}
@Override public int size() {
return map.size();
}
@Override public boolean contains(@Nullable Object o) {
//noinspection SuspiciousMethodCalls
return map.containsKey(o);
}
@Override public boolean remove(@Nullable Object o) {
final Node<E> node = map.remove(o);
if (node == null) {
return false;
}
for (int i = 0; i < node.parentList.size(); i++) {
Node<E> parent = node.parentList.get(i);
for (Node<E> child : node.childList) {
if (parent.e == null && child.e == null) {
parent.childList.remove(node);
continue;
}
replace(parent.childList, node, child);
}
}
for (int i = 0; i < node.childList.size(); i++) {
Node<E> child = node.childList.get(i);
for (Node<E> parent : node.parentList) {
if (child.e == null && parent.e == null) {
child.parentList.remove(node);
continue;
}
replace(child.parentList, node, parent);
}
}
return true;
}
/**
* Adds an element to this lattice.
*/
@Override public boolean add(E e) {
requireNonNull(e, "e");
assert !CalciteSystemProperty.DEBUG.value() || isValid(true);
Node<E> node = map.get(e);
if (node != null) {
// already present
return false;
}
Set<Node<E>> parents = findParents(e);
Set<Node<E>> children = findChildren(e);
node = new Node<>(e);
for (Node<E> parent : parents) {
node.parentList.add(parent);
int n = 0;
for (int i = 0; i < parent.childList.size(); i++) {
Node<E> child = parent.childList.get(i);
if (child.e == null || ordering.lessThan(child.e, e)) {
if (parent.childList.contains(node)) {
parent.childList.remove(i);
--i;
} else {
parent.childList.set(i, node);
}
replace(child.parentList, parent, node);
if (!node.childList.contains(child)) {
node.childList.add(child);
}
++n;
}
}
if (n == 0) {
parent.childList.add(node);
}
}
// Nodes reachable from parents.
final Set<Node<E>> childSet = new HashSet<>(node.childList);
for (Node<E> child : children) {
if (!isDescendantOfAny(child, childSet)) {
node.childList.add(child);
if (!child.parentList.contains(node)) {
child.parentList.add(node);
}
}
}
map.put(node.e, node);
assert !CalciteSystemProperty.DEBUG.value() || isValid(true);
return true;
}
/**
* Returns whether node's value is a descendant of any of the values in
* nodeSet.
*
* @param node Node
* @param nodeSet Suspected ancestors
* @return Whether node is a descendant of any of the nodes
*/
private boolean isDescendantOfAny(
Node<E> node,
Set<Node<E>> nodeSet) {
final Deque<Node<E>> deque = new ArrayDeque<>();
final Set<Node<E>> seen = new HashSet<>();
deque.add(node);
while (!deque.isEmpty()) {
final Node<E> node1 = deque.pop();
if (nodeSet.contains(node1)) {
return true;
}
for (Node<E> parent : node1.parentList) {
if (seen.add(parent)) {
deque.add(parent);
}
}
}
return false;
}
private Set<Node<E>> findChildren(E e) {
final Deque<Node<E>> descendants = new ArrayDeque<>();
descendants.add(bottomNode);
return findParentsChildren(e, descendants, false);
}
private Set<Node<E>> findParents(E e) {
final Deque<Node<E>> ancestors = new ArrayDeque<>();
ancestors.add(topNode);
return findParentsChildren(e, ancestors, true);
}
private Set<Node<E>> findParentsChildren(
E e,
Deque<Node<E>> ancestors,
boolean up) {
final Set<Node<E>> parents = new HashSet<>();
while (!ancestors.isEmpty()) {
final Node<E> ancestor = ancestors.pop();
assert ancestor.e == null
|| (up
? !ordering.lessThan(ancestor.e, e)
: !ordering.lessThan(e, ancestor.e));
assert ancestor.e != e; // e not in tree yet
// Example: e = "a", ancestor = "abc".
// If there is at least one child c of ancestor such that e <= c
// (e.g. "ab", "ac") examine those children. If there are no
// such children, ancestor becomes a parent
int found = 0;
for (Node<E> child : up ? ancestor.childList : ancestor.parentList) {
if (child.e == null) {
continue; // child is the bottom node
}
if (up
? ordering.lessThan(e, child.e)
: ordering.lessThan(child.e, e)) {
ancestors.add(child);
++found;
} else if (up
? !ordering.lessThan(child.e, e)
: !ordering.lessThan(e, child.e)) {
// e is not less than child (and therefore some descendant
// of child might be less than e). Recurse into its
// children.
ancestors.add(child);
}
}
if (found == 0) {
// None of the descendants of the node are greater than e.
// Therefore node is a parent, provided that e is definitely
// less than node
if (ancestor.e == null
|| (up
? ordering.lessThan(e, ancestor.e)
: ordering.lessThan(ancestor.e, e))) {
parents.add(ancestor);
}
}
}
return parents;
}
private static <T> void replace(List<T> list, T remove, T add) {
if (list.contains(add)) {
list.remove(remove);
} else {
final int index = list.indexOf(remove);
if (index >= 0) {
list.set(index, add);
} else {
list.add(add);
}
}
}
/**
* Checks internal consistency of this lattice.
*
* @param fail Whether to throw an assertion error
* @return Whether valid
*/
@SuppressWarnings({"ConstantConditions" })
public boolean isValid(boolean fail) {
// Top has no parents.
// Bottom has no children.
// Each node except top has at least one parent.
// Each node except bottom has at least one child.
// Every node's children list it as a parent.
// Every node's parents list it as a child.
for (Node<E> node : map.values()) {
if ((node == topNode)
!= node.parentList.isEmpty()) {
assert !fail
: "only top node should have no parents " + node
+ ", parents " + node.parentList;
return false;
}
if ((node == bottomNode)
!= node.childList.isEmpty()) {
assert !fail
: "only bottom node should have no children " + node
+ ", children " + node.childList;
return false;
}
for (int i = 0; i < node.childList.size(); i++) {
Node<E> child = node.childList.get(i);
if (!child.parentList.contains(node)) {
assert !fail
: "child " + child + " of " + node
+ " does not know its parent";
return false;
}
if (child.e != null && !ordering.lessThan(child.e, node.e)) {
assert !fail
: "child " + child.e + " not less than parent "
+ node.e;
return false;
}
for (int i2 = 0; i2 < node.childList.size(); i2++) {
Node<E> child2 = node.childList.get(i2);
if (child == child2
&& i != i2) {
assert !fail
: "duplicate child " + child + " of parent " + node;
return false;
}
if (child.e != null
&& child2.e != null
&& child != child2
&& ordering.lessThan(child.e, child2.e)) {
assert !fail
: "relation between children " + child.e
+ " and " + child2.e + " of node " + node.e;
return false;
}
}
}
for (Node<E> parent : node.parentList) {
if (!parent.childList.contains(node)) {
assert !fail;
return false;
}
}
}
final Map<Node, Integer> distanceToRoot = new HashMap<>();
distanceRecurse(distanceToRoot, topNode, 0);
for (Node<E> node : map.values()) {
if (!distanceToRoot.containsKey(node)) {
assert !fail : "node " + node + " is not reachable";
return false;
}
}
// For each pair of elements, ensure that elements are related if and
// only if they are in the ancestors or descendants lists.
final Map<Node<E>, Set<E>> nodeAncestors = new HashMap<>();
final Map<Node<E>, Set<E>> nodeDescendants = new HashMap<>();
for (Node<E> node : map.values()) {
nodeAncestors.put(node, new HashSet<>(getAncestors(node.e)));
nodeDescendants.put(node, new HashSet<>(getDescendants(node.e)));
}
for (Node<E> node1 : map.values()) {
for (Node<E> node2 : map.values()) {
final boolean lt12 = ordering.lessThan(node1.e, node2.e);
final boolean lt21 = ordering.lessThan(node2.e, node1.e);
if (node1 == node2) {
if (!(lt12 && lt21)) {
assert !fail
: "self should be less than self: " + node1;
}
}
if (lt12 && lt21) {
if (!(node1 == node2)) {
assert !fail
: "node " + node1.e + " and node " + node2.e
+ " are less than each other but are not the same"
+ " value";
return false;
}
}
if (lt12 && !lt21) {
if (!get(nodeAncestors, node1, "nodeAncestors").contains(node2.e)) {
assert !fail
: node1.e + " is less than " + node2.e + " but "
+ node2.e + " is not in the ancestor set of "
+ node1.e;
return false;
}
if (!get(nodeDescendants, node2, "nodeDescendants").contains(node1.e)) {
assert !fail
: node1.e + " is less than " + node2.e + " but "
+ node1.e + " is not in the descendant set of "
+ node2.e;
return false;
}
}
if (lt21 && !lt12) {
if (!get(nodeAncestors, node2, "nodeAncestors").contains(node1.e)) {
assert !fail
: node2.e + " is less than " + node1.e + " but "
+ node1.e + " is not in the ancestor set of "
+ node2.e;
return false;
}
if (!get(nodeDescendants, node1, "nodeDescendants").contains(node2.e)) {
assert !fail
: node2.e + " is less than " + node1.e + " but "
+ node2.e + " is not in the descendant set of "
+ node1.e;
return false;
}
}
}
}
return true;
}
private static <E> Set<E> get(Map<Node<E>, Set<E>> map, Node<E> node, String label) {
return requireNonNull(map.get(node),
() -> label + " for node " + node);
}
private void distanceRecurse(
Map<Node, Integer> distanceToRoot,
Node<E> node,
int distance) {
final Integer best = distanceToRoot.get(node);
if (best == null || distance < best) {
distanceToRoot.put(node, distance);
}
if (best != null) {
return;
}
for (Node<E> child : node.childList) {
distanceRecurse(
distanceToRoot,
child,
distance + 1);
}
}
public void out(StringBuilder buf) {
buf.append("PartiallyOrderedSet size: ");
buf.append(size());
buf.append(" elements: {\n");
// breadth-first search, to iterate over every element once, printing
// those nearest the top element first
final Set<E> seen = new HashSet<>();
final Deque<E> unseen = new ArrayDeque<>(getNonChildren());
while (!unseen.isEmpty()) {
E e = unseen.pop();
buf.append(" ");
buf.append(e);
buf.append(" parents: ");
final List<E> parents = getParents(e);
buf.append(parents);
buf.append(" children: ");
final List<E> children = getChildren(e);
buf.append(children);
buf.append("\n");
if (children != null) {
for (E child : children) {
if (seen.add(child)) {
unseen.add(child);
}
}
}
}
buf.append("}");
}
/**
* Returns the values in this partially-ordered set that are less-than
* a given value and there are no intervening values.
*
* <p>If the value is not in this set, returns null.
*
* @see #getDescendants
*
* @param e Value
* @return List of values in this set that are directly less than the given
* value
*/
public @Nullable List<E> getChildren(E e) {
return getChildren(e, false);
}
/**
* Returns the values in this partially-ordered set that are less-than
* a given value and there are no intervening values.
*
* <p>If the value is not in this set, returns null if {@code hypothetical}
* is false.
*
* @see #getDescendants
*
* @param e Value
* @param hypothetical Whether to generate a list if value is not in the set
* @return List of values in this set that are directly less than the given
* value
*/
public @Nullable List<E> getChildren(E e, boolean hypothetical) {
final Node<E> node = map.get(e);
if (node == null) {
if (hypothetical) {
return strip(findChildren(e));
} else {
return null;
}
} else {
return strip(node.childList);
}
}
/**
* Returns the values in this partially-ordered set that are greater-than
* a given value and there are no intervening values.
*
* <p>If the value is not in this set, returns null.
*
* @see #getAncestors
*
* @param e Value
* @return List of values in this set that are directly greater than the
* given value
*/
public @Nullable List<E> getParents(E e) {
return getParents(e, false);
}
/**
* Returns the values in this partially-ordered set that are greater-than
* a given value and there are no intervening values.
*
* <p>If the value is not in this set, returns {@code null} if
* {@code hypothetical} is false.
*
* @see #getAncestors
*
* @param e Value
* @param hypothetical Whether to generate a list if value is not in the set
* @return List of values in this set that are directly greater than the
* given value
*/
public @Nullable List<E> getParents(E e, boolean hypothetical) {
final Node<E> node = map.get(e);
if (node == null) {
if (hypothetical) {
if (parentFunction != null) {
final ImmutableList.Builder<E> list = new ImmutableList.Builder<>();
closure(parentFunction, e, list, new HashSet<>());
return list.build();
} else {
return ImmutableList.copyOf(strip(findParents(e)));
}
} else {
return null;
}
} else {
return ImmutableList.copyOf(strip(node.parentList));
}
}
private void closure(Function<E, Iterable<E>> generator, E e, ImmutableList.Builder<E> list,
Set<E> set) {
for (E p : requireNonNull(generator.apply(e))) {
if (set.add(e)) {
if (map.containsKey(p)) {
list.add(p);
} else {
closure(generator, p, list, set);
}
}
}
}
/**
* Returns all elements in the set that are not children. These elements appear at the top of
* the poset, and they usually referred to as roots/maximal elements of the poset.
*
* @return a list of elements that are not children.
*/
public List<E> getNonChildren() {
return strip(topNode.childList);
}
/**
* Returns all elements in the set that are not parents. These elements appear at the bottom of
* the poset, and they usually referred to as leafs/minimal elements of the poset.
*
* @return a list of elements that are not parents.
*/
public List<E> getNonParents() {
return strip(bottomNode.parentList);
}
@Override public void clear() {
map.clear();
assert topNode.parentList.isEmpty();
topNode.childList.clear();
topNode.childList.add(bottomNode);
assert bottomNode.childList.isEmpty();
bottomNode.parentList.clear();
bottomNode.parentList.add(topNode);
}
/**
* 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.
*
* @param e Value
* @return Values less than given value
*/
public List<E> getDescendants(E e) {
return descendants(e, true);
}
/** Returns a list, backed by a list of
* {@link org.apache.calcite.util.PartiallyOrderedSet.Node}s, that strips
* away the node and returns the element inside.
*
* @param <E> Element type
*/
public static <E> List<E> strip(List<Node<E>> list) {
if (list.size() == 1
&& list.get(0).e == null) {
// If parent list contains top element, a node whose element is null,
// officially there are no parents.
// Similarly child list and bottom element.
return ImmutableList.of();
}
return Util.transform(list, node -> node.e);
}
/** 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.
*
* @param <E> Element type
*/
private static <E> ImmutableList<E> strip(Iterable<Node<E>> iterable) {
final Iterator<Node<E>> iterator = iterable.iterator();
if (!iterator.hasNext()) {
return ImmutableList.of();
}
Node<E> node = iterator.next();
if (!iterator.hasNext()) {
if (node.e == null) {
return ImmutableList.of();
} else {
return ImmutableList.of(node.e);
}
}
final ImmutableList.Builder<E> builder = ImmutableList.builder();
for (;;) {
builder.add(node.e);
if (!iterator.hasNext()) {
return builder.build();
}
node = iterator.next();
}
}
/**
* 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.
*
* @param e Value
* @return Values less than given value
*/
public List<E> getAncestors(E e) {
return descendants(e, false);
}
private List<E> descendants(E e, boolean up) {
Node<E> node = map.get(e);
final Collection<Node<E>> c;
if (node == null) {
c = up ? findChildren(e) : findParents(e);
} else {
c = up ? node.childList : node.parentList;
}
if (c.size() == 1 && c.iterator().next().e == null) {
return Collections.emptyList();
}
final Deque<Node<E>> deque = new ArrayDeque<>(c);
final Set<Node<E>> seen = new HashSet<>();
final ImmutableList.Builder<E> list = new ImmutableList.Builder<>();
while (!deque.isEmpty()) {
Node<E> node1 = deque.pop();
list.add(node1.e);
for (Node<E> child : up ? node1.childList : node1.parentList) {
if (child.e == null) {
// Node is top or bottom.
break;
}
if (seen.add(child)) {
deque.add(child);
}
}
}
return list.build();
}
/**
* Holds a value, its parent nodes, and child nodes.
*
* <p>We deliberately do not override {@link #hashCode} or
* {@link #equals(Object)}. A canonizing map ensures that within a
* given PartiallyOrderedSet, two nodes are identical if and only if they
* contain the same value.
*
* @param <E> Element type
*/
private static class Node<E> {
final List<Node<E>> parentList = new ArrayList<>();
final List<Node<E>> childList = new ArrayList<>();
final E e;
Node(E e) {
this.e = e;
}
@Override public String toString() {
return String.valueOf(e);
}
}
/**
* Subclass of Node for top/bottom nodes. Improves readability when
* debugging.
*
* @param <E> Element type
*/
private static class TopBottomNode<E> extends Node<E> {
private final String description;
TopBottomNode(boolean top) {
super(castNonNull(null));
this.description = top ? "top" : "bottom";
}
@Override public String toString() {
return description;
}
}
/**
* Ordering relation.
*
* <p>To obey the constraints of the partially-ordered set, the function
* must be consistent with the reflexive, anti-symmetric, and transitive
* properties required by a partially ordered set.
*
* <p>For instance, if {@code ordering(foo, foo)} returned false for any
* not-null value of foo, it would violate the reflexive property.
*
* <p>If an ordering violates any of these required properties, the behavior
* of a {@link PartiallyOrderedSet} is unspecified. (But mayhem is
* likely.)
*
* @param <E> Element type
*/
public interface Ordering<E> {
/**
* Returns whether element e1 is ≤ e2 according to
* the relation that defines a partially-ordered set.
*
* @param e1 Element 1
* @param e2 Element 2
* @return Whether element 1 is ≤ element 2
*/
boolean lessThan(E e1, E e2);
}
}