1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.collect.Lists.newArrayList; 21import static com.google.common.testing.SerializableTester.reserialize; 22import static com.google.common.testing.SerializableTester.reserializeAndAssert; 23import static java.util.Arrays.asList; 24import static org.truth0.Truth.ASSERT; 25 26import com.google.common.annotations.GwtCompatible; 27import com.google.common.base.Function; 28import com.google.common.base.Functions; 29import com.google.common.collect.Ordering.ArbitraryOrdering; 30import com.google.common.collect.Ordering.IncomparableValueException; 31import com.google.common.collect.testing.Helpers; 32import com.google.common.primitives.Ints; 33import com.google.common.testing.EqualsTester; 34 35import junit.framework.TestCase; 36 37import java.util.Arrays; 38import java.util.Collections; 39import java.util.Comparator; 40import java.util.Iterator; 41import java.util.List; 42import java.util.Random; 43import java.util.RandomAccess; 44 45import javax.annotation.Nullable; 46 47/** 48 * Unit tests for {@code Ordering}. 49 * 50 * @author Jesse Wilson 51 */ 52@GwtCompatible(emulated = true) 53public class OrderingTest extends TestCase { 54 // TODO(cpovirk): some of these are inexplicably slow (20-30s) under GWT 55 56 private final Ordering<Number> numberOrdering = new NumberOrdering(); 57 58 public void testAllEqual() { 59 Ordering<Object> comparator = Ordering.allEqual(); 60 assertSame(comparator, comparator.reverse()); 61 62 assertEquals(comparator.compare(null, null), 0); 63 assertEquals(comparator.compare(new Object(), new Object()), 0); 64 assertEquals(comparator.compare("apples", "oranges"), 0); 65 assertSame(comparator, reserialize(comparator)); 66 assertEquals("Ordering.allEqual()", comparator.toString()); 67 68 List<String> strings = ImmutableList.of("b", "a", "d", "c"); 69 assertEquals(strings, comparator.sortedCopy(strings)); 70 assertEquals(strings, comparator.immutableSortedCopy(strings)); 71 } 72 73 public void testNatural() { 74 Ordering<Integer> comparator = Ordering.natural(); 75 Helpers.testComparator(comparator, 76 Integer.MIN_VALUE, -1, 0, 1, Integer.MAX_VALUE); 77 try { 78 comparator.compare(1, null); 79 fail(); 80 } catch (NullPointerException expected) {} 81 try { 82 comparator.compare(null, 2); 83 fail(); 84 } catch (NullPointerException expected) {} 85 try { 86 comparator.compare(null, null); 87 fail(); 88 } catch (NullPointerException expected) {} 89 assertSame(comparator, reserialize(comparator)); 90 assertEquals("Ordering.natural()", comparator.toString()); 91 } 92 93 public void testFrom() { 94 Ordering<String> caseInsensitiveOrdering 95 = Ordering.from(String.CASE_INSENSITIVE_ORDER); 96 assertEquals(0, caseInsensitiveOrdering.compare("A", "a")); 97 assertTrue(caseInsensitiveOrdering.compare("a", "B") < 0); 98 assertTrue(caseInsensitiveOrdering.compare("B", "a") > 0); 99 100 @SuppressWarnings("deprecation") // test of deprecated method 101 Ordering<String> orderingFromOrdering = 102 Ordering.from(Ordering.<String>natural()); 103 new EqualsTester() 104 .addEqualityGroup(caseInsensitiveOrdering, Ordering.from(String.CASE_INSENSITIVE_ORDER)) 105 .addEqualityGroup(orderingFromOrdering, Ordering.natural()) 106 .testEquals(); 107 } 108 109 public void testExplicit_none() { 110 Comparator<Integer> c 111 = Ordering.explicit(Collections.<Integer>emptyList()); 112 try { 113 c.compare(0, 0); 114 fail(); 115 } catch (IncomparableValueException expected) { 116 assertEquals(0, expected.value); 117 } 118 reserializeAndAssert(c); 119 } 120 121 public void testExplicit_one() { 122 Comparator<Integer> c = Ordering.explicit(0); 123 assertEquals(0, c.compare(0, 0)); 124 try { 125 c.compare(0, 1); 126 fail(); 127 } catch (IncomparableValueException expected) { 128 assertEquals(1, expected.value); 129 } 130 reserializeAndAssert(c); 131 assertEquals("Ordering.explicit([0])", c.toString()); 132 } 133 134 public void testExplicit_two() { 135 Comparator<Integer> c = Ordering.explicit(42, 5); 136 assertEquals(0, c.compare(5, 5)); 137 assertTrue(c.compare(5, 42) > 0); 138 assertTrue(c.compare(42, 5) < 0); 139 try { 140 c.compare(5, 666); 141 fail(); 142 } catch (IncomparableValueException expected) { 143 assertEquals(666, expected.value); 144 } 145 new EqualsTester() 146 .addEqualityGroup(c, Ordering.explicit(42, 5)) 147 .addEqualityGroup(Ordering.explicit(5, 42)) 148 .addEqualityGroup(Ordering.explicit(42)) 149 .testEquals(); 150 reserializeAndAssert(c); 151 } 152 153 public void testExplicit_sortingExample() { 154 Comparator<Integer> c 155 = Ordering.explicit(2, 8, 6, 1, 7, 5, 3, 4, 0, 9); 156 List<Integer> list = Arrays.asList(0, 3, 5, 6, 7, 8, 9); 157 Collections.sort(list, c); 158 ASSERT.that(list).has().exactly(8, 6, 7, 5, 3, 0, 9).inOrder(); 159 reserializeAndAssert(c); 160 } 161 162 public void testExplicit_withDuplicates() { 163 try { 164 Ordering.explicit(1, 2, 3, 4, 2); 165 fail(); 166 } catch (IllegalArgumentException expected) { 167 } 168 } 169 170 // A more limited test than the one that follows, but this one uses the 171 // actual public API. 172 public void testArbitrary_withoutCollisions() { 173 List<Object> list = Lists.newArrayList(); 174 for (int i = 0; i < 50; i++) { 175 list.add(new Object()); 176 } 177 178 Ordering<Object> arbitrary = Ordering.arbitrary(); 179 Collections.sort(list, arbitrary); 180 181 // Now we don't care what order it's put the list in, only that 182 // comparing any pair of elements gives the answer we expect. 183 Helpers.testComparator(arbitrary, list); 184 185 assertEquals("Ordering.arbitrary()", arbitrary.toString()); 186 } 187 188 public void testArbitrary_withCollisions() { 189 List<Integer> list = Lists.newArrayList(); 190 for (int i = 0; i < 50; i++) { 191 list.add(i); 192 } 193 194 Ordering<Object> arbitrary = new ArbitraryOrdering() { 195 @Override int identityHashCode(Object object) { 196 return ((Integer) object) % 5; // fake tons of collisions! 197 } 198 }; 199 200 // Don't let the elements be in such a predictable order 201 list = shuffledCopy(list, new Random(1)); 202 203 Collections.sort(list, arbitrary); 204 205 // Now we don't care what order it's put the list in, only that 206 // comparing any pair of elements gives the answer we expect. 207 Helpers.testComparator(arbitrary, list); 208 } 209 210 public void testUsingToString() { 211 Ordering<Object> ordering = Ordering.usingToString(); 212 Helpers.testComparator(ordering, 1, 12, 124, 2); 213 assertEquals("Ordering.usingToString()", ordering.toString()); 214 assertSame(ordering, reserialize(ordering)); 215 } 216 217 // use an enum to get easy serializability 218 private enum CharAtFunction implements Function<String, Character> { 219 AT0(0), 220 AT1(1), 221 AT2(2), 222 AT3(3), 223 AT4(4), 224 AT5(5), 225 ; 226 227 final int index; 228 CharAtFunction(int index) { 229 this.index = index; 230 } 231 @Override 232 public Character apply(String string) { 233 return string.charAt(index); 234 } 235 } 236 237 private static Ordering<String> byCharAt(int index) { 238 return Ordering.natural().onResultOf(CharAtFunction.values()[index]); 239 } 240 241 public void testCompound_static() { 242 Comparator<String> comparator = Ordering.compound(ImmutableList.of( 243 byCharAt(0), byCharAt(1), byCharAt(2), 244 byCharAt(3), byCharAt(4), byCharAt(5))); 245 Helpers.testComparator(comparator, ImmutableList.of( 246 "applesauce", 247 "apricot", 248 "artichoke", 249 "banality", 250 "banana", 251 "banquet", 252 "tangelo", 253 "tangerine")); 254 reserializeAndAssert(comparator); 255 } 256 257 public void testCompound_instance() { 258 Comparator<String> comparator = byCharAt(1).compound(byCharAt(0)); 259 Helpers.testComparator(comparator, ImmutableList.of( 260 "red", 261 "yellow", 262 "violet", 263 "blue", 264 "indigo", 265 "green", 266 "orange")); 267 } 268 269 public void testCompound_instance_generics() { 270 Ordering<Object> objects = Ordering.explicit((Object) 1); 271 Ordering<Number> numbers = Ordering.explicit((Number) 1); 272 Ordering<Integer> integers = Ordering.explicit(1); 273 274 // Like by like equals like 275 Ordering<Number> a = numbers.compound(numbers); 276 277 // The compound takes the more specific type of the two, regardless of order 278 279 Ordering<Number> b = numbers.compound(objects); 280 Ordering<Number> c = objects.compound(numbers); 281 282 Ordering<Integer> d = numbers.compound(integers); 283 Ordering<Integer> e = integers.compound(numbers); 284 285 // This works with three levels too (IDEA falsely reports errors as noted 286 // below. Both javac and eclipse handle these cases correctly.) 287 288 Ordering<Number> f = numbers.compound(objects).compound(objects); //bad IDEA 289 Ordering<Number> g = objects.compound(numbers).compound(objects); 290 Ordering<Number> h = objects.compound(objects).compound(numbers); 291 292 Ordering<Number> i = numbers.compound(objects.compound(objects)); 293 Ordering<Number> j = objects.compound(numbers.compound(objects)); //bad IDEA 294 Ordering<Number> k = objects.compound(objects.compound(numbers)); 295 296 // You can also arbitrarily assign a more restricted type - not an intended 297 // feature, exactly, but unavoidable (I think) and harmless 298 Ordering<Integer> l = objects.compound(numbers); 299 300 // This correctly doesn't work: 301 // Ordering<Object> m = numbers.compound(objects); 302 303 // Sadly, the following works in javac 1.6, but at least it fails for 304 // eclipse, and is *correctly* highlighted red in IDEA. 305 // Ordering<Object> n = objects.compound(numbers); 306 } 307 308 public void testReverse() { 309 Ordering<Number> reverseOrder = numberOrdering.reverse(); 310 Helpers.testComparator(reverseOrder, 311 Integer.MAX_VALUE, 1, 0, -1, Integer.MIN_VALUE); 312 313 new EqualsTester() 314 .addEqualityGroup(reverseOrder, numberOrdering.reverse()) 315 .addEqualityGroup(Ordering.natural().reverse()) 316 .addEqualityGroup(Collections.reverseOrder()) 317 .testEquals(); 318 } 319 320 public void testReverseOfReverseSameAsForward() { 321 // Not guaranteed by spec, but it works, and saves us from testing 322 // exhaustively 323 assertSame(numberOrdering, numberOrdering.reverse().reverse()); 324 } 325 326 private enum StringLengthFunction implements Function<String, Integer> { 327 StringLength; 328 329 @Override 330 public Integer apply(String string) { 331 return string.length(); 332 } 333 } 334 335 private static final Ordering<Integer> DECREASING_INTEGER 336 = Ordering.natural().reverse(); 337 338 public void testOnResultOf_natural() { 339 Comparator<String> comparator 340 = Ordering.natural().onResultOf(StringLengthFunction.StringLength); 341 assertTrue(comparator.compare("to", "be") == 0); 342 assertTrue(comparator.compare("or", "not") < 0); 343 assertTrue(comparator.compare("that", "to") > 0); 344 345 new EqualsTester() 346 .addEqualityGroup( 347 comparator, 348 Ordering.natural().onResultOf(StringLengthFunction.StringLength)) 349 .addEqualityGroup(DECREASING_INTEGER) 350 .testEquals(); 351 reserializeAndAssert(comparator); 352 assertEquals("Ordering.natural().onResultOf(StringLength)", 353 comparator.toString()); 354 } 355 356 public void testOnResultOf_chained() { 357 Comparator<String> comparator = DECREASING_INTEGER.onResultOf( 358 StringLengthFunction.StringLength); 359 assertTrue(comparator.compare("to", "be") == 0); 360 assertTrue(comparator.compare("not", "or") < 0); 361 assertTrue(comparator.compare("to", "that") > 0); 362 363 new EqualsTester() 364 .addEqualityGroup( 365 comparator, 366 DECREASING_INTEGER.onResultOf(StringLengthFunction.StringLength)) 367 .addEqualityGroup( 368 DECREASING_INTEGER.onResultOf(Functions.constant(1))) 369 .addEqualityGroup(Ordering.natural()) 370 .testEquals(); 371 reserializeAndAssert(comparator); 372 assertEquals("Ordering.natural().reverse().onResultOf(StringLength)", 373 comparator.toString()); 374 } 375 376 @SuppressWarnings("unchecked") // dang varargs 377 public void testLexicographical() { 378 Ordering<String> ordering = Ordering.natural(); 379 Ordering<Iterable<String>> lexy = ordering.lexicographical(); 380 381 ImmutableList<String> empty = ImmutableList.of(); 382 ImmutableList<String> a = ImmutableList.of("a"); 383 ImmutableList<String> aa = ImmutableList.of("a", "a"); 384 ImmutableList<String> ab = ImmutableList.of("a", "b"); 385 ImmutableList<String> b = ImmutableList.of("b"); 386 387 Helpers.testComparator(lexy, empty, a, aa, ab, b); 388 389 new EqualsTester() 390 .addEqualityGroup(lexy, ordering.lexicographical()) 391 .addEqualityGroup(numberOrdering.lexicographical()) 392 .addEqualityGroup(Ordering.natural()) 393 .testEquals(); 394 } 395 396 public void testNullsFirst() { 397 Ordering<Integer> ordering = Ordering.natural().nullsFirst(); 398 Helpers.testComparator(ordering, null, Integer.MIN_VALUE, 0, 1); 399 400 new EqualsTester() 401 .addEqualityGroup(ordering, Ordering.natural().nullsFirst()) 402 .addEqualityGroup(numberOrdering.nullsFirst()) 403 .addEqualityGroup(Ordering.natural()) 404 .testEquals(); 405 } 406 407 public void testNullsLast() { 408 Ordering<Integer> ordering = Ordering.natural().nullsLast(); 409 Helpers.testComparator(ordering, 0, 1, Integer.MAX_VALUE, null); 410 411 new EqualsTester() 412 .addEqualityGroup(ordering, Ordering.natural().nullsLast()) 413 .addEqualityGroup(numberOrdering.nullsLast()) 414 .addEqualityGroup(Ordering.natural()) 415 .testEquals(); 416 } 417 418 public void testBinarySearch() { 419 List<Integer> ints = Lists.newArrayList(0, 2, 3, 5, 7, 9); 420 assertEquals(4, numberOrdering.binarySearch(ints, 7)); 421 } 422 423 public void testSortedCopy() { 424 List<Integer> unsortedInts = Collections.unmodifiableList( 425 Arrays.asList(5, 0, 3, null, 0, 9)); 426 List<Integer> sortedInts = 427 numberOrdering.nullsLast().sortedCopy(unsortedInts); 428 assertEquals(Arrays.asList(0, 0, 3, 5, 9, null), sortedInts); 429 430 assertEquals(Collections.emptyList(), 431 numberOrdering.sortedCopy(Collections.<Integer>emptyList())); 432 } 433 434 public void testImmutableSortedCopy() { 435 ImmutableList<Integer> unsortedInts = ImmutableList.of(5, 3, 0, 9, 3); 436 ImmutableList<Integer> sortedInts 437 = numberOrdering.immutableSortedCopy(unsortedInts); 438 assertEquals(Arrays.asList(0, 3, 3, 5, 9), sortedInts); 439 440 assertEquals(Collections.<Integer>emptyList(), 441 numberOrdering.immutableSortedCopy(Collections.<Integer>emptyList())); 442 443 List<Integer> listWithNull = Arrays.asList(5, 3, null, 9); 444 try { 445 Ordering.natural().nullsFirst().immutableSortedCopy(listWithNull); 446 fail(); 447 } catch (NullPointerException expected) { 448 } 449 } 450 451 public void testIsOrdered() { 452 assertFalse(numberOrdering.isOrdered(asList(5, 3, 0, 9))); 453 assertFalse(numberOrdering.isOrdered(asList(0, 5, 3, 9))); 454 assertTrue(numberOrdering.isOrdered(asList(0, 3, 5, 9))); 455 assertTrue(numberOrdering.isOrdered(asList(0, 0, 3, 3))); 456 assertTrue(numberOrdering.isOrdered(asList(0, 3))); 457 assertTrue(numberOrdering.isOrdered(Collections.singleton(1))); 458 assertTrue(numberOrdering.isOrdered(Collections.<Integer>emptyList())); 459 } 460 461 public void testIsStrictlyOrdered() { 462 assertFalse(numberOrdering.isStrictlyOrdered(asList(5, 3, 0, 9))); 463 assertFalse(numberOrdering.isStrictlyOrdered(asList(0, 5, 3, 9))); 464 assertTrue(numberOrdering.isStrictlyOrdered(asList(0, 3, 5, 9))); 465 assertFalse(numberOrdering.isStrictlyOrdered(asList(0, 0, 3, 3))); 466 assertTrue(numberOrdering.isStrictlyOrdered(asList(0, 3))); 467 assertTrue(numberOrdering.isStrictlyOrdered(Collections.singleton(1))); 468 assertTrue(numberOrdering.isStrictlyOrdered( 469 Collections.<Integer>emptyList())); 470 } 471 472 public void testLeastOfIterable_empty_0() { 473 List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 0); 474 assertTrue(result instanceof RandomAccess); 475 assertListImmutable(result); 476 assertEquals(ImmutableList.<Integer>of(), result); 477 } 478 479 public void testLeastOfIterator_empty_0() { 480 List<Integer> result = numberOrdering.leastOf( 481 Iterators.<Integer>emptyIterator(), 0); 482 assertTrue(result instanceof RandomAccess); 483 assertListImmutable(result); 484 assertEquals(ImmutableList.<Integer>of(), result); 485 } 486 487 public void testLeastOfIterable_empty_1() { 488 List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 1); 489 assertTrue(result instanceof RandomAccess); 490 assertListImmutable(result); 491 assertEquals(ImmutableList.<Integer>of(), result); 492 } 493 494 public void testLeastOfIterator_empty_1() { 495 List<Integer> result = numberOrdering.leastOf( 496 Iterators.<Integer>emptyIterator(), 1); 497 assertTrue(result instanceof RandomAccess); 498 assertListImmutable(result); 499 assertEquals(ImmutableList.<Integer>of(), result); 500 } 501 502 public void testLeastOfIterable_simple_negativeOne() { 503 try { 504 numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), -1); 505 fail(); 506 } catch (IllegalArgumentException expected) { 507 } 508 } 509 510 public void testLeastOfIterator_simple_negativeOne() { 511 try { 512 numberOrdering.leastOf(Iterators.forArray(3, 4, 5, -1), -1); 513 fail(); 514 } catch (IllegalArgumentException expected) { 515 } 516 } 517 518 public void testLeastOfIterable_singleton_0() { 519 List<Integer> result = numberOrdering.leastOf(Arrays.asList(3), 0); 520 assertTrue(result instanceof RandomAccess); 521 assertListImmutable(result); 522 assertEquals(ImmutableList.<Integer>of(), result); 523 } 524 525 public void testLeastOfIterator_singleton_0() { 526 List<Integer> result = numberOrdering.leastOf( 527 Iterators.singletonIterator(3), 0); 528 assertTrue(result instanceof RandomAccess); 529 assertListImmutable(result); 530 assertEquals(ImmutableList.<Integer>of(), result); 531 } 532 533 public void testLeastOfIterable_simple_0() { 534 List<Integer> result = numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), 0); 535 assertTrue(result instanceof RandomAccess); 536 assertListImmutable(result); 537 assertEquals(ImmutableList.<Integer>of(), result); 538 } 539 540 public void testLeastOfIterator_simple_0() { 541 List<Integer> result = numberOrdering.leastOf( 542 Iterators.forArray(3, 4, 5, -1), 0); 543 assertTrue(result instanceof RandomAccess); 544 assertListImmutable(result); 545 assertEquals(ImmutableList.<Integer>of(), result); 546 } 547 548 public void testLeastOfIterable_simple_1() { 549 List<Integer> result = numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), 1); 550 assertTrue(result instanceof RandomAccess); 551 assertListImmutable(result); 552 assertEquals(ImmutableList.of(-1), result); 553 } 554 555 public void testLeastOfIterator_simple_1() { 556 List<Integer> result = numberOrdering.leastOf( 557 Iterators.forArray(3, 4, 5, -1), 1); 558 assertTrue(result instanceof RandomAccess); 559 assertListImmutable(result); 560 assertEquals(ImmutableList.of(-1), result); 561 } 562 563 public void testLeastOfIterable_simple_nMinusOne_withNullElement() { 564 List<Integer> list = Arrays.asList(3, null, 5, -1); 565 List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size() - 1); 566 assertTrue(result instanceof RandomAccess); 567 assertListImmutable(result); 568 assertEquals(ImmutableList.of(-1, 3, 5), result); 569 } 570 571 public void testLeastOfIterator_simple_nMinusOne_withNullElement() { 572 Iterator<Integer> itr = Iterators.forArray(3, null, 5, -1); 573 List<Integer> result = Ordering.natural().nullsLast().leastOf(itr, 3); 574 assertTrue(result instanceof RandomAccess); 575 assertListImmutable(result); 576 assertEquals(ImmutableList.of(-1, 3, 5), result); 577 } 578 579 public void testLeastOfIterable_simple_nMinusOne() { 580 List<Integer> list = Arrays.asList(3, 4, 5, -1); 581 List<Integer> result = numberOrdering.leastOf(list, list.size() - 1); 582 assertTrue(result instanceof RandomAccess); 583 assertListImmutable(result); 584 assertEquals(ImmutableList.of(-1, 3, 4), result); 585 } 586 587 public void testLeastOfIterator_simple_nMinusOne() { 588 List<Integer> list = Arrays.asList(3, 4, 5, -1); 589 List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size() - 1); 590 assertTrue(result instanceof RandomAccess); 591 assertListImmutable(result); 592 assertEquals(ImmutableList.of(-1, 3, 4), result); 593 } 594 595 public void testLeastOfIterable_simple_n() { 596 List<Integer> list = Arrays.asList(3, 4, 5, -1); 597 List<Integer> result = numberOrdering.leastOf(list, list.size()); 598 assertTrue(result instanceof RandomAccess); 599 assertListImmutable(result); 600 assertEquals(ImmutableList.of(-1, 3, 4, 5), result); 601 } 602 603 public void testLeastOfIterator_simple_n() { 604 List<Integer> list = Arrays.asList(3, 4, 5, -1); 605 List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size()); 606 assertTrue(result instanceof RandomAccess); 607 assertListImmutable(result); 608 assertEquals(ImmutableList.of(-1, 3, 4, 5), result); 609 } 610 611 public void testLeastOfIterable_simple_n_withNullElement() { 612 List<Integer> list = Arrays.asList(3, 4, 5, null, -1); 613 List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size()); 614 assertTrue(result instanceof RandomAccess); 615 assertListImmutable(result); 616 assertEquals(Arrays.asList(-1, 3, 4, 5, null), result); 617 } 618 619 public void testLeastOfIterator_simple_n_withNullElement() { 620 List<Integer> list = Arrays.asList(3, 4, 5, null, -1); 621 List<Integer> result = Ordering.natural().nullsLast().leastOf( 622 list.iterator(), list.size()); 623 assertTrue(result instanceof RandomAccess); 624 assertListImmutable(result); 625 assertEquals(Arrays.asList(-1, 3, 4, 5, null), result); 626 } 627 628 public void testLeastOfIterable_simple_nPlusOne() { 629 List<Integer> list = Arrays.asList(3, 4, 5, -1); 630 List<Integer> result = numberOrdering.leastOf(list, list.size() + 1); 631 assertTrue(result instanceof RandomAccess); 632 assertListImmutable(result); 633 assertEquals(ImmutableList.of(-1, 3, 4, 5), result); 634 } 635 636 public void testLeastOfIterator_simple_nPlusOne() { 637 List<Integer> list = Arrays.asList(3, 4, 5, -1); 638 List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size() + 1); 639 assertTrue(result instanceof RandomAccess); 640 assertListImmutable(result); 641 assertEquals(ImmutableList.of(-1, 3, 4, 5), result); 642 } 643 644 public void testLeastOfIterable_ties() { 645 Integer foo = new Integer(Integer.MAX_VALUE - 10); 646 Integer bar = new Integer(Integer.MAX_VALUE - 10); 647 648 assertNotSame(foo, bar); 649 assertEquals(foo, bar); 650 651 List<Integer> list = Arrays.asList(3, foo, bar, -1); 652 List<Integer> result = numberOrdering.leastOf(list, list.size()); 653 assertEquals(ImmutableList.of(-1, 3, foo, bar), result); 654 } 655 656 public void testLeastOfIterator_ties() { 657 Integer foo = new Integer(Integer.MAX_VALUE - 10); 658 Integer bar = new Integer(Integer.MAX_VALUE - 10); 659 660 assertNotSame(foo, bar); 661 assertEquals(foo, bar); 662 663 List<Integer> list = Arrays.asList(3, foo, bar, -1); 664 List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size()); 665 assertEquals(ImmutableList.of(-1, 3, foo, bar), result); 666 } 667 668 public void testLeastOf_reconcileAgainstSortAndSublistSmall() { 669 runLeastOfComparison(10, 30, 2); 670 } 671 672 private static void runLeastOfComparison( 673 int iterations, int elements, int seeds) { 674 Random random = new Random(42); 675 Ordering<Integer> ordering = Ordering.natural(); 676 677 for (int i = 0; i < iterations; i++) { 678 List<Integer> list = Lists.newArrayList(); 679 for (int j = 0; j < elements; j++) { 680 list.add(random.nextInt(10 * i + j + 1)); 681 } 682 683 for (int seed = 1; seed < seeds; seed++) { 684 int k = random.nextInt(10 * seed); 685 assertEquals(ordering.sortedCopy(list).subList(0, k), 686 ordering.leastOf(list, k)); 687 } 688 } 689 } 690 691 public void testLeastOfIterableLargeK() { 692 List<Integer> list = Arrays.asList(4, 2, 3, 5, 1); 693 assertEquals(Arrays.asList(1, 2, 3, 4, 5), Ordering.natural() 694 .leastOf(list, Integer.MAX_VALUE)); 695 } 696 697 public void testLeastOfIteratorLargeK() { 698 List<Integer> list = Arrays.asList(4, 2, 3, 5, 1); 699 assertEquals(Arrays.asList(1, 2, 3, 4, 5), Ordering.natural() 700 .leastOf(list.iterator(), Integer.MAX_VALUE)); 701 } 702 703 public void testGreatestOfIterable_simple() { 704 /* 705 * If greatestOf() promised to be implemented as reverse().leastOf(), this 706 * test would be enough. It doesn't... but we'll cheat and act like it does 707 * anyway. There's a comment there to remind us to fix this if we change it. 708 */ 709 List<Integer> list = Arrays.asList(3, 1, 3, 2, 4, 2, 4, 3); 710 assertEquals(Arrays.asList(4, 4, 3, 3), numberOrdering.greatestOf(list, 4)); 711 } 712 713 public void testGreatestOfIterator_simple() { 714 /* 715 * If greatestOf() promised to be implemented as reverse().leastOf(), this 716 * test would be enough. It doesn't... but we'll cheat and act like it does 717 * anyway. There's a comment there to remind us to fix this if we change it. 718 */ 719 List<Integer> list = Arrays.asList(3, 1, 3, 2, 4, 2, 4, 3); 720 assertEquals(Arrays.asList(4, 4, 3, 3), 721 numberOrdering.greatestOf(list.iterator(), 4)); 722 } 723 724 private static void assertListImmutable(List<Integer> result) { 725 try { 726 result.set(0, 1); 727 fail(); 728 } catch (UnsupportedOperationException expected) { 729 // pass 730 } 731 } 732 733 public void testIteratorMinAndMax() { 734 List<Integer> ints = Lists.newArrayList(5, 3, 0, 9); 735 assertEquals(9, (int) numberOrdering.max(ints.iterator())); 736 assertEquals(0, (int) numberOrdering.min(ints.iterator())); 737 738 // when the values are the same, the first argument should be returned 739 Integer a = new Integer(4); 740 Integer b = new Integer(4); 741 ints = Lists.newArrayList(a, b, b); 742 assertSame(a, numberOrdering.max(ints.iterator())); 743 assertSame(a, numberOrdering.min(ints.iterator())); 744 } 745 746 public void testIteratorMinExhaustsIterator() { 747 List<Integer> ints = Lists.newArrayList(9, 0, 3, 5); 748 Iterator<Integer> iterator = ints.iterator(); 749 assertEquals(0, (int) numberOrdering.min(iterator)); 750 assertFalse(iterator.hasNext()); 751 } 752 753 public void testIteratorMaxExhaustsIterator() { 754 List<Integer> ints = Lists.newArrayList(9, 0, 3, 5); 755 Iterator<Integer> iterator = ints.iterator(); 756 assertEquals(9, (int) numberOrdering.max(iterator)); 757 assertFalse(iterator.hasNext()); 758 } 759 760 public void testIterableMinAndMax() { 761 List<Integer> ints = Lists.newArrayList(5, 3, 0, 9); 762 assertEquals(9, (int) numberOrdering.max(ints)); 763 assertEquals(0, (int) numberOrdering.min(ints)); 764 765 // when the values are the same, the first argument should be returned 766 Integer a = new Integer(4); 767 Integer b = new Integer(4); 768 ints = Lists.newArrayList(a, b, b); 769 assertSame(a, numberOrdering.max(ints)); 770 assertSame(a, numberOrdering.min(ints)); 771 } 772 773 public void testVarargsMinAndMax() { 774 // try the min and max values in all positions, since some values are proper 775 // parameters and others are from the varargs array 776 assertEquals(9, (int) numberOrdering.max(9, 3, 0, 5, 8)); 777 assertEquals(9, (int) numberOrdering.max(5, 9, 0, 3, 8)); 778 assertEquals(9, (int) numberOrdering.max(5, 3, 9, 0, 8)); 779 assertEquals(9, (int) numberOrdering.max(5, 3, 0, 9, 8)); 780 assertEquals(9, (int) numberOrdering.max(5, 3, 0, 8, 9)); 781 assertEquals(0, (int) numberOrdering.min(0, 3, 5, 9, 8)); 782 assertEquals(0, (int) numberOrdering.min(5, 0, 3, 9, 8)); 783 assertEquals(0, (int) numberOrdering.min(5, 3, 0, 9, 8)); 784 assertEquals(0, (int) numberOrdering.min(5, 3, 9, 0, 8)); 785 assertEquals(0, (int) numberOrdering.min(5, 3, 0, 9, 0)); 786 787 // when the values are the same, the first argument should be returned 788 Integer a = new Integer(4); 789 Integer b = new Integer(4); 790 assertSame(a, numberOrdering.max(a, b, b)); 791 assertSame(a, numberOrdering.min(a, b, b)); 792 } 793 794 public void testParameterMinAndMax() { 795 assertEquals(5, (int) numberOrdering.max(3, 5)); 796 assertEquals(5, (int) numberOrdering.max(5, 3)); 797 assertEquals(3, (int) numberOrdering.min(3, 5)); 798 assertEquals(3, (int) numberOrdering.min(5, 3)); 799 800 // when the values are the same, the first argument should be returned 801 Integer a = new Integer(4); 802 Integer b = new Integer(4); 803 assertSame(a, numberOrdering.max(a, b)); 804 assertSame(a, numberOrdering.min(a, b)); 805 } 806 807 private static class NumberOrdering extends Ordering<Number> { 808 @Override public int compare(Number a, Number b) { 809 return ((Double) a.doubleValue()).compareTo(b.doubleValue()); 810 } 811 @Override public int hashCode() { 812 return NumberOrdering.class.hashCode(); 813 } 814 @Override public boolean equals(Object other) { 815 return other instanceof NumberOrdering; 816 } 817 private static final long serialVersionUID = 0; 818 } 819 820 /* 821 * Now we have monster tests that create hundreds of Orderings using different 822 * combinations of methods, then checks compare(), binarySearch() and so 823 * forth on each one. 824 */ 825 826 // should periodically try increasing this, but it makes the test run long 827 private static final int RECURSE_DEPTH = 2; 828 829 public void testCombinationsExhaustively_startingFromNatural() { 830 testExhaustively(Ordering.<String>natural(), "a", "b", "d"); 831 } 832 833 /** 834 * Requires at least 3 elements in {@code strictlyOrderedElements} in order to 835 * test the varargs version of min/max. 836 */ 837 private static <T> void testExhaustively( 838 Ordering<? super T> ordering, T... strictlyOrderedElements) { 839 checkArgument(strictlyOrderedElements.length >= 3, "strictlyOrderedElements " 840 + "requires at least 3 elements"); 841 List<T> list = Arrays.asList(strictlyOrderedElements); 842 843 // for use calling Collection.toArray later 844 T[] emptyArray = Platform.newArray(strictlyOrderedElements, 0); 845 846 // shoot me, but I didn't want to deal with wildcards through the whole test 847 @SuppressWarnings("unchecked") 848 Scenario<T> starter = new Scenario<T>((Ordering) ordering, list, emptyArray); 849 verifyScenario(starter, 0); 850 } 851 852 private static <T> void verifyScenario(Scenario<T> scenario, int level) { 853 scenario.testCompareTo(); 854 scenario.testIsOrdered(); 855 scenario.testMinAndMax(); 856 scenario.testBinarySearch(); 857 scenario.testSortedCopy(); 858 859 if (level < RECURSE_DEPTH) { 860 for (OrderingMutation alteration : OrderingMutation.values()) { 861 verifyScenario(alteration.mutate(scenario), level + 1); 862 } 863 } 864 } 865 866 /** 867 * An aggregation of an ordering with a list (of size > 1) that should prove 868 * to be in strictly increasing order according to that ordering. 869 */ 870 private static class Scenario<T> { 871 final Ordering<T> ordering; 872 final List<T> strictlyOrderedList; 873 final T[] emptyArray; 874 875 Scenario(Ordering<T> ordering, List<T> strictlyOrderedList, T[] emptyArray) { 876 this.ordering = ordering; 877 this.strictlyOrderedList = strictlyOrderedList; 878 this.emptyArray = emptyArray; 879 } 880 881 void testCompareTo() { 882 Helpers.testComparator(ordering, strictlyOrderedList); 883 } 884 885 void testIsOrdered() { 886 assertTrue(ordering.isOrdered(strictlyOrderedList)); 887 assertTrue(ordering.isStrictlyOrdered(strictlyOrderedList)); 888 } 889 890 @SuppressWarnings("unchecked") // generic arrays and unchecked cast 891 void testMinAndMax() { 892 List<T> shuffledList = Lists.newArrayList(strictlyOrderedList); 893 shuffledList = shuffledCopy(shuffledList, new Random(5)); 894 895 T min = strictlyOrderedList.get(0); 896 T max = strictlyOrderedList.get(strictlyOrderedList.size() - 1); 897 898 T first = shuffledList.get(0); 899 T second = shuffledList.get(1); 900 T third = shuffledList.get(2); 901 T[] rest = shuffledList.subList(3, shuffledList.size()).toArray(emptyArray); 902 903 assertEquals(min, ordering.min(shuffledList)); 904 assertEquals(min, ordering.min(shuffledList.iterator())); 905 assertEquals(min, ordering.min(first, second, third, rest)); 906 assertEquals(min, ordering.min(min, max)); 907 assertEquals(min, ordering.min(max, min)); 908 909 assertEquals(max, ordering.max(shuffledList)); 910 assertEquals(max, ordering.max(shuffledList.iterator())); 911 assertEquals(max, ordering.max(first, second, third, rest)); 912 assertEquals(max, ordering.max(min, max)); 913 assertEquals(max, ordering.max(max, min)); 914 } 915 916 void testBinarySearch() { 917 for (int i = 0; i < strictlyOrderedList.size(); i++) { 918 assertEquals(i, ordering.binarySearch( 919 strictlyOrderedList, strictlyOrderedList.get(i))); 920 } 921 List<T> newList = Lists.newArrayList(strictlyOrderedList); 922 T valueNotInList = newList.remove(1); 923 assertEquals(-2, ordering.binarySearch(newList, valueNotInList)); 924 } 925 926 void testSortedCopy() { 927 List<T> shuffledList = Lists.newArrayList(strictlyOrderedList); 928 shuffledList = shuffledCopy(shuffledList, new Random(5)); 929 930 assertEquals(strictlyOrderedList, ordering.sortedCopy(shuffledList)); 931 932 if (!strictlyOrderedList.contains(null)) { 933 assertEquals(strictlyOrderedList, ordering.immutableSortedCopy(shuffledList)); 934 } 935 } 936 } 937 938 /** 939 * A means for changing an Ordering into another Ordering. Each instance is 940 * responsible for creating the alternate Ordering, and providing a List that 941 * is known to be ordered, based on an input List known to be ordered 942 * according to the input Ordering. 943 */ 944 private enum OrderingMutation { 945 REVERSE { 946 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 947 List<T> newList = Lists.newArrayList(scenario.strictlyOrderedList); 948 Collections.reverse(newList); 949 return new Scenario<T>(scenario.ordering.reverse(), newList, scenario.emptyArray); 950 } 951 }, 952 NULLS_FIRST { 953 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 954 @SuppressWarnings("unchecked") 955 List<T> newList = Lists.newArrayList((T) null); 956 for (T t : scenario.strictlyOrderedList) { 957 if (t != null) { 958 newList.add(t); 959 } 960 } 961 return new Scenario<T>(scenario.ordering.nullsFirst(), newList, scenario.emptyArray); 962 } 963 }, 964 NULLS_LAST { 965 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 966 List<T> newList = Lists.newArrayList(); 967 for (T t : scenario.strictlyOrderedList) { 968 if (t != null) { 969 newList.add(t); 970 } 971 } 972 newList.add(null); 973 return new Scenario<T>(scenario.ordering.nullsLast(), newList, scenario.emptyArray); 974 } 975 }, 976 ON_RESULT_OF { 977 @Override <T> Scenario<?> mutate(final Scenario<T> scenario) { 978 Ordering<Integer> ordering = scenario.ordering.onResultOf( 979 new Function<Integer, T>() { 980 @Override 981 public T apply(@Nullable Integer from) { 982 return scenario.strictlyOrderedList.get(from); 983 } 984 }); 985 List<Integer> list = Lists.newArrayList(); 986 for (int i = 0; i < scenario.strictlyOrderedList.size(); i++) { 987 list.add(i); 988 } 989 return new Scenario<Integer>(ordering, list, new Integer[0]); 990 } 991 }, 992 COMPOUND_THIS_WITH_NATURAL { 993 @SuppressWarnings("unchecked") // raw array 994 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 995 List<Composite<T>> composites = Lists.newArrayList(); 996 for (T t : scenario.strictlyOrderedList) { 997 composites.add(new Composite<T>(t, 1)); 998 composites.add(new Composite<T>(t, 2)); 999 } 1000 Ordering<Composite<T>> ordering = 1001 scenario.ordering.onResultOf(Composite.<T>getValueFunction()) 1002 .compound(Ordering.natural()); 1003 return new Scenario<Composite<T>>(ordering, composites, new Composite[0]); 1004 } 1005 }, 1006 COMPOUND_NATURAL_WITH_THIS { 1007 @SuppressWarnings("unchecked") // raw array 1008 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 1009 List<Composite<T>> composites = Lists.newArrayList(); 1010 for (T t : scenario.strictlyOrderedList) { 1011 composites.add(new Composite<T>(t, 1)); 1012 } 1013 for (T t : scenario.strictlyOrderedList) { 1014 composites.add(new Composite<T>(t, 2)); 1015 } 1016 Ordering<Composite<T>> ordering = Ordering.natural().compound( 1017 scenario.ordering.onResultOf(Composite.<T>getValueFunction())); 1018 return new Scenario<Composite<T>>(ordering, composites, new Composite[0]); 1019 } 1020 }, 1021 LEXICOGRAPHICAL { 1022 @SuppressWarnings("unchecked") // dang varargs 1023 @Override <T> Scenario<?> mutate(Scenario<T> scenario) { 1024 List<Iterable<T>> words = Lists.newArrayList(); 1025 words.add(Collections.<T>emptyList()); 1026 for (T t : scenario.strictlyOrderedList) { 1027 words.add(Arrays.asList(t)); 1028 for (T s : scenario.strictlyOrderedList) { 1029 words.add(Arrays.asList(t, s)); 1030 } 1031 } 1032 return new Scenario<Iterable<T>>( 1033 scenario.ordering.lexicographical(), words, new Iterable[0]); 1034 } 1035 }, 1036 ; 1037 1038 abstract <T> Scenario<?> mutate(Scenario<T> scenario); 1039 } 1040 1041 /** 1042 * A dummy object we create so that we can have something meaningful to have 1043 * a compound ordering over. 1044 */ 1045 private static class Composite<T> implements Comparable<Composite<T>> { 1046 final T value; 1047 final int rank; 1048 1049 Composite(T value, int rank) { 1050 this.value = value; 1051 this.rank = rank; 1052 } 1053 1054 // natural order is by rank only; the test will compound() this with the 1055 // order of 't'. 1056 @Override 1057 public int compareTo(Composite<T> that) { 1058 return Ints.compare(rank, that.rank); 1059 } 1060 1061 static <T> Function<Composite<T>, T> getValueFunction() { 1062 return new Function<Composite<T>, T>() { 1063 @Override 1064 public T apply(Composite<T> from) { 1065 return from.value; 1066 } 1067 }; 1068 } 1069 } 1070 1071 private static <T> List<T> shuffledCopy(List<T> in, Random random) { 1072 List<T> mutable = newArrayList(in); 1073 List<T> out = newArrayList(); 1074 while (!mutable.isEmpty()) { 1075 out.add(mutable.remove(random.nextInt(mutable.size()))); 1076 } 1077 return out; 1078 } 1079} 1080 1081