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 { 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
