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.collect.BstModificationResult.ModificationType.IDENTITY; 19 import static com.google.common.collect.BstModificationResult.ModificationType.REBUILDING_CHANGE; 20 import static com.google.common.collect.BstModificationResult.ModificationType.REBALANCING_CHANGE; 21 import static com.google.common.collect.BstSide.LEFT; 22 import static com.google.common.collect.BstSide.RIGHT; 23 24 import com.google.common.annotations.GwtCompatible; 25 import com.google.common.collect.BstModificationResult.ModificationType; 26 27 import javax.annotation.Nullable; 28 29 /** 30 * The result of a mutation operation performed at a single location in a binary search tree. 31 * 32 * @author Louis Wasserman 33 * @param <K> The key type of the nodes in the modified binary search tree. 34 * @param <N> The type of the nodes in the modified binary search tree. 35 */ 36 @GwtCompatible 37 final class BstMutationResult<K, N extends BstNode<K, N>> { 38 /** 39 * Creates a {@code BstMutationResult}. 40 * 41 * @param targetKey The key targeted for modification. If {@code originalTarget} or {@code 42 * changedTarget} are non-null, their keys must compare as equal to {@code targetKey}. 43 * @param originalRoot The root of the subtree that was modified. 44 * @param changedRoot The root of the subtree, after the modification and any rebalancing. 45 * @param modificationResult The result of the local modification to an entry. 46 */ mutationResult( @ullable K targetKey, @Nullable N originalRoot, @Nullable N changedRoot, BstModificationResult<N> modificationResult)47 public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> mutationResult( 48 @Nullable K targetKey, @Nullable N originalRoot, @Nullable N changedRoot, 49 BstModificationResult<N> modificationResult) { 50 return new BstMutationResult<K, N>(targetKey, originalRoot, changedRoot, modificationResult); 51 } 52 53 private final K targetKey; 54 55 @Nullable 56 private N originalRoot; 57 58 @Nullable 59 private N changedRoot; 60 61 private final BstModificationResult<N> modificationResult; 62 BstMutationResult(@ullable K targetKey, @Nullable N originalRoot, @Nullable N changedRoot, BstModificationResult<N> modificationResult)63 private BstMutationResult(@Nullable K targetKey, @Nullable N originalRoot, 64 @Nullable N changedRoot, BstModificationResult<N> modificationResult) { 65 this.targetKey = targetKey; 66 this.originalRoot = originalRoot; 67 this.changedRoot = changedRoot; 68 this.modificationResult = checkNotNull(modificationResult); 69 } 70 71 /** 72 * Returns the key which was the target of this modification. 73 */ getTargetKey()74 public K getTargetKey() { 75 return targetKey; 76 } 77 78 /** 79 * Returns the root of the subtree that was modified. 80 */ 81 @Nullable getOriginalRoot()82 public N getOriginalRoot() { 83 return originalRoot; 84 } 85 86 /** 87 * Returns the root of the subtree, after the modification and any rebalancing was performed. 88 */ 89 @Nullable getChangedRoot()90 public N getChangedRoot() { 91 return changedRoot; 92 } 93 94 /** 95 * Returns the entry in the original subtree with key {@code targetKey}, if any. This should not 96 * be treated as a subtree, but only as an entry, and no guarantees are made about its children 97 * when viewed as a subtree. 98 */ 99 @Nullable getOriginalTarget()100 public N getOriginalTarget() { 101 return modificationResult.getOriginalTarget(); 102 } 103 104 /** 105 * Returns the result of the modification to {@link #getOriginalTarget()}. This should not be 106 * treated as a subtree, but only as an entry, and no guarantees are made about its children when 107 * viewed as a subtree. 108 */ 109 @Nullable getChangedTarget()110 public N getChangedTarget() { 111 return modificationResult.getChangedTarget(); 112 } 113 modificationType()114 ModificationType modificationType() { 115 return modificationResult.getType(); 116 } 117 118 /** 119 * If this mutation was to an immediate child subtree of the specified root on the specified 120 * side, returns the {@code BstMutationResult} of applying the mutation to the appropriate child 121 * of the specified root and rebalancing using the specified mutation rule. 122 */ lift(N liftOriginalRoot, BstSide side, BstNodeFactory<N> nodeFactory, BstBalancePolicy<N> balancePolicy)123 public BstMutationResult<K, N> lift(N liftOriginalRoot, BstSide side, 124 BstNodeFactory<N> nodeFactory, BstBalancePolicy<N> balancePolicy) { 125 assert liftOriginalRoot != null & side != null & nodeFactory != null & balancePolicy != null; 126 switch (modificationType()) { 127 case IDENTITY: 128 this.originalRoot = this.changedRoot = liftOriginalRoot; 129 return this; 130 case REBUILDING_CHANGE: 131 case REBALANCING_CHANGE: 132 this.originalRoot = liftOriginalRoot; 133 N resultLeft = liftOriginalRoot.childOrNull(LEFT); 134 N resultRight = liftOriginalRoot.childOrNull(RIGHT); 135 switch (side) { 136 case LEFT: 137 resultLeft = changedRoot; 138 break; 139 case RIGHT: 140 resultRight = changedRoot; 141 break; 142 default: 143 throw new AssertionError(); 144 } 145 if (modificationType() == REBUILDING_CHANGE) { 146 this.changedRoot = nodeFactory.createNode(liftOriginalRoot, resultLeft, resultRight); 147 } else { 148 this.changedRoot = 149 balancePolicy.balance(nodeFactory, liftOriginalRoot, resultLeft, resultRight); 150 } 151 return this; 152 default: 153 throw new AssertionError(); 154 } 155 } 156 } 157