| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 // Dart test for Splaytrees. | 5 // Dart test for Splaytrees. |
| 6 library splay_tree_test; | 6 library splay_tree_test; |
| 7 |
| 7 import "package:expect/expect.dart"; | 8 import "package:expect/expect.dart"; |
| 8 import 'dart:collection'; | 9 import 'dart:collection'; |
| 9 | 10 |
| 10 | |
| 11 main() { | 11 main() { |
| 12 // Simple tests. | 12 // Simple tests. |
| 13 SplayTreeMap tree = new SplayTreeMap(); | 13 SplayTreeMap tree = new SplayTreeMap(); |
| 14 tree[1] = "first"; | 14 tree[1] = "first"; |
| 15 tree[3] = "third"; | 15 tree[3] = "third"; |
| 16 tree[5] = "fifth"; | 16 tree[5] = "fifth"; |
| 17 tree[2] = "second"; | 17 tree[2] = "second"; |
| 18 tree[4] = "fourth"; | 18 tree[4] = "fourth"; |
| 19 | 19 |
| 20 var correctSolution = ["first", "second", "third", "fourth", "fifth"]; | 20 var correctSolution = ["first", "second", "third", "fourth", "fifth"]; |
| 21 | 21 |
| 22 tree.forEach((key, value) { | 22 tree.forEach((key, value) { |
| 23 Expect.equals(true, key >= 1); | 23 Expect.equals(true, key >= 1); |
| 24 Expect.equals(true, key <= 5); | 24 Expect.equals(true, key <= 5); |
| 25 Expect.equals(value, correctSolution[key - 1]); | 25 Expect.equals(value, correctSolution[key - 1]); |
| 26 }); | 26 }); |
| 27 | 27 |
| 28 for (var v in ["first", "second", "third", "fourth", "fifth"]) { | 28 for (var v in ["first", "second", "third", "fourth", "fifth"]) { |
| 29 Expect.isTrue(tree.containsValue(v)); | 29 Expect.isTrue(tree.containsValue(v)); |
| 30 }; | 30 } |
| 31 ; |
| 31 Expect.isFalse(tree.containsValue("sixth")); | 32 Expect.isFalse(tree.containsValue("sixth")); |
| 32 | 33 |
| 33 tree[7] = "seventh"; | 34 tree[7] = "seventh"; |
| 34 | 35 |
| 35 Expect.equals(1, tree.firstKey()); | 36 Expect.equals(1, tree.firstKey()); |
| 36 Expect.equals(7, tree.lastKey()); | 37 Expect.equals(7, tree.lastKey()); |
| 37 | 38 |
| 38 Expect.equals(2, tree.lastKeyBefore(3)); | 39 Expect.equals(2, tree.lastKeyBefore(3)); |
| 39 Expect.equals(4, tree.firstKeyAfter(3)); | 40 Expect.equals(4, tree.firstKeyAfter(3)); |
| 40 | 41 |
| (...skipping 27 matching lines...) Expand all Loading... |
| 68 return x.isOdd; | 69 return x.isOdd; |
| 69 }); | 70 }); |
| 70 } | 71 } |
| 71 | 72 |
| 72 void regressRemoveWhere2() { | 73 void regressRemoveWhere2() { |
| 73 // Regression test for http://dartbug.com/18676 | 74 // Regression test for http://dartbug.com/18676 |
| 74 // Removing all elements with removeWhere causes error. | 75 // Removing all elements with removeWhere causes error. |
| 75 | 76 |
| 76 var t = new SplayTreeSet(); | 77 var t = new SplayTreeSet(); |
| 77 t.addAll([1, 2, 3, 4, 5]); | 78 t.addAll([1, 2, 3, 4, 5]); |
| 78 t.removeWhere((_) => true); // Should not throw. | 79 t.removeWhere((_) => true); // Should not throw. |
| 79 Expect.isTrue(t.isEmpty); | 80 Expect.isTrue(t.isEmpty); |
| 80 t.addAll([1, 2, 3, 4, 5]); | 81 t.addAll([1, 2, 3, 4, 5]); |
| 81 t.retainWhere((_) => false); // Should not throw. | 82 t.retainWhere((_) => false); // Should not throw. |
| 82 Expect.isTrue(t.isEmpty); | 83 Expect.isTrue(t.isEmpty); |
| 83 } | 84 } |
| 84 | 85 |
| 85 void testSetFrom() { | 86 void testSetFrom() { |
| 86 var set1 = new SplayTreeSet<num>()..addAll([1, 2, 3, 4, 5]); | 87 var set1 = new SplayTreeSet<num>()..addAll([1, 2, 3, 4, 5]); |
| 87 var set2 = new SplayTreeSet<int>.from(set1); | 88 var set2 = new SplayTreeSet<int>.from(set1); |
| 88 Expect.equals(5, set2.length); | 89 Expect.equals(5, set2.length); |
| 89 for (int i = 1; i <= 5; i++) { | 90 for (int i = 1; i <= 5; i++) { |
| 90 Expect.isTrue(set2.contains(i)); | 91 Expect.isTrue(set2.contains(i)); |
| 91 } | 92 } |
| 92 | 93 |
| 93 set1 = new SplayTreeSet<num>()..addAll([0, 1, 2.4, 3.14, 5]); | 94 set1 = new SplayTreeSet<num>()..addAll([0, 1, 2.4, 3.14, 5]); |
| 94 set2 = new SplayTreeSet<int>.from(set1.where((x) => x is int)); | 95 set2 = new SplayTreeSet<int>.from(set1.where((x) => x is int)); |
| 95 Expect.equals(3, set2.length); | 96 Expect.equals(3, set2.length); |
| 96 } | 97 } |
| 97 | 98 |
| 98 | |
| 99 | |
| 100 void regressFromCompare() { | 99 void regressFromCompare() { |
| 101 // Regression test for http://dartbug.com/23387. | 100 // Regression test for http://dartbug.com/23387. |
| 102 // The compare and isValidKey arguments to SplayTreeMap.from were ignored. | 101 // The compare and isValidKey arguments to SplayTreeMap.from were ignored. |
| 103 | 102 |
| 104 int compare(a, b) { | 103 int compare(a, b) { |
| 105 if (a is IncomparableKey && b is IncomparableKey) { | 104 if (a is IncomparableKey && b is IncomparableKey) { |
| 106 return b.id - a.id; | 105 return b.id - a.id; |
| 107 } | 106 } |
| 108 throw "isValidKey failure"; | 107 throw "isValidKey failure"; |
| 109 } | 108 } |
| 109 |
| 110 bool isValidKey(o) => o is IncomparableKey; | 110 bool isValidKey(o) => o is IncomparableKey; |
| 111 IncomparableKey key(int n) => new IncomparableKey(n); | 111 IncomparableKey key(int n) => new IncomparableKey(n); |
| 112 | 112 |
| 113 var entries = {key(0): 0, key(1): 1, key(2): 2, key(0): 0}; | 113 var entries = {key(0): 0, key(1): 1, key(2): 2, key(0): 0}; |
| 114 Expect.equals(4, entries.length); | 114 Expect.equals(4, entries.length); |
| 115 var map = new SplayTreeMap<IncomparableKey, int>.from( | 115 var map = |
| 116 entries, compare, isValidKey); | 116 new SplayTreeMap<IncomparableKey, int>.from(entries, compare, isValidKey); |
| 117 Expect.equals(3, map.length); | 117 Expect.equals(3, map.length); |
| 118 for (int i = 0; i < 3; i++) { | 118 for (int i = 0; i < 3; i++) { |
| 119 Expect.isTrue(map.containsKey(key(i))); | 119 Expect.isTrue(map.containsKey(key(i))); |
| 120 Expect.equals(i, map[key(i)]); | 120 Expect.equals(i, map[key(i)]); |
| 121 } | 121 } |
| 122 Expect.isFalse(map.containsKey(key(5))); | 122 Expect.isFalse(map.containsKey(key(5))); |
| 123 Expect.isFalse(map.containsKey(1)); | 123 Expect.isFalse(map.containsKey(1)); |
| 124 Expect.isFalse(map.containsKey("string")); | 124 Expect.isFalse(map.containsKey("string")); |
| 125 Expect.equals(null, map[key(5)]); | 125 Expect.equals(null, map[key(5)]); |
| 126 Expect.equals(null, map[1]); | 126 Expect.equals(null, map[1]); |
| 127 Expect.equals(null, map["string"]); | 127 Expect.equals(null, map["string"]); |
| 128 Expect.throws(() { map[1] = 42; }); | 128 Expect.throws(() { |
| 129 Expect.throws(() { map["string"] = 42; }); | 129 map[1] = 42; |
| 130 }); |
| 131 Expect.throws(() { |
| 132 map["string"] = 42; |
| 133 }); |
| 130 map[key(5)] = 42; | 134 map[key(5)] = 42; |
| 131 Expect.equals(4, map.length); | 135 Expect.equals(4, map.length); |
| 132 Expect.equals(42, map[key(5)]); | 136 Expect.equals(42, map[key(5)]); |
| 133 } | 137 } |
| 134 | 138 |
| 135 class IncomparableKey { | 139 class IncomparableKey { |
| 136 final int id; | 140 final int id; |
| 137 IncomparableKey(this.id); | 141 IncomparableKey(this.id); |
| 138 } | 142 } |
| OLD | NEW |