Add BoolList class. (#120)
Adds `BoolList` class which implements a list of booleans with one bit of storage per value.
diff --git a/lib/collection.dart b/lib/collection.dart
index 27a75c8..f6f4ae3 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -4,6 +4,7 @@
export 'src/algorithms.dart'
show binarySearch, insertionSort, lowerBound, mergeSort, shuffle, reverse;
+export 'src/boollist.dart';
export 'src/canonicalized_map.dart';
export 'src/combined_wrappers/combined_iterable.dart';
export 'src/combined_wrappers/combined_list.dart';
diff --git a/lib/src/boollist.dart b/lib/src/boollist.dart
new file mode 100644
index 0000000..cf23b57
--- /dev/null
+++ b/lib/src/boollist.dart
@@ -0,0 +1,258 @@
+// Copyright (c) 2020, 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.
+
+import 'dart:collection' show ListMixin;
+import 'dart:typed_data' show Uint32List;
+
+import 'unmodifiable_wrappers.dart' show NonGrowableListMixin;
+
+/// A space-efficient list of boolean values.
+///
+/// Uses list of integers as internal storage to reduce memory usage.
+abstract class BoolList with ListMixin<bool> {
+ static const int _entryShift = 5;
+
+ static const int _bitsPerEntry = 32;
+
+ static const int _entrySignBitIndex = 31;
+
+ int _length;
+
+ Uint32List _data;
+
+ BoolList._(this._data, this._length);
+
+ factory BoolList._selectType(int length, bool growable) {
+ if (growable) {
+ return _GrowableBoolList(length);
+ } else {
+ return _NonGrowableBoolList(length);
+ }
+ }
+
+ /// Creates a list of booleans with the provided length.
+ ///
+ /// The list is initially filled with the [fill] value, and
+ /// the list is growable if [growable] is true.
+ factory BoolList(int length, {bool fill = false, bool growable = false}) {
+ RangeError.checkNotNegative(length, 'length');
+
+ BoolList boolist;
+ if (growable) {
+ boolist = _GrowableBoolList(length);
+ } else {
+ boolist = _NonGrowableBoolList(length);
+ }
+
+ if (fill) {
+ boolist.fillRange(0, length, true);
+ }
+
+ return boolist;
+ }
+
+ /// Creates an empty list of booleans.
+ ///
+ /// The list defaults to being growable unless [growable] is `false`.
+ /// If [capacity] is provided, and [growable] is not `false`,
+ /// the implementation will attempt to make space for that
+ /// many elements before needing to grow its internal storage.
+ factory BoolList.empty({bool growable = true, int capacity = 0}) {
+ RangeError.checkNotNegative(capacity, 'length');
+
+ if (growable) {
+ return _GrowableBoolList._withCapacity(0, capacity);
+ } else {
+ return _NonGrowableBoolList._withCapacity(0, capacity);
+ }
+ }
+
+ /// Generates a [BoolList] of values.
+ ///
+ /// Creates a [BoolList] with [length] positions and fills it with values created by
+ /// calling [generator] for each index in the range `0` .. `length - 1` in increasing order.
+ ///
+ /// The created list is fixed-length unless [growable] is true.
+ factory BoolList.generate(
+ int length,
+ bool Function(int) generator, {
+ bool growable = true,
+ }) {
+ RangeError.checkNotNegative(length, 'length');
+
+ var instance = BoolList._selectType(length, growable);
+ for (var i = 0; i < length; i++) {
+ instance._setBit(i, generator(i));
+ }
+ return instance;
+ }
+
+ /// Creates a list containing all [elements].
+ ///
+ /// The [Iterator] of [elements] provides the order of the elements.
+ ///
+ /// This constructor creates a growable [BoolList] when [growable] is true;
+ /// otherwise, it returns a fixed-length list.
+ factory BoolList.from(Iterable<bool> elements, {bool growable = false}) {
+ return BoolList._selectType(elements.length, growable)..setAll(0, elements);
+ }
+
+ @override
+ int get length => _length;
+
+ @override
+ bool operator [](int index) {
+ RangeError.checkValidIndex(index, this, 'index', _length);
+ return (_data[index >> _entryShift] &
+ (1 << (index & _entrySignBitIndex))) !=
+ 0;
+ }
+
+ @override
+ void operator []=(int index, bool val) {
+ RangeError.checkValidIndex(index, this, 'index', _length);
+ _setBit(index, val);
+ }
+
+ @override
+ void fillRange(int start, int end, [bool? fill]) {
+ RangeError.checkValidRange(start, end, _length);
+ fill ??= false;
+
+ var startWord = start >> _entryShift;
+ var endWord = (end - 1) >> _entryShift;
+
+ var startBit = start & _entrySignBitIndex;
+ var endBit = (end - 1) & _entrySignBitIndex;
+
+ if (startWord < endWord) {
+ if (fill) {
+ _data[startWord] |= -1 << startBit;
+ _data.fillRange(startWord + 1, endWord, -1);
+ _data[endWord] |= (1 << (endBit + 1)) - 1;
+ } else {
+ _data[startWord] &= (1 << startBit) - 1;
+ _data.fillRange(startWord + 1, endWord, 0);
+ _data[endWord] &= -1 << (endBit + 1);
+ }
+ } else {
+ if (fill) {
+ _data[startWord] |= ((1 << (endBit - startBit + 1)) - 1) << startBit;
+ } else {
+ _data[startWord] &= ((1 << startBit) - 1) | (-1 << (endBit + 1));
+ }
+ }
+ }
+
+ /// Returns custom iterator for [BoolList].
+ ///
+ /// To provide null safety [Iterator.current] getter of returned iterator
+ /// returns `false` before and after iteration process.
+ @override
+ Iterator<bool> get iterator => _BoolListIterator(this);
+
+ void _setBit(int index, bool val) {
+ if (val) {
+ _data[index >> _entryShift] |= 1 << (index & _entrySignBitIndex);
+ } else {
+ _data[index >> _entryShift] &= ~(1 << (index & _entrySignBitIndex));
+ }
+ }
+
+ static int _lengthInWords(int bitsLength) {
+ return (bitsLength + (_bitsPerEntry - 1)) >> _entryShift;
+ }
+}
+
+class _GrowableBoolList extends BoolList {
+ static const int _growthFactor = 2;
+
+ _GrowableBoolList._withCapacity(int length, int capacity)
+ : super._(
+ Uint32List(BoolList._lengthInWords(capacity)),
+ length,
+ );
+
+ _GrowableBoolList(int length)
+ : super._(
+ Uint32List(BoolList._lengthInWords(length * _growthFactor)),
+ length,
+ );
+
+ @override
+ set length(int length) {
+ RangeError.checkNotNegative(length, 'length');
+ if (length > _length) {
+ _expand(length);
+ } else if (length < _length) {
+ _shrink(length);
+ }
+ }
+
+ void _expand(int length) {
+ if (length > _data.length * BoolList._bitsPerEntry) {
+ _data = Uint32List(
+ BoolList._lengthInWords(length * _growthFactor),
+ )..setAll(0, _data);
+ }
+ _length = length;
+ }
+
+ void _shrink(int length) {
+ if (length < _length ~/ _growthFactor) {
+ var newDataLength = BoolList._lengthInWords(length);
+ _data = Uint32List(newDataLength)..setRange(0, newDataLength, _data);
+ }
+
+ for (var i = length; i < _data.length * BoolList._bitsPerEntry; i++) {
+ _setBit(i, false);
+ }
+
+ _length = length;
+ }
+}
+
+class _NonGrowableBoolList extends BoolList with NonGrowableListMixin<bool> {
+ _NonGrowableBoolList._withCapacity(int length, int capacity)
+ : super._(
+ Uint32List(BoolList._lengthInWords(capacity)),
+ length,
+ );
+
+ _NonGrowableBoolList(int length)
+ : super._(
+ Uint32List(BoolList._lengthInWords(length)),
+ length,
+ );
+}
+
+class _BoolListIterator implements Iterator<bool> {
+ bool _current = false;
+ int _pos = 0;
+ final int _length;
+
+ final BoolList _boolList;
+
+ _BoolListIterator(this._boolList) : _length = _boolList._length;
+
+ @override
+ bool get current => _current;
+
+ @override
+ bool moveNext() {
+ if (_boolList._length != _length) {
+ throw ConcurrentModificationError(_boolList);
+ }
+
+ if (_pos < _boolList.length) {
+ var pos = _pos++;
+ _current = _boolList._data[pos >> BoolList._entryShift] &
+ (1 << (pos & BoolList._entrySignBitIndex)) !=
+ 0;
+ return true;
+ }
+ _current = false;
+ return false;
+ }
+}
diff --git a/test/boollist_test.dart b/test/boollist_test.dart
new file mode 100644
index 0000000..263186c
--- /dev/null
+++ b/test/boollist_test.dart
@@ -0,0 +1,162 @@
+// Copyright (c) 2020, 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 for BoolList.
+
+import 'package:collection/collection.dart';
+import 'package:test/test.dart';
+
+void main() {
+ bool generator(int index) {
+ if (index < 512) {
+ return index.isEven;
+ }
+ return false;
+ }
+
+ test('BoolList()', () {
+ expect(BoolList(1024, fill: false), List.filled(1024, false));
+
+ expect(BoolList(1024, fill: true), List.filled(1024, true));
+ });
+
+ test('BoolList.empty()', () {
+ expect(BoolList.empty(growable: true, capacity: 1024), []);
+
+ expect(BoolList.empty(growable: false, capacity: 1024), []);
+ });
+
+ test('BoolList.generate()', () {
+ expect(
+ BoolList.generate(1024, generator),
+ List.generate(1024, generator),
+ );
+ });
+
+ test('BoolList.from()', () {
+ var src = List.generate(1024, generator);
+ expect(BoolList.from(src), src);
+ });
+
+ group('[], []=', () {
+ test('RangeError', () {
+ var b = BoolList(1024, fill: false);
+
+ expect(() {
+ b[-1];
+ }, throwsRangeError);
+
+ expect(() {
+ b[1024];
+ }, throwsRangeError);
+ });
+
+ test('[], []=', () {
+ var b = BoolList(1024, fill: false);
+
+ bool posVal;
+ for (var pos = 0; pos < 1024; ++pos) {
+ posVal = generator(pos);
+ b[pos] = posVal;
+ expect(b[pos], posVal, reason: 'at pos $pos');
+ }
+ });
+ });
+
+ group('length', () {
+ test('shrink length', () {
+ var b = BoolList(1024, fill: true, growable: true);
+
+ b.length = 768;
+ expect(b, List.filled(768, true));
+
+ b.length = 128;
+ expect(b, List.filled(128, true));
+
+ b.length = 0;
+ expect(b, []);
+ });
+
+ test('expand from != 0', () {
+ var b = BoolList(256, fill: true, growable: true);
+
+ b.length = 384;
+ expect(b, List.filled(384, false)..fillRange(0, 256, true));
+
+ b.length = 2048;
+ expect(b, List.filled(2048, false)..fillRange(0, 256, true));
+ });
+
+ test('expand from = 0', () {
+ var b = BoolList(0, growable: true);
+ expect(b.length, 0);
+
+ b.length = 256;
+ expect(b, List.filled(256, false));
+ });
+
+ test('throw UnsupportedError', () {
+ expect(() {
+ BoolList(1024).length = 512;
+ }, throwsUnsupportedError);
+ });
+ });
+
+ group('fillRange', () {
+ test('In one word', () {
+ expect(
+ BoolList(1024)..fillRange(32, 64, true),
+ List.filled(1024, false)..fillRange(32, 64, true),
+ );
+
+ expect(
+ // BoolList.filled constructor isn't used due internal usage of fillRange
+ BoolList.generate(1024, (i) => true)..fillRange(32, 64, false),
+ List.filled(1024, true)..fillRange(32, 64, false),
+ );
+ });
+
+ test('In several words', () {
+ expect(
+ BoolList(1024)..fillRange(32, 128, true),
+ List.filled(1024, false)..fillRange(32, 128, true),
+ );
+
+ expect(
+ // BoolList.filled constructor isn't used due internal usage of fillRange
+ BoolList.generate(1024, (i) => true)..fillRange(32, 128, false),
+ List.filled(1024, true)..fillRange(32, 128, false),
+ );
+ });
+ });
+
+ group('Iterator', () {
+ test('Iterator', () {
+ var b = BoolList.generate(1024, generator);
+ var iter = b.iterator;
+
+ expect(iter.current, false);
+ for (var i = 0; i < 1024; i++) {
+ expect(iter.moveNext(), true);
+
+ expect(iter.current, generator(i), reason: 'at pos $i');
+ }
+
+ expect(iter.moveNext(), false);
+ expect(iter.current, false);
+ });
+
+ test('throw ConcurrentModificationError', () {
+ var b = BoolList(1024, fill: true, growable: true);
+
+ var iter = b.iterator;
+
+ iter.moveNext();
+ b.length = 512;
+ expect(() {
+ iter.moveNext();
+ }, throwsConcurrentModificationError);
+ });
+ });
+}
