priority_queue_test.dart

// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

/// Tests priority queue implementations utilities.
library;

import 'package:collection/src/priority_queue.dart';
import 'package:test/test.dart';

void main() {
  testDefault();
  testInt(HeapPriorityQueue<int>.new);
  testCustom(HeapPriorityQueue<C>.new);
  testDuplicates();
  testNullable();
  testConcurrentModification();
}

void testDefault() {
  test('PriorityQueue() returns a HeapPriorityQueue', () {
    expect(PriorityQueue<int>(), const TypeMatcher<HeapPriorityQueue<int>>());
  });
  testInt(PriorityQueue<int>.new);
  testCustom(PriorityQueue<C>.new);
}

void testInt(PriorityQueue<int> Function() create) {
  for (var count in [1, 5, 127, 128]) {
    testQueue('int:$count', create, List<int>.generate(count, (x) => x), count);
  }
}

void testCustom(
    PriorityQueue<C> Function(int Function(C, C)? comparator) create) {
  for (var count in [1, 5, 127, 128]) {
    testQueue('Custom:$count/null', () => create(null),
        List<C>.generate(count, C.new), C(count));
    testQueue('Custom:$count/compare', () => create(compare),
        List<C>.generate(count, C.new), C(count));
    testQueue('Custom:$count/compareNeg', () => create(compareNeg),
        List<C>.generate(count, (x) => C(count - x)), const C(0));
  }
}

/// Test that a queue behaves correctly.
///
/// The elements must be in priority order, from highest to lowest.
void testQueue<T>(
  String name,
  PriorityQueue<T> Function() create,
  List<T> elements,
  T notElement,
) {
  test(name, () => testQueueBody(create, elements, notElement));
}

void testQueueBody<T>(
    PriorityQueue<T> Function() create, List<T> elements, T notElement) {
  var q = create();
  expect(q.isEmpty, isTrue);
  expect(q, hasLength(0));
  expect(() {
    q.first;
  }, throwsStateError);
  expect(() {
    q.removeFirst();
  }, throwsStateError);

  // Tests removeFirst, first, contains, toList and toSet.
  void testElements() {
    expect(q.isNotEmpty, isTrue);
    expect(q, hasLength(elements.length));

    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);
    }
    expect(q.contains(notElement), isFalse);

    var all = [];
    while (q.isNotEmpty) {
      var expected = q.first;
      var actual = q.removeFirst();
      expect(actual, same(expected));
      all.add(actual);
    }

    expect(all.length, elements.length);
    for (var i = 0; i < all.length; i++) {
      expect(all[i], same(elements[i]));
    }

    expect(q.isEmpty, isTrue);
  }

  q.addAll(elements);
  testElements();

  q.addAll(elements.reversed);
  testElements();

  // Add elements in a non-linear order (gray order).
  for (var i = 0, j = 0; i < elements.length; i++) {
    int gray;
    do {
      gray = j ^ (j >> 1);
      j++;
    } while (gray >= elements.length);
    q.add(elements[gray]);
  }
  testElements();

  // Add elements by picking the middle element first, and then recursing
  // on each side.
  void addRec(int min, int max) {
    var mid = min + ((max - min) >> 1);
    q.add(elements[mid]);
    if (mid + 1 < max) addRec(mid + 1, max);
    if (mid > min) addRec(min, mid);
  }

  addRec(0, elements.length);
  testElements();

  // Test removeAll.
  q.addAll(elements);
  expect(q, hasLength(elements.length));
  var all = q.removeAll();
  expect(q.isEmpty, isTrue);
  expect(all, hasLength(elements.length));
  for (var i = 0; i < elements.length; i++) {
    expect(all, contains(elements[i]));
  }

  // Test the same element more than once in queue.
  q.addAll(elements);
  q.addAll(elements.reversed);
  expect(q, hasLength(elements.length * 2));
  for (var i = 0; i < elements.length; i++) {
    var element = elements[i];
    expect(q.contains(element), isTrue);
    expect(q.removeFirst(), element);
    expect(q.removeFirst(), element);
  }

  // Test queue with all same element.
  var a = elements[0];
  for (var i = 0; i < elements.length; i++) {
    q.add(a);
  }
  expect(q, hasLength(elements.length));
  expect(q.contains(a), isTrue);
  expect(q.contains(notElement), isFalse);
  q.removeAll().forEach((x) => expect(x, same(a)));

  // Test remove.
  q.addAll(elements);
  for (var element in elements.reversed) {
    expect(q.remove(element), isTrue);
  }
  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 = const C(0);
    // ignore: prefer_const_constructors
    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 = const C(1);
  var c2 = const C(2);
  var c3 = const 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]);
  });
}

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;
int compareNeg(C c1, C c2) => c2.value - c1.value;

class C implements Comparable<C> {
  final int value;
  const C(this.value);
  @override
  int get hashCode => value;
  @override
  bool operator ==(Object other) => other is C && value == other.value;
  @override
  int compareTo(C other) => value - other.value;
  @override
  String toString() => 'C($value)';
}