common/collect/OrderingTest.java

/*
 * Copyright (C) 2007 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.testing.SerializableTester.reserialize;
import static com.google.common.testing.SerializableTester.reserializeAndAssert;
import static java.util.Arrays.asList;
import static org.junit.contrib.truth.Truth.ASSERT;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Function;
import com.google.common.base.Functions;
import com.google.common.collect.Ordering.ArbitraryOrdering;
import com.google.common.collect.Ordering.IncomparableValueException;
import com.google.common.collect.testing.Helpers;
import com.google.common.testing.EqualsTester;
import com.google.common.testing.NullPointerTester;

import junit.framework.TestCase;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.RandomAccess;

import javax.annotation.Nullable;

/**
 * Unit tests for {@code Ordering}.
 *
 * @author Jesse Wilson
 */
@GwtCompatible(emulated = true)
public class OrderingTest extends TestCase {
  // TODO(cpovirk): some of these are inexplicably slow (20-30s) under GWT

  private final Ordering<Number> numberOrdering = new NumberOrdering();

  public void testNatural() {
    Ordering<Integer> comparator = Ordering.natural();
    Helpers.testComparator(comparator,
        Integer.MIN_VALUE, -1, 0, 1, Integer.MAX_VALUE);
    try {
      comparator.compare(1, null);
      fail();
    } catch (NullPointerException expected) {}
    try {
      comparator.compare(null, 2);
      fail();
    } catch (NullPointerException expected) {}
    try {
      comparator.compare(null, null);
      fail();
    } catch (NullPointerException expected) {}
    assertSame(comparator, reserialize(comparator));
    assertEquals("Ordering.natural()", comparator.toString());
  }

  public void testFrom() {
    Ordering<String> caseInsensitiveOrdering
        = Ordering.from(String.CASE_INSENSITIVE_ORDER);
    assertEquals(0, caseInsensitiveOrdering.compare("A", "a"));
    assertTrue(caseInsensitiveOrdering.compare("a", "B") < 0);
    assertTrue(caseInsensitiveOrdering.compare("B", "a") > 0);

    @SuppressWarnings("deprecation") // test of deprecated method
    Ordering<String> orderingFromOrdering =
        Ordering.from(Ordering.<String>natural());
    new EqualsTester()
        .addEqualityGroup(caseInsensitiveOrdering, Ordering.from(String.CASE_INSENSITIVE_ORDER))
        .addEqualityGroup(orderingFromOrdering, Ordering.natural())
        .testEquals();
  }

  public void testExplicit_none() {
    Comparator<Integer> c
        = Ordering.explicit(Collections.<Integer>emptyList());
    try {
      c.compare(0, 0);
      fail();
    } catch (IncomparableValueException expected) {
      assertEquals(0, expected.value);
    }
    reserializeAndAssert(c);
  }

  public void testExplicit_one() {
    Comparator<Integer> c = Ordering.explicit(0);
    assertEquals(0, c.compare(0, 0));
    try {
      c.compare(0, 1);
      fail();
    } catch (IncomparableValueException expected) {
      assertEquals(1, expected.value);
    }
    reserializeAndAssert(c);
    assertEquals("Ordering.explicit([0])", c.toString());
  }

  public void testExplicit_two() {
    Comparator<Integer> c = Ordering.explicit(42, 5);
    assertEquals(0, c.compare(5, 5));
    assertTrue(c.compare(5, 42) > 0);
    assertTrue(c.compare(42, 5) < 0);
    try {
      c.compare(5, 666);
      fail();
    } catch (IncomparableValueException expected) {
      assertEquals(666, expected.value);
    }
    new EqualsTester()
        .addEqualityGroup(c, Ordering.explicit(42, 5))
        .addEqualityGroup(Ordering.explicit(5, 42))
        .addEqualityGroup(Ordering.explicit(42))
        .testEquals();
    reserializeAndAssert(c);
  }

  public void testExplicit_sortingExample() {
    Comparator<Integer> c
        = Ordering.explicit(2, 8, 6, 1, 7, 5, 3, 4, 0, 9);
    List<Integer> list = Arrays.asList(0, 3, 5, 6, 7, 8, 9);
    Collections.sort(list, c);
    ASSERT.that(list).hasContentsInOrder(8, 6, 7, 5, 3, 0, 9);
    reserializeAndAssert(c);
  }

  public void testExplicit_withDuplicates() {
    try {
      Ordering.explicit(1, 2, 3, 4, 2);
      fail();
    } catch (IllegalArgumentException expected) {
    }
  }

  // A more limited test than the one that follows, but this one uses the
  // actual public API.
  public void testArbitrary_withoutCollisions() {
    List<Object> list = Lists.newArrayList();
    for (int i = 0; i < 50; i++) {
      list.add(new Object());
    }

    Ordering<Object> arbitrary = Ordering.arbitrary();
    Collections.sort(list, arbitrary);

    // Now we don't care what order it's put the list in, only that
    // comparing any pair of elements gives the answer we expect.
    Helpers.testComparator(arbitrary, list);

    assertEquals("Ordering.arbitrary()", arbitrary.toString());
  }

  public void testArbitrary_withCollisions() {
    List<Integer> list = Lists.newArrayList();
    for (int i = 0; i < 50; i++) {
      list.add(i);
    }

    Ordering<Object> arbitrary = new ArbitraryOrdering() {
      @Override int identityHashCode(Object object) {
        return ((Integer) object) % 5; // fake tons of collisions!
      }
    };

    // Don't let the elements be in such a predictable order
    list = shuffledCopy(list, new Random(1));

    Collections.sort(list, arbitrary);

    // Now we don't care what order it's put the list in, only that
    // comparing any pair of elements gives the answer we expect.
    Helpers.testComparator(arbitrary, list);
  }

  public void testUsingToString() {
    Ordering<Object> ordering = Ordering.usingToString();
    Helpers.testComparator(ordering, 1, 12, 124, 2);
    assertEquals("Ordering.usingToString()", ordering.toString());
    assertSame(ordering, reserialize(ordering));
  }

  // use an enum to get easy serializability
  private enum CharAtFunction implements Function<String, Character> {
    AT0(0),
    AT1(1),
    AT2(2),
    AT3(3),
    AT4(4),
    AT5(5),
    ;

    final int index;
    CharAtFunction(int index) {
      this.index = index;
    }
    @Override
    public Character apply(String string) {
      return string.charAt(index);
    }
  }

  private static Ordering<String> byCharAt(int index) {
    return Ordering.natural().onResultOf(CharAtFunction.values()[index]);
  }

  public void testCompound_static() {
    Comparator<String> comparator = Ordering.compound(asList(
        byCharAt(0), byCharAt(1), byCharAt(2),
        byCharAt(3), byCharAt(4), byCharAt(5)));
    Helpers.testComparator(comparator, ImmutableList.of(
        "applesauce",
        "apricot",
        "artichoke",
        "banality",
        "banana",
        "banquet",
        "tangelo",
        "tangerine"));
    reserializeAndAssert(comparator);
  }

  public void testCompound_instance() {
    Comparator<String> comparator = byCharAt(1).compound(byCharAt(0));
    Helpers.testComparator(comparator, ImmutableList.of(
        "red",
        "yellow",
        "violet",
        "blue",
        "indigo",
        "green",
        "orange"));
  }

  public void testCompound_instance_generics() {
    Ordering<Object> objects = Ordering.explicit((Object) 1);
    Ordering<Number> numbers = Ordering.explicit((Number) 1);
    Ordering<Integer> integers = Ordering.explicit(1);

    // Like by like equals like
    Ordering<Number> a = numbers.compound(numbers);

    // The compound takes the more specific type of the two, regardless of order

    Ordering<Number> b = numbers.compound(objects);
    Ordering<Number> c = objects.compound(numbers);

    Ordering<Integer> d = numbers.compound(integers);
    Ordering<Integer> e = integers.compound(numbers);

    // This works with three levels too (IDEA falsely reports errors as noted
    // below. Both javac and eclipse handle these cases correctly.)

    Ordering<Number> f = numbers.compound(objects).compound(objects); //bad IDEA
    Ordering<Number> g = objects.compound(numbers).compound(objects);
    Ordering<Number> h = objects.compound(objects).compound(numbers);

    Ordering<Number> i = numbers.compound(objects.compound(objects));
    Ordering<Number> j = objects.compound(numbers.compound(objects)); //bad IDEA
    Ordering<Number> k = objects.compound(objects.compound(numbers));

    // You can also arbitrarily assign a more restricted type - not an intended
    // feature, exactly, but unavoidable (I think) and harmless
    Ordering<Integer> l = objects.compound(numbers);

    // This correctly doesn't work:
    // Ordering<Object> m = numbers.compound(objects);

    // Sadly, the following works in javac 1.6, but at least it fails for
    // eclipse, and is *correctly* highlighted red in IDEA.
    // Ordering<Object> n = objects.compound(numbers);
  }

  public void testReverse() {
    Ordering<Number> reverseOrder = numberOrdering.reverse();
    Helpers.testComparator(reverseOrder,
        Integer.MAX_VALUE, 1, 0, -1, Integer.MIN_VALUE);

    new EqualsTester()
        .addEqualityGroup(reverseOrder, numberOrdering.reverse())
        .addEqualityGroup(Ordering.natural().reverse())
        .addEqualityGroup(Collections.reverseOrder())
        .testEquals();
  }

  public void testReverseOfReverseSameAsForward() {
    // Not guaranteed by spec, but it works, and saves us from testing
    // exhaustively
    assertSame(numberOrdering, numberOrdering.reverse().reverse());
  }

  private enum StringLengthFunction implements Function<String, Integer> {
    StringLength;

    @Override
    public Integer apply(String string) {
      return string.length();
    }
  }

  private static final Ordering<Integer> DECREASING_INTEGER
      = Ordering.natural().reverse();

  public void testOnResultOf_natural() {
    Comparator<String> comparator
        = Ordering.natural().onResultOf(StringLengthFunction.StringLength);
    assertTrue(comparator.compare("to", "be") == 0);
    assertTrue(comparator.compare("or", "not") < 0);
    assertTrue(comparator.compare("that", "to") > 0);

    new EqualsTester()
        .addEqualityGroup(
            comparator,
            Ordering.natural().onResultOf(StringLengthFunction.StringLength))
        .addEqualityGroup(DECREASING_INTEGER)
        .testEquals();
    reserializeAndAssert(comparator);
    assertEquals("Ordering.natural().onResultOf(StringLength)",
        comparator.toString());
  }

  public void testOnResultOf_chained() {
    Comparator<String> comparator = DECREASING_INTEGER.onResultOf(
        StringLengthFunction.StringLength);
    assertTrue(comparator.compare("to", "be") == 0);
    assertTrue(comparator.compare("not", "or") < 0);
    assertTrue(comparator.compare("to", "that") > 0);

    new EqualsTester()
        .addEqualityGroup(
            comparator,
            DECREASING_INTEGER.onResultOf(StringLengthFunction.StringLength))
        .addEqualityGroup(
            DECREASING_INTEGER.onResultOf(Functions.constant(1)))
        .addEqualityGroup(Ordering.natural())
        .testEquals();
    reserializeAndAssert(comparator);
    assertEquals("Ordering.natural().reverse().onResultOf(StringLength)",
        comparator.toString());
  }

  @SuppressWarnings("unchecked") // dang varargs
  public void testLexicographical() {
    Ordering<String> ordering = Ordering.natural();
    Ordering<Iterable<String>> lexy = ordering.lexicographical();

    ImmutableList<String> empty = ImmutableList.of();
    ImmutableList<String> a = ImmutableList.of("a");
    ImmutableList<String> aa = ImmutableList.of("a", "a");
    ImmutableList<String> ab = ImmutableList.of("a", "b");
    ImmutableList<String> b = ImmutableList.of("b");

    Helpers.testComparator(lexy, empty, a, aa, ab, b);
  }

  public void testNullsFirst() {
    Ordering<Integer> ordering = Ordering.natural().nullsFirst();
    Helpers.testComparator(ordering, null, Integer.MIN_VALUE, 0, 1);
  }

  public void testNullsLast() {
    Ordering<Integer> ordering = Ordering.natural().nullsLast();
    Helpers.testComparator(ordering, 0, 1, Integer.MAX_VALUE, null);
  }

  public void testBinarySearch() {
    List<Integer> ints = Lists.newArrayList(0, 2, 3, 5, 7, 9);
    assertEquals(4, numberOrdering.binarySearch(ints, 7));
  }

  public void testSortedCopy() {
    List<Integer> unsortedInts = Collections.unmodifiableList(
        Arrays.asList(5, 0, 3, null, 0, 9));
    List<Integer> sortedInts =
        numberOrdering.nullsLast().sortedCopy(unsortedInts);
    assertEquals(Arrays.asList(0, 0, 3, 5, 9, null), sortedInts);

    assertEquals(Collections.emptyList(),
        numberOrdering.sortedCopy(Collections.<Integer>emptyList()));
  }

  public void testImmutableSortedCopy() {
    ImmutableList<Integer> unsortedInts = ImmutableList.of(5, 3, 0, 9, 3);
    ImmutableList<Integer> sortedInts
        = numberOrdering.immutableSortedCopy(unsortedInts);
    assertEquals(Arrays.asList(0, 3, 3, 5, 9), sortedInts);

    assertEquals(Collections.<Integer>emptyList(),
        numberOrdering.immutableSortedCopy(Collections.<Integer>emptyList()));

    List<Integer> listWithNull = Arrays.asList(5, 3, null, 9);
    try {
      Ordering.natural().nullsFirst().immutableSortedCopy(listWithNull);
      fail();
    } catch (NullPointerException expected) {
    }
  }

  public void testIsOrdered() {
    assertFalse(numberOrdering.isOrdered(asList(5, 3, 0, 9)));
    assertFalse(numberOrdering.isOrdered(asList(0, 5, 3, 9)));
    assertTrue(numberOrdering.isOrdered(asList(0, 3, 5, 9)));
    assertTrue(numberOrdering.isOrdered(asList(0, 0, 3, 3)));
    assertTrue(numberOrdering.isOrdered(asList(0, 3)));
    assertTrue(numberOrdering.isOrdered(Collections.singleton(1)));
    assertTrue(numberOrdering.isOrdered(Collections.<Integer>emptyList()));
  }

  public void testIsStrictlyOrdered() {
    assertFalse(numberOrdering.isStrictlyOrdered(asList(5, 3, 0, 9)));
    assertFalse(numberOrdering.isStrictlyOrdered(asList(0, 5, 3, 9)));
    assertTrue(numberOrdering.isStrictlyOrdered(asList(0, 3, 5, 9)));
    assertFalse(numberOrdering.isStrictlyOrdered(asList(0, 0, 3, 3)));
    assertTrue(numberOrdering.isStrictlyOrdered(asList(0, 3)));
    assertTrue(numberOrdering.isStrictlyOrdered(Collections.singleton(1)));
    assertTrue(numberOrdering.isStrictlyOrdered(
        Collections.<Integer>emptyList()));
  }

  public void testLeastOf_emptyList_0() {
    List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 0);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.<Integer>of(), result);
  }

  public void testLeastOf_emptyList_1() {
    List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 1);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.<Integer>of(), result);
  }

  public void testLeastOf_simple_negativeOne() {
    try {
      numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), -1);
      fail();
    } catch (IllegalArgumentException expected) {
    }
  }

  public void testLeastOf_singletonList_0() {
    List<Integer> result = numberOrdering.leastOf(Arrays.asList(3), 0);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.<Integer>of(), result);
  }

  public void testLeastOf_simple_0() {
    List<Integer> result = numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), 0);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.<Integer>of(), result);
  }

  public void testLeastOf_simple_1() {
    List<Integer> result = numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), 1);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.of(-1), result);
  }

  public void testLeastOf_simple_nMinusOne() {
    List<Integer> list = Arrays.asList(3, 4, 5, -1);
    List<Integer> result = numberOrdering.leastOf(list, list.size() - 1);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.of(-1, 3, 4), result);
  }

  public void testLeastOf_simple_n() {
    List<Integer> list = Arrays.asList(3, 4, 5, -1);
    List<Integer> result = numberOrdering.leastOf(list, list.size());
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
  }

  public void testLeastOf_simple_nPlusOne() {
    List<Integer> list = Arrays.asList(3, 4, 5, -1);
    List<Integer> result = numberOrdering.leastOf(list, list.size() + 1);
    assertTrue(result instanceof RandomAccess);
    assertListImmutable(result);
    assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
  }

  public void testLeastOf_ties() {
    Integer foo = new Integer(Integer.MAX_VALUE - 10);
    Integer bar = new Integer(Integer.MAX_VALUE - 10);

    assertNotSame(foo, bar);
    assertEquals(foo, bar);

    List<Integer> list = Arrays.asList(3, foo, bar, -1);
    List<Integer> result = numberOrdering.leastOf(list, list.size());
    assertEquals(ImmutableList.of(-1, 3, foo, bar), result);
  }

  @GwtIncompatible("slow")
  public void testLeastOf_reconcileAgainstSortAndSublist() {
    runLeastOfComparison(1000, 300, 20);
  }

  public void testLeastOf_reconcileAgainstSortAndSublistSmall() {
    runLeastOfComparison(10, 30, 2);
  }

  private static void runLeastOfComparison(
      int iterations, int elements, int seeds) {
    Random random = new Random(42);
    Ordering<Integer> ordering = Ordering.natural();

    for (int i = 0; i < iterations; i++) {
      List<Integer> list = Lists.newArrayList();
      for (int j = 0; j < elements; j++) {
        list.add(random.nextInt(10 * i + j + 1));
      }

      for (int seed = 1; seed < seeds; seed++) {
        int k = random.nextInt(10 * seed);
        assertEquals(ordering.sortedCopy(list).subList(0, k),
            ordering.leastOf(list, k));
      }
    }
  }

  public void testGreatestOf_simple() {
    /*
     * If greatestOf() promised to be implemented as reverse().leastOf(), this
     * test would be enough. It doesn't... but we'll cheat and act like it does
     * anyway. There's a comment there to remind us to fix this if we change it.
     */
    List<Integer> list = Arrays.asList(3, 1, 3, 2, 4, 2, 4, 3);
    assertEquals(Arrays.asList(4, 4, 3, 3), numberOrdering.greatestOf(list, 4));
  }

  private static void assertListImmutable(List<Integer> result) {
    try {
      result.set(0, 1);
      fail();
    } catch (UnsupportedOperationException expected) {
      // pass
    }
  }

  public void testIteratorMinAndMax() {
    List<Integer> ints = Lists.newArrayList(5, 3, 0, 9);
    assertEquals(9, (int) numberOrdering.max(ints.iterator()));
    assertEquals(0, (int) numberOrdering.min(ints.iterator()));

    // when the values are the same, the first argument should be returned
    Integer a = new Integer(4);
    Integer b = new Integer(4);
    ints = Lists.newArrayList(a, b, b);
    assertSame(a, numberOrdering.max(ints.iterator()));
    assertSame(a, numberOrdering.min(ints.iterator()));
  }

  public void testIteratorMinExhaustsIterator() {
    List<Integer> ints = Lists.newArrayList(9, 0, 3, 5);
    Iterator<Integer> iterator = ints.iterator();
    assertEquals(0, (int) numberOrdering.min(iterator));
    assertFalse(iterator.hasNext());
  }

  public void testIteratorMaxExhaustsIterator() {
    List<Integer> ints = Lists.newArrayList(9, 0, 3, 5);
    Iterator<Integer> iterator = ints.iterator();
    assertEquals(9, (int) numberOrdering.max(iterator));
    assertFalse(iterator.hasNext());
  }

  public void testIterableMinAndMax() {
    List<Integer> ints = Lists.newArrayList(5, 3, 0, 9);
    assertEquals(9, (int) numberOrdering.max(ints));
    assertEquals(0, (int) numberOrdering.min(ints));

    // when the values are the same, the first argument should be returned
    Integer a = new Integer(4);
    Integer b = new Integer(4);
    ints = Lists.newArrayList(a, b, b);
    assertSame(a, numberOrdering.max(ints));
    assertSame(a, numberOrdering.min(ints));
  }

  public void testVarargsMinAndMax() {
    // try the min and max values in all positions, since some values are proper
    // parameters and others are from the varargs array
    assertEquals(9, (int) numberOrdering.max(9, 3, 0, 5, 8));
    assertEquals(9, (int) numberOrdering.max(5, 9, 0, 3, 8));
    assertEquals(9, (int) numberOrdering.max(5, 3, 9, 0, 8));
    assertEquals(9, (int) numberOrdering.max(5, 3, 0, 9, 8));
    assertEquals(9, (int) numberOrdering.max(5, 3, 0, 8, 9));
    assertEquals(0, (int) numberOrdering.min(0, 3, 5, 9, 8));
    assertEquals(0, (int) numberOrdering.min(5, 0, 3, 9, 8));
    assertEquals(0, (int) numberOrdering.min(5, 3, 0, 9, 8));
    assertEquals(0, (int) numberOrdering.min(5, 3, 9, 0, 8));
    assertEquals(0, (int) numberOrdering.min(5, 3, 0, 9, 0));

    // when the values are the same, the first argument should be returned
    Integer a = new Integer(4);
    Integer b = new Integer(4);
    assertSame(a, numberOrdering.max(a, b, b));
    assertSame(a, numberOrdering.min(a, b, b));
  }

  public void testParameterMinAndMax() {
    assertEquals(5, (int) numberOrdering.max(3, 5));
    assertEquals(5, (int) numberOrdering.max(5, 3));
    assertEquals(3, (int) numberOrdering.min(3, 5));
    assertEquals(3, (int) numberOrdering.min(5, 3));

    // when the values are the same, the first argument should be returned
    Integer a = new Integer(4);
    Integer b = new Integer(4);
    assertSame(a, numberOrdering.max(a, b));
    assertSame(a, numberOrdering.min(a, b));
  }

  private static class NumberOrdering extends Ordering<Number> {
    @Override public int compare(Number a, Number b) {
      return ((Double) a.doubleValue()).compareTo(b.doubleValue());
    }
    @Override public int hashCode() {
      return NumberOrdering.class.hashCode();
    }
    @Override public boolean equals(Object other) {
      return other instanceof NumberOrdering;
    }
    private static final long serialVersionUID = 0;
  }

  /*
   * Now we have monster tests that create hundreds of Orderings using different
   * combinations of methods, then checks compare(), binarySearch() and so
   * forth on each one.
   */

  // should periodically try increasing this, but it makes the test run long
  private static final int RECURSE_DEPTH = 2;

  public void testCombinationsExhaustively_startingFromNatural() {
    testExhaustively(Ordering.<String>natural(), Arrays.asList("a", "b"));
  }

  public void testCombinationsExhaustively_startingFromExplicit() {
    testExhaustively(Ordering.explicit("a", "b", "c", "d"),
        Arrays.asList("b", "d"));
  }

  public void testCombinationsExhaustively_startingFromUsingToString() {
    testExhaustively(Ordering.usingToString(), Arrays.asList(1, 12, 2));
  }

  public void testCombinationsExhaustively_startingFromArbitrary() {
    Ordering<Object> arbitrary = Ordering.arbitrary();
    List<Object> list = Arrays.asList(1, "foo", new Object());

    // There's no way to tell what the order should be except empirically
    Collections.sort(list, arbitrary);
    testExhaustively(arbitrary, list);
  }

  private static <T> void testExhaustively(
      Ordering<? super T> ordering, List<T> list) {
    // shoot me, but I didn't want to deal with wildcards through the whole test
    @SuppressWarnings("unchecked")
    Scenario<T> starter = new Scenario<T>((Ordering) ordering, list);
    verifyScenario(starter, 0);
  }

  private static <T> void verifyScenario(Scenario<T> scenario, int level) {
    scenario.testCompareTo();
    scenario.testIsOrdered();
    scenario.testMinAndMax();
    scenario.testBinarySearch();

    if (level < RECURSE_DEPTH) {
      for (OrderingMutation alteration : OrderingMutation.values()) {
        verifyScenario(alteration.mutate(scenario), level + 1);
      }
    }
  }

  /**
   * An aggregation of an ordering with a list (of size > 1) that should prove
   * to be in strictly increasing order according to that ordering.
   */
  private static class Scenario<T> {
    final Ordering<T> ordering;
    final List<T> strictlyOrderedList;

    Scenario(Ordering<T> ordering, List<T> strictlyOrderedList) {
      this.ordering = ordering;
      this.strictlyOrderedList = strictlyOrderedList;
    }

    void testCompareTo() {
      Helpers.testComparator(ordering, strictlyOrderedList);
    }

    void testIsOrdered() {
      assertTrue(ordering.isOrdered(strictlyOrderedList));
      assertTrue(ordering.isStrictlyOrdered(strictlyOrderedList));
    }

    void testMinAndMax() {
      List<T> shuffledList = Lists.newArrayList(strictlyOrderedList);
      shuffledList = shuffledCopy(shuffledList, new Random(5));

      assertEquals(strictlyOrderedList.get(0), ordering.min(shuffledList));
      assertEquals(strictlyOrderedList.get(strictlyOrderedList.size() - 1),
          ordering.max(shuffledList));
    }

    void testBinarySearch() {
      for (int i = 0; i < strictlyOrderedList.size(); i++) {
        assertEquals(i, ordering.binarySearch(
            strictlyOrderedList, strictlyOrderedList.get(i)));
      }
      List<T> newList = Lists.newArrayList(strictlyOrderedList);
      T valueNotInList = newList.remove(1);
      assertEquals(-2, ordering.binarySearch(newList, valueNotInList));
    }
  }

  /**
   * A means for changing an Ordering into another Ordering. Each instance is
   * responsible for creating the alternate Ordering, and providing a List that
   * is known to be ordered, based on an input List known to be ordered
   * according to the input Ordering.
   */
  private enum OrderingMutation {
    REVERSE {
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        List<T> newList = Lists.newArrayList(scenario.strictlyOrderedList);
        Collections.reverse(newList);
        return new Scenario<T>(scenario.ordering.reverse(), newList);
      }
    },
    NULLS_FIRST {
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        @SuppressWarnings("unchecked")
        List<T> newList = Lists.newArrayList((T) null);
        for (T t : scenario.strictlyOrderedList) {
          if (t != null) {
            newList.add(t);
          }
        }
        return new Scenario<T>(scenario.ordering.nullsFirst(), newList);
      }
    },
    NULLS_LAST {
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        List<T> newList = Lists.newArrayList();
        for (T t : scenario.strictlyOrderedList) {
          if (t != null) {
            newList.add(t);
          }
        }
        newList.add(null);
        return new Scenario<T>(scenario.ordering.nullsLast(), newList);
      }
    },
    ON_RESULT_OF {
      @Override <T> Scenario<?> mutate(final Scenario<T> scenario) {
        Ordering<Integer> ordering = scenario.ordering.onResultOf(
            new Function<Integer, T>() {
              @Override
              public T apply(@Nullable Integer from) {
                return scenario.strictlyOrderedList.get(from);
              }
            });
        List<Integer> list = Lists.newArrayList();
        for (int i = 0; i < scenario.strictlyOrderedList.size(); i++) {
          list.add(i);
        }
        return new Scenario<Integer>(ordering, list);
      }
    },
    COMPOUND_THIS_WITH_NATURAL {
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        List<Composite<T>> composites = Lists.newArrayList();
        for (T t : scenario.strictlyOrderedList) {
          composites.add(new Composite<T>(t, 1));
          composites.add(new Composite<T>(t, 2));
        }
        Ordering<Composite<T>> ordering =
            scenario.ordering.onResultOf(Composite.<T>getValueFunction())
                .compound(Ordering.natural());
        return new Scenario<Composite<T>>(ordering, composites);
      }
    },
    COMPOUND_NATURAL_WITH_THIS {
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        List<Composite<T>> composites = Lists.newArrayList();
        for (T t : scenario.strictlyOrderedList) {
          composites.add(new Composite<T>(t, 1));
        }
        for (T t : scenario.strictlyOrderedList) {
          composites.add(new Composite<T>(t, 2));
        }
        Ordering<Composite<T>> ordering = Ordering.natural().compound(
            scenario.ordering.onResultOf(Composite.<T>getValueFunction()));
        return new Scenario<Composite<T>>(ordering, composites);
      }
    },
    LEXICOGRAPHICAL {
      @SuppressWarnings("unchecked") // dang varargs
      @Override <T> Scenario<?> mutate(Scenario<T> scenario) {
        List<Iterable<T>> words = Lists.newArrayList();
        words.add(Collections.<T>emptyList());
        for (T t : scenario.strictlyOrderedList) {
          words.add(Arrays.asList(t));
          for (T s : scenario.strictlyOrderedList) {
            words.add(Arrays.asList(t, s));
          }
        }
        return new Scenario<Iterable<T>>(
            scenario.ordering.lexicographical(), words);
      }
    },
    ;

    abstract <T> Scenario<?> mutate(Scenario<T> scenario);
  }

  /**
   * A dummy object we create so that we can have something meaningful to have
   * a compound ordering over.
   */
  private static class Composite<T> implements Comparable<Composite<T>> {
    final T value;
    final int rank;

    Composite(T value, int rank) {
      this.value = value;
      this.rank = rank;
    }

    // natural order is by rank only; the test will compound() this with the
    // order of 't'.
    @Override
    public int compareTo(Composite<T> that) {
      return rank < that.rank ? -1 : rank > that.rank ? 1 : 0;
    }

    static <T> Function<Composite<T>, T> getValueFunction() {
      return new Function<Composite<T>, T>() {
        @Override
        public T apply(Composite<T> from) {
          return from.value;
        }
      };
    }
  }

  @GwtIncompatible("NullPointerTester")
  public void testNullPointerExceptions() throws Exception {
    NullPointerTester tester = new NullPointerTester();
    tester.testAllPublicStaticMethods(Ordering.class);

    // any Ordering<Object> instance that accepts nulls should be good enough
    tester.testAllPublicInstanceMethods(Ordering.usingToString().nullsFirst());
  }

  private static <T> List<T> shuffledCopy(List<T> in, Random random) {
    List<T> mutable = newArrayList(in);
    List<T> out = newArrayList();
    while (!mutable.isEmpty()) {
      out.add(mutable.remove(random.nextInt(mutable.size())));
    }
    return out;
  }
}