Jens Johansen
4d3d70af23
Kernel sdk version was bumped from 3.6 to 3.12 in https://dart-review.googlesource.com/c/sdk/+/487542 (and to `^3.12.0-0` in https://dart-review.googlesource.com/c/sdk/+/487880) but the source was never formatted. This is, if nothing else, bad for reviews, where editing a file changes the file in lots of places because of new formatting. This CL is the result of running ``` out/ReleaseX64/dart-sdk/bin/dart format pkg/kernel/ ``` but also updates the formatter version used by a source generator (`pkg/front_end/tool/visitor_generator.dart`) so things agree. Change-Id: I66e35d4f1e2d08cecc30fb314546cae78b49e99b Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/490082 Reviewed-by: Chloe Stefantsova <cstefantsova@google.com> Reviewed-by: Johnni Winther <johnniwinther@google.com> Commit-Queue: Jens Johansen <jensj@google.com>
109 lines
2.7 KiB
Dart
109 lines
2.7 KiB
Dart
// Copyright (c) 2021, 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:kernel/src/union_find.dart';
|
|
|
|
void testSame<T>(UnionFind<T> unionFind, T a, T b, bool expected) {
|
|
expect(expected, unionFind.nodesInSameSet(unionFind[a], unionFind[b]));
|
|
}
|
|
|
|
void testSets<T>(UnionFind<T> unionFind, Set<Set<T>> sets) {
|
|
for (Set<T> set in sets) {
|
|
UnionFindNode<T> root = unionFind.findNode(unionFind[set.first]);
|
|
for (T value in unionFind.values) {
|
|
testSame(unionFind, value, root.value, set.contains(value));
|
|
}
|
|
}
|
|
}
|
|
|
|
void testFind<T>(UnionFind<T> unionFind, T value, T expected) {
|
|
expect(expected, unionFind.findNode(unionFind[value]).value);
|
|
}
|
|
|
|
void testUnion<T>(UnionFind<T> unionFind, T a, T b, T expected) {
|
|
expect(expected, unionFind.unionOfNodes(unionFind[a], unionFind[b]).value);
|
|
}
|
|
|
|
void main() {
|
|
UnionFind<int> unionFind = new UnionFind();
|
|
// {0}
|
|
testFind(unionFind, 0, 0);
|
|
testSame(unionFind, 0, 0, true);
|
|
testSets(unionFind, {
|
|
{0},
|
|
});
|
|
|
|
// {0}, {1}
|
|
testFind(unionFind, 1, 1);
|
|
testSame(unionFind, 0, 1, false);
|
|
testSame(unionFind, 1, 0, false);
|
|
testSame(unionFind, 1, 1, true);
|
|
testSets(unionFind, {
|
|
{0},
|
|
{1},
|
|
});
|
|
|
|
// {0}, {1}, {2}
|
|
testFind(unionFind, 2, 2);
|
|
testSame(unionFind, 0, 2, false);
|
|
testSame(unionFind, 1, 2, false);
|
|
testSame(unionFind, 2, 2, true);
|
|
testSets(unionFind, {
|
|
{0},
|
|
{1},
|
|
{2},
|
|
});
|
|
|
|
// {0}, {1}, {2}
|
|
testUnion(unionFind, 0, 0, 0);
|
|
testSame(unionFind, 0, 0, true);
|
|
testSame(unionFind, 0, 1, false);
|
|
testSame(unionFind, 0, 2, false);
|
|
testSets(unionFind, {
|
|
{0},
|
|
{1},
|
|
{2},
|
|
});
|
|
|
|
// {0, 1}, {2}
|
|
testUnion(unionFind, 0, 1, 0);
|
|
testSame(unionFind, 0, 0, true);
|
|
testSame(unionFind, 0, 1, true);
|
|
testSame(unionFind, 1, 0, true);
|
|
testSame(unionFind, 0, 2, false);
|
|
testFind(unionFind, 0, 0);
|
|
testFind(unionFind, 1, 0);
|
|
testSets(unionFind, {
|
|
{0, 1},
|
|
{2},
|
|
});
|
|
|
|
// {0, 1}, {2, 3}
|
|
testUnion(unionFind, 2, 3, 2);
|
|
testSame(unionFind, 0, 0, true);
|
|
testSame(unionFind, 0, 1, true);
|
|
testSame(unionFind, 0, 2, false);
|
|
testSame(unionFind, 0, 3, false);
|
|
testSame(unionFind, 0, 0, true);
|
|
testSame(unionFind, 0, 1, true);
|
|
testSame(unionFind, 0, 2, false);
|
|
testSame(unionFind, 0, 3, false);
|
|
testFind(unionFind, 2, 2);
|
|
testFind(unionFind, 3, 2);
|
|
testSets(unionFind, {
|
|
{0, 1},
|
|
{2, 3},
|
|
});
|
|
|
|
// {0, 1, 2, 3}
|
|
testUnion(unionFind, 1, 2, 0);
|
|
testSets(unionFind, {
|
|
{0, 1, 2, 3},
|
|
});
|
|
}
|
|
|
|
void expect(expected, actual) {
|
|
if (expected != actual) throw 'Expected $expected, actual $actual';
|
|
}
|