| /* |
| * 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.base.Preconditions.checkArgument; |
| 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 com.google.common.truth.Truth.assertThat; |
| import static java.util.Arrays.asList; |
| |
| import com.google.common.annotations.GwtCompatible; |
| 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.primitives.Ints; |
| import com.google.common.testing.EqualsTester; |
| |
| 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 testAllEqual() { |
| Ordering<Object> comparator = Ordering.allEqual(); |
| assertSame(comparator, comparator.reverse()); |
| |
| assertEquals(comparator.compare(null, null), 0); |
| assertEquals(comparator.compare(new Object(), new Object()), 0); |
| assertEquals(comparator.compare("apples", "oranges"), 0); |
| assertSame(comparator, reserialize(comparator)); |
| assertEquals("Ordering.allEqual()", comparator.toString()); |
| |
| List<String> strings = ImmutableList.of("b", "a", "d", "c"); |
| assertEquals(strings, comparator.sortedCopy(strings)); |
| assertEquals(strings, comparator.immutableSortedCopy(strings)); |
| } |
| |
| 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); |
| assertThat(list).has().exactly(8, 6, 7, 5, 3, 0, 9).inOrder(); |
| 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(ImmutableList.of( |
| 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); |
| |
| new EqualsTester() |
| .addEqualityGroup(lexy, ordering.lexicographical()) |
| .addEqualityGroup(numberOrdering.lexicographical()) |
| .addEqualityGroup(Ordering.natural()) |
| .testEquals(); |
| } |
| |
| public void testNullsFirst() { |
| Ordering<Integer> ordering = Ordering.natural().nullsFirst(); |
| Helpers.testComparator(ordering, null, Integer.MIN_VALUE, 0, 1); |
| |
| new EqualsTester() |
| .addEqualityGroup(ordering, Ordering.natural().nullsFirst()) |
| .addEqualityGroup(numberOrdering.nullsFirst()) |
| .addEqualityGroup(Ordering.natural()) |
| .testEquals(); |
| } |
| |
| public void testNullsLast() { |
| Ordering<Integer> ordering = Ordering.natural().nullsLast(); |
| Helpers.testComparator(ordering, 0, 1, Integer.MAX_VALUE, null); |
| |
| new EqualsTester() |
| .addEqualityGroup(ordering, Ordering.natural().nullsLast()) |
| .addEqualityGroup(numberOrdering.nullsLast()) |
| .addEqualityGroup(Ordering.natural()) |
| .testEquals(); |
| } |
| |
| 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 testLeastOfIterable_empty_0() { |
| List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 0); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterator_empty_0() { |
| List<Integer> result = numberOrdering.leastOf( |
| Iterators.<Integer>emptyIterator(), 0); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterable_empty_1() { |
| List<Integer> result = numberOrdering.leastOf(Arrays.<Integer>asList(), 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterator_empty_1() { |
| List<Integer> result = numberOrdering.leastOf( |
| Iterators.<Integer>emptyIterator(), 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterable_simple_negativeOne() { |
| try { |
| numberOrdering.leastOf(Arrays.asList(3, 4, 5, -1), -1); |
| fail(); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| public void testLeastOfIterator_simple_negativeOne() { |
| try { |
| numberOrdering.leastOf(Iterators.forArray(3, 4, 5, -1), -1); |
| fail(); |
| } catch (IllegalArgumentException expected) { |
| } |
| } |
| |
| public void testLeastOfIterable_singleton_0() { |
| List<Integer> result = numberOrdering.leastOf(Arrays.asList(3), 0); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterator_singleton_0() { |
| List<Integer> result = numberOrdering.leastOf( |
| Iterators.singletonIterator(3), 0); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterable_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 testLeastOfIterator_simple_0() { |
| List<Integer> result = numberOrdering.leastOf( |
| Iterators.forArray(3, 4, 5, -1), 0); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.<Integer>of(), result); |
| } |
| |
| public void testLeastOfIterable_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 testLeastOfIterator_simple_1() { |
| List<Integer> result = numberOrdering.leastOf( |
| Iterators.forArray(3, 4, 5, -1), 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1), result); |
| } |
| |
| public void testLeastOfIterable_simple_nMinusOne_withNullElement() { |
| List<Integer> list = Arrays.asList(3, null, 5, -1); |
| List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size() - 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1, 3, 5), result); |
| } |
| |
| public void testLeastOfIterator_simple_nMinusOne_withNullElement() { |
| Iterator<Integer> itr = Iterators.forArray(3, null, 5, -1); |
| List<Integer> result = Ordering.natural().nullsLast().leastOf(itr, 3); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1, 3, 5), result); |
| } |
| |
| public void testLeastOfIterable_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 testLeastOfIterator_simple_nMinusOne() { |
| List<Integer> list = Arrays.asList(3, 4, 5, -1); |
| List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size() - 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1, 3, 4), result); |
| } |
| |
| public void testLeastOfIterable_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 testLeastOfIterator_simple_n() { |
| List<Integer> list = Arrays.asList(3, 4, 5, -1); |
| List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size()); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1, 3, 4, 5), result); |
| } |
| |
| public void testLeastOfIterable_simple_n_withNullElement() { |
| List<Integer> list = Arrays.asList(3, 4, 5, null, -1); |
| List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size()); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(Arrays.asList(-1, 3, 4, 5, null), result); |
| } |
| |
| public void testLeastOfIterator_simple_n_withNullElement() { |
| List<Integer> list = Arrays.asList(3, 4, 5, null, -1); |
| List<Integer> result = Ordering.natural().nullsLast().leastOf( |
| list.iterator(), list.size()); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(Arrays.asList(-1, 3, 4, 5, null), result); |
| } |
| |
| public void testLeastOfIterable_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 testLeastOfIterator_simple_nPlusOne() { |
| List<Integer> list = Arrays.asList(3, 4, 5, -1); |
| List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size() + 1); |
| assertTrue(result instanceof RandomAccess); |
| assertListImmutable(result); |
| assertEquals(ImmutableList.of(-1, 3, 4, 5), result); |
| } |
| |
| public void testLeastOfIterable_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); |
| } |
| |
| public void testLeastOfIterator_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.iterator(), list.size()); |
| assertEquals(ImmutableList.of(-1, 3, foo, bar), result); |
| } |
| |
| 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 testLeastOfIterableLargeK() { |
| List<Integer> list = Arrays.asList(4, 2, 3, 5, 1); |
| assertEquals(Arrays.asList(1, 2, 3, 4, 5), Ordering.natural() |
| .leastOf(list, Integer.MAX_VALUE)); |
| } |
| |
| public void testLeastOfIteratorLargeK() { |
| List<Integer> list = Arrays.asList(4, 2, 3, 5, 1); |
| assertEquals(Arrays.asList(1, 2, 3, 4, 5), Ordering.natural() |
| .leastOf(list.iterator(), Integer.MAX_VALUE)); |
| } |
| |
| public void testGreatestOfIterable_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)); |
| } |
| |
| public void testGreatestOfIterator_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.iterator(), 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(), "a", "b", "d"); |
| } |
| |
| /** |
| * Requires at least 3 elements in {@code strictlyOrderedElements} in order to |
| * test the varargs version of min/max. |
| */ |
| private static <T> void testExhaustively( |
| Ordering<? super T> ordering, T... strictlyOrderedElements) { |
| checkArgument(strictlyOrderedElements.length >= 3, "strictlyOrderedElements " |
| + "requires at least 3 elements"); |
| List<T> list = Arrays.asList(strictlyOrderedElements); |
| |
| // for use calling Collection.toArray later |
| T[] emptyArray = Platform.newArray(strictlyOrderedElements, 0); |
| |
| // 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, emptyArray); |
| verifyScenario(starter, 0); |
| } |
| |
| private static <T> void verifyScenario(Scenario<T> scenario, int level) { |
| scenario.testCompareTo(); |
| scenario.testIsOrdered(); |
| scenario.testMinAndMax(); |
| scenario.testBinarySearch(); |
| scenario.testSortedCopy(); |
| |
| 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; |
| final T[] emptyArray; |
| |
| Scenario(Ordering<T> ordering, List<T> strictlyOrderedList, T[] emptyArray) { |
| this.ordering = ordering; |
| this.strictlyOrderedList = strictlyOrderedList; |
| this.emptyArray = emptyArray; |
| } |
| |
| void testCompareTo() { |
| Helpers.testComparator(ordering, strictlyOrderedList); |
| } |
| |
| void testIsOrdered() { |
| assertTrue(ordering.isOrdered(strictlyOrderedList)); |
| assertTrue(ordering.isStrictlyOrdered(strictlyOrderedList)); |
| } |
| |
| @SuppressWarnings("unchecked") // generic arrays and unchecked cast |
| void testMinAndMax() { |
| List<T> shuffledList = Lists.newArrayList(strictlyOrderedList); |
| shuffledList = shuffledCopy(shuffledList, new Random(5)); |
| |
| T min = strictlyOrderedList.get(0); |
| T max = strictlyOrderedList.get(strictlyOrderedList.size() - 1); |
| |
| T first = shuffledList.get(0); |
| T second = shuffledList.get(1); |
| T third = shuffledList.get(2); |
| T[] rest = shuffledList.subList(3, shuffledList.size()).toArray(emptyArray); |
| |
| assertEquals(min, ordering.min(shuffledList)); |
| assertEquals(min, ordering.min(shuffledList.iterator())); |
| assertEquals(min, ordering.min(first, second, third, rest)); |
| assertEquals(min, ordering.min(min, max)); |
| assertEquals(min, ordering.min(max, min)); |
| |
| assertEquals(max, ordering.max(shuffledList)); |
| assertEquals(max, ordering.max(shuffledList.iterator())); |
| assertEquals(max, ordering.max(first, second, third, rest)); |
| assertEquals(max, ordering.max(min, max)); |
| assertEquals(max, ordering.max(max, min)); |
| } |
| |
| 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)); |
| } |
| |
| void testSortedCopy() { |
| List<T> shuffledList = Lists.newArrayList(strictlyOrderedList); |
| shuffledList = shuffledCopy(shuffledList, new Random(5)); |
| |
| assertEquals(strictlyOrderedList, ordering.sortedCopy(shuffledList)); |
| |
| if (!strictlyOrderedList.contains(null)) { |
| assertEquals(strictlyOrderedList, ordering.immutableSortedCopy(shuffledList)); |
| } |
| } |
| } |
| |
| /** |
| * 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, scenario.emptyArray); |
| } |
| }, |
| 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, scenario.emptyArray); |
| } |
| }, |
| 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, scenario.emptyArray); |
| } |
| }, |
| 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, new Integer[0]); |
| } |
| }, |
| COMPOUND_THIS_WITH_NATURAL { |
| @SuppressWarnings("unchecked") // raw array |
| @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, new Composite[0]); |
| } |
| }, |
| COMPOUND_NATURAL_WITH_THIS { |
| @SuppressWarnings("unchecked") // raw array |
| @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, new Composite[0]); |
| } |
| }, |
| 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, new Iterable[0]); |
| } |
| }, |
| ; |
| |
| 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 Ints.compare(rank, that.rank); |
| } |
| |
| static <T> Function<Composite<T>, T> getValueFunction() { |
| return new Function<Composite<T>, T>() { |
| @Override |
| public T apply(Composite<T> from) { |
| return from.value; |
| } |
| }; |
| } |
| } |
| |
| 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; |
| } |
| } |
| |
