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 com.google.common.annotations.GwtCompatible;
18
19import javax.annotation.Nullable;
20
21/**
22 * A specification for a local change to an entry in a binary search tree.
23 *
24 * @author Louis Wasserman
25 */
26@GwtCompatible
27interface BstModifier<K, N extends BstNode<K, N>> {
28
29  /**
30   * Given a target key and the original entry (if any) with the specified key, returns the entry
31   * with key {@code key} after this mutation has been performed. The result must either be {@code
32   * null} or must have a key that compares as equal to {@code key}. A deletion operation, for
33   * example, would always return {@code null}, or an insertion operation would always return a
34   * non-null {@code insertedEntry}.
35   *
36   * <p>If this method returns a non-null entry of type {@code N}, any children it has will be
37   * ignored.
38   *
39   * <p>This method may return {@code originalEntry} itself to indicate that no change is made.
40   *
41   * @param key The key being targeted for modification.
42   * @param originalEntry The original entry in the binary search tree with the specified key, if
43   *        any. No guarantees are made about the children of this entry when treated as a node; in
44   *        particular, they are not necessarily the children of the corresponding node in the
45   *        binary search tree.
46   * @return the entry (if any) with the specified key after this modification is performed
47   */
48  BstModificationResult<N> modify(K key, @Nullable N originalEntry);
49}
50