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
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkNotNull;
18import static com.google.common.collect.BstModificationResult.ModificationType.IDENTITY;
19import static com.google.common.collect.BstModificationResult.ModificationType.REBUILDING_CHANGE;
20import static com.google.common.collect.BstModificationResult.ModificationType.REBALANCING_CHANGE;
21import static com.google.common.collect.BstSide.LEFT;
22import static com.google.common.collect.BstSide.RIGHT;
23
24import com.google.common.annotations.GwtCompatible;
25import com.google.common.collect.BstModificationResult.ModificationType;
26
27import 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
37final 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   */
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
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   */
74  public K getTargetKey() {
75    return targetKey;
76  }
77
78  /**
79   * Returns the root of the subtree that was modified.
80   */
81  @Nullable
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
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
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
110  public N getChangedTarget() {
111    return modificationResult.getChangedTarget();
112  }
113
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   */
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