1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the
10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
11 * express or implied. See the License for the specific language governing permissions and
12 * limitations under the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkNotNull;
18import static com.google.common.base.Preconditions.checkState;
19import static com.google.common.collect.BstSide.LEFT;
20import static com.google.common.collect.BstSide.RIGHT;
21
22import com.google.common.annotations.GwtCompatible;
23
24import java.util.Comparator;
25
26import javax.annotation.Nullable;
27
28/**
29 * A reusable abstraction for a node in a binary search tree. Null keys are allowed.
30 *
31 * <p>The node is considered to be immutable. Any subclass with mutable fields must create a new
32 * {@code BstNode} object upon any mutation, as the {@code Bst} classes assume that two nodes
33 * {@code a} and {@code b} represent exactly the same tree if and only if {@code a == b}.
34 *
35 * <p>A {@code BstNode} can be considered to be an <i>entry</i>, containing a key and possibly some
36 * value data, or it can be considered to be a <i>subtree</i>, representative of it and all its
37 * descendants.
38 *
39 * @author Louis Wasserman
40 * @param <K> The key type associated with this tree.
41 * @param <N> The type of the nodes in this tree.
42 */
43@GwtCompatible
44class BstNode<K, N extends BstNode<K, N>> {
45  /**
46   * The key on which this binary search tree is ordered. All descendants of the left subtree of
47   * this node must have keys strictly less than {@code this.key}.
48   */
49  private final K key;
50
51  /**
52   * The left child of this node. A null value indicates that this node has no left child.
53   */
54  @Nullable
55  private final N left;
56
57  /**
58   * The right child of this node. A null value indicates that this node has no right child.
59   */
60  @Nullable
61  private final N right;
62
63  BstNode(@Nullable K key, @Nullable N left, @Nullable N right) {
64    this.key = key;
65    this.left = left;
66    this.right = right;
67  }
68
69  /**
70   * Returns the ordered key associated with this node.
71   */
72  @Nullable
73  public final K getKey() {
74    return key;
75  }
76
77  /**
78   * Returns the child on the specified side, or {@code null} if there is no such child.
79   */
80  @Nullable
81  public final N childOrNull(BstSide side) {
82    switch (side) {
83      case LEFT:
84        return left;
85      case RIGHT:
86        return right;
87      default:
88        throw new AssertionError();
89    }
90  }
91
92  /**
93   * Returns {@code true} if this node has a child on the specified side.
94   */
95  public final boolean hasChild(BstSide side) {
96    return childOrNull(side) != null;
97  }
98
99  /**
100   * Returns this node's child on the specified side.
101   *
102   * @throws IllegalStateException if this node has no such child
103   */
104  public final N getChild(BstSide side) {
105    N child = childOrNull(side);
106    checkState(child != null);
107    return child;
108  }
109
110  /**
111   * Returns {@code true} if the traditional binary search tree ordering invariant holds with
112   * respect to the specified {@code comparator}.
113   */
114  protected final boolean orderingInvariantHolds(Comparator<? super K> comparator) {
115    checkNotNull(comparator);
116    boolean result = true;
117    if (hasChild(LEFT)) {
118      result &= comparator.compare(getChild(LEFT).getKey(), key) < 0;
119    }
120    if (hasChild(RIGHT)) {
121      result &= comparator.compare(getChild(RIGHT).getKey(), key) > 0;
122    }
123    return result;
124  }
125}
126