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.collect.BstSide.LEFT;
 import static com.google.common.collect.BstSide.RIGHT;
 
 
 
Tools to perform single-key queries and mutations in binary search trees.

Author(s):
Louis Wasserman
 
 final class BstOperations {
   private BstOperations() {}

  
Returns the node with key key in tree, if any.
 
   @Nullable
   public static <K, N extends BstNode<K, N>> N seek(
       Comparator<? super K> comparator, @Nullable N tree, @Nullable K key) {
     checkNotNull(comparator);
     if (tree == null) {
       return null;
     }
     int cmp = comparator.compare(keytree.getKey());
     if (cmp == 0) {
       return tree;
     } else {
       BstSide side = (cmp < 0) ?  : ;
       return seek(comparatortree.childOrNull(side), key);
     }
   }

  
Returns the result of performing the mutation specified by mutationRule in tree at the location with key key.
  • If the returned BstModificationResult has type IDENTITY, the exact original tree is returned.
  • If the returned BstModificationResult has type REBUILDING_CHANGE, the tree will be rebuilt with the node factory of the mutation rule, but not rebalanced.
  • If the returned BstModificationResult has type REBALANCING_CHANGE, the tree will be rebalanced using the balance policy of the mutation rule.
 
   public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> mutate(
       Comparator<? super K> comparatorBstMutationRule<K, N> mutationRule, @Nullable N tree,
       @Nullable K key) {
     checkNotNull(comparator);
     checkNotNull(mutationRule);
 
     if (tree != null) {
       int cmp = comparator.compare(keytree.getKey());
       if (cmp != 0) {
         BstSide side = (cmp < 0) ?  : ;
         BstMutationResult<K, N> mutation =
             mutate(comparatormutationRuletree.childOrNull(side), key);
         return mutation.lift(
             treesidemutationRule.getNodeFactory(), mutationRule.getBalancePolicy());
       }
     }
     return modify(treekeymutationRule);
   }

  
Perform the local mutation at the tip of the specified path.
 
   public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> mutate(
       BstInOrderPath<N> pathBstMutationRule<K, N> mutationRule) {
     checkNotNull(path);
     checkNotNull(mutationRule);
     BstBalancePolicy<N> balancePolicy = mutationRule.getBalancePolicy();
     BstNodeFactory<N> nodeFactory = mutationRule.getNodeFactory();
 
     N target = path.getTip();
     K key = target.getKey();
     BstMutationResult<K, N> result = modify(targetkeymutationRule);
    while (path.hasPrefix()) {
      BstInOrderPath<N> prefix = path.getPrefix();
      result = result.lift(prefix.getTip(), path.getSideOfExtension(), nodeFactorybalancePolicy);
      path = prefix;
    }
    return result;
  }

  
Perform the local mutation right here, at the specified node.
  private static <K, N extends BstNode<K, N>> BstMutationResult<K, N> modify(
      @Nullable N tree, K keyBstMutationRule<K, N> mutationRule) {
    BstBalancePolicy<N> rebalancePolicy = mutationRule.getBalancePolicy();
    BstNodeFactory<N> nodeFactory = mutationRule.getNodeFactory();
    BstModifier<K, N> modifier = mutationRule.getModifier();
    N originalRoot = tree;
    N changedRoot;
    N originalTarget = (tree == null) ? null : nodeFactory.createLeaf(tree);
    BstModificationResult<N> modResult = modifier.modify(keyoriginalTarget);
    N originalLeft = null;
    N originalRight = null;
    if (tree != null) {
      originalLeft = tree.childOrNull();
      originalRight = tree.childOrNull();
    }
    switch (modResult.getType()) {
      case :
        changedRoot = tree;
        break;
      case :
        if (modResult.getChangedTarget() != null) {
          changedRoot =
              nodeFactory.createNode(modResult.getChangedTarget(), originalLeftoriginalRight);
        } else if (tree == null) {
          changedRoot = null;
        } else {
          throw new AssertionError(
              "Modification result is a REBUILDING_CHANGE, but rebalancing required");
        }
        break;
      case :
        if (modResult.getChangedTarget() != null) {
          changedRoot = rebalancePolicy.balance(
              nodeFactorymodResult.getChangedTarget(), originalLeftoriginalRight);
        } else if (tree != null) {
          changedRoot = rebalancePolicy.combine(nodeFactoryoriginalLeftoriginalRight);
        } else {
          changedRoot = null;
        }
        break;
      default:
        throw new AssertionError();
    }
    return BstMutationResult.mutationResult(keyoriginalRootchangedRootmodResult);
  }

  
Returns the result of removing the minimum element from the specified subtree.
  public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> extractMin(
      N rootBstNodeFactory<N> nodeFactoryBstBalancePolicy<N> balancePolicy) {
    checkNotNull(root);
    checkNotNull(nodeFactory);
    checkNotNull(balancePolicy);
    if (root.hasChild()) {
      BstMutationResult<K, N> subResult =
          extractMin(root.getChild(), nodeFactorybalancePolicy);
      return subResult.lift(rootnodeFactorybalancePolicy);
    }
    return BstMutationResult.mutationResult(
        root.getKey(), rootroot.childOrNull(), 
        BstModificationResult.rebalancingChange(rootnull));
  }

  
Returns the result of removing the maximum element from the specified subtree.
  public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> extractMax(
      N rootBstNodeFactory<N> nodeFactoryBstBalancePolicy<N> balancePolicy) {
    checkNotNull(root);
    checkNotNull(nodeFactory);
    checkNotNull(balancePolicy);
    if (root.hasChild()) {
      BstMutationResult<K, N> subResult =
          extractMax(root.getChild(), nodeFactorybalancePolicy);
      return subResult.lift(rootnodeFactorybalancePolicy);
    }
    return BstMutationResult.mutationResult(root.getKey(), rootroot.childOrNull(),
        BstModificationResult.rebalancingChange(rootnull));
  }

  
Inserts the specified entry into the tree as the minimum entry. Assumes that entry.getKey() is less than the key of all nodes in the subtree root.
  public static <N extends BstNode<?, N>> N insertMin(@Nullable N root, N entry,
      BstNodeFactory<N> nodeFactoryBstBalancePolicy<N> balancePolicy) {
    checkNotNull(entry);
    checkNotNull(nodeFactory);
    checkNotNull(balancePolicy);
    if (root == null) {
      return nodeFactory.createLeaf(entry);
    } else {
      return balancePolicy.balance(nodeFactoryroot,
          insertMin(root.childOrNull(), entrynodeFactorybalancePolicy),
          root.childOrNull());
    }
  }

  
Inserts the specified entry into the tree as the maximum entry. Assumes that entry.getKey() is greater than the key of all nodes in the subtree root.
  public static <N extends BstNode<?, N>> N insertMax(@Nullable N root, N entry,
      BstNodeFactory<N> nodeFactoryBstBalancePolicy<N> balancePolicy) {
    checkNotNull(entry);
    checkNotNull(nodeFactory);
    checkNotNull(balancePolicy);
    if (root == null) {
      return nodeFactory.createLeaf(entry);
    } else {
      return balancePolicy.balance(nodeFactoryrootroot.childOrNull(),
          insertMax(root.childOrNull(), entrynodeFactorybalancePolicy));
    }
  }
New to GrepCode? Check out our FAQ X