11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * express or implied. See the License for the specific language governing permissions and 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A specification for a local change to an entry in a binary search tree. 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertinterface BstModifier<K, N extends BstNode<K, N>> { 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Given a target key and the original entry (if any) with the specified key, returns the entry 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * with key {@code key} after this mutation has been performed. The result must either be {@code 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * null} or must have a key that compares as equal to {@code key}. A deletion operation, for 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * example, would always return {@code null}, or an insertion operation would always return a 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * non-null {@code insertedEntry}. 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If this method returns a non-null entry of type {@code N}, any children it has will be 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ignored. 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method may return {@code originalEntry} itself to indicate that no change is made. 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param key The key being targeted for modification. 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param originalEntry The original entry in the binary search tree with the specified key, if 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * any. No guarantees are made about the children of this entry when treated as a node; in 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * particular, they are not necessarily the children of the corresponding node in the 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * binary search tree. 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the entry (if any) with the specified key after this modification is performed 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BstModificationResult<N> modify(K key, @Nullable N originalEntry); 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 50