Implement PriorityQueue.iterator()
Also fixes inconsistent state in addAll()
when collection with null elements passed.
Removes containsAll method which is the same
as Collection.containsAll.
Change-Id: Ie1927ce2b0555920d6801709738a6d303371655f
diff --git a/tools/api-checker/config/gwt27_28userApi.conf b/tools/api-checker/config/gwt27_28userApi.conf
index 1b40f2d..297e668 100644
--- a/tools/api-checker/config/gwt27_28userApi.conf
+++ b/tools/api-checker/config/gwt27_28userApi.conf
@@ -218,4 +218,8 @@
java.util.AbstractQueue::offer(Ljava/lang/Object;) MISSING
java.util.AbstractQueue::peek() MISSING
java.util.AbstractQueue::poll() MISSING
-java.util.AbstractSequentialList::size() MISSING
\ No newline at end of file
+java.util.AbstractSequentialList::size() MISSING
+
+# Removed some JRE incompatible PriorityQueue APIs
+java.util.PriorityQueue::makeHeap(I) MISSING
+java.util.PriorityQueue::mergeHeaps(I) MISSING
\ No newline at end of file
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 90480b8..a493491 100644
--- a/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
+++ b/user/super/com/google/gwt/emul/java/util/PriorityQueue.java
@@ -17,7 +17,9 @@
import static javaemul.internal.InternalPreconditions.checkArgument;
import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
+import static javaemul.internal.InternalPreconditions.checkElement;
import static javaemul.internal.InternalPreconditions.checkNotNull;
+import static javaemul.internal.InternalPreconditions.checkState;
/**
* An unbounded priority queue based on a priority heap.
@@ -80,14 +82,12 @@
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
- // TODO(jat): better solution
this(c.size(), (Comparator<? super E>) c.comparator());
addAll(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
- // TODO(jat): better solution
this(c.size(), (Comparator<? super E>) c.comparator());
addAll(c);
}
@@ -96,7 +96,12 @@
public boolean addAll(Collection<? extends E> c) {
checkNotNull(c);
checkArgument(c != this);
- if (heap.addAll(c)) {
+
+ int oldSize = heap.size();
+ for (E e : c) {
+ heap.add(checkCriticalNotNull(e));
+ }
+ if (oldSize != heap.size()) {
makeHeap(0);
return true;
}
@@ -114,39 +119,33 @@
@Override
public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
-
- @Override
- public boolean containsAll(Collection<?> c) {
- return heap.containsAll(c);
+ return indexOf(o) != -1;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
- private E current = null;
- // Make a copy of the elements so that remove() doesn't screw up the order.
- Iterator<E> elementsToTraverse = new ArrayList<>(heap).iterator();
+ int i = 0, last = -1;
+
@Override
public boolean hasNext() {
- return elementsToTraverse.hasNext();
+ return i < heap.size();
}
@Override
public E next() {
- current = elementsToTraverse.next();
- return current;
+ checkElement(hasNext());
+
+ last = i++;
+ return heap.get(last);
}
@Override
public void remove() {
- if (current == null) {
- throw new IllegalStateException("remove() called before iteration or removed already.");
- }
- // Remove the current element. Keep on iterating.
- PriorityQueue.this.remove(current);
- current = null;
+ checkState(last != -1);
+
+ removeAtIndex(i = last);
+ last = -1;
}
};
}
@@ -238,7 +237,7 @@
*
* @param node
*/
- protected void makeHeap(int node) {
+ private void makeHeap(int node) {
if (isLeaf(node)) {
// leaf node are automatically valid heaps
return;
@@ -259,7 +258,7 @@
*
* @param node the parent of the two subtrees to merge
*/
- protected void mergeHeaps(int node) {
+ private void mergeHeaps(int node) {
int heapSize = heap.size();
E value = heap.get(node);
while (!isLeaf(node, heapSize)) {
@@ -296,6 +295,10 @@
return isLeaf(node, heap.size());
}
+ /**
+ * This method leaves the elements at up to i-1, inclusive, untouched.
+ * This information is used by PriorityQueue iterator implementation.
+ */
private void removeAtIndex(int index) {
// Remove the last element; put it in place of the really removed element.
E lastValue = heap.remove(heap.size() - 1);
diff --git a/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java b/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
index 4f10055..abed20f 100644
--- a/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/PriorityQueueTest.java
@@ -15,13 +15,12 @@
*/
package com.google.gwt.emultest.java.util;
-import com.google.gwt.junit.client.GWTTestCase;
+import org.apache.commons.collections.TestCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
-import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.TreeSet;
@@ -29,12 +28,7 @@
/**
* Test PriorityQueue.
*/
-public class PriorityQueueTest extends GWTTestCase {
-
- @Override
- public String getModuleName() {
- return "com.google.gwt.emultest.EmulSuite";
- }
+public class PriorityQueueTest extends TestCollection {
public void testAdd() {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
@@ -65,6 +59,7 @@
fail();
} catch (NullPointerException expected) {
}
+ assertTrue(Arrays.asList(1).containsAll(queue));
queue = new PriorityQueue<>();
queue.addAll(Arrays.asList(2, 1, 3));
@@ -248,38 +243,31 @@
return pq;
}
- public void testIteratorRemove() {
- PriorityQueue<Integer> queue = new PriorityQueue<>();
- queue.add(1);
- queue.add(2);
- queue.add(3);
- queue.add(5);
- queue.add(6);
+ /**
+ * Null elements are prohibited in PriorityQueue.
+ */
+ @Override
+ protected Object[] getFullElements() {
+ return new Integer[] {1, 2, 3, 4};
+ }
- int sum = 0;
- Iterator<Integer> it = queue.iterator();
- while (it.hasNext()) {
- int i = it.next();
- if (i == 2) {
- it.remove();
- }
- sum += i;
- }
- assertEquals(17, sum);
- assertEquals(4, queue.size());
+ @Override
+ protected Object[] getOtherElements() {
+ return new Integer[] {5, 6, 7, 8};
+ }
- try {
- queue.iterator().remove();
- fail();
- } catch (IllegalStateException e) { }
+ @Override
+ protected Collection makeConfirmedCollection() {
+ return new ArrayList<>();
+ }
- try {
- Iterator<Integer> itt = queue.iterator();
- while (itt.hasNext()) {
- it.remove();
- it.remove();
- fail();
- }
- } catch (IllegalStateException e) { };
+ @Override
+ protected Collection makeConfirmedFullCollection() {
+ return new ArrayList<>(Arrays.asList(getFullElements()));
+ }
+
+ @Override
+ protected Collection makeCollection() {
+ return new PriorityQueue();
}
}
