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 |