blob: 80a1742640783f9040cc528e72bc07dd117ed490 [file] [log] [blame]
// Copyright (c) 2011, 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.
// Dart test for Splaytrees.
library splay_tree_test;
import "package:expect/expect.dart";
import 'dart:collection';
main() {
// Simple tests.
SplayTreeMap tree = new SplayTreeMap();
tree[1] = "first";
tree[3] = "third";
tree[5] = "fifth";
tree[2] = "second";
tree[4] = "fourth";
var correctSolution = ["first", "second", "third", "fourth", "fifth"];
tree.forEach((key, value) {
Expect.equals(true, key >= 1);
Expect.equals(true, key <= 5);
Expect.equals(value, correctSolution[key - 1]);
});
for (var v in ["first", "second", "third", "fourth", "fifth"]) {
Expect.isTrue(tree.containsValue(v));
};
Expect.isFalse(tree.containsValue("sixth"));
tree[7] = "seventh";
Expect.equals(1, tree.firstKey());
Expect.equals(7, tree.lastKey());
Expect.equals(2, tree.lastKeyBefore(3));
Expect.equals(4, tree.firstKeyAfter(3));
Expect.equals(null, tree.lastKeyBefore(1));
Expect.equals(2, tree.firstKeyAfter(1));
Expect.equals(4, tree.lastKeyBefore(5));
Expect.equals(7, tree.firstKeyAfter(5));
Expect.equals(5, tree.lastKeyBefore(7));
Expect.equals(null, tree.firstKeyAfter(7));
Expect.equals(5, tree.lastKeyBefore(6));
Expect.equals(7, tree.firstKeyAfter(6));
testSetFrom();
regressRemoveWhere();
regressRemoveWhere2();
}
void regressRemoveWhere() {
// Regression test. Fix in https://codereview.chromium.org/148523006/
var t = new SplayTreeSet();
t.addAll([1, 3, 5, 7, 2, 4, 6, 8, 0]);
var seen = new List<bool>.filled(9, false);
t.removeWhere((x) {
// Called only once per element.
Expect.isFalse(seen[x], "seen $x");
seen[x] = true;
return x.isOdd;
});
}
void regressRemoveWhere2() {
// Regression test for http://dartbug.com/18676
// Removing all elements with removeWhere causes error.
var t = new SplayTreeSet();
t.addAll([1, 2, 3, 4, 5]);
t.removeWhere((_) => true); // Should not throw.
Expect.isTrue(t.isEmpty);
t.addAll([1, 2, 3, 4, 5]);
t.retainWhere((_) => false); // Should not throw.
Expect.isTrue(t.isEmpty);
}
void testSetFrom() {
var set1 = new SplayTreeSet<num>()..addAll([1, 2, 3, 4, 5]);
var set2 = new SplayTreeSet<int>.from(set1);
Expect.equals(5, set2.length);
for (int i = 1; i <= 5; i++) {
Expect.isTrue(set2.contains(i));
}
set1 = new SplayTreeSet<num>()..addAll([0, 1, 2.4, 3.14, 5]);
set2 = new SplayTreeSet<int>.from(set1.where((x) => x is int));
Expect.equals(3, set2.length);
}