Add `unorderedElements` getter to PriorityQueue. (#155)
* Add `unorderedElements` getter to PriorityQueue.
* Fix bug in queue_list which made tests fail.
diff --git a/lib/src/priority_queue.dart b/lib/src/priority_queue.dart
index 6abce79..6952a81 100644
--- a/lib/src/priority_queue.dart
+++ b/lib/src/priority_queue.dart
@@ -58,6 +58,16 @@
/// an object.
bool contains(E object);
+ /// Provides efficient access to all the elements curently in the queue.
+ ///
+ /// The operation should be performed without copying or moving
+ /// the elements, if at all possible.
+ ///
+ /// The elements are iterated in no particular order.
+ /// The order is stable as long as the queue is not modified.
+ /// The queue must not be modified during an iteration.
+ Iterable<E> get unorderedElements;
+
/// Adds element to the queue.
///
/// The element will become the next to be removed by [removeFirst]
@@ -177,6 +187,11 @@
/// The heap is implemented in the first [_length] entries of [_queue].
int _length = 0;
+ /// Modification count.
+ ///
+ /// Used to detect concurrent modifications during iteration.
+ int _modificationCount = 0;
+
/// Create a new priority queue.
///
/// The [comparison] is a [Comparator] used to compare the priority of
@@ -193,18 +208,23 @@
@override
void add(E element) {
+ _modificationCount++;
_add(element);
}
@override
void addAll(Iterable<E> elements) {
+ var modified = 0;
for (var element in elements) {
+ modified = 1;
_add(element);
}
+ _modificationCount += modified;
}
@override
void clear() {
+ _modificationCount++;
_queue = const [];
_length = 0;
}
@@ -212,6 +232,16 @@
@override
bool contains(E object) => _locate(object) >= 0;
+ /// Provides efficient access to all the elements curently in the queue.
+ ///
+ /// The operation is performed in the order they occur
+ /// in the underlying heap structure.
+ ///
+ /// The order is stable as long as the queue is not modified.
+ /// The queue must not be modified during an iteration.
+ @override
+ Iterable<E> get unorderedElements => _UnorderedElementsIterable<E>(this);
+
@override
E get first {
if (_length == 0) throw StateError('No element');
@@ -231,6 +261,7 @@
bool remove(E element) {
var index = _locate(element);
if (index < 0) return false;
+ _modificationCount++;
var last = _removeLast();
if (index < _length) {
var comp = comparison(last, element);
@@ -243,8 +274,15 @@
return true;
}
+ /// Removes all the elements from this queue and returns them.
+ ///
+ /// The returned iterable has no specified order.
+ /// The operation does not copy the elements,
+ /// but instead keeps them in the existing heap structure,
+ /// and iterates over that directly.
@override
Iterable<E> removeAll() {
+ _modificationCount++;
var result = _queue;
var length = _length;
_queue = const [];
@@ -255,6 +293,7 @@
@override
E removeFirst() {
if (_length == 0) throw StateError('No element');
+ _modificationCount++;
var result = _elementAt(0);
var last = _removeLast();
if (_length > 0) {
@@ -418,3 +457,41 @@
_queue = newQueue;
}
}
+
+/// Implementation of [HeapPriorityQueue.unorderedElements].
+class _UnorderedElementsIterable<E> extends Iterable<E> {
+ final HeapPriorityQueue<E> _queue;
+ _UnorderedElementsIterable(this._queue);
+ @override
+ Iterator<E> get iterator => _UnorderedElementsIterator<E>(_queue);
+}
+
+class _UnorderedElementsIterator<E> implements Iterator<E> {
+ final HeapPriorityQueue<E> _queue;
+ final int _initialModificationCount;
+ E? _current;
+ int _index = -1;
+
+ _UnorderedElementsIterator(this._queue)
+ : _initialModificationCount = _queue._modificationCount;
+
+ @override
+ bool moveNext() {
+ if (_initialModificationCount != _queue._modificationCount) {
+ throw ConcurrentModificationError(_queue);
+ }
+ var nextIndex = _index + 1;
+ if (0 <= nextIndex && nextIndex < _queue.length) {
+ _current = _queue._queue[nextIndex];
+ _index = nextIndex;
+ return true;
+ }
+ _current = null;
+ _index = -2;
+ return false;
+ }
+
+ @override
+ E get current =>
+ _index < 0 ? throw StateError('No element') : (_current ?? null as E);
+}
diff --git a/lib/src/queue_list.dart b/lib/src/queue_list.dart
index 2bda02b..14b696e 100644
--- a/lib/src/queue_list.dart
+++ b/lib/src/queue_list.dart
@@ -150,14 +150,10 @@
@override
set length(int value) {
if (value < 0) throw RangeError('Length $value may not be negative.');
- if (value > length) {
- try {
- null as E;
- } on TypeError {
- throw UnsupportedError(
- 'The length can only be increased when the element type is '
- 'nullable, but the current element type is `$E`.');
- }
+ if (value > length && null is! E) {
+ throw UnsupportedError(
+ 'The length can only be increased when the element type is '
+ 'nullable, but the current element type is `$E`.');
}
var delta = value - length;
diff --git a/test/priority_queue_test.dart b/test/priority_queue_test.dart
index 191857d..ae27f98 100644
--- a/test/priority_queue_test.dart
+++ b/test/priority_queue_test.dart
@@ -14,6 +14,7 @@
testCustom((comparator) => HeapPriorityQueue<C>(comparator));
testDuplicates();
testNullable();
+ testConcurrentModification();
}
void testDefault() {
@@ -69,6 +70,11 @@
expect(q.toList(), equals(elements));
expect(q.toSet().toList(), equals(elements));
+ expect(q.toUnorderedList(), unorderedEquals(elements));
+ expect(q.unorderedElements, unorderedEquals(elements));
+
+ var allElements = q.removeAll();
+ q.addAll(allElements);
for (var i = 0; i < elements.length; i++) {
expect(q.contains(elements[i]), isTrue);
@@ -261,6 +267,98 @@
});
}
+void testConcurrentModification() {
+ group('concurrent modification for', () {
+ test('add', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ q.add(12); // Modifiation before creating iterator is not a problem.
+ var it = e.iterator;
+ q.add(7); // Modification after creatig iterator is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+
+ it = e.iterator; // New iterator is not affected.
+ expect(it.moveNext(), true);
+ expect(it.moveNext(), true);
+ q.add(9); // Modification during iteration is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+
+ test('addAll', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ q.addAll([12]); // Modifiation before creating iterator is not a problem.
+ var it = e.iterator;
+ q.addAll([7]); // Modification after creatig iterator is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+ it = e.iterator; // New iterator is not affected.
+ expect(it.moveNext(), true);
+ q.addAll([]); // Adding nothing is not a modification.
+ expect(it.moveNext(), true);
+ q.addAll([9]); // Modification during iteration is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+
+ test('removeFirst', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ expect(q.removeFirst(),
+ 2); // Modifiation before creating iterator is not a problem.
+ var it = e.iterator;
+ expect(q.removeFirst(),
+ 3); // Modification after creatig iterator is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+
+ it = e.iterator; // New iterator is not affected.
+ expect(it.moveNext(), true);
+ expect(it.moveNext(), true);
+ expect(q.removeFirst(), 4); // Modification during iteration is a problem.
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+
+ test('remove', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ expect(q.remove(3), true);
+ var it = e.iterator;
+ expect(q.remove(2), true);
+ expect(it.moveNext, throwsConcurrentModificationError);
+ it = e.iterator;
+ expect(q.remove(99), false);
+ expect(it.moveNext(), true);
+ expect(it.moveNext(), true);
+ expect(q.remove(5), true);
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+
+ test('removeAll', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ var it = e.iterator;
+ expect(it.moveNext(), true);
+ expect(it.moveNext(), true);
+ expect(q.removeAll(), hasLength(6));
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+
+ test('clear', () {
+ var q = HeapPriorityQueue<int>((a, b) => a - b)
+ ..addAll([6, 4, 2, 3, 5, 8]);
+ var e = q.unorderedElements;
+ var it = e.iterator;
+ expect(it.moveNext(), true);
+ expect(it.moveNext(), true);
+ q.clear();
+ expect(it.moveNext, throwsConcurrentModificationError);
+ });
+ });
+}
+
// Custom class.
// Class is comparable, comparators match normal and inverse order.
int compare(C c1, C c2) => c1.value - c2.value;
