test/queue_test.dart

// Copyright (c) 2019, 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.

// ignore_for_file: avoid_function_literals_in_foreach_calls

import "package:test/test.dart";

import "package:typed_data/typed_data.dart";

/// The initial capacity of queues if the user doesn't specify one.
const capacity = 16;

void main() {
  group("Uint8Queue()", () {
    test("creates an empty Uint8Queue", () {
      expect(Uint8Queue(), isEmpty);
    });

    test("takes an initial capacity", () {
      expect(Uint8Queue(100), isEmpty);
    });
  });

  group("add() adds an element to the end", () {
    forEachInternalRepresentation((queue) {
      queue.add(16);
      expect(queue, equals(oneThrough(capacity)));
    });
  });

  group("addFirst() adds an element to the beginning", () {
    forEachInternalRepresentation((queue) {
      queue.addFirst(0);
      expect(queue, equals([0, ...oneThrough(capacity - 1)]));
    });
  });

  group("removeFirst() removes an element from the beginning", () {
    forEachInternalRepresentation((queue) {
      expect(queue.removeFirst(), equals(1));
      expect(queue, equals(oneThrough(capacity - 1).skip(1)));
    });

    test("throws a StateError for an empty queue", () {
      expect(Uint8Queue().removeFirst, throwsStateError);
    });
  });

  group("removeLast() removes an element from the end", () {
    forEachInternalRepresentation((queue) {
      expect(queue.removeLast(), equals(15));
      expect(queue, equals(oneThrough(capacity - 2)));
    });

    test("throws a StateError for an empty queue", () {
      expect(Uint8Queue().removeLast, throwsStateError);
    });
  });

  group("removeRange()", () {
    group("removes a prefix", () {
      forEachInternalRepresentation((queue) {
        queue.removeRange(0, 5);
        expect(queue, equals(oneThrough(capacity - 1).skip(5)));
      });
    });

    group("removes a suffix", () {
      forEachInternalRepresentation((queue) {
        queue.removeRange(10, 15);
        expect(queue, equals(oneThrough(capacity - 6)));
      });
    });

    group("removes from the middle", () {
      forEachInternalRepresentation((queue) {
        queue.removeRange(5, 10);
        expect(queue, equals([1, 2, 3, 4, 5, 11, 12, 13, 14, 15]));
      });
    });

    group("removes everything", () {
      forEachInternalRepresentation((queue) {
        queue.removeRange(0, 15);
        expect(queue, isEmpty);
      });
    });

    test("throws a RangeError for an invalid range", () {
      expect(() => Uint8Queue().removeRange(0, 1), throwsRangeError);
    });
  });

  group("setRange()", () {
    group("sets a range to the contents of an iterable", () {
      forEachInternalRepresentation((queue) {
        queue.setRange(5, 10, oneThrough(10).map((n) => 100 + n), 2);
        expect(queue,
            [1, 2, 3, 4, 5, 103, 104, 105, 106, 107, 11, 12, 13, 14, 15]);
      });
    });

    group("sets a range to the contents of a list", () {
      forEachInternalRepresentation((queue) {
        queue.setRange(5, 10, oneThrough(10).map((n) => 100 + n).toList(), 2);
        expect(queue,
            [1, 2, 3, 4, 5, 103, 104, 105, 106, 107, 11, 12, 13, 14, 15]);
      });
    });

    group(
        "sets a range to a section of the same queue overlapping at the beginning",
        () {
      forEachInternalRepresentation((queue) {
        queue.setRange(5, 10, queue, 2);
        expect(queue, [1, 2, 3, 4, 5, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15]);
      });
    });

    group("sets a range to a section of the same queue overlapping at the end",
        () {
      forEachInternalRepresentation((queue) {
        queue.setRange(5, 10, queue, 6);
        expect(queue, [1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 11, 12, 13, 14, 15]);
      });
    });

    test("throws a RangeError for an invalid range", () {
      expect(() => Uint8Queue().setRange(0, 1, [1]), throwsRangeError);
    });
  });

  group("length returns the length", () {
    forEachInternalRepresentation((queue) {
      expect(queue.length, equals(15));
    });
  });

  group("length=", () {
    group("empties", () {
      forEachInternalRepresentation((queue) {
        queue.length = 0;
        expect(queue, isEmpty);
      });
    });

    group("shrinks", () {
      forEachInternalRepresentation((queue) {
        queue.length = 5;
        expect(queue, equals([1, 2, 3, 4, 5]));
      });
    });

    group("grows", () {
      forEachInternalRepresentation((queue) {
        queue.length = 20;
        expect(
            queue,
            equals(oneThrough(capacity - 1) +
                List.filled(20 - (capacity - 1), 0)));
      });
    });

    group("zeroes out existing data", () {
      forEachInternalRepresentation((queue) {
        queue.length = 0;
        queue.length = 15;
        expect(queue, equals([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]));
      });
    });

    test("throws a RangeError if length is less than 0", () {
      expect(() => Uint8Queue().length = -1, throwsRangeError);
    });
  });

  group("[]", () {
    group("returns individual entries", () {
      forEachInternalRepresentation((queue) {
        for (var i = 0; i < capacity - 1; i++) {
          expect(queue[i], equals(i + 1));
        }
      });
    });

    test("throws a RangeError if the index is less than 0", () {
      var queue = Uint8Queue.fromList([1, 2, 3]);
      expect(() => queue[-1], throwsRangeError);
    });

    test(
        "throws a RangeError if the index is greater than or equal to the "
        "length", () {
      var queue = Uint8Queue.fromList([1, 2, 3]);
      expect(() => queue[3], throwsRangeError);
    });
  });

  group("[]=", () {
    group("sets individual entries", () {
      forEachInternalRepresentation((queue) {
        for (var i = 0; i < capacity - 1; i++) {
          queue[i] = 100 + i;
        }
        expect(queue, equals(List.generate(capacity - 1, (i) => 100 + i)));
      });
    });

    test("throws a RangeError if the index is less than 0", () {
      var queue = Uint8Queue.fromList([1, 2, 3]);
      expect(() {
        queue[-1] = 0;
      }, throwsRangeError);
    });

    test(
        "throws a RangeError if the index is greater than or equal to the "
        "length", () {
      var queue = Uint8Queue.fromList([1, 2, 3]);
      expect(() {
        queue[3] = 4;
      }, throwsRangeError);
    });
  });

  group("throws a modification error for", () {
    Uint8Queue queue;
    setUp(() {
      queue = Uint8Queue.fromList([1, 2, 3]);
    });

    test("add", () {
      expect(() => queue.forEach((_) => queue.add(4)),
          throwsConcurrentModificationError);
    });

    test("addAll", () {
      expect(() => queue.forEach((_) => queue.addAll([4, 5, 6])),
          throwsConcurrentModificationError);
    });

    test("addFirst", () {
      expect(() => queue.forEach((_) => queue.addFirst(0)),
          throwsConcurrentModificationError);
    });

    test("removeFirst", () {
      expect(() => queue.forEach((_) => queue.removeFirst()),
          throwsConcurrentModificationError);
    });

    test("removeLast", () {
      expect(() => queue.forEach((_) => queue.removeLast()),
          throwsConcurrentModificationError);
    });

    test("length=", () {
      expect(() => queue.forEach((_) => queue.length = 1),
          throwsConcurrentModificationError);
    });
  });
}

/// Runs [callback] in multiple tests, all with queues containing numbers from
/// one through 15 in various different internal states.
void forEachInternalRepresentation(void Function(Uint8Queue queue) callback) {
  // Test with a queue whose internal table has plenty of room.
  group("for a queue that's below capacity", () {
    // Test with a queue whose elements are in one contiguous block, so `_head <
    // _tail`.
    test("with contiguous elements", () {
      callback(Uint8Queue(capacity * 2)..addAll(oneThrough(capacity - 1)));
    });

    // Test with a queue whose elements are split across the ends of the table,
    // so `_head > _tail`.
    test("with an internal gap", () {
      var queue = Uint8Queue(capacity * 2);
      for (var i = capacity ~/ 2; i < capacity; i++) {
        queue.add(i);
      }
      for (var i = capacity ~/ 2 - 1; i > 0; i--) {
        queue.addFirst(i);
      }
      callback(queue);
    });
  });

  // Test with a queue whose internal table will need to expand if one more
  // element is added.
  group("for a queue that's at capacity", () {
    test("with contiguous elements", () {
      callback(Uint8Queue()..addAll(oneThrough(capacity - 1)));
    });

    test("with an internal gap", () {
      var queue = Uint8Queue();
      for (var i = capacity ~/ 2; i < capacity; i++) {
        queue.add(i);
      }
      for (var i = capacity ~/ 2 - 1; i > 0; i--) {
        queue.addFirst(i);
      }
      callback(queue);
    });
  });
}

/// Returns a list containing the integers from one through [n].
List<int> oneThrough(int n) => List.generate(n, (i) => i + 1);

/// Returns a matcher that expects that a closure throws a
/// [ConcurrentModificationError].
final throwsConcurrentModificationError =
    throwsA(const TypeMatcher<ConcurrentModificationError>());