1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.collect.Lists.newArrayList;
21 import static com.google.common.testing.SerializableTester.reserialize;
22 import static com.google.common.testing.SerializableTester.reserializeAndAssert;
23 import static com.google.common.truth.Truth.assertThat;
24 import static java.util.Arrays.asList;
25
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.base.Function;
28 import com.google.common.base.Functions;
29 import com.google.common.collect.Ordering.ArbitraryOrdering;
30 import com.google.common.collect.Ordering.IncomparableValueException;
31 import com.google.common.collect.testing.Helpers;
32 import com.google.common.primitives.Ints;
33 import com.google.common.testing.EqualsTester;
34
35 import junit.framework.TestCase;
36
37 import java.util.Arrays;
38 import java.util.Collections;
39 import java.util.Comparator;
40 import java.util.Iterator;
41 import java.util.List;
42 import java.util.Random;
43 import java.util.RandomAccess;
44
45 import javax.annotation.Nullable;
46
47
48
49
50
51
52 @GwtCompatible(emulated = true)
53 public class OrderingTest extends TestCase {
54
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")
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 assertThat(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
171
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
182
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;
197 }
198 };
199
200
201 list = shuffledCopy(list, new Random(1));
202
203 Collections.sort(list, arbitrary);
204
205
206
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
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
275 Ordering<Number> a = numbers.compound(numbers);
276
277
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
286
287
288 Ordering<Number> f = numbers.compound(objects).compound(objects);
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));
294 Ordering<Number> k = objects.compound(objects.compound(numbers));
295
296
297
298 Ordering<Integer> l = objects.compound(numbers);
299
300
301
302
303
304
305
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
322
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")
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
706
707
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
716
717
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
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
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
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
775
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
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
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
822
823
824
825
826
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
835
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
844 T[] emptyArray = Platform.newArray(strictlyOrderedElements, 0);
845
846
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
868
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")
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
940
941
942
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")
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")
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")
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
1043
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
1055
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