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