• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
15 package com.google.common.collect;
16 
17 import static com.google.common.collect.BstSide.LEFT;
18 import static com.google.common.collect.BstTesting.assertInOrderTraversalIs;
19 import static com.google.common.collect.BstTesting.balancePolicy;
20 import static com.google.common.collect.BstTesting.defaultNullPointerTester;
21 import static com.google.common.collect.BstTesting.extension;
22 import static com.google.common.collect.BstTesting.nodeFactory;
23 import static com.google.common.collect.BstTesting.pathFactory;
24 import static org.easymock.EasyMock.eq;
25 import static org.easymock.EasyMock.expect;
26 import static org.easymock.EasyMock.isNull;
27 import static org.easymock.EasyMock.replay;
28 import static org.easymock.EasyMock.reportMatcher;
29 import static org.easymock.EasyMock.same;
30 import static org.easymock.EasyMock.verify;
31 
32 import com.google.common.annotations.GwtCompatible;
33 import com.google.common.annotations.GwtIncompatible;
34 import com.google.common.collect.BstModificationResult.ModificationType;
35 import com.google.common.collect.BstTesting.SimpleNode;
36 
37 import junit.framework.TestCase;
38 
39 import org.easymock.EasyMock;
40 import org.easymock.IArgumentMatcher;
41 
42 /**
43  * Tests for {@code BstOperations}.
44  *
45  * @author Louis Wasserman
46  */
47 @GwtCompatible(emulated = true)
48 public class BstOperationsTest extends TestCase {
testSeek1()49   public void testSeek1() {
50     //    d
51     //   / \
52     //  b   f
53     // /     \
54     // a     g
55     SimpleNode a = new SimpleNode('a', null, null);
56     SimpleNode b = new SimpleNode('b', a, null);
57     SimpleNode g = new SimpleNode('g', null, null);
58     SimpleNode f = new SimpleNode('f', null, g);
59     SimpleNode d = new SimpleNode('d', b, f);
60     assertEquals(a, BstOperations.seek(Ordering.natural(), d, 'a'));
61     assertEquals(b, BstOperations.seek(Ordering.natural(), d, 'b'));
62     assertNull(BstOperations.seek(Ordering.natural(), d, 'c'));
63     assertEquals(d, BstOperations.seek(Ordering.natural(), d, 'd'));
64     assertNull(BstOperations.seek(Ordering.natural(), d, 'e'));
65     assertEquals(f, BstOperations.seek(Ordering.natural(), d, 'f'));
66     assertEquals(g, BstOperations.seek(Ordering.natural(), d, 'g'));
67   }
68 
testSeek2()69   public void testSeek2() {
70     //    d
71     //   / \
72     //  b   f
73     //   \ /
74     //   c e
75     SimpleNode c = new SimpleNode('c', null, null);
76     SimpleNode b = new SimpleNode('b', null, c);
77     SimpleNode e = new SimpleNode('e', null, null);
78     SimpleNode f = new SimpleNode('f', e, null);
79     SimpleNode d = new SimpleNode('d', b, f);
80     assertNull(BstOperations.seek(Ordering.natural(), d, 'a'));
81     assertEquals(b, BstOperations.seek(Ordering.natural(), d, 'b'));
82     assertEquals(c, BstOperations.seek(Ordering.natural(), d, 'c'));
83     assertEquals(d, BstOperations.seek(Ordering.natural(), d, 'd'));
84     assertEquals(e, BstOperations.seek(Ordering.natural(), d, 'e'));
85     assertEquals(f, BstOperations.seek(Ordering.natural(), d, 'f'));
86     assertNull(BstOperations.seek(Ordering.natural(), d, 'g'));
87   }
88 
89   @GwtIncompatible("EasyMock")
90   @SuppressWarnings("unchecked")
testModifyInsertAbsentNode()91   public void testModifyInsertAbsentNode() {
92     //    d
93     //   / \
94     //  b   f
95     // /     \
96     // a     g
97     SimpleNode a = new SimpleNode('a', null, null);
98     SimpleNode b = new SimpleNode('b', a, null);
99     SimpleNode g = new SimpleNode('g', null, null);
100     SimpleNode f = new SimpleNode('f', null, g);
101     SimpleNode d = new SimpleNode('d', b, f);
102 
103     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
104     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
105     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
106 
107     SimpleNode c = new SimpleNode('c', null, null);
108     expect(modifier.modify(eq('c'), (SimpleNode) isNull())).andReturn(
109         BstModificationResult.rebalancingChange(null, c));
110 
111     expect(balancePolicy.balance(
112         same(nodeFactory), same(c), (SimpleNode) isNull(), (SimpleNode) isNull()))
113         .andReturn(c)
114         .times(0, 1);
115 
116     SimpleNode bWithC = new SimpleNode('b', a, c);
117     expectPossibleEntryfication(nodeFactory, b);
118     expect(balancePolicy.balance(
119         same(nodeFactory), withKey('b'), same(a), withKey('c')))
120         .andReturn(bWithC);
121 
122     SimpleNode dWithBWithC = new SimpleNode('d', bWithC, f);
123     expectPossibleEntryfication(nodeFactory, d);
124     expect(
125         balancePolicy.balance(same(nodeFactory), withKey('d'), same(bWithC), same(f)))
126         .andReturn(dWithBWithC);
127     replay(nodeFactory, balancePolicy, modifier);
128     BstMutationRule<Character, SimpleNode> mutationRule =
129         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
130     BstMutationResult<Character, SimpleNode> mutationResult =
131         BstOperations.mutate(Ordering.natural(), mutationRule, d, 'c');
132     assertEquals('c', mutationResult.getTargetKey().charValue());
133     assertNull(mutationResult.getOriginalTarget());
134     assertEquals('c', mutationResult
135         .getChangedTarget()
136         .getKey()
137         .charValue());
138     assertSame(d, mutationResult.getOriginalRoot());
139     assertSame(dWithBWithC, mutationResult.getChangedRoot());
140     assertEquals(ModificationType.REBALANCING_CHANGE, mutationResult.modificationType());
141     verify(nodeFactory, balancePolicy, modifier);
142   }
143 
144   @GwtIncompatible("EasyMock")
145   @SuppressWarnings("unchecked")
testModifyInsertPresentNode()146   public void testModifyInsertPresentNode() {
147     // We wish to test that BstOperations & co. treat IDENTITY modifications as the same.
148     //    d
149     //   / \
150     //  b   f
151     // /     \
152     // a     g
153     SimpleNode a = new SimpleNode('a', null, null);
154     SimpleNode b = new SimpleNode('b', a, null);
155     SimpleNode g = new SimpleNode('g', null, null);
156     SimpleNode f = new SimpleNode('f', null, g);
157     SimpleNode d = new SimpleNode('d', b, f);
158 
159     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
160     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
161     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
162 
163     expectPossibleEntryfication(nodeFactory, a);
164     expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
165         BstModificationResult.identity(a));
166     replay(nodeFactory, balancePolicy, modifier);
167     BstMutationRule<Character, SimpleNode> mutationRule =
168         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
169     BstMutationResult<Character, SimpleNode> mutationResult =
170         BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
171     assertEquals('a', mutationResult.getTargetKey().charValue());
172     assertSame(a, mutationResult.getOriginalTarget());
173     assertSame(a, mutationResult.getChangedTarget());
174     assertSame(d, mutationResult.getOriginalRoot());
175     assertSame(d, mutationResult.getChangedRoot());
176     assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
177     verify(nodeFactory, balancePolicy, modifier);
178   }
179 
180   @GwtIncompatible("EasyMock")
181   @SuppressWarnings("unchecked")
testModifyInsertInequivalentNode()182   public void testModifyInsertInequivalentNode() {
183     // We wish to test that BstOperations & co. treat non-equivalent() nodes as different.
184     //    d
185     //   / \
186     //  b   f
187     // /     \
188     // a     g
189     SimpleNode a = new SimpleNode('a', null, null);
190     SimpleNode b = new SimpleNode('b', a, null);
191     SimpleNode g = new SimpleNode('g', null, null);
192     SimpleNode f = new SimpleNode('f', null, g);
193     SimpleNode d = new SimpleNode('d', b, f);
194 
195     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
196     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
197     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
198 
199     expectPossibleEntryfication(nodeFactory, a);
200     SimpleNode a2 = new SimpleNode('a', null, null);
201     expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
202         BstModificationResult.rebuildingChange(a, a2));
203 
204     expectPossibleEntryfication(nodeFactory, a2);
205 
206     SimpleNode bWithA2 = new SimpleNode('b', a2, null);
207     expect(nodeFactory.createNode(same(b), withKey('a'), (SimpleNode) isNull())).andReturn(
208         bWithA2);
209 
210     SimpleNode dWithA2 = new SimpleNode('d', bWithA2, f);
211     expect(nodeFactory.createNode(same(d), same(bWithA2), same(f))).andReturn(
212         dWithA2);
213 
214     replay(nodeFactory, balancePolicy, modifier);
215     BstMutationRule<Character, SimpleNode> mutationRule =
216         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
217     BstMutationResult<Character, SimpleNode> mutationResult =
218         BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
219     assertEquals('a', mutationResult.getTargetKey().charValue());
220     assertSame(a, mutationResult.getOriginalTarget());
221     assertEquals('a', mutationResult.getChangedTarget().getKey().charValue());
222     assertSame(d, mutationResult.getOriginalRoot());
223     assertSame(dWithA2, mutationResult.getChangedRoot());
224     assertEquals(ModificationType.REBUILDING_CHANGE, mutationResult.modificationType());
225     verify(nodeFactory, balancePolicy, modifier);
226   }
227 
228   @GwtIncompatible("EasyMock")
229   @SuppressWarnings("unchecked")
testModifyDeletePresentNode()230   public void testModifyDeletePresentNode() {
231     //    d
232     //   / \
233     //  b   f
234     // /     \
235     // a     g
236     SimpleNode a = new SimpleNode('a', null, null);
237     SimpleNode b = new SimpleNode('b', a, null);
238     SimpleNode g = new SimpleNode('g', null, null);
239     SimpleNode f = new SimpleNode('f', null, g);
240     SimpleNode d = new SimpleNode('d', b, f);
241 
242     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
243     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
244     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
245 
246     expectPossibleEntryfication(nodeFactory, a);
247     expect(modifier.modify(eq('a'), withKey('a'))).andReturn(
248         BstModificationResult.rebalancingChange(a, null));
249 
250     expect(balancePolicy.combine(same(nodeFactory), (SimpleNode) isNull(), (SimpleNode) isNull()))
251         .andReturn(null);
252 
253     expectPossibleEntryfication(nodeFactory, b);
254     SimpleNode leafB = new SimpleNode('b', null, null);
255     expect(
256         balancePolicy.balance(same(nodeFactory), withKey('b'), (SimpleNode) isNull(),
257             (SimpleNode) isNull())).andReturn(leafB);
258 
259     SimpleNode dWithLeafB = new SimpleNode('d', leafB, f);
260     expectPossibleEntryfication(nodeFactory, d);
261     expect(
262         balancePolicy.balance(same(nodeFactory), withKey('d'), same(leafB), same(f)))
263         .andReturn(dWithLeafB);
264     replay(nodeFactory, balancePolicy, modifier);
265     BstMutationRule<Character, SimpleNode> mutationRule =
266         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
267     BstMutationResult<Character, SimpleNode> mutationResult =
268         BstOperations.mutate(Ordering.natural(), mutationRule, d, 'a');
269     assertEquals('a', mutationResult.getTargetKey().charValue());
270     assertEquals('a', mutationResult
271         .getOriginalTarget()
272         .getKey()
273         .charValue());
274     assertNull(mutationResult.getChangedTarget());
275     assertSame(d, mutationResult.getOriginalRoot());
276     assertSame(dWithLeafB, mutationResult.getChangedRoot());
277     assertEquals(ModificationType.REBALANCING_CHANGE, mutationResult.modificationType());
278     verify(nodeFactory, balancePolicy, modifier);
279   }
280 
281   @GwtIncompatible("EasyMock")
282   @SuppressWarnings("unchecked")
testModifyDeleteAbsentNode()283   public void testModifyDeleteAbsentNode() {
284     //    d
285     //   / \
286     //  b   f
287     // /     \
288     // a     g
289     SimpleNode a = new SimpleNode('a', null, null);
290     SimpleNode b = new SimpleNode('b', a, null);
291     SimpleNode g = new SimpleNode('g', null, null);
292     SimpleNode f = new SimpleNode('f', null, g);
293     SimpleNode d = new SimpleNode('d', b, f);
294 
295     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
296     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
297     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
298 
299     expectPossibleEntryfication(nodeFactory, a);
300     expect(modifier.modify(eq('c'), (SimpleNode) isNull())).andReturn(
301         BstModificationResult.<SimpleNode> identity(null));
302     replay(nodeFactory, balancePolicy, modifier);
303     BstMutationRule<Character, SimpleNode> mutationRule =
304         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
305     BstMutationResult<Character, SimpleNode> mutationResult =
306         BstOperations.mutate(Ordering.natural(), mutationRule, d, 'c');
307     assertEquals('c', mutationResult.getTargetKey().charValue());
308     assertEquals(d, mutationResult.getOriginalRoot());
309     assertEquals(d, mutationResult.getChangedRoot());
310     assertNull(mutationResult.getOriginalTarget());
311     assertNull(mutationResult.getChangedTarget());
312     assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
313     verify(nodeFactory, balancePolicy, modifier);
314   }
315 
316   @GwtIncompatible("EasyMock")
317   @SuppressWarnings("unchecked")
testModifyPathInsertPresentNode()318   public void testModifyPathInsertPresentNode() {
319     // We wish to test that BstOperations & co. treat identity-different nodes as changed,
320     // instead of using SimpleNode.equals().
321     //    d
322     //   / \
323     //  b   f
324     // /     \
325     // a     g
326     SimpleNode a = new SimpleNode('a', null, null);
327     SimpleNode b = new SimpleNode('b', a, null);
328     SimpleNode g = new SimpleNode('g', null, null);
329     SimpleNode f = new SimpleNode('f', null, g);
330     SimpleNode d = new SimpleNode('d', b, f);
331 
332     BstNodeFactory<SimpleNode> nodeFactory = EasyMock.createStrictMock(BstNodeFactory.class);
333     BstBalancePolicy<SimpleNode> balancePolicy = EasyMock.createStrictMock(BstBalancePolicy.class);
334     BstModifier<Character, SimpleNode> modifier = EasyMock.createStrictMock(BstModifier.class);
335 
336     expectPossibleEntryfication(nodeFactory, a);
337     expect(modifier.modify(eq('a'), withKey('a'))).andReturn(BstModificationResult.identity(a));
338     replay(nodeFactory, balancePolicy, modifier);
339     BstInOrderPath<SimpleNode> path = extension(pathFactory, d, LEFT, LEFT);
340     BstMutationRule<Character, SimpleNode> mutationRule =
341         BstMutationRule.createRule(modifier, balancePolicy, nodeFactory);
342     BstMutationResult<Character, SimpleNode> mutationResult =
343         BstOperations.mutate(path, mutationRule);
344     assertEquals('a', mutationResult.getTargetKey().charValue());
345     assertSame(a, mutationResult.getOriginalTarget());
346     assertSame(a, mutationResult.getChangedTarget());
347     assertSame(d, mutationResult.getOriginalRoot());
348     assertSame(d, mutationResult.getChangedRoot());
349     assertEquals(ModificationType.IDENTITY, mutationResult.modificationType());
350     verify(nodeFactory, balancePolicy, modifier);
351   }
352 
353   @GwtIncompatible("EasyMock")
withKey(final char c)354   private SimpleNode withKey(final char c) {
355     reportMatcher(new IArgumentMatcher() {
356       @Override
357       public void appendTo(StringBuffer buffer) {
358         buffer.append("Expected BstNode with key ").append(c);
359       }
360 
361       @Override
362       public boolean matches(Object argument) {
363         return argument instanceof SimpleNode
364             && ((SimpleNode) argument).getKey().charValue() == c;
365       }
366     });
367     return null;
368   }
369 
370   /**
371    * The implementation may remove the children of a node it treats as an entry for safety. Expect
372    * this and handle it.
373    */
374   @GwtIncompatible("EasyMock")
expectPossibleEntryfication(BstNodeFactory<SimpleNode> factory, SimpleNode entry)375   private void expectPossibleEntryfication(BstNodeFactory<SimpleNode> factory, SimpleNode entry) {
376     expect(factory.createNode(same(entry), (SimpleNode) isNull(), (SimpleNode) isNull()))
377         .andReturn(new SimpleNode(entry.getKey(), null, null))
378         .times(0, 1);
379   }
testInsertMin1()380   public void testInsertMin1() {
381     //    d
382     //   / \
383     //  b   f
384     //   \   \
385     //   c   g
386     SimpleNode c = new SimpleNode('c', null, null);
387     SimpleNode b = new SimpleNode('b', null, c);
388     SimpleNode g = new SimpleNode('g', null, null);
389     SimpleNode f = new SimpleNode('f', null, g);
390     SimpleNode d = new SimpleNode('d', b, f);
391 
392     SimpleNode a = new SimpleNode('a', null, null);
393     SimpleNode newRoot = BstOperations.insertMin(d, a, nodeFactory, balancePolicy);
394     assertInOrderTraversalIs(newRoot, "abcdfg");
395   }
396 
testInsertMin2()397   public void testInsertMin2() {
398     //    d
399     //   / \
400     //  b   f
401     //       \
402     //       g
403     SimpleNode b = new SimpleNode('b', null, null);
404     SimpleNode g = new SimpleNode('g', null, null);
405     SimpleNode f = new SimpleNode('f', null, g);
406     SimpleNode d = new SimpleNode('d', b, f);
407 
408     SimpleNode a = new SimpleNode('a', null, null);
409     SimpleNode newRoot = BstOperations.insertMin(d, a, nodeFactory, balancePolicy);
410     assertInOrderTraversalIs(newRoot, "abdfg");
411   }
412 
testInsertMinEmpty()413   public void testInsertMinEmpty() {
414     SimpleNode a = new SimpleNode('a', null, null);
415     SimpleNode newRoot = BstOperations.insertMin(null, a, nodeFactory, balancePolicy);
416     assertInOrderTraversalIs(newRoot, "a");
417   }
418 
testInsertMax1()419   public void testInsertMax1() {
420     //    d
421     //   / \
422     //  b   f
423     //   \   \
424     //   c   g
425     SimpleNode c = new SimpleNode('c', null, null);
426     SimpleNode b = new SimpleNode('b', null, c);
427     SimpleNode g = new SimpleNode('g', null, null);
428     SimpleNode f = new SimpleNode('f', null, g);
429     SimpleNode d = new SimpleNode('d', b, f);
430 
431     SimpleNode h = new SimpleNode('h', null, null);
432     SimpleNode newRoot = BstOperations.insertMax(d, h, nodeFactory, balancePolicy);
433     assertInOrderTraversalIs(newRoot, "bcdfgh");
434   }
435 
testInsertMax2()436   public void testInsertMax2() {
437     //    d
438     //   / \
439     //  b   f
440     //     /
441     //     e
442     SimpleNode b = new SimpleNode('b', null, null);
443     SimpleNode e = new SimpleNode('e', null, null);
444     SimpleNode f = new SimpleNode('f', e, null);
445     SimpleNode d = new SimpleNode('d', b, f);
446 
447     SimpleNode h = new SimpleNode('h', null, null);
448     SimpleNode newRoot = BstOperations.insertMax(d, h, nodeFactory, balancePolicy);
449     assertInOrderTraversalIs(newRoot, "bdefh");
450   }
451 
testInsertMaxEmpty()452   public void testInsertMaxEmpty() {
453     SimpleNode a = new SimpleNode('a', null, null);
454     SimpleNode newRoot = BstOperations.insertMax(null, a, nodeFactory, balancePolicy);
455     assertInOrderTraversalIs(newRoot, "a");
456   }
457 
testExtractMin1()458   public void testExtractMin1() {
459     //    d
460     //   / \
461     //  b   f
462     //   \   \
463     //   c   g
464     SimpleNode c = new SimpleNode('c', null, null);
465     SimpleNode b = new SimpleNode('b', null, c);
466     SimpleNode g = new SimpleNode('g', null, null);
467     SimpleNode f = new SimpleNode('f', null, g);
468     SimpleNode d = new SimpleNode('d', b, f);
469 
470     BstMutationResult<Character, SimpleNode> extractMin =
471         BstOperations.extractMin(d, nodeFactory, balancePolicy);
472     assertEquals('b', extractMin.getTargetKey().charValue());
473     assertEquals(d, extractMin.getOriginalRoot());
474     assertEquals(b, extractMin.getOriginalTarget());
475     assertNull(extractMin.getChangedTarget());
476     assertInOrderTraversalIs(extractMin.getChangedRoot(), "cdfg");
477   }
478 
testExtractMin2()479   public void testExtractMin2() {
480     //    d
481     //   / \
482     //  b   f
483     //       \
484     //       g
485     SimpleNode b = new SimpleNode('b', null, null);
486     SimpleNode g = new SimpleNode('g', null, null);
487     SimpleNode f = new SimpleNode('f', null, g);
488     SimpleNode d = new SimpleNode('d', b, f);
489 
490     BstMutationResult<Character, SimpleNode> extractMin =
491         BstOperations.extractMin(d, nodeFactory, balancePolicy);
492     assertEquals('b', extractMin.getTargetKey().charValue());
493     assertEquals(d, extractMin.getOriginalRoot());
494     assertEquals(b, extractMin.getOriginalTarget());
495     assertNull(extractMin.getChangedTarget());
496     assertInOrderTraversalIs(extractMin.getChangedRoot(), "dfg");
497   }
498 
testExtractMax1()499   public void testExtractMax1() {
500     //    d
501     //   / \
502     //  b   f
503     //   \   \
504     //   c   g
505     SimpleNode c = new SimpleNode('c', null, null);
506     SimpleNode b = new SimpleNode('b', null, c);
507     SimpleNode g = new SimpleNode('g', null, null);
508     SimpleNode f = new SimpleNode('f', null, g);
509     SimpleNode d = new SimpleNode('d', b, f);
510 
511     BstMutationResult<Character, SimpleNode> extractMax =
512         BstOperations.extractMax(d, nodeFactory, balancePolicy);
513     assertEquals('g', extractMax.getTargetKey().charValue());
514     assertEquals(d, extractMax.getOriginalRoot());
515     assertEquals(g, extractMax.getOriginalTarget());
516     assertNull(extractMax.getChangedTarget());
517     assertInOrderTraversalIs(extractMax.getChangedRoot(), "bcdf");
518   }
519 
testExtractMax2()520   public void testExtractMax2() {
521     //    d
522     //   / \
523     //  b   f
524     //     /
525     //     e
526     SimpleNode b = new SimpleNode('b', null, null);
527     SimpleNode e = new SimpleNode('e', null, null);
528     SimpleNode f = new SimpleNode('f', e, null);
529     SimpleNode d = new SimpleNode('d', b, f);
530 
531     BstMutationResult<Character, SimpleNode> extractMax =
532         BstOperations.extractMax(d, nodeFactory, balancePolicy);
533     assertEquals('f', extractMax.getTargetKey().charValue());
534     assertEquals(d, extractMax.getOriginalRoot());
535     assertEquals(f, extractMax.getOriginalTarget());
536     assertNull(extractMax.getChangedTarget());
537     assertInOrderTraversalIs(extractMax.getChangedRoot(), "bde");
538   }
539 
540   @GwtIncompatible("NullPointerTester")
testNullPointers()541   public void testNullPointers() throws Exception {
542     defaultNullPointerTester().testAllPublicStaticMethods(BstOperations.class);
543   }
544 }
545