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(); } }