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.BstOperations.extractMax;
 import static com.google.common.collect.BstOperations.extractMin;
 import static com.google.common.collect.BstOperations.insertMax;
 import static com.google.common.collect.BstOperations.insertMin;
 import static com.google.common.collect.BstSide.LEFT;
 import static com.google.common.collect.BstSide.RIGHT;
 
 
A tree-size-based set of balancing policies, based on Stephen Adams, "Efficient sets: a balancing act.".

Author(s):
Louis Wasserman
 
   private BstCountBasedBalancePolicies() {}
 
   private static final int SINGLE_ROTATE_RATIO = 4;
   private static final int SECOND_ROTATE_RATIO = 2;

  
Returns a balance policy that does no balancing or the bare minimum (for combine).
 
   public static <N extends BstNode<?, N>> BstBalancePolicy<N> noRebalancePolicy(
       final BstAggregate<N> countAggregate) {
     checkNotNull(countAggregate);
     return new BstBalancePolicy<N>() {
       @Override
       public N balance(
           BstNodeFactory<N> nodeFactory, N source, @Nullable N left, @Nullable N right) {
         return checkNotNull(nodeFactory).createNode(sourceleftright);
       }
 
       @Nullable
       @Override
       public N combine(BstNodeFactory<N> nodeFactory, @Nullable N left, @Nullable N right) {
         if (left == null) {
           return right;
         } else if (right == null) {
           return left;
         } else if (countAggregate.treeValue(left) > countAggregate.treeValue(right)) {
           return nodeFactory.createNode(
               leftleft.childOrNull(), combine(nodeFactoryleft.childOrNull(), right));
         } else {
           return nodeFactory.createNode(rightcombine(nodeFactoryleftright.childOrNull()),
               right.childOrNull());
         }
       }
     };
   }

  
Returns a balance policy that expects the sizes of each side to be at most one node (added or removed) away from being balanced. balance takes O(1) time, and combine takes O(log n) time.
 
   public static <K, N extends BstNode<K, N>> BstBalancePolicy<N> singleRebalancePolicy(
       final BstAggregate<N> countAggregate) {
     checkNotNull(countAggregate);
     return new BstBalancePolicy<N>() {
       @Override
       public N balance(
           BstNodeFactory<N> nodeFactory, N source, @Nullable N left, @Nullable N right) {
         long countL = countAggregate.treeValue(left);
         long countR = countAggregate.treeValue(right);
         if (countL + countR > 1) {
           if (countR >=  * countL) {
             return rotateL(nodeFactorysourceleftright);
           } else if (countL >=  * countR) {
             return rotateR(nodeFactorysourceleftright);
           }
         }
         return nodeFactory.createNode(sourceleftright);
       }
 
       private N rotateL(BstNodeFactory<N> nodeFactory, N source, @Nullable N left, N right) {
         checkNotNull(right);
        N rl = right.childOrNull();
        N rr = right.childOrNull();
        if (countAggregate.treeValue(rl) >=  * countAggregate.treeValue(rr)) {
          right = singleR(nodeFactoryrightrlrr);
        }
        return singleL(nodeFactorysourceleftright);
      }
      private N rotateR(BstNodeFactory<N> nodeFactory, N source, N left, @Nullable N right) {
        checkNotNull(left);
        N lr = left.childOrNull();
        N ll = left.childOrNull();
        if (countAggregate.treeValue(lr) >=  * countAggregate.treeValue(ll)) {
          left = singleL(nodeFactoryleftlllr);
        }
        return singleR(nodeFactorysourceleftright);
      }
      private N singleL(BstNodeFactory<N> nodeFactory, N source, @Nullable N left, N right) {
        checkNotNull(right);
        return nodeFactory.createNode(right,
            nodeFactory.createNode(sourceleftright.childOrNull()),
            right.childOrNull());
      }
      private N singleR(BstNodeFactory<N> nodeFactory, N source, N left, @Nullable N right) {
        checkNotNull(left);
        return nodeFactory.createNode(leftleft.childOrNull(),
            nodeFactory.createNode(sourceleft.childOrNull(), right));
      }
      @Nullable
      @Override
      public N combine(BstNodeFactory<N> nodeFactory, @Nullable N left, @Nullable N right) {
        if (left == null) {
          return right;
        } else if (right == null) {
          return left;
        }
        N newRootSource;
        if (countAggregate.treeValue(left) > countAggregate.treeValue(right)) {
          BstMutationResult<K, N> extractLeftMax = extractMax(leftnodeFactorythis);
          newRootSource = extractLeftMax.getOriginalTarget();
          left = extractLeftMax.getChangedRoot();
        } else {
          BstMutationResult<K, N> extractRightMin = extractMin(rightnodeFactorythis);
          newRootSource = extractRightMin.getOriginalTarget();
          right = extractRightMin.getChangedRoot();
        }
        return nodeFactory.createNode(newRootSourceleftright);
      }
    };
  }

  
Returns a balance policy that makes no assumptions on the relative balance of the two sides and performs a full rebalancing as necessary. Both balance and combine take O(log n) time.
  public static <K, N extends BstNode<K, N>> BstBalancePolicy<N> fullRebalancePolicy(
      final BstAggregate<N> countAggregate) {
    checkNotNull(countAggregate);
    final BstBalancePolicy<N> singleBalancePolicy =
        BstCountBasedBalancePolicies.<K, N>singleRebalancePolicy(countAggregate);
    return new BstBalancePolicy<N>() {
      @Override
      public N balance(
          BstNodeFactory<N> nodeFactory, N source, @Nullable N left, @Nullable N right) {
        if (left == null) {
          return insertMin(rightsourcenodeFactorysingleBalancePolicy);
        } else if (right == null) {
          return insertMax(leftsourcenodeFactorysingleBalancePolicy);
        }
        long countL = countAggregate.treeValue(left);
        long countR = countAggregate.treeValue(right);
        if ( * countL <= countR) {
          N resultLeft = balance(nodeFactorysourceleftright.childOrNull());
          return singleBalancePolicy.balance(
              nodeFactoryrightresultLeftright.childOrNull());
        } else if ( * countR <= countL) {
          N resultRight = balance(nodeFactorysourceleft.childOrNull(), right);
          return singleBalancePolicy.balance(
              nodeFactoryleftleft.childOrNull(), resultRight);
        } else {
          return nodeFactory.createNode(sourceleftright);
        }
      }
      @Nullable
      @Override
      public N combine(BstNodeFactory<N> nodeFactory, @Nullable N left, @Nullable N right) {
        if (left == null) {
          return right;
        } else if (right == null) {
          return left;
        }
        long countL = countAggregate.treeValue(left);
        long countR = countAggregate.treeValue(right);
        if ( * countL <= countR) {
          N resultLeft = combine(nodeFactoryleftright.childOrNull());
          return singleBalancePolicy.balance(
              nodeFactoryrightresultLeftright.childOrNull());
        } else if ( * countR <= countL) {
          N resultRight = combine(nodeFactoryleft.childOrNull(), right);
          return singleBalancePolicy.balance(
              nodeFactoryleftleft.childOrNull(), resultRight);
        } else {
          return singleBalancePolicy.combine(nodeFactoryleftright);
        }
      }
    };
  }
New to GrepCode? Check out our FAQ X