/*
* 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.BstModificationResult.ModificationType.IDENTITY;
import static com.google.common.collect.BstModificationResult.ModificationType.REBUILDING_CHANGE;
import static com.google.common.collect.BstModificationResult.ModificationType.REBALANCING_CHANGE;
import static com.google.common.collect.BstSide.LEFT;
import static com.google.common.collect.BstSide.RIGHT;
import com.google.common.annotations.GwtCompatible;
import com.google.common.collect.BstModificationResult.ModificationType;
import javax.annotation.Nullable;
/**
* The result of a mutation operation performed at a single location in a binary search tree.
*
* @author Louis Wasserman
* @param <K> The key type of the nodes in the modified binary search tree.
* @param <N> The type of the nodes in the modified binary search tree.
*/
@GwtCompatible
final class BstMutationResult<K, N extends BstNode<K, N>> {
/**
* Creates a {@code BstMutationResult}.
*
* @param targetKey The key targeted for modification. If {@code originalTarget} or {@code
* changedTarget} are non-null, their keys must compare as equal to {@code targetKey}.
* @param originalRoot The root of the subtree that was modified.
* @param changedRoot The root of the subtree, after the modification and any rebalancing.
* @param modificationResult The result of the local modification to an entry.
*/
public static <K, N extends BstNode<K, N>> BstMutationResult<K, N> mutationResult(K targetKey,
@Nullable N originalRoot, @Nullable N changedRoot,
BstModificationResult<N> modificationResult) {
return new BstMutationResult<K, N>(targetKey, originalRoot, changedRoot, modificationResult);
}
private final K targetKey;
@Nullable
private N originalRoot;
@Nullable
private N changedRoot;
private final BstModificationResult<N> modificationResult;
private BstMutationResult(K targetKey, @Nullable N originalRoot, @Nullable N changedRoot,
BstModificationResult<N> modificationResult) {
this.targetKey = checkNotNull(targetKey);
this.originalRoot = originalRoot;
this.changedRoot = changedRoot;
this.modificationResult = checkNotNull(modificationResult);
}
/**
* Returns the key which was the target of this modification.
*/
public K getTargetKey() {
return targetKey;
}
/**
* Returns the root of the subtree that was modified.
*/
@Nullable
public N getOriginalRoot() {
return originalRoot;
}
/**
* Returns the root of the subtree, after the modification and any rebalancing was performed.
*/
@Nullable
public N getChangedRoot() {
return changedRoot;
}
/**
* Returns the entry in the original subtree with key {@code targetKey}, if any. This should not
* be treated as a subtree, but only as an entry, and no guarantees are made about its children
* when viewed as a subtree.
*/
@Nullable
public N getOriginalTarget() {
return modificationResult.getOriginalTarget();
}
/**
* Returns the result of the modification to {@link #getOriginalTarget()}. This should not be
* treated as a subtree, but only as an entry, and no guarantees are made about its children when
* viewed as a subtree.
*/
@Nullable
public N getChangedTarget() {
return modificationResult.getChangedTarget();
}
ModificationType modificationType() {
return modificationResult.getType();
}
/**
* If this mutation was to an immediate child subtree of the specified root on the specified
* side, returns the {@code BstMutationResult} of applying the mutation to the appropriate child
* of the specified root and rebalancing using the specified mutation rule.
*/
public BstMutationResult<K, N> lift(N liftOriginalRoot, BstSide side,
BstNodeFactory<N> nodeFactory, BstBalancePolicy<N> balancePolicy) {
assert liftOriginalRoot != null & side != null & nodeFactory != null & balancePolicy != null;
switch (modificationType()) {
case IDENTITY:
this.originalRoot = this.changedRoot = liftOriginalRoot;
return this;
case REBUILDING_CHANGE:
case REBALANCING_CHANGE:
this.originalRoot = liftOriginalRoot;
N resultLeft = liftOriginalRoot.childOrNull(LEFT);
N resultRight = liftOriginalRoot.childOrNull(RIGHT);
switch (side) {
case LEFT:
resultLeft = changedRoot;
break;
case RIGHT:
resultRight = changedRoot;
break;
default:
throw new AssertionError();
}
if (modificationType() == REBUILDING_CHANGE) {
this.changedRoot = nodeFactory.createNode(liftOriginalRoot, resultLeft, resultRight);
} else {
this.changedRoot =
balancePolicy.balance(nodeFactory, liftOriginalRoot, resultLeft, resultRight);
}
return this;
default:
throw new AssertionError();
}
}
}
|