HeapBasedPriorityQueue迭代器问题：队列修改后hasNext未正确返回false

HeapBasedPriorityQueue的以下elements()方法实现存在错误：

public Iterator<E> elements() {
        return new Iterator<E>() {
            private int currentIndex = 0;
            private int expectedModificationCount = modificationCount;

        @Override
        public boolean hasNext() {

            return currentIndex < size;
        }

        @Override
        public K next() {
            // checkModificationCount();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return heap[currentIndex++].getKey();
        }

        private void checkModificationCount() {
            if (expectedModificationCount != modificationCount) {
                throw new ConcurrentModificationException("Priority queue modified during     iteration");
            }
        }
    };
}

public Iterator<E> elements() {
    return new Iterator<E>() {
        private int currentIndex = 0;
        private int expectedModificationCount = modificationCount;

        @Override
        public boolean hasNext() {
            //checkModificationCount();
            return currentIndex < size;
        }

        @Override
        public E next() {
            checkModificationCount();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E element = heap[currentIndex].getElement();
            currentIndex++;
            return element;
        }

        private void checkModificationCount() {
            if (expectedModificationCount != modificationCount) {
                throw new ConcurrentModificationException("Priority queue modified during iteration");
            }
        }
    };
}

当优先队列被修改后，对应的迭代器应当终止。运行如下测试方法时：

@Test
void testContinuingElements() {
    PriorityQueue<String, Integer> pq = new HeapBasedPriorityQueue<>(STRING_COMPARATOR);
    pq.insert("test1", 1);
    Iterator<Integer> elements1 = pq.elements();
    pq.insert("test2", 2);
    Iterator<Integer> elements2 = pq.elements();
    assertFalse(elements1.hasNext(), "Iterator should be ended after modification of the priority queue");
    assertThrows(ConcurrentModificationException.class, elements1::next, "Iterator should throw ConcurrentModificationException after modification of the priority queue");
    assertTrue(elements2.hasNext(), "Iterator generated after last change can continue");
    assertEquals(1, elements2.next(), "Iterator generated after last change can continue");
}

要求elements1.hasNext()返回false以通过测试断言，但当前实现无法满足该要求。

当前实现的hasNext()方法仅判断currentIndex < size，完全没有检查队列是否被修改。当队列插入新元素后，size变大，elements1的hasNext()会返回true，不符合测试要求。

要满足需求，需要修改hasNext()方法：先检查队列是否被修改，若已修改则直接返回false；未修改时再判断是否还有元素可迭代。同时保留next()方法中的并发修改检查，确保调用next()时抛出ConcurrentModificationException。

修复后的elements()方法代码如下：

public Iterator<E> elements() {
    return new Iterator<E>() {
        private int currentIndex = 0;
        private int expectedModificationCount = modificationCount;

        @Override
        public boolean hasNext() {
            // 先检查队列是否被修改，修改则返回false
            if (expectedModificationCount != modificationCount) {
                return false;
            }
            return currentIndex < size;
        }

        @Override
        public E next() {
            checkModificationCount();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E element = heap[currentIndex].getElement();
            currentIndex++;
            return element;
        }

        private void checkModificationCount() {
            if (expectedModificationCount != modificationCount) {
                throw new ConcurrentModificationException("Priority queue modified during iteration");
            }
        }
    };
}

修复说明 #

1. hasNext()方法新增并发修改检查：当expectedModificationCount与modificationCount不一致时，直接返回false，符合测试对elements1.hasNext()的要求。
2. next()方法保留原有的checkModificationCount()调用，确保队列被修改后调用next()会抛出ConcurrentModificationException，满足测试断言。
3. 新生成的elements2迭代器会使用修改后的modificationCount，因此能正常迭代队列元素。

内容的提问来源于stack exchange，提问作者ivan