diff options
Diffstat (limited to 'guava/src/com/google/common/collect/BstNode.java')
-rw-r--r-- | guava/src/com/google/common/collect/BstNode.java | 125 |
1 files changed, 125 insertions, 0 deletions
diff --git a/guava/src/com/google/common/collect/BstNode.java b/guava/src/com/google/common/collect/BstNode.java new file mode 100644 index 0000000..818f85a --- /dev/null +++ b/guava/src/com/google/common/collect/BstNode.java @@ -0,0 +1,125 @@ +/* + * Copyright (C) 2011 The Guava Authors + * + * Licensed 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 com.google.common.collect; + +import static com.google.common.base.Preconditions.checkNotNull; +import static com.google.common.base.Preconditions.checkState; +import static com.google.common.collect.BstSide.LEFT; +import static com.google.common.collect.BstSide.RIGHT; + +import com.google.common.annotations.GwtCompatible; + +import java.util.Comparator; + +import javax.annotation.Nullable; + +/** + * A reusable abstraction for a node in a binary search tree. Null keys are allowed. + * + * <p>The node is considered to be immutable. Any subclass with mutable fields must create a new + * {@code BstNode} object upon any mutation, as the {@code Bst} classes assume that two nodes + * {@code a} and {@code b} represent exactly the same tree if and only if {@code a == b}. + * + * <p>A {@code BstNode} can be considered to be an <i>entry</i>, containing a key and possibly some + * value data, or it can be considered to be a <i>subtree</i>, representative of it and all its + * descendants. + * + * @author Louis Wasserman + * @param <K> The key type associated with this tree. + * @param <N> The type of the nodes in this tree. + */ +@GwtCompatible +class BstNode<K, N extends BstNode<K, N>> { + /** + * The key on which this binary search tree is ordered. All descendants of the left subtree of + * this node must have keys strictly less than {@code this.key}. + */ + private final K key; + + /** + * The left child of this node. A null value indicates that this node has no left child. + */ + @Nullable + private final N left; + + /** + * The right child of this node. A null value indicates that this node has no right child. + */ + @Nullable + private final N right; + + BstNode(@Nullable K key, @Nullable N left, @Nullable N right) { + this.key = key; + this.left = left; + this.right = right; + } + + /** + * Returns the ordered key associated with this node. + */ + @Nullable + public final K getKey() { + return key; + } + + /** + * Returns the child on the specified side, or {@code null} if there is no such child. + */ + @Nullable + public final N childOrNull(BstSide side) { + switch (side) { + case LEFT: + return left; + case RIGHT: + return right; + default: + throw new AssertionError(); + } + } + + /** + * Returns {@code true} if this node has a child on the specified side. + */ + public final boolean hasChild(BstSide side) { + return childOrNull(side) != null; + } + + /** + * Returns this node's child on the specified side. + * + * @throws IllegalStateException if this node has no such child + */ + public final N getChild(BstSide side) { + N child = childOrNull(side); + checkState(child != null); + return child; + } + + /** + * Returns {@code true} if the traditional binary search tree ordering invariant holds with + * respect to the specified {@code comparator}. + */ + protected final boolean orderingInvariantHolds(Comparator<? super K> comparator) { + checkNotNull(comparator); + boolean result = true; + if (hasChild(LEFT)) { + result &= comparator.compare(getChild(LEFT).getKey(), key) < 0; + } + if (hasChild(RIGHT)) { + result &= comparator.compare(getChild(RIGHT).getKey(), key) > 0; + } + return result; + } +} |