Merge "Fix PriorityQueue.removeAt(.), call siftUp(.) if needed."

2 files changed, 23 insertions, 3 deletions

diff --git a/luni/src/main/java/java/util/PriorityQueue.java b/luni/src/main/java/java/util/PriorityQueue.java
index cc9bfe6..690c1f8 100644
--- a/luni/src/main/java/java/util/PriorityQueue.java
+++ b/luni/src/main/java/java/util/PriorityQueue.java
@@ -26,8 +26,8 @@ import java.io.Serializable;
  * construction time. If the queue uses natural ordering, only elements that are
  * comparable are permitted to be inserted into the queue.
  * <p>
- * The least element of the specified ordering is stored at the head of the
- * queue and the greatest element is stored at the tail of the queue.
+ * The least element of the specified ordering is the first retrieved with
+ * {@link #poll()} and the greatest element is the last.
  * <p>
  * A PriorityQueue is not synchronized. If multiple threads will have to access
  * it concurrently, use the {@link java.util.concurrent.PriorityBlockingQueue}.
@@ -341,9 +341,13 @@ public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
 
     private void removeAt(int index) {
         size--;
-        elements[index] = elements[size];
+        E moved = elements[size];
+        elements[index] = moved;
         siftDown(index);
         elements[size] = null;
+        if (moved == elements[index]) {
+            siftUp(index);
+        }
     }
 
     private int compare(E o1, E o2) {
diff --git a/luni/src/test/java/libcore/java/util/OldPriorityQueueTest.java b/luni/src/test/java/libcore/java/util/OldPriorityQueueTest.java
index de24cf9..26527aa 100644
--- a/luni/src/test/java/libcore/java/util/OldPriorityQueueTest.java
+++ b/luni/src/test/java/libcore/java/util/OldPriorityQueueTest.java
@@ -104,4 +104,20 @@ public class OldPriorityQueueTest extends TestCase {
         }
     }
 
+    /**
+     * removeAt(.) must sometimes perform siftUp(.).
+     */
+    public void test_removeAt_siftUp() {
+        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
+        // Adding a valid heap will keep elements in the same order
+        for (int i : new int[] { 0, 3, 1, 4, 5, 6, 2 }) {
+            q.add(i);
+        }
+        q.remove(4);  // 2 replaces 4 but parent is 3, siftUp(.) is needed
+        for (int i : new int[] { 0, 1, 2, 3, 5, 6 }) {
+            assertEquals(i, (int) q.poll());
+        }
+        assertNull(q.poll());
+    }
+
 }