Add `toUnorderedList` to `PriorityQueue`. (#152)
Add `toUnorderedList` to `PriorityQueue`.
Also change `HeapPriorityQueue` to use `==` for
`contains` and `remove` checks.
Fix a bad null-safety migration for HeapPriorityQueue,
and add tests to ensure it works with `null` values.
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 6e3a846..0c76f58 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,12 @@
+## 1.15.0-nullsafety.3
+
+* Make `HeapPriorityQueue`'s `remove` and `contains` methods
+ use `==` for equality checks.
+ Previously used `comparison(a, b) == 0` as criteria, but it's possible
+ to have multiple elements with the same priority in a queue, so that
+ could remove the wrong element.
+ Still requires that objects that are `==` also have the same priority.
+
## 1.15.0-nullsafety.2
Update for the 2.10 dev sdk.
diff --git a/lib/src/priority_queue.dart b/lib/src/priority_queue.dart
index d4355b0..6abce79 100644
--- a/lib/src/priority_queue.dart
+++ b/lib/src/priority_queue.dart
@@ -9,6 +9,18 @@
/// A priority queue is a priority based work-list of elements.
///
/// The queue allows adding elements, and removing them again in priority order.
+/// The same object can be added to the queue more than once.
+/// There is no specified ordering for objects with the same priority
+/// (where the `comparison` function returns zero).
+///
+/// Operations which care about object equality, [contains] and [remove],
+/// use [Object.==] for testing equality.
+/// In most situations this will be the same as identity ([identical]),
+/// but there are types, like [String], where users can reasonably expect
+/// distinct objects to represent the same value.
+/// If elements override [Object.==], the `comparison` function must
+/// always give equal objects the same priority,
+/// otherwise [contains] or [remove] might not work correctly.
abstract class PriorityQueue<E> {
/// Creates an empty [PriorityQueue].
///
@@ -36,6 +48,14 @@
/// Checks if [object] is in the queue.
///
/// Returns true if the element is found.
+ ///
+ /// Uses the [Object.==] of elements in the queue to check
+ /// for whether they are equal to [object].
+ /// Equal objects objects must have the same priority
+ /// according to the [comparison] function.
+ /// That is, if `a == b` then `comparison(a, b) == 0`.
+ /// If that is not the case, this check might fail to find
+ /// an object.
bool contains(E object);
/// Adds element to the queue.
@@ -63,10 +83,21 @@
/// The queue must not be empty when this method is called.
E removeFirst();
- /// Removes an element that compares equal to [element] in the queue.
+ /// Removes an element of the queue that compares equal to [element].
///
/// Returns true if an element is found and removed,
/// and false if no equal element is found.
+ ///
+ /// If the queue contains more than one object equal to [element],
+ /// only one of them is removed.
+ ///
+ /// Uses the [Object.==] of elements in the queue to check
+ /// for whether they are equal to [element].
+ /// Equal objects objects must have the same priority
+ /// according to the [comparison] function.
+ /// That is, if `a == b` then `comparison(a, b) == 0`.
+ /// If that is not the case, this check might fail to find
+ /// an object.
bool remove(E element);
/// Removes all the elements from this queue and returns them.
@@ -85,6 +116,14 @@
/// removed from this queue using [removeFirst].
List<E> toList();
+ /// Returns a list of the elements of this queue in no specific order.
+ ///
+ /// The queue is not modified.
+ ///
+ /// The order of the elements is implementation specific.
+ /// The order may differ between different calls on the same queue.
+ List<E> toUnorderedList();
+
/// Return a comparator based set using the comparator of this queue.
///
/// The queue is not modified.
@@ -115,6 +154,8 @@
/// queue for the elements, taking O(n) time.
/// * The [toList] operation effectively sorts the elements, taking O(n*log(n))
/// time.
+/// * The [toUnorderedList] operation copies, but does not sort, the elements,
+/// and is linear, O(n).
/// * The [toSet] operation effectively adds each element to the new set, taking
/// an expected O(n*log(n)) time.
class HeapPriorityQueue<E> implements PriorityQueue<E> {
@@ -148,6 +189,8 @@
HeapPriorityQueue([int Function(E, E)? comparison])
: comparison = comparison ?? defaultCompare<E>();
+ E _elementAt(int index) => _queue[index] ?? (null as E);
+
@override
void add(E element) {
_add(element);
@@ -167,14 +210,12 @@
}
@override
- bool contains(E object) {
- return _locate(object) >= 0;
- }
+ bool contains(E object) => _locate(object) >= 0;
@override
E get first {
- if (_length == 0) throw StateError('No such element');
- return _queue[0]!;
+ if (_length == 0) throw StateError('No element');
+ return _elementAt(0);
}
@override
@@ -213,8 +254,8 @@
@override
E removeFirst() {
- if (_length == 0) throw StateError('No such element');
- var result = _queue[0]!;
+ if (_length == 0) throw StateError('No element');
+ var result = _elementAt(0);
var last = _removeLast();
if (_length > 0) {
_bubbleDown(last, 0);
@@ -223,18 +264,23 @@
}
@override
- List<E> toList() =>
- List<E>.generate(_length, (i) => _queue[i]!)..sort(comparison);
+ List<E> toList() => _toUnorderedList()..sort(comparison);
@override
Set<E> toSet() {
var set = SplayTreeSet<E>(comparison);
for (var i = 0; i < _length; i++) {
- set.add(_queue[i]!);
+ set.add(_elementAt(i));
}
return set;
}
+ @override
+ List<E> toUnorderedList() => _toUnorderedList();
+
+ List<E> _toUnorderedList() =>
+ [for (var i = 0; i < _length; i++) _elementAt(i)];
+
/// Returns some representation of the queue.
///
/// The format isn't significant, and may change in the future.
@@ -254,6 +300,9 @@
/// Find the index of an object in the heap.
///
/// Returns -1 if the object is not found.
+ ///
+ /// A matching object, `o`, must satisfy that
+ /// `comparison(o, object) == 0 && o == object`.
int _locate(E object) {
if (_length == 0) return -1;
// Count positions from one instead of zero. This gives the numbers
@@ -267,10 +316,10 @@
// in the heap will also have lower priority.
do {
var index = position - 1;
- var element = _queue[index]!;
+ var element = _elementAt(index);
var comp = comparison(element, object);
- if (comp == 0) return index;
- if (comp < 0) {
+ if (comp <= 0) {
+ if (comp == 0 && element == object) return index;
// Element may be in subtree.
// Continue with the left child, if it is there.
var leftChildPosition = position * 2;
@@ -294,7 +343,7 @@
E _removeLast() {
var newLength = _length - 1;
- var last = _queue[newLength]!;
+ var last = _elementAt(newLength);
_queue[newLength] = null;
_length = newLength;
return last;
@@ -308,7 +357,7 @@
void _bubbleUp(E element, int index) {
while (index > 0) {
var parentIndex = (index - 1) ~/ 2;
- var parent = _queue[parentIndex]!;
+ var parent = _elementAt(parentIndex);
if (comparison(element, parent) > 0) break;
_queue[index] = parent;
index = parentIndex;
@@ -325,8 +374,8 @@
var rightChildIndex = index * 2 + 2;
while (rightChildIndex < _length) {
var leftChildIndex = rightChildIndex - 1;
- var leftChild = _queue[leftChildIndex]!;
- var rightChild = _queue[rightChildIndex]!;
+ var leftChild = _elementAt(leftChildIndex);
+ var rightChild = _elementAt(rightChildIndex);
var comp = comparison(leftChild, rightChild);
int minChildIndex;
E minChild;
@@ -348,7 +397,7 @@
}
var leftChildIndex = rightChildIndex - 1;
if (leftChildIndex < _length) {
- var child = _queue[leftChildIndex]!;
+ var child = _elementAt(leftChildIndex);
var comp = comparison(element, child);
if (comp > 0) {
_queue[index] = child;
diff --git a/lib/src/union_set.dart b/lib/src/union_set.dart
index 208a2a5..2fe6e3e 100644
--- a/lib/src/union_set.dart
+++ b/lib/src/union_set.dart
@@ -71,6 +71,7 @@
var result = set.lookup(element);
if (result != null) return result;
}
+ return null;
}
@override
diff --git a/pubspec.yaml b/pubspec.yaml
index e45737f..cd57aca 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,11 +1,11 @@
name: collection
-version: 1.15.0-nullsafety.2
+version: 1.15.0-nullsafety.3
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
environment:
- sdk: '>=2.10.0-0 <2.10.0'
+ sdk: '>=2.10.0-78 <2.10.0'
dev_dependencies:
pedantic: ^1.0.0
diff --git a/test/priority_queue_test.dart b/test/priority_queue_test.dart
index b38b3aa..191857d 100644
--- a/test/priority_queue_test.dart
+++ b/test/priority_queue_test.dart
@@ -12,6 +12,8 @@
testDefault();
testInt(() => HeapPriorityQueue<int>());
testCustom((comparator) => HeapPriorityQueue<C>(comparator));
+ testDuplicates();
+ testNullable();
}
void testDefault() {
@@ -157,6 +159,108 @@
expect(q.isEmpty, isTrue);
}
+void testDuplicates() {
+ // Check how the heap handles duplicate, or equal-but-not-identical, values.
+ test('duplicates', () {
+ var q = HeapPriorityQueue<C>(compare);
+ var c1 = C(0);
+ var c2 = C(0);
+
+ // Can contain the same element more than once.
+ expect(c1, equals(c2));
+ expect(c1, isNot(same(c2)));
+ q.add(c1);
+ q.add(c1);
+ expect(q.length, 2);
+ expect(q.contains(c1), true);
+ expect(q.contains(c2), true);
+ expect(q.remove(c2), true);
+ expect(q.length, 1);
+ expect(q.removeFirst(), same(c1));
+
+ // Can contain equal elements.
+ q.add(c1);
+ q.add(c2);
+ expect(q.length, 2);
+ expect(q.contains(c1), true);
+ expect(q.contains(c2), true);
+ expect(q.remove(c1), true);
+ expect(q.length, 1);
+ expect(q.first, anyOf(same(c1), same(c2)));
+ });
+}
+
+void testNullable() {
+ // Check that the queue works with a nullable type, and a comparator
+ // which accepts `null`.
+ // Compares `null` before instances of `C`.
+ int nullCompareFirst(C? a, C? b) => a == null
+ ? b == null
+ ? 0
+ : -1
+ : b == null
+ ? 1
+ : compare(a, b);
+
+ int nullCompareLast(C? a, C? b) => a == null
+ ? b == null
+ ? 0
+ : 1
+ : b == null
+ ? -1
+ : compare(a, b);
+
+ var c1 = C(1);
+ var c2 = C(2);
+ var c3 = C(3);
+
+ test('nulls first', () {
+ var q = HeapPriorityQueue<C?>(nullCompareFirst);
+ q.add(c2);
+ q.add(c1);
+ q.add(null);
+ expect(q.length, 3);
+ expect(q.contains(null), true);
+ expect(q.contains(c1), true);
+ expect(q.contains(c3), false);
+
+ expect(q.removeFirst(), null);
+ expect(q.length, 2);
+ expect(q.contains(null), false);
+ q.add(null);
+ expect(q.length, 3);
+ expect(q.contains(null), true);
+ q.add(null);
+ expect(q.length, 4);
+ expect(q.contains(null), true);
+ expect(q.remove(null), true);
+ expect(q.length, 3);
+ expect(q.toList(), [null, c1, c2]);
+ });
+
+ test('nulls last', () {
+ var q = HeapPriorityQueue<C?>(nullCompareLast);
+ q.add(c2);
+ q.add(c1);
+ q.add(null);
+ expect(q.length, 3);
+ expect(q.contains(null), true);
+ expect(q.contains(c1), true);
+ expect(q.contains(c3), false);
+ expect(q.first, c1);
+
+ q.add(null);
+ expect(q.length, 4);
+ expect(q.contains(null), true);
+ q.add(null);
+ expect(q.length, 5);
+ expect(q.contains(null), true);
+ expect(q.remove(null), true);
+ expect(q.length, 4);
+ expect(q.toList(), [c1, c2, null, null]);
+ });
+}
+
// Custom class.
// Class is comparable, comparators match normal and inverse order.
int compare(C c1, C c2) => c1.value - c2.value;
