OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 /// Tests priority queue implementations utilities. | 5 /// Tests priority queue implementations utilities. |
6 | 6 |
7 import "package:collection/priority_queue.dart"; | |
8 import "package:test/test.dart"; | 7 import "package:test/test.dart"; |
9 | 8 |
| 9 import "package:collection/src/priority_queue.dart"; |
| 10 |
10 void main() { | 11 void main() { |
| 12 testDefault(); |
11 testInt(() => new HeapPriorityQueue<int>()); | 13 testInt(() => new HeapPriorityQueue<int>()); |
12 testCustom((comparator) => new HeapPriorityQueue<C>(comparator)); | 14 testCustom((comparator) => new HeapPriorityQueue<C>(comparator)); |
13 } | 15 } |
14 | 16 |
| 17 void testDefault() { |
| 18 test('new PriorityQueue() returns a HeapPriorityQueue', () { |
| 19 expect( |
| 20 new PriorityQueue<int>(), new isInstanceOf<HeapPriorityQueue<int>>()); |
| 21 }); |
| 22 testInt(() => new PriorityQueue<int>()); |
| 23 testCustom((comparator) => new PriorityQueue<C>(comparator)); |
| 24 } |
| 25 |
15 void testInt(PriorityQueue<int> create()) { | 26 void testInt(PriorityQueue<int> create()) { |
16 for (int count in [1, 5, 127, 128]) { | 27 for (int count in [1, 5, 127, 128]) { |
17 testQueue("int:$count", | 28 testQueue( |
18 create, | 29 "int:$count", create, new List<int>.generate(count, (x) => x), count); |
19 new List<int>.generate(count, (x) => x), | |
20 count); | |
21 } | 30 } |
22 } | 31 } |
23 | 32 |
24 void testCustom(PriorityQueue<C> create(comparator)) { | 33 void testCustom(PriorityQueue<C> create(comparator)) { |
25 for (int count in [1, 5, 127, 128]) { | 34 for (int count in [1, 5, 127, 128]) { |
26 testQueue("Custom:$count/null", | 35 testQueue("Custom:$count/null", () => create(null), |
27 () => create(null), | 36 new List<C>.generate(count, (x) => new C(x)), new C(count)); |
28 new List<C>.generate(count, (x) => new C(x)), | 37 testQueue("Custom:$count/compare", () => create(compare), |
29 new C(count)); | 38 new List<C>.generate(count, (x) => new C(x)), new C(count)); |
30 testQueue("Custom:$count/compare", | 39 testQueue("Custom:$count/compareNeg", () => create(compareNeg), |
31 () => create(compare), | 40 new List<C>.generate(count, (x) => new C(count - x)), new C(0)); |
32 new List<C>.generate(count, (x) => new C(x)), | |
33 new C(count)); | |
34 testQueue("Custom:$count/compareNeg", | |
35 () => create(compareNeg), | |
36 new List<C>.generate(count, (x) => new C(count - x)), | |
37 new C(0)); | |
38 } | 41 } |
39 } | 42 } |
40 | 43 |
41 /** | 44 /// Test that a queue behaves correctly. |
42 * Test that a queue behaves correctly. | 45 /// |
43 * | 46 /// The elements must be in priority order, from highest to lowest. |
44 * The elements must be in priority order, from highest to lowest. | |
45 */ | |
46 void testQueue(String name, PriorityQueue create(), List elements, notElement) { | 47 void testQueue(String name, PriorityQueue create(), List elements, notElement) { |
47 test(name, () => testQueueBody(create, elements, notElement)); | 48 test(name, () => testQueueBody(create, elements, notElement)); |
48 } | 49 } |
49 | 50 |
50 void testQueueBody(PriorityQueue create(), List elements, notElement) { | 51 void testQueueBody(PriorityQueue create(), List elements, notElement) { |
51 PriorityQueue q = create(); | 52 PriorityQueue q = create(); |
52 expect(q.isEmpty, isTrue); | 53 expect(q.isEmpty, isTrue); |
53 expect(q, hasLength(0)); | 54 expect(q, hasLength(0)); |
54 expect(() { q.first; }, throwsStateError); | 55 expect(() { |
55 expect(() { q.removeFirst(); }, throwsStateError); | 56 q.first; |
| 57 }, throwsStateError); |
| 58 expect(() { |
| 59 q.removeFirst(); |
| 60 }, throwsStateError); |
56 | 61 |
57 // Tests removeFirst, first, contains, toList and toSet. | 62 // Tests removeFirst, first, contains, toList and toSet. |
58 void testElements() { | 63 void testElements() { |
59 expect(q.isNotEmpty, isTrue); | 64 expect(q.isNotEmpty, isTrue); |
60 expect(q, hasLength(elements.length)); | 65 expect(q, hasLength(elements.length)); |
61 | 66 |
62 expect(q.toList(), equals(elements)); | 67 expect(q.toList(), equals(elements)); |
63 expect(q.toSet().toList(), equals(elements)); | 68 expect(q.toSet().toList(), equals(elements)); |
64 | 69 |
65 for (int i = 0; i < elements.length; i++) { | 70 for (int i = 0; i < elements.length; i++) { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
101 testElements(); | 106 testElements(); |
102 | 107 |
103 // Add elements by picking the middle element first, and then recursing | 108 // Add elements by picking the middle element first, and then recursing |
104 // on each side. | 109 // on each side. |
105 void addRec(int min, int max) { | 110 void addRec(int min, int max) { |
106 int mid = min + ((max - min) >> 1); | 111 int mid = min + ((max - min) >> 1); |
107 q.add(elements[mid]); | 112 q.add(elements[mid]); |
108 if (mid + 1 < max) addRec(mid + 1, max); | 113 if (mid + 1 < max) addRec(mid + 1, max); |
109 if (mid > min) addRec(min, mid); | 114 if (mid > min) addRec(min, mid); |
110 } | 115 } |
| 116 |
111 addRec(0, elements.length); | 117 addRec(0, elements.length); |
112 testElements(); | 118 testElements(); |
113 | 119 |
114 // Test removeAll. | 120 // Test removeAll. |
115 q.addAll(elements); | 121 q.addAll(elements); |
116 expect(q, hasLength(elements.length)); | 122 expect(q, hasLength(elements.length)); |
117 Iterable all = q.removeAll(); | 123 Iterable all = q.removeAll(); |
118 expect(q.isEmpty, isTrue); | 124 expect(q.isEmpty, isTrue); |
119 expect(all, hasLength(elements.length)); | 125 expect(all, hasLength(elements.length)); |
120 for (int i = 0; i < elements.length; i++) { | 126 for (int i = 0; i < elements.length; i++) { |
(...skipping 22 matching lines...) Expand all Loading... |
143 q.removeAll().forEach((x) => expect(x, same(a))); | 149 q.removeAll().forEach((x) => expect(x, same(a))); |
144 | 150 |
145 // Test remove. | 151 // Test remove. |
146 q.addAll(elements); | 152 q.addAll(elements); |
147 for (var element in elements.reversed) { | 153 for (var element in elements.reversed) { |
148 expect(q.remove(element), isTrue); | 154 expect(q.remove(element), isTrue); |
149 } | 155 } |
150 expect(q.isEmpty, isTrue); | 156 expect(q.isEmpty, isTrue); |
151 } | 157 } |
152 | 158 |
153 | |
154 // Custom class. | 159 // Custom class. |
155 // Class is comparable, comparators match normal and inverse order. | 160 // Class is comparable, comparators match normal and inverse order. |
156 int compare(C c1, C c2) => c1.value - c2.value; | 161 int compare(C c1, C c2) => c1.value - c2.value; |
157 int compareNeg(C c1, C c2) => c2.value - c1.value; | 162 int compareNeg(C c1, C c2) => c2.value - c1.value; |
158 | 163 |
159 class C implements Comparable { | 164 class C implements Comparable<C> { |
160 final int value; | 165 final int value; |
161 const C(this.value); | 166 const C(this.value); |
162 int get hashCode => value; | 167 int get hashCode => value; |
163 bool operator==(Object other) => other is C && value == other.value; | 168 bool operator ==(Object other) => other is C && value == other.value; |
164 int compareTo(C other) => value - other.value; | 169 int compareTo(C other) => value - other.value; |
165 String toString() => "C($value)"; | 170 String toString() => "C($value)"; |
166 } | 171 } |
OLD | NEW |