]>
Commit | Line | Data |
---|---|---|
c34b1796 AL |
1 | // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use std::collections::BinaryHeap; | |
5bcae85e | 12 | use std::collections::binary_heap::Drain; |
c34b1796 AL |
13 | |
14 | #[test] | |
15 | fn test_iterator() { | |
16 | let data = vec![5, 9, 3]; | |
17 | let iterout = [9, 5, 3]; | |
9cc50fc6 | 18 | let heap = BinaryHeap::from(data); |
c34b1796 AL |
19 | let mut i = 0; |
20 | for el in &heap { | |
21 | assert_eq!(*el, iterout[i]); | |
22 | i += 1; | |
23 | } | |
24 | } | |
25 | ||
26 | #[test] | |
27 | fn test_iterator_reverse() { | |
28 | let data = vec![5, 9, 3]; | |
29 | let iterout = vec![3, 5, 9]; | |
9cc50fc6 | 30 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
31 | |
32 | let v: Vec<_> = pq.iter().rev().cloned().collect(); | |
33 | assert_eq!(v, iterout); | |
34 | } | |
35 | ||
36 | #[test] | |
37 | fn test_move_iter() { | |
38 | let data = vec![5, 9, 3]; | |
39 | let iterout = vec![9, 5, 3]; | |
9cc50fc6 | 40 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
41 | |
42 | let v: Vec<_> = pq.into_iter().collect(); | |
43 | assert_eq!(v, iterout); | |
44 | } | |
45 | ||
46 | #[test] | |
47 | fn test_move_iter_size_hint() { | |
48 | let data = vec![5, 9]; | |
9cc50fc6 | 49 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
50 | |
51 | let mut it = pq.into_iter(); | |
52 | ||
53 | assert_eq!(it.size_hint(), (2, Some(2))); | |
54 | assert_eq!(it.next(), Some(9)); | |
55 | ||
56 | assert_eq!(it.size_hint(), (1, Some(1))); | |
57 | assert_eq!(it.next(), Some(5)); | |
58 | ||
59 | assert_eq!(it.size_hint(), (0, Some(0))); | |
60 | assert_eq!(it.next(), None); | |
61 | } | |
62 | ||
63 | #[test] | |
64 | fn test_move_iter_reverse() { | |
65 | let data = vec![5, 9, 3]; | |
66 | let iterout = vec![3, 5, 9]; | |
9cc50fc6 | 67 | let pq = BinaryHeap::from(data); |
c34b1796 AL |
68 | |
69 | let v: Vec<_> = pq.into_iter().rev().collect(); | |
70 | assert_eq!(v, iterout); | |
71 | } | |
72 | ||
73 | #[test] | |
74 | fn test_peek_and_pop() { | |
75 | let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; | |
76 | let mut sorted = data.clone(); | |
77 | sorted.sort(); | |
9cc50fc6 | 78 | let mut heap = BinaryHeap::from(data); |
c34b1796 AL |
79 | while !heap.is_empty() { |
80 | assert_eq!(heap.peek().unwrap(), sorted.last().unwrap()); | |
81 | assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap()); | |
82 | } | |
83 | } | |
84 | ||
3157f602 XL |
85 | #[test] |
86 | fn test_peek_mut() { | |
87 | let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; | |
88 | let mut heap = BinaryHeap::from(data); | |
89 | assert_eq!(heap.peek(), Some(&10)); | |
90 | { | |
91 | let mut top = heap.peek_mut().unwrap(); | |
92 | *top -= 2; | |
93 | } | |
94 | assert_eq!(heap.peek(), Some(&9)); | |
95 | } | |
96 | ||
c34b1796 AL |
97 | #[test] |
98 | fn test_push() { | |
9cc50fc6 | 99 | let mut heap = BinaryHeap::from(vec![2, 4, 9]); |
c34b1796 AL |
100 | assert_eq!(heap.len(), 3); |
101 | assert!(*heap.peek().unwrap() == 9); | |
102 | heap.push(11); | |
103 | assert_eq!(heap.len(), 4); | |
104 | assert!(*heap.peek().unwrap() == 11); | |
105 | heap.push(5); | |
106 | assert_eq!(heap.len(), 5); | |
107 | assert!(*heap.peek().unwrap() == 11); | |
108 | heap.push(27); | |
109 | assert_eq!(heap.len(), 6); | |
110 | assert!(*heap.peek().unwrap() == 27); | |
111 | heap.push(3); | |
112 | assert_eq!(heap.len(), 7); | |
113 | assert!(*heap.peek().unwrap() == 27); | |
114 | heap.push(103); | |
115 | assert_eq!(heap.len(), 8); | |
116 | assert!(*heap.peek().unwrap() == 103); | |
117 | } | |
118 | ||
119 | #[test] | |
120 | fn test_push_unique() { | |
9cc50fc6 | 121 | let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]); |
c34b1796 AL |
122 | assert_eq!(heap.len(), 3); |
123 | assert!(*heap.peek().unwrap() == box 9); | |
124 | heap.push(box 11); | |
125 | assert_eq!(heap.len(), 4); | |
126 | assert!(*heap.peek().unwrap() == box 11); | |
127 | heap.push(box 5); | |
128 | assert_eq!(heap.len(), 5); | |
129 | assert!(*heap.peek().unwrap() == box 11); | |
130 | heap.push(box 27); | |
131 | assert_eq!(heap.len(), 6); | |
132 | assert!(*heap.peek().unwrap() == box 27); | |
133 | heap.push(box 3); | |
134 | assert_eq!(heap.len(), 7); | |
135 | assert!(*heap.peek().unwrap() == box 27); | |
136 | heap.push(box 103); | |
137 | assert_eq!(heap.len(), 8); | |
138 | assert!(*heap.peek().unwrap() == box 103); | |
139 | } | |
140 | ||
141 | #[test] | |
9e0c209e | 142 | #[allow(deprecated)] |
c34b1796 | 143 | fn test_push_pop() { |
9cc50fc6 | 144 | let mut heap = BinaryHeap::from(vec![5, 5, 2, 1, 3]); |
c34b1796 AL |
145 | assert_eq!(heap.len(), 5); |
146 | assert_eq!(heap.push_pop(6), 6); | |
147 | assert_eq!(heap.len(), 5); | |
148 | assert_eq!(heap.push_pop(0), 5); | |
149 | assert_eq!(heap.len(), 5); | |
150 | assert_eq!(heap.push_pop(4), 5); | |
151 | assert_eq!(heap.len(), 5); | |
152 | assert_eq!(heap.push_pop(1), 4); | |
153 | assert_eq!(heap.len(), 5); | |
154 | } | |
155 | ||
156 | #[test] | |
9e0c209e | 157 | #[allow(deprecated)] |
c34b1796 | 158 | fn test_replace() { |
9cc50fc6 | 159 | let mut heap = BinaryHeap::from(vec![5, 5, 2, 1, 3]); |
c34b1796 AL |
160 | assert_eq!(heap.len(), 5); |
161 | assert_eq!(heap.replace(6).unwrap(), 5); | |
162 | assert_eq!(heap.len(), 5); | |
163 | assert_eq!(heap.replace(0).unwrap(), 6); | |
164 | assert_eq!(heap.len(), 5); | |
165 | assert_eq!(heap.replace(4).unwrap(), 5); | |
166 | assert_eq!(heap.len(), 5); | |
167 | assert_eq!(heap.replace(1).unwrap(), 4); | |
168 | assert_eq!(heap.len(), 5); | |
169 | } | |
170 | ||
171 | fn check_to_vec(mut data: Vec<i32>) { | |
9cc50fc6 | 172 | let heap = BinaryHeap::from(data.clone()); |
c34b1796 AL |
173 | let mut v = heap.clone().into_vec(); |
174 | v.sort(); | |
175 | data.sort(); | |
176 | ||
177 | assert_eq!(v, data); | |
178 | assert_eq!(heap.into_sorted_vec(), data); | |
179 | } | |
180 | ||
181 | #[test] | |
182 | fn test_to_vec() { | |
183 | check_to_vec(vec![]); | |
184 | check_to_vec(vec![5]); | |
185 | check_to_vec(vec![3, 2]); | |
186 | check_to_vec(vec![2, 3]); | |
187 | check_to_vec(vec![5, 1, 2]); | |
188 | check_to_vec(vec![1, 100, 2, 3]); | |
189 | check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]); | |
190 | check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]); | |
191 | check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]); | |
192 | check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); | |
193 | check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]); | |
194 | check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]); | |
195 | check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]); | |
196 | } | |
197 | ||
198 | #[test] | |
199 | fn test_empty_pop() { | |
200 | let mut heap = BinaryHeap::<i32>::new(); | |
201 | assert!(heap.pop().is_none()); | |
202 | } | |
203 | ||
204 | #[test] | |
205 | fn test_empty_peek() { | |
206 | let empty = BinaryHeap::<i32>::new(); | |
207 | assert!(empty.peek().is_none()); | |
208 | } | |
209 | ||
3157f602 XL |
210 | #[test] |
211 | fn test_empty_peek_mut() { | |
212 | let mut empty = BinaryHeap::<i32>::new(); | |
213 | assert!(empty.peek_mut().is_none()); | |
214 | } | |
215 | ||
c34b1796 | 216 | #[test] |
9e0c209e | 217 | #[allow(deprecated)] |
c34b1796 AL |
218 | fn test_empty_replace() { |
219 | let mut heap = BinaryHeap::new(); | |
220 | assert!(heap.replace(5).is_none()); | |
221 | } | |
222 | ||
223 | #[test] | |
224 | fn test_from_iter() { | |
225 | let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1]; | |
226 | ||
227 | let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect(); | |
228 | ||
229 | for &x in &xs { | |
230 | assert_eq!(q.pop().unwrap(), x); | |
231 | } | |
232 | } | |
233 | ||
234 | #[test] | |
235 | fn test_drain() { | |
236 | let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect(); | |
237 | ||
238 | assert_eq!(q.drain().take(5).count(), 5); | |
239 | ||
240 | assert!(q.is_empty()); | |
241 | } | |
62682a34 SL |
242 | |
243 | #[test] | |
244 | fn test_extend_ref() { | |
245 | let mut a = BinaryHeap::new(); | |
246 | a.push(1); | |
247 | a.push(2); | |
248 | ||
249 | a.extend(&[3, 4, 5]); | |
250 | ||
251 | assert_eq!(a.len(), 5); | |
252 | assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); | |
253 | ||
254 | let mut a = BinaryHeap::new(); | |
255 | a.push(1); | |
256 | a.push(2); | |
257 | let mut b = BinaryHeap::new(); | |
258 | b.push(3); | |
259 | b.push(4); | |
260 | b.push(5); | |
261 | ||
262 | a.extend(&b); | |
263 | ||
264 | assert_eq!(a.len(), 5); | |
265 | assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]); | |
266 | } | |
a7813a04 XL |
267 | |
268 | #[test] | |
269 | fn test_append() { | |
270 | let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); | |
271 | let mut b = BinaryHeap::from(vec![-20, 5, 43]); | |
272 | ||
273 | a.append(&mut b); | |
274 | ||
275 | assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); | |
276 | assert!(b.is_empty()); | |
277 | } | |
278 | ||
279 | #[test] | |
280 | fn test_append_to_empty() { | |
281 | let mut a = BinaryHeap::new(); | |
282 | let mut b = BinaryHeap::from(vec![-20, 5, 43]); | |
283 | ||
284 | a.append(&mut b); | |
285 | ||
286 | assert_eq!(a.into_sorted_vec(), [-20, 5, 43]); | |
287 | assert!(b.is_empty()); | |
288 | } | |
289 | ||
290 | #[test] | |
291 | fn test_extend_specialization() { | |
292 | let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]); | |
293 | let b = BinaryHeap::from(vec![-20, 5, 43]); | |
294 | ||
295 | a.extend(b); | |
296 | ||
297 | assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]); | |
298 | } | |
5bcae85e SL |
299 | |
300 | #[allow(dead_code)] | |
301 | fn assert_covariance() { | |
c30ab7b3 SL |
302 | fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { |
303 | d | |
304 | } | |
5bcae85e | 305 | } |