in core/src/main/java/org/apache/calcite/util/PartiallyOrderedSet.java [392:525]
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;
}