Home | History | Annotate | Download | only in collect 
      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 
     15 package com.google.common.collect;
     16 
     17 import static com.google.common.base.Preconditions.checkNotNull;
     18 import static com.google.common.base.Preconditions.checkState;
     19 import static com.google.common.collect.BstSide.LEFT;
     20 import static com.google.common.collect.BstSide.RIGHT;
     21 
     22 import com.google.common.annotations.GwtCompatible;
     23 
     24 import java.util.Comparator;
     25 
     26 import 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
     44 class 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