aboutsummaryrefslogtreecommitdiffstats
path: root/guava-tests/test/com/google/common/collect/BstOperationsTest.java
diff options
context:
space:
mode:
Diffstat (limited to 'guava-tests/test/com/google/common/collect/BstOperationsTest.java')
-rw-r--r--guava-tests/test/com/google/common/collect/BstOperationsTest.java544
1 files changed, 544 insertions, 0 deletions
diff --git a/guava-tests/test/com/google/common/collect/BstOperationsTest.java b/guava-tests/test/com/google/common/collect/BstOperationsTest.java
new file mode 100644
index 0000000..7ced712
--- /dev/null
+++ b/guava-tests/test/com/google/common/collect/BstOperationsTest.java
@@ -0,0 +1,544 @@
+/*
+ * 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.collect.BstSide.LEFT;
+import static com.google.common.collect.BstTesting.assertInOrderTraversalIs;
+import static com.google.common.collect.BstTesting.balancePolicy;
+import static com.google.common.collect.BstTesting.defaultNullPointerTester;
+import static com.google.common.collect.BstTesting.extension;
+import static com.google.common.collect.BstTesting.nodeFactory;
+import static com.google.common.collect.BstTesting.pathFactory;
+import static org.easymock.EasyMock.eq;
+import static org.easymock.EasyMock.expect;
+import static org.easymock.EasyMock.isNull;
+import static org.easymock.EasyMock.replay;
+import static org.easymock.EasyMock.reportMatcher;
+import static org.easymock.EasyMock.same;
+import static org.easymock.EasyMock.verify;
+
+import com.google.common.annotations.GwtCompatible;
+import com.google.common.annotations.GwtIncompatible;
+import com.google.common.collect.BstModificationResult.ModificationType;
+import com.google.common.collect.BstTesting.SimpleNode;
+
+import junit.framework.TestCase;
+
+import org.easymock.EasyMock;
+import org.easymock.IArgumentMatcher;
+
+/**
+ * Tests for {@code BstOperations}.
+ *
+ * @author Louis Wasserman
+ */
+@GwtCompatible(emulated = true)
+public class BstOperationsTest extends TestCase {
+ public void testSeek1() {
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+ assertEquals(a, BstOperations.seek(Ordering.natural(), d, 'a'));
+ assertEquals(b, BstOperations.seek(Ordering.natural(), d, 'b'));
+ assertNull(BstOperations.seek(Ordering.natural(), d, 'c'));
+ assertEquals(d, BstOperations.seek(Ordering.natural(), d, 'd'));
+ assertNull(BstOperations.seek(Ordering.natural(), d, 'e'));
+ assertEquals(f, BstOperations.seek(Ordering.natural(), d, 'f'));
+ assertEquals(g, BstOperations.seek(Ordering.natural(), d, 'g'));
+ }
+
+ public void testSeek2() {
+ // d
+ // / \
+ // b f
+ // \ /
+ // c e
+ SimpleNode c = new SimpleNode('c', null, null);
+ SimpleNode b = new SimpleNode('b', null, c);
+ SimpleNode e = new SimpleNode('e', null, null);
+ SimpleNode f = new SimpleNode('f', e, null);
+ SimpleNode d = new SimpleNode('d', b, f);
+ assertNull(BstOperations.seek(Ordering.natural(), d, 'a'));
+ assertEquals(b, BstOperations.seek(Ordering.natural(), d, 'b'));
+ assertEquals(c, BstOperations.seek(Ordering.natural(), d, 'c'));
+ assertEquals(d, BstOperations.seek(Ordering.natural(), d, 'd'));
+ assertEquals(e, BstOperations.seek(Ordering.natural(), d, 'e'));
+ assertEquals(f, BstOperations.seek(Ordering.natural(), d, 'f'));
+ assertNull(BstOperations.seek(Ordering.natural(), d, 'g'));
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyInsertAbsentNode() {
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ SimpleNode c = new SimpleNode('c', null, null);
+ expect(modifier.modify(eq('c'), (SimpleNode) isNull())).andReturn(
+ BstModificationResult.rebalancingChange(null, c));
+
+ expect(balancePolicy.balance(
+ same(nodeFactory), same(c), (SimpleNode) isNull(), (SimpleNode) isNull()))
+ .andReturn(c)
+ .times(0, 1);
+
+ SimpleNode bWithC = new SimpleNode('b', a, c);
+ expectPossibleEntryfication(nodeFactory, b);
+ expect(balancePolicy.balance(
+ same(nodeFactory), withKey('b'), same(a), withKey('c')))
+ .andReturn(bWithC);
+
+ SimpleNode dWithBWithC = new SimpleNode('d', bWithC, f);
+ expectPossibleEntryfication(nodeFactory, d);
+ expect(
+ balancePolicy.balance(same(nodeFactory), withKey('d'), same(bWithC), same(f)))
+ .andReturn(dWithBWithC);
+ replay(nodeFactory, balancePolicy, modifier);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(Ordering.natural(), mutationRule, d, 'c');
+ assertEquals('c', mutationResult.getTargetKey().charValue());
+ assertNull(mutationResult.getOriginalTarget());
+ assertEquals('c', mutationResult
+ .getChangedTarget()
+ .getKey()
+ .charValue());
+ assertSame(d, mutationResult.getOriginalRoot());
+ assertSame(dWithBWithC, mutationResult.getChangedRoot());
+ assertEquals(ModificationType.REBALANCING_CHANGE, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyInsertPresentNode() {
+ // We wish to test that BstOperations & co. treat IDENTITY modifications as the same.
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ expectPossibleEntryfication(nodeFactory, a);
+ expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
+ BstModificationResult.identity(a));
+ replay(nodeFactory, balancePolicy, modifier);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
+ assertEquals('a', mutationResult.getTargetKey().charValue());
+ assertSame(a, mutationResult.getOriginalTarget());
+ assertSame(a, mutationResult.getChangedTarget());
+ assertSame(d, mutationResult.getOriginalRoot());
+ assertSame(d, mutationResult.getChangedRoot());
+ assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyInsertInequivalentNode() {
+ // We wish to test that BstOperations & co. treat non-equivalent() nodes as different.
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ expectPossibleEntryfication(nodeFactory, a);
+ SimpleNode a2 = new SimpleNode('a', null, null);
+ expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
+ BstModificationResult.rebuildingChange(a, a2));
+
+ expectPossibleEntryfication(nodeFactory, a2);
+
+ SimpleNode bWithA2 = new SimpleNode('b', a2, null);
+ expect(nodeFactory.createNode(same(b), withKey('a'), (SimpleNode) isNull())).andReturn(
+ bWithA2);
+
+ SimpleNode dWithA2 = new SimpleNode('d', bWithA2, f);
+ expect(nodeFactory.createNode(same(d), same(bWithA2), same(f))).andReturn(
+ dWithA2);
+
+ replay(nodeFactory, balancePolicy, modifier);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
+ assertEquals('a', mutationResult.getTargetKey().charValue());
+ assertSame(a, mutationResult.getOriginalTarget());
+ assertEquals('a', mutationResult.getChangedTarget().getKey().charValue());
+ assertSame(d, mutationResult.getOriginalRoot());
+ assertSame(dWithA2, mutationResult.getChangedRoot());
+ assertEquals(ModificationType.REBUILDING_CHANGE, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyDeletePresentNode() {
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ expectPossibleEntryfication(nodeFactory, a);
+ expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
+ BstModificationResult.rebalancingChange(a, null));
+
+ expect(balancePolicy.combine(same(nodeFactory), (SimpleNode) isNull(), (SimpleNode) isNull()))
+ .andReturn(null);
+
+ expectPossibleEntryfication(nodeFactory, b);
+ SimpleNode leafB = new SimpleNode('b', null, null);
+ expect(
+ balancePolicy.balance(same(nodeFactory), withKey('b'), (SimpleNode) isNull(),
+ (SimpleNode) isNull())).andReturn(leafB);
+
+ SimpleNode dWithLeafB = new SimpleNode('d', leafB, f);
+ expectPossibleEntryfication(nodeFactory, d);
+ expect(
+ balancePolicy.balance(same(nodeFactory), withKey('d'), same(leafB), same(f)))
+ .andReturn(dWithLeafB);
+ replay(nodeFactory, balancePolicy, modifier);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
+ assertEquals('a', mutationResult.getTargetKey().charValue());
+ assertEquals('a', mutationResult
+ .getOriginalTarget()
+ .getKey()
+ .charValue());
+ assertNull(mutationResult.getChangedTarget());
+ assertSame(d, mutationResult.getOriginalRoot());
+ assertSame(dWithLeafB, mutationResult.getChangedRoot());
+ assertEquals(ModificationType.REBALANCING_CHANGE, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyDeleteAbsentNode() {
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ expectPossibleEntryfication(nodeFactory, a);
+ expect(modifier.modify(eq('c'), (SimpleNode) isNull())).andReturn(
+ BstModificationResult.<SimpleNode> identity(null));
+ replay(nodeFactory, balancePolicy, modifier);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(Ordering.natural(), mutationRule, d, 'c');
+ assertEquals('c', mutationResult.getTargetKey().charValue());
+ assertEquals(d, mutationResult.getOriginalRoot());
+ assertEquals(d, mutationResult.getChangedRoot());
+ assertNull(mutationResult.getOriginalTarget());
+ assertNull(mutationResult.getChangedTarget());
+ assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ @SuppressWarnings("unchecked")
+ public void testModifyPathInsertPresentNode() {
+ // We wish to test that BstOperations & co. treat identity-different nodes as changed,
+ // instead of using SimpleNode.equals().
+ // d
+ // / \
+ // b f
+ // / \
+ // a g
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode b = new SimpleNode('b', a, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
+ BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
+ BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
+
+ expectPossibleEntryfication(nodeFactory, a);
+ expect(modifier.modify(eq('a'), withKey('a'))).andReturn(BstModificationResult.identity(a));
+ replay(nodeFactory, balancePolicy, modifier);
+ BstInOrderPath<SimpleNode> path = extension(pathFactory, d, LEFT, LEFT);
+ BstMutationRule<Character, SimpleNode> mutationRule =
+ BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
+ BstMutationResult<Character, SimpleNode> mutationResult =
+ BstOperations.mutate(path, mutationRule);
+ assertEquals('a', mutationResult.getTargetKey().charValue());
+ assertSame(a, mutationResult.getOriginalTarget());
+ assertSame(a, mutationResult.getChangedTarget());
+ assertSame(d, mutationResult.getOriginalRoot());
+ assertSame(d, mutationResult.getChangedRoot());
+ assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
+ verify(nodeFactory, balancePolicy, modifier);
+ }
+
+ @GwtIncompatible("EasyMock")
+ private SimpleNode withKey(final char c) {
+ reportMatcher(new IArgumentMatcher() {
+ @Override
+ public void appendTo(StringBuffer buffer) {
+ buffer.append("Expected BstNode with key ").append(c);
+ }
+
+ @Override
+ public boolean matches(Object argument) {
+ return argument instanceof SimpleNode
+ && ((SimpleNode) argument).getKey().charValue() == c;
+ }
+ });
+ return null;
+ }
+
+ /**
+ * The implementation may remove the children of a node it treats as an entry for safety. Expect
+ * this and handle it.
+ */
+ @GwtIncompatible("EasyMock")
+ private void expectPossibleEntryfication(BstNodeFactory<SimpleNode> factory, SimpleNode entry) {
+ expect(factory.createNode(same(entry), (SimpleNode) isNull(), (SimpleNode) isNull()))
+ .andReturn(new SimpleNode(entry.getKey(), null, null))
+ .times(0, 1);
+ }
+ public void testInsertMin1() {
+ // d
+ // / \
+ // b f
+ // \ \
+ // c g
+ SimpleNode c = new SimpleNode('c', null, null);
+ SimpleNode b = new SimpleNode('b', null, c);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode newRoot = BstOperations.insertMin(d, a, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "abcdfg");
+ }
+
+ public void testInsertMin2() {
+ // d
+ // / \
+ // b f
+ // \
+ // g
+ SimpleNode b = new SimpleNode('b', null, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode newRoot = BstOperations.insertMin(d, a, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "abdfg");
+ }
+
+ public void testInsertMinEmpty() {
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode newRoot = BstOperations.insertMin(null, a, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "a");
+ }
+
+ public void testInsertMax1() {
+ // d
+ // / \
+ // b f
+ // \ \
+ // c g
+ SimpleNode c = new SimpleNode('c', null, null);
+ SimpleNode b = new SimpleNode('b', null, c);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ SimpleNode h = new SimpleNode('h', null, null);
+ SimpleNode newRoot = BstOperations.insertMax(d, h, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "bcdfgh");
+ }
+
+ public void testInsertMax2() {
+ // d
+ // / \
+ // b f
+ // /
+ // e
+ SimpleNode b = new SimpleNode('b', null, null);
+ SimpleNode e = new SimpleNode('e', null, null);
+ SimpleNode f = new SimpleNode('f', e, null);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ SimpleNode h = new SimpleNode('h', null, null);
+ SimpleNode newRoot = BstOperations.insertMax(d, h, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "bdefh");
+ }
+
+ public void testInsertMaxEmpty() {
+ SimpleNode a = new SimpleNode('a', null, null);
+ SimpleNode newRoot = BstOperations.insertMax(null, a, nodeFactory, balancePolicy);
+ assertInOrderTraversalIs(newRoot, "a");
+ }
+
+ public void testExtractMin1() {
+ // d
+ // / \
+ // b f
+ // \ \
+ // c g
+ SimpleNode c = new SimpleNode('c', null, null);
+ SimpleNode b = new SimpleNode('b', null, c);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstMutationResult<Character, SimpleNode> extractMin =
+ BstOperations.extractMin(d, nodeFactory, balancePolicy);
+ assertEquals('b', extractMin.getTargetKey().charValue());
+ assertEquals(d, extractMin.getOriginalRoot());
+ assertEquals(b, extractMin.getOriginalTarget());
+ assertNull(extractMin.getChangedTarget());
+ assertInOrderTraversalIs(extractMin.getChangedRoot(), "cdfg");
+ }
+
+ public void testExtractMin2() {
+ // d
+ // / \
+ // b f
+ // \
+ // g
+ SimpleNode b = new SimpleNode('b', null, null);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstMutationResult<Character, SimpleNode> extractMin =
+ BstOperations.extractMin(d, nodeFactory, balancePolicy);
+ assertEquals('b', extractMin.getTargetKey().charValue());
+ assertEquals(d, extractMin.getOriginalRoot());
+ assertEquals(b, extractMin.getOriginalTarget());
+ assertNull(extractMin.getChangedTarget());
+ assertInOrderTraversalIs(extractMin.getChangedRoot(), "dfg");
+ }
+
+ public void testExtractMax1() {
+ // d
+ // / \
+ // b f
+ // \ \
+ // c g
+ SimpleNode c = new SimpleNode('c', null, null);
+ SimpleNode b = new SimpleNode('b', null, c);
+ SimpleNode g = new SimpleNode('g', null, null);
+ SimpleNode f = new SimpleNode('f', null, g);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstMutationResult<Character, SimpleNode> extractMax =
+ BstOperations.extractMax(d, nodeFactory, balancePolicy);
+ assertEquals('g', extractMax.getTargetKey().charValue());
+ assertEquals(d, extractMax.getOriginalRoot());
+ assertEquals(g, extractMax.getOriginalTarget());
+ assertNull(extractMax.getChangedTarget());
+ assertInOrderTraversalIs(extractMax.getChangedRoot(), "bcdf");
+ }
+
+ public void testExtractMax2() {
+ // d
+ // / \
+ // b f
+ // /
+ // e
+ SimpleNode b = new SimpleNode('b', null, null);
+ SimpleNode e = new SimpleNode('e', null, null);
+ SimpleNode f = new SimpleNode('f', e, null);
+ SimpleNode d = new SimpleNode('d', b, f);
+
+ BstMutationResult<Character, SimpleNode> extractMax =
+ BstOperations.extractMax(d, nodeFactory, balancePolicy);
+ assertEquals('f', extractMax.getTargetKey().charValue());
+ assertEquals(d, extractMax.getOriginalRoot());
+ assertEquals(f, extractMax.getOriginalTarget());
+ assertNull(extractMax.getChangedTarget());
+ assertInOrderTraversalIs(extractMax.getChangedRoot(), "bde");
+ }
+
+ @GwtIncompatible("NullPointerTester")
+ public void testNullPointers() throws Exception {
+ defaultNullPointerTester().testAllPublicStaticMethods(BstOperations.class);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-07 17:23:07 +0000