Small refactoring of Collection's impl
Also refactors and fixes internal comparators usage.
Change-Id: Ifc64c515191d2a62f76990db4f0c0573e322edae
diff --git a/user/super/com/google/gwt/emul/java/util/Arrays.java b/user/super/com/google/gwt/emul/java/util/Arrays.java
index d3cfd15..b288ec2 100644
--- a/user/super/com/google/gwt/emul/java/util/Arrays.java
+++ b/user/super/com/google/gwt/emul/java/util/Arrays.java
@@ -120,7 +120,7 @@
@SuppressWarnings("unchecked")
@Override
public <T> T[] toArray(T[] out) {
- int size = size();
+ int size = array.length;
if (out.length < size) {
out = ArrayHelper.createFrom(out, size);
}
@@ -502,9 +502,7 @@
private static <T> int binarySearch0(final T[] sortedArray, int fromIndex, int toIndex,
final T key, Comparator<? super T> comparator) {
- if (comparator == null) {
- comparator = Comparators.natural();
- }
+ comparator = Comparators.nullToNaturalOrder(comparator);
int low = fromIndex;
int high = toIndex - 1;
@@ -1696,9 +1694,7 @@
*/
@SuppressWarnings("unchecked")
private static void mergeSort(Object[] x, int fromIndex, int toIndex, Comparator<?> comp) {
- if (comp == null) {
- comp = Comparators.natural();
- }
+ comp = Comparators.nullToNaturalOrder(comp);
Object[] temp = ArrayHelper.unsafeClone(x, fromIndex, toIndex);
mergeSort(temp, x, fromIndex, toIndex, -fromIndex,
(Comparator<Object>) comp);
diff --git a/user/super/com/google/gwt/emul/java/util/Collections.java b/user/super/com/google/gwt/emul/java/util/Collections.java
index 8acab17..c41e884 100644
--- a/user/super/com/google/gwt/emul/java/util/Collections.java
+++ b/user/super/com/google/gwt/emul/java/util/Collections.java
@@ -199,15 +199,6 @@
}
}
- private static final class ReverseComparator implements Comparator<Comparable<Object>> {
- static final ReverseComparator INSTANCE = new ReverseComparator();
-
- @Override
- public int compare(Comparable<Object> o1, Comparable<Object> o2) {
- return o2.compareTo(o1);
- }
- }
-
private static final class SetFromMap<E> extends AbstractSet<E>
implements Serializable {
@@ -963,9 +954,7 @@
* in the JDK docs for non-RandomAccess Lists. Until GWT provides a
* LinkedList, this shouldn't be an issue.
*/
- if (comparator == null) {
- comparator = Comparators.natural();
- }
+ comparator = Comparators.nullToNaturalOrder(comparator);
int low = 0;
int high = sortedList.size() - 1;
@@ -1091,9 +1080,7 @@
public static <T> T max(Collection<? extends T> coll,
Comparator<? super T> comp) {
- if (comp == null) {
- comp = Comparators.natural();
- }
+ comp = Comparators.nullToNaturalOrder(comp);
Iterator<? extends T> it = coll.iterator();
@@ -1165,19 +1152,11 @@
@SuppressWarnings("unchecked")
public static <T> Comparator<T> reverseOrder() {
- return (Comparator<T>) ReverseComparator.INSTANCE;
+ return (Comparator<T>) Comparator.reverseOrder();
}
- public static <T> Comparator<T> reverseOrder(final Comparator<T> cmp) {
- if (cmp == null) {
- return reverseOrder();
- }
- return new Comparator<T>() {
- @Override
- public int compare(T t1, T t2) {
- return cmp.compare(t2, t1);
- }
- };
+ public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
+ return cmp == null ? reverseOrder() : cmp.reversed();
}
/**
diff --git a/user/super/com/google/gwt/emul/java/util/Comparator.java b/user/super/com/google/gwt/emul/java/util/Comparator.java
index 9b8235d..39df0fa 100644
--- a/user/super/com/google/gwt/emul/java/util/Comparator.java
+++ b/user/super/com/google/gwt/emul/java/util/Comparator.java
@@ -39,7 +39,7 @@
boolean equals(Object other);
default Comparator<T> reversed() {
- return (a, b) -> compare(b, a);
+ return new Comparators.ReversedComparator<T>(this);
}
default Comparator<T> thenComparing(Comparator<? super T> other) {
@@ -104,7 +104,7 @@
}
static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
- return Comparators.natural();
+ return Comparators.naturalOrder();
}
static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) {
@@ -116,6 +116,6 @@
}
static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
- return Comparators.reverseOrder();
+ return Comparators.reverseNaturalOrder();
}
}
diff --git a/user/super/com/google/gwt/emul/java/util/Comparators.java b/user/super/com/google/gwt/emul/java/util/Comparators.java
index b01804c..7e1c1e4 100644
--- a/user/super/com/google/gwt/emul/java/util/Comparators.java
+++ b/user/super/com/google/gwt/emul/java/util/Comparators.java
@@ -28,9 +28,60 @@
* This class is package protected since it is not in the JRE.
*/
- private static final Comparator<Comparable<Object>> NATURAL = (a, b) -> checkNotNull(a).compareTo(checkNotNull(b));
+ private static final Comparator<Comparable<Object>> INTERNAL_NATURAL_ORDER =
+ new NaturalOrderComparator();
- private static final Comparator<Comparable<Object>> REVERSE_ORDER = (a, b) -> checkNotNull(b).compareTo(checkNotNull(a));
+ private static final Comparator<Comparable<Object>> NATURAL_ORDER =
+ new NaturalOrderComparator();
+
+ private static final Comparator<Comparable<Object>> REVERSE_NATURAL_ORDER =
+ new ReverseNaturalOrderComparator();
+
+ private static final class NaturalOrderComparator
+ implements Comparator<Comparable<Object>>, Serializable {
+
+ @Override
+ public int compare(Comparable<Object> a, Comparable<Object> b) {
+ return checkNotNull(a).compareTo(checkNotNull(b));
+ }
+
+ @Override
+ public Comparator<Comparable<Object>> reversed() {
+ return REVERSE_NATURAL_ORDER;
+ }
+ }
+
+ private static final class ReverseNaturalOrderComparator
+ implements Comparator<Comparable<Object>>, Serializable {
+
+ @Override
+ public int compare(Comparable<Object> a, Comparable<Object> b) {
+ return checkNotNull(b).compareTo(checkNotNull(a));
+ }
+
+ @Override
+ public Comparator<Comparable<Object>> reversed() {
+ return NATURAL_ORDER;
+ }
+ }
+
+ static final class ReversedComparator<T> implements Comparator<T>, Serializable {
+ private final Comparator<T> comparator;
+
+ ReversedComparator(Comparator<T> comparator) {
+ this.comparator = comparator;
+ }
+
+ @Override
+ public int compare(T a, T b) {
+ return comparator.compare(b, a);
+ }
+
+ @Override
+ public Comparator<T> reversed() {
+ return comparator;
+ }
+ }
static final class NullComparator<T> implements Comparator<T>, Serializable {
private final boolean nullFirst;
@@ -68,20 +119,51 @@
/**
* Returns the natural Comparator which compares two Objects
* according to their <i>natural ordering</i>.
- * <p>
- * Example:
- *
- * <pre>Comparator<String> compareString = Comparators.natural()</pre>
- *
- * @return the natural Comparator
*/
@SuppressWarnings("unchecked")
- public static <T> Comparator<T> natural() {
- return (Comparator<T>) NATURAL;
+ static <T> Comparator<T> naturalOrder() {
+ return (Comparator<T>) NATURAL_ORDER;
}
+ /**
+ * Returns reversed natural Comparator which compares two Objects
+ * according to their <i>reversed natural ordering</i>.
+ */
@SuppressWarnings("unchecked")
- public static <T> Comparator<T> reverseOrder() {
- return (Comparator<T>) REVERSE_ORDER;
+ static <T> Comparator<T> reverseNaturalOrder() {
+ return (Comparator<T>) REVERSE_NATURAL_ORDER;
}
+
+ /**
+ * Returns the given comparator if it is non-null; natural order comparator otherwise.
+ * This comparator must not be the same object as {@link Comparators#NATURAL_ORDER} comparator
+ * because it's used to mask out client provided comparators in TreeMap and PriorityQueue
+ * in {@link Comparators#naturalOrderToNull(Comparator)}.
+ *
+ * See:
+ * {@link Arrays#binarySearch(Object[], Object, Comparator)}
+ * {@link Arrays#binarySearch(Object[], int, int, Object, Comparator)}
+ * {@link Arrays#sort(Object[], Comparator)}
+ * {@link Arrays#sort(Object[], int, int, Comparator)}
+ * {@link TreeMap#TreeMap(Comparator)}
+ * {@link PriorityQueue#PriorityQueue(Comparator)}
+ */
+ @SuppressWarnings("unchecked")
+ static <T> Comparator<T> nullToNaturalOrder(Comparator<T> cmp) {
+ return cmp == null ? (Comparator<T>) INTERNAL_NATURAL_ORDER : cmp;
+ }
+
+ /**
+ * Return null if the given comparator is natural order comparator returned by
+ * {@link Comparators#nullToNaturalOrder(Comparator)}; given comparator otherwise.
+ *
+ * See:
+ * {@link TreeMap#comparator()}
+ * {@link PriorityQueue#comparator()}
+ */
+ static <T> Comparator<T> naturalOrderToNull(Comparator<T> cmp) {
+ return cmp == INTERNAL_NATURAL_ORDER ? null : cmp;
+ }
+
+ private Comparators() { }
}
diff --git a/user/super/com/google/gwt/emul/java/util/HashSet.java b/user/super/com/google/gwt/emul/java/util/HashSet.java
index 63d4585..c620d60 100644
--- a/user/super/com/google/gwt/emul/java/util/HashSet.java
+++ b/user/super/com/google/gwt/emul/java/util/HashSet.java
@@ -103,9 +103,4 @@
return map.size();
}
- @Override
- public String toString() {
- return map.keySet().toString();
- }
-
}
diff --git a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
index aa53418..59de7e9 100644
--- a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
+++ b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
@@ -70,11 +70,8 @@
}
public PriorityQueue(int initialCapacity, Comparator<? super E> cmp) {
- heap = new ArrayList<E>(initialCapacity);
- if (cmp == null) {
- cmp = Comparators.natural();
- }
- this.cmp = cmp;
+ heap = new ArrayList<>(initialCapacity);
+ this.cmp = Comparators.nullToNaturalOrder(cmp);
}
public PriorityQueue(Comparator<? super E> comparator) {
@@ -112,7 +109,7 @@
}
public Comparator<? super E> comparator() {
- return cmp == Comparators.natural() ? null : cmp;
+ return Comparators.naturalOrderToNull(cmp);
}
@Override
@@ -126,11 +123,6 @@
}
@Override
- public boolean isEmpty() {
- return heap.isEmpty();
- }
-
- @Override
public Iterator<E> iterator() {
// TODO(jat): PriorityQueue is supposed to have a modifiable iterator.
return Collections.unmodifiableList(heap).iterator();
@@ -158,19 +150,15 @@
@Override
public E peek() {
- if (heap.size() == 0) {
- return null;
- }
- return heap.get(0);
+ return heap.isEmpty() ? null : heap.get(0);
}
@Override
public E poll() {
- if (heap.size() == 0) {
- return null;
+ E value = peek();
+ if (value != null) {
+ removeAtIndex(0);
}
- E value = heap.get(0);
- removeAtIndex(0);
return value;
}
@@ -222,14 +210,9 @@
return heap.toArray(a);
}
- @Override
- public String toString() {
- return heap.toString();
- }
-
/**
* Make the subtree rooted at <code>node</code> a valid heap. O(n) time
- *
+ *
* @param node
*/
protected void makeHeap(int node) {
diff --git a/user/super/com/google/gwt/emul/java/util/TreeMap.java b/user/super/com/google/gwt/emul/java/util/TreeMap.java
index 7a5125b..2cb5cce 100644
--- a/user/super/com/google/gwt/emul/java/util/TreeMap.java
+++ b/user/super/com/google/gwt/emul/java/util/TreeMap.java
@@ -247,12 +247,7 @@
@Override
public Set<Entry<K, V>> entrySet() {
- return new SubMap.EntrySet() {
- @Override
- public boolean isEmpty() {
- return SubMap.this.isEmpty();
- }
- };
+ return new SubMap.EntrySet();
}
@Override
@@ -269,11 +264,6 @@
}
@Override
- public boolean isEmpty() {
- return getFirstEntry() == null;
- }
-
- @Override
public V put(K key, V value) {
if (!inRange(key)) {
throw new IllegalArgumentException(key + " outside the range "
@@ -294,6 +284,10 @@
@Override
public int size() {
+ if (getFirstEntry() == null) {
+ return 0;
+ }
+
// TODO(jat): more efficient way to do this?
int count = 0;
for (Iterator<Entry<K, V>> it = entryIterator(); it.hasNext(); it.next()) {
@@ -488,10 +482,7 @@
@SuppressWarnings("unchecked")
public TreeMap(Comparator<? super K> c) {
root = null;
- if (c == null) {
- c = Comparators.natural();
- }
- cmp = c;
+ cmp = Comparators.nullToNaturalOrder(c);
}
public TreeMap(Map<? extends K, ? extends V> map) {
@@ -513,10 +504,7 @@
@Override
public Comparator<? super K> comparator() {
- if (cmp == Comparators.natural()) {
- return null;
- }
- return cmp;
+ return Comparators.naturalOrderToNull(cmp);
}
@Override
diff --git a/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
index c8cc026..e614fd1 100644
--- a/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/TreeMapTest.java
@@ -322,6 +322,32 @@
} else {
assertEquals(getComparator(), sortedMap.comparator());
}
+
+ TreeMap<K, V> treeMap = new TreeMap<>();
+ TreeMap<K, V> secondTreeMap = new TreeMap<>(treeMap);
+ assertNull(treeMap.comparator());
+ assertNull(secondTreeMap.comparator());
+
+ treeMap = new TreeMap<>((Comparator<? super K>) null);
+ secondTreeMap = new TreeMap<>(treeMap);
+ assertNull(treeMap.comparator());
+ assertNull(secondTreeMap.comparator());
+
+ final Comparator<? super K> customComparator = new Comparator<K>() {
+ @Override
+ public int compare(K o1, K o2) {
+ return o1.compareTo(o2);
+ }
+ };
+ treeMap = new TreeMap<>(customComparator);
+ secondTreeMap = new TreeMap<>(treeMap);
+ assertSame(customComparator, treeMap.comparator());
+ assertSame(customComparator, secondTreeMap.comparator());
+
+ treeMap = new TreeMap<>(new HashMap<K, V>());
+ secondTreeMap = new TreeMap<>(treeMap);
+ assertNull(treeMap.comparator());
+ assertNull(secondTreeMap.comparator());
}
/**
diff --git a/user/test/com/google/gwt/emultest/java8/util/ComparatorTest.java b/user/test/com/google/gwt/emultest/java8/util/ComparatorTest.java
index 9460571..f18a32f 100644
--- a/user/test/com/google/gwt/emultest/java8/util/ComparatorTest.java
+++ b/user/test/com/google/gwt/emultest/java8/util/ComparatorTest.java
@@ -76,23 +76,32 @@
// pre-sorted lists to test against, named for which char (1-indexed) they are sorted on
String[] first = {"1b3", "2a1", "3c2"};
String[] second = {"2a1", "1b3", "3c2"};
- String[] secondReversed = {"3c2", "1b3", "2a1"};
String[] third = {"2a1", "3c2", "1b3"};
// keyextractor
assertSortedEquals(first, strings, Comparator.comparing(Function.identity()));
+ Comparator<String> comparing = Comparator.comparing(Function.identity());
+ assertSortedEquals(reverse(first), strings, comparing.reversed());
assertSortedEquals(second, strings, Comparator.comparing(a -> a.substring(1)));
assertSortedEquals(third, strings, Comparator.comparing(a -> a.substring(2)));
// keyextractor, keycomparator
- assertSortedEquals(secondReversed, strings, Comparator.comparing(a -> a.substring(1), Comparator.<String>reverseOrder()));
+ assertSortedEquals(reverse(second), strings, Comparator.comparing(a -> a.substring(1), Comparator.reverseOrder()));
+ comparing = Comparator.comparing(a -> a.substring(1));
+ assertSortedEquals(reverse(second), strings, comparing.reversed());
// double key extractor
- assertSortedEquals(third, strings, Comparator.comparingDouble(a -> Double.parseDouble(a.substring(2))));
+ comparing = Comparator.comparingDouble(a -> Double.parseDouble(a.substring(2)));
+ assertSortedEquals(third, strings, comparing);
+ assertSortedEquals(reverse(third), strings, comparing.reversed());
// int key extractor
- assertSortedEquals(third, strings, Comparator.comparingInt(a -> Integer.parseInt(a.substring(2))));
+ comparing = Comparator.comparingInt(a -> Integer.parseInt(a.substring(2)));
+ assertSortedEquals(third, strings, comparing);
+ assertSortedEquals(reverse(third), strings, comparing.reversed());
// long key extractor
- assertSortedEquals(third, strings, Comparator.comparingLong(a -> Long.parseLong(a.substring(2))));
+ comparing = Comparator.comparingLong(a -> Long.parseLong(a.substring(2)));
+ assertSortedEquals(third, strings, comparing);
+ assertSortedEquals(reverse(third), strings, comparing.reversed());
}
public void testNullsFirst() {
@@ -128,4 +137,13 @@
Arrays.sort(presortedArray, comparator);
assertEquals(expected, presortedArray);
}
+
+ private static String[] reverse(String[] array) {
+ int length = array.length;
+ String[] reversed = new String[length];
+ for (int i = 0, j = length - 1; i < length; ++i, --j) {
+ reversed[i] = array[j];
+ }
+ return reversed;
+ }
}
diff --git a/user/test/com/google/gwt/emultest/java8/util/TreeMapTest.java b/user/test/com/google/gwt/emultest/java8/util/TreeMapTest.java
index 62b24aa..7b9f52c 100644
--- a/user/test/com/google/gwt/emultest/java8/util/TreeMapTest.java
+++ b/user/test/com/google/gwt/emultest/java8/util/TreeMapTest.java
@@ -15,6 +15,7 @@
*/
package com.google.gwt.emultest.java8.util;
+import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
@@ -23,6 +24,13 @@
*/
public class TreeMapTest extends AbstractJava8MapTest {
+ public void testComparator() {
+ TreeMap<Integer, Object> treeMap = new TreeMap<>(Comparator.naturalOrder());
+ TreeMap<Integer, Object> secondTreeMap = new TreeMap<>(treeMap);
+ assertSame(Comparator.naturalOrder(), treeMap.comparator());
+ assertSame(Comparator.naturalOrder(), secondTreeMap.comparator());
+ }
+
@Override
protected Map<String, String> createMap() {
return new TreeMap<>();