Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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;
 
 
 
A reusable abstraction for a node in a binary search tree. Null keys are allowed.

The node is considered to be immutable. Any subclass with mutable fields must create a new BstNode object upon any mutation, as the Bst classes assume that two nodes a and b represent exactly the same tree if and only if a == b.

A BstNode can be considered to be an entry, containing a key and possibly some value data, or it can be considered to be a subtree, representative of it and all its descendants.

Parameters:
<K> The key type associated with this tree.
<N> The type of the nodes in this tree.
Author(s):
Louis Wasserman
 
 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 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;
     this. = left;
     this. = right;
   }

  
Returns the ordered key associated with this node.
 
   @Nullable
   public final K getKey() {
     return ;
   }

  
Returns the child on the specified side, or null if there is no such child.
 
   @Nullable
   public final N childOrNull(BstSide side) {
     switch (side) {
       case :
         return ;
       case :
         return ;
       default:
         throw new AssertionError();
     }
   }

  
Returns 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:
java.lang.IllegalStateException if this node has no such child
  public final N getChild(BstSide side) {
    N child = childOrNull(side);
    checkState(child != null);
    return child;
  }

  
Returns true if the traditional binary search tree ordering invariant holds with respect to the specified comparator.
  protected final boolean orderingInvariantHolds(Comparator<? super K> comparator) {
    checkNotNull(comparator);
    boolean result = true;
    if (hasChild()) {
      result &= comparator.compare(getChild().getKey(), ) < 0;
    }
    if (hasChild()) {
      result &= comparator.compare(getChild().getKey(), ) > 0;
    }
    return result;
  }
New to GrepCode? Check out our FAQ X