Alexander Markov
c65ce1f82e
Issue: https://github.com/dart-lang/sdk/issues/61635 Change-Id: If45f0d5e8b10a7927fb4e783efd2c8e90a763af6 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/465361 Commit-Queue: Alexander Markov <alexmarkov@google.com> Reviewed-by: Slava Egorov <vegorov@google.com>
133 lines
3.6 KiB
Dart
133 lines
3.6 KiB
Dart
// Copyright (c) 2025, 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 'package:cfg/utils/bit_vector.dart';
|
|
import 'package:test/test.dart';
|
|
|
|
void main() {
|
|
test('size 0', () {
|
|
final bv1 = BitVector(0);
|
|
final bv2 = BitVector(0);
|
|
final bv3 = BitVector(0);
|
|
expect(bv1.elements, isEmpty);
|
|
|
|
bv1.intersect(bv2);
|
|
expect(bv1.elements, isEmpty);
|
|
|
|
expect(bv1.addAll(bv2), isFalse);
|
|
expect(bv1.elements, isEmpty);
|
|
|
|
expect(bv1.addSubtraction(bv2, bv3), isFalse);
|
|
expect(bv1.elements, isEmpty);
|
|
|
|
expect(bv1.addIntersection(bv2, bv3), isFalse);
|
|
expect(bv1.elements, isEmpty);
|
|
});
|
|
|
|
test('indexing add remove', () {
|
|
for (var n in [20, 63, 64, 65, 200, 2000]) {
|
|
final mid = n ~/ 2;
|
|
final bv = BitVector(n);
|
|
|
|
expect(bv[0], isFalse);
|
|
expect(bv[mid], isFalse);
|
|
expect(bv[n - 1], isFalse);
|
|
|
|
bv.add(0);
|
|
bv.add(mid);
|
|
bv.add(n - 1);
|
|
expect(bv[0], isTrue);
|
|
expect(bv[1], isFalse);
|
|
expect(bv[mid - 1], isFalse);
|
|
expect(bv[mid], isTrue);
|
|
expect(bv[n - 2], isFalse);
|
|
expect(bv[n - 1], isTrue);
|
|
expect(bv.elements.toList(), equals([0, mid, n - 1]));
|
|
|
|
bv.remove(0);
|
|
bv.remove(1);
|
|
bv.remove(n - 1);
|
|
expect(bv[0], isFalse);
|
|
expect(bv[1], isFalse);
|
|
expect(bv[mid - 1], isFalse);
|
|
expect(bv[mid], isTrue);
|
|
expect(bv[n - 2], isFalse);
|
|
expect(bv[n - 1], isFalse);
|
|
expect(bv.elements.toList(), equals([mid]));
|
|
|
|
bv[0] = true;
|
|
bv[1] = false;
|
|
bv[mid - 1] = true;
|
|
bv[n - 2] = true;
|
|
expect(bv[0], isTrue);
|
|
expect(bv[1], isFalse);
|
|
expect(bv[mid - 1], isTrue);
|
|
expect(bv[mid], isTrue);
|
|
expect(bv[n - 2], isTrue);
|
|
expect(bv[n - 1], isFalse);
|
|
expect(bv.elements.toList(), equals([0, mid - 1, mid, n - 2]));
|
|
}
|
|
});
|
|
|
|
test('bulk operations', () {
|
|
for (var n in [20, 63, 64, 65, 200, 2000]) {
|
|
final bv1 = BitVector(n);
|
|
final bv2 = BitVector(n);
|
|
final bv3 = BitVector(n);
|
|
|
|
for (var i = 0; i < n; i += 3) {
|
|
bv2[i] = true;
|
|
}
|
|
for (var i = 0; i < n; i += 5) {
|
|
bv3[i] = true;
|
|
}
|
|
|
|
expect(bv1.addAll(bv2), isTrue);
|
|
expect(bv1.addAll(bv2), isFalse);
|
|
bv1.intersect(bv3);
|
|
for (var i = 0; i < n; ++i) {
|
|
expect(bv1[i], equals(i % 15 == 0));
|
|
expect(bv2[i], equals(i % 3 == 0));
|
|
expect(bv3[i], equals(i % 5 == 0));
|
|
}
|
|
|
|
expect(bv2.addAll(bv1), isFalse);
|
|
expect(bv3.addAll(bv1), isFalse);
|
|
for (var i = 0; i < n; ++i) {
|
|
expect(bv1[i], equals(i % 15 == 0));
|
|
expect(bv2[i], equals(i % 3 == 0));
|
|
expect(bv3[i], equals(i % 5 == 0));
|
|
}
|
|
|
|
expect(bv2.addSubtraction(bv3, bv1), isTrue);
|
|
for (var i = 0; i < n; ++i) {
|
|
expect(bv1[i], equals(i % 15 == 0));
|
|
expect(bv2[i], equals(i % 3 == 0 || i % 5 == 0));
|
|
expect(bv3[i], equals(i % 5 == 0));
|
|
}
|
|
expect(bv3.addSubtraction(bv1, bv2), isFalse);
|
|
|
|
expect(bv3.addIntersection(bv1, bv2), isFalse);
|
|
expect(bv1.addIntersection(bv2, bv3), isTrue);
|
|
for (var i = 0; i < n; ++i) {
|
|
expect(bv1[i], equals(i % 5 == 0));
|
|
expect(bv2[i], equals(i % 3 == 0 || i % 5 == 0));
|
|
expect(bv3[i], equals(i % 5 == 0));
|
|
}
|
|
|
|
bv3.clear();
|
|
for (var i = 0; i < n; ++i) {
|
|
expect(bv3[i], isFalse);
|
|
}
|
|
|
|
var k = 0;
|
|
for (int bit in bv1.elements) {
|
|
expect(bit, equals(k * 5));
|
|
++k;
|
|
}
|
|
expect(k, equals(1 + (n - 1) ~/ 5));
|
|
}
|
|
});
|
|
}
|