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.collect.BstSide.LEFT;
18import static com.google.common.collect.BstTesting.assertInOrderTraversalIs;
19import static com.google.common.collect.BstTesting.balancePolicy;
20import static com.google.common.collect.BstTesting.defaultNullPointerTester;
21import static com.google.common.collect.BstTesting.extension;
22import static com.google.common.collect.BstTesting.nodeFactory;
23import static com.google.common.collect.BstTesting.pathFactory;
24import static org.easymock.EasyMock.eq;
25import static org.easymock.EasyMock.expect;
26import static org.easymock.EasyMock.isNull;
27import static org.easymock.EasyMock.replay;
28import static org.easymock.EasyMock.reportMatcher;
29import static org.easymock.EasyMock.same;
30import static org.easymock.EasyMock.verify;
31
32import com.google.common.annotations.GwtCompatible;
33import com.google.common.annotations.GwtIncompatible;
34import com.google.common.collect.BstModificationResult.ModificationType;
35import com.google.common.collect.BstTesting.SimpleNode;
36
37import junit.framework.TestCase;
38
39import org.easymock.EasyMock;
40import org.easymock.IArgumentMatcher;
41
42/**
43 * Tests for {@code BstOperations}.
44 *
45 * @author Louis Wasserman
46 */
47@GwtCompatible(emulated = true)
48public class BstOperationsTest extends TestCase {
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
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")
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")
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")
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")
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")
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")
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")
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")
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  }
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
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
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
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
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
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
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
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
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
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")
541  public void testNullPointers() throws Exception {
542    defaultNullPointerTester().testAllPublicStaticMethods(BstOperations.class);
543  }
544}
545