]>
Commit | Line | Data |
---|---|---|
c34b1796 AL |
1 | // Copyright 2012-2015 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::LinkedList; | |
12 | use std::hash::{SipHasher, self}; | |
13 | ||
14 | use test; | |
15 | ||
16 | #[test] | |
17 | fn test_basic() { | |
18 | let mut m = LinkedList::<Box<_>>::new(); | |
19 | assert_eq!(m.pop_front(), None); | |
20 | assert_eq!(m.pop_back(), None); | |
21 | assert_eq!(m.pop_front(), None); | |
22 | m.push_front(box 1); | |
23 | assert_eq!(m.pop_front(), Some(box 1)); | |
24 | m.push_back(box 2); | |
25 | m.push_back(box 3); | |
26 | assert_eq!(m.len(), 2); | |
27 | assert_eq!(m.pop_front(), Some(box 2)); | |
28 | assert_eq!(m.pop_front(), Some(box 3)); | |
29 | assert_eq!(m.len(), 0); | |
30 | assert_eq!(m.pop_front(), None); | |
31 | m.push_back(box 1); | |
32 | m.push_back(box 3); | |
33 | m.push_back(box 5); | |
34 | m.push_back(box 7); | |
35 | assert_eq!(m.pop_front(), Some(box 1)); | |
36 | ||
37 | let mut n = LinkedList::new(); | |
38 | n.push_front(2); | |
39 | n.push_front(3); | |
40 | { | |
41 | assert_eq!(n.front().unwrap(), &3); | |
42 | let x = n.front_mut().unwrap(); | |
43 | assert_eq!(*x, 3); | |
44 | *x = 0; | |
45 | } | |
46 | { | |
47 | assert_eq!(n.back().unwrap(), &2); | |
48 | let y = n.back_mut().unwrap(); | |
49 | assert_eq!(*y, 2); | |
50 | *y = 1; | |
51 | } | |
52 | assert_eq!(n.pop_front(), Some(0)); | |
53 | assert_eq!(n.pop_front(), Some(1)); | |
54 | } | |
55 | ||
56 | #[cfg(test)] | |
57 | fn generate_test() -> LinkedList<i32> { | |
58 | list_from(&[0,1,2,3,4,5,6]) | |
59 | } | |
60 | ||
61 | #[cfg(test)] | |
62 | fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { | |
63 | v.iter().cloned().collect() | |
64 | } | |
65 | ||
66 | #[test] | |
67 | fn test_split_off() { | |
68 | // singleton | |
69 | { | |
70 | let mut m = LinkedList::new(); | |
71 | m.push_back(1); | |
72 | ||
73 | let p = m.split_off(0); | |
74 | assert_eq!(m.len(), 0); | |
75 | assert_eq!(p.len(), 1); | |
76 | assert_eq!(p.back(), Some(&1)); | |
77 | assert_eq!(p.front(), Some(&1)); | |
78 | } | |
79 | ||
80 | // not singleton, forwards | |
81 | { | |
82 | let u = vec![1,2,3,4,5]; | |
83 | let mut m = list_from(&u); | |
84 | let mut n = m.split_off(2); | |
85 | assert_eq!(m.len(), 2); | |
86 | assert_eq!(n.len(), 3); | |
87 | for elt in 1..3 { | |
88 | assert_eq!(m.pop_front(), Some(elt)); | |
89 | } | |
90 | for elt in 3..6 { | |
91 | assert_eq!(n.pop_front(), Some(elt)); | |
92 | } | |
93 | } | |
94 | // not singleton, backwards | |
95 | { | |
96 | let u = vec![1,2,3,4,5]; | |
97 | let mut m = list_from(&u); | |
98 | let mut n = m.split_off(4); | |
99 | assert_eq!(m.len(), 4); | |
100 | assert_eq!(n.len(), 1); | |
101 | for elt in 1..5 { | |
102 | assert_eq!(m.pop_front(), Some(elt)); | |
103 | } | |
104 | for elt in 5..6 { | |
105 | assert_eq!(n.pop_front(), Some(elt)); | |
106 | } | |
107 | } | |
108 | ||
109 | // no-op on the last index | |
110 | { | |
111 | let mut m = LinkedList::new(); | |
112 | m.push_back(1); | |
113 | ||
114 | let p = m.split_off(1); | |
115 | assert_eq!(m.len(), 1); | |
116 | assert_eq!(p.len(), 0); | |
117 | assert_eq!(m.back(), Some(&1)); | |
118 | assert_eq!(m.front(), Some(&1)); | |
119 | } | |
120 | ||
121 | } | |
122 | ||
123 | #[test] | |
124 | fn test_iterator() { | |
125 | let m = generate_test(); | |
126 | for (i, elt) in m.iter().enumerate() { | |
127 | assert_eq!(i as i32, *elt); | |
128 | } | |
129 | let mut n = LinkedList::new(); | |
130 | assert_eq!(n.iter().next(), None); | |
131 | n.push_front(4); | |
132 | let mut it = n.iter(); | |
133 | assert_eq!(it.size_hint(), (1, Some(1))); | |
134 | assert_eq!(it.next().unwrap(), &4); | |
135 | assert_eq!(it.size_hint(), (0, Some(0))); | |
136 | assert_eq!(it.next(), None); | |
137 | } | |
138 | ||
139 | #[test] | |
140 | fn test_iterator_clone() { | |
141 | let mut n = LinkedList::new(); | |
142 | n.push_back(2); | |
143 | n.push_back(3); | |
144 | n.push_back(4); | |
145 | let mut it = n.iter(); | |
146 | it.next(); | |
147 | let mut jt = it.clone(); | |
148 | assert_eq!(it.next(), jt.next()); | |
149 | assert_eq!(it.next_back(), jt.next_back()); | |
150 | assert_eq!(it.next(), jt.next()); | |
151 | } | |
152 | ||
153 | #[test] | |
154 | fn test_iterator_double_end() { | |
155 | let mut n = LinkedList::new(); | |
156 | assert_eq!(n.iter().next(), None); | |
157 | n.push_front(4); | |
158 | n.push_front(5); | |
159 | n.push_front(6); | |
160 | let mut it = n.iter(); | |
161 | assert_eq!(it.size_hint(), (3, Some(3))); | |
162 | assert_eq!(it.next().unwrap(), &6); | |
163 | assert_eq!(it.size_hint(), (2, Some(2))); | |
164 | assert_eq!(it.next_back().unwrap(), &4); | |
165 | assert_eq!(it.size_hint(), (1, Some(1))); | |
166 | assert_eq!(it.next_back().unwrap(), &5); | |
167 | assert_eq!(it.next_back(), None); | |
168 | assert_eq!(it.next(), None); | |
169 | } | |
170 | ||
171 | #[test] | |
172 | fn test_rev_iter() { | |
173 | let m = generate_test(); | |
174 | for (i, elt) in m.iter().rev().enumerate() { | |
175 | assert_eq!((6 - i) as i32, *elt); | |
176 | } | |
177 | let mut n = LinkedList::new(); | |
178 | assert_eq!(n.iter().rev().next(), None); | |
179 | n.push_front(4); | |
180 | let mut it = n.iter().rev(); | |
181 | assert_eq!(it.size_hint(), (1, Some(1))); | |
182 | assert_eq!(it.next().unwrap(), &4); | |
183 | assert_eq!(it.size_hint(), (0, Some(0))); | |
184 | assert_eq!(it.next(), None); | |
185 | } | |
186 | ||
187 | #[test] | |
188 | fn test_mut_iter() { | |
189 | let mut m = generate_test(); | |
190 | let mut len = m.len(); | |
191 | for (i, elt) in m.iter_mut().enumerate() { | |
192 | assert_eq!(i as i32, *elt); | |
193 | len -= 1; | |
194 | } | |
195 | assert_eq!(len, 0); | |
196 | let mut n = LinkedList::new(); | |
197 | assert!(n.iter_mut().next().is_none()); | |
198 | n.push_front(4); | |
199 | n.push_back(5); | |
200 | let mut it = n.iter_mut(); | |
201 | assert_eq!(it.size_hint(), (2, Some(2))); | |
202 | assert!(it.next().is_some()); | |
203 | assert!(it.next().is_some()); | |
204 | assert_eq!(it.size_hint(), (0, Some(0))); | |
205 | assert!(it.next().is_none()); | |
206 | } | |
207 | ||
208 | #[test] | |
209 | fn test_iterator_mut_double_end() { | |
210 | let mut n = LinkedList::new(); | |
211 | assert!(n.iter_mut().next_back().is_none()); | |
212 | n.push_front(4); | |
213 | n.push_front(5); | |
214 | n.push_front(6); | |
215 | let mut it = n.iter_mut(); | |
216 | assert_eq!(it.size_hint(), (3, Some(3))); | |
217 | assert_eq!(*it.next().unwrap(), 6); | |
218 | assert_eq!(it.size_hint(), (2, Some(2))); | |
219 | assert_eq!(*it.next_back().unwrap(), 4); | |
220 | assert_eq!(it.size_hint(), (1, Some(1))); | |
221 | assert_eq!(*it.next_back().unwrap(), 5); | |
222 | assert!(it.next_back().is_none()); | |
223 | assert!(it.next().is_none()); | |
224 | } | |
225 | ||
226 | #[test] | |
227 | fn test_mut_rev_iter() { | |
228 | let mut m = generate_test(); | |
229 | for (i, elt) in m.iter_mut().rev().enumerate() { | |
230 | assert_eq!((6 - i) as i32, *elt); | |
231 | } | |
232 | let mut n = LinkedList::new(); | |
233 | assert!(n.iter_mut().rev().next().is_none()); | |
234 | n.push_front(4); | |
235 | let mut it = n.iter_mut().rev(); | |
236 | assert!(it.next().is_some()); | |
237 | assert!(it.next().is_none()); | |
238 | } | |
239 | ||
240 | #[test] | |
241 | fn test_eq() { | |
242 | let mut n = list_from(&[]); | |
243 | let mut m = list_from(&[]); | |
244 | assert!(n == m); | |
245 | n.push_front(1); | |
246 | assert!(n != m); | |
247 | m.push_back(1); | |
248 | assert!(n == m); | |
249 | ||
250 | let n = list_from(&[2,3,4]); | |
251 | let m = list_from(&[1,2,3]); | |
252 | assert!(n != m); | |
253 | } | |
254 | ||
255 | #[test] | |
256 | fn test_hash() { | |
257 | let mut x = LinkedList::new(); | |
258 | let mut y = LinkedList::new(); | |
259 | ||
260 | assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y)); | |
261 | ||
262 | x.push_back(1); | |
263 | x.push_back(2); | |
264 | x.push_back(3); | |
265 | ||
266 | y.push_front(3); | |
267 | y.push_front(2); | |
268 | y.push_front(1); | |
269 | ||
270 | assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y)); | |
271 | } | |
272 | ||
273 | #[test] | |
274 | fn test_ord() { | |
275 | let n = list_from(&[]); | |
276 | let m = list_from(&[1,2,3]); | |
277 | assert!(n < m); | |
278 | assert!(m > n); | |
279 | assert!(n <= n); | |
280 | assert!(n >= n); | |
281 | } | |
282 | ||
283 | #[test] | |
284 | fn test_ord_nan() { | |
285 | let nan = 0.0f64/0.0; | |
286 | let n = list_from(&[nan]); | |
287 | let m = list_from(&[nan]); | |
288 | assert!(!(n < m)); | |
289 | assert!(!(n > m)); | |
290 | assert!(!(n <= m)); | |
291 | assert!(!(n >= m)); | |
292 | ||
293 | let n = list_from(&[nan]); | |
294 | let one = list_from(&[1.0f64]); | |
295 | assert!(!(n < one)); | |
296 | assert!(!(n > one)); | |
297 | assert!(!(n <= one)); | |
298 | assert!(!(n >= one)); | |
299 | ||
300 | let u = list_from(&[1.0f64,2.0,nan]); | |
301 | let v = list_from(&[1.0f64,2.0,3.0]); | |
302 | assert!(!(u < v)); | |
303 | assert!(!(u > v)); | |
304 | assert!(!(u <= v)); | |
305 | assert!(!(u >= v)); | |
306 | ||
307 | let s = list_from(&[1.0f64,2.0,4.0,2.0]); | |
308 | let t = list_from(&[1.0f64,2.0,3.0,2.0]); | |
309 | assert!(!(s < t)); | |
310 | assert!(s > one); | |
311 | assert!(!(s <= one)); | |
312 | assert!(s >= one); | |
313 | } | |
314 | ||
315 | #[test] | |
316 | fn test_show() { | |
317 | let list: LinkedList<_> = (0..10).collect(); | |
318 | assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); | |
319 | ||
320 | let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); | |
321 | assert_eq!(format!("{:?}", list), "[\"just\", \"one\", \"test\", \"more\"]"); | |
322 | } | |
323 | ||
62682a34 SL |
324 | #[test] |
325 | fn test_extend_ref() { | |
326 | let mut a = LinkedList::new(); | |
327 | a.push_back(1); | |
328 | ||
329 | a.extend(&[2, 3, 4]); | |
330 | ||
331 | assert_eq!(a.len(), 4); | |
332 | assert_eq!(a, list_from(&[1, 2, 3, 4])); | |
333 | ||
334 | let mut b = LinkedList::new(); | |
335 | b.push_back(5); | |
336 | b.push_back(6); | |
337 | a.extend(&b); | |
338 | ||
339 | assert_eq!(a.len(), 6); | |
340 | assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6])); | |
341 | } | |
342 | ||
c34b1796 AL |
343 | #[bench] |
344 | fn bench_collect_into(b: &mut test::Bencher) { | |
345 | let v = &[0; 64]; | |
346 | b.iter(|| { | |
347 | let _: LinkedList<_> = v.iter().cloned().collect(); | |
348 | }) | |
349 | } | |
350 | ||
351 | #[bench] | |
352 | fn bench_push_front(b: &mut test::Bencher) { | |
353 | let mut m: LinkedList<_> = LinkedList::new(); | |
354 | b.iter(|| { | |
355 | m.push_front(0); | |
356 | }) | |
357 | } | |
358 | ||
359 | #[bench] | |
360 | fn bench_push_back(b: &mut test::Bencher) { | |
361 | let mut m: LinkedList<_> = LinkedList::new(); | |
362 | b.iter(|| { | |
363 | m.push_back(0); | |
364 | }) | |
365 | } | |
366 | ||
367 | #[bench] | |
368 | fn bench_push_back_pop_back(b: &mut test::Bencher) { | |
369 | let mut m: LinkedList<_> = LinkedList::new(); | |
370 | b.iter(|| { | |
371 | m.push_back(0); | |
372 | m.pop_back(); | |
373 | }) | |
374 | } | |
375 | ||
376 | #[bench] | |
377 | fn bench_push_front_pop_front(b: &mut test::Bencher) { | |
378 | let mut m: LinkedList<_> = LinkedList::new(); | |
379 | b.iter(|| { | |
380 | m.push_front(0); | |
381 | m.pop_front(); | |
382 | }) | |
383 | } | |
384 | ||
385 | #[bench] | |
386 | fn bench_iter(b: &mut test::Bencher) { | |
387 | let v = &[0; 128]; | |
388 | let m: LinkedList<_> = v.iter().cloned().collect(); | |
389 | b.iter(|| { | |
390 | assert!(m.iter().count() == 128); | |
391 | }) | |
392 | } | |
393 | #[bench] | |
394 | fn bench_iter_mut(b: &mut test::Bencher) { | |
395 | let v = &[0; 128]; | |
396 | let mut m: LinkedList<_> = v.iter().cloned().collect(); | |
397 | b.iter(|| { | |
398 | assert!(m.iter_mut().count() == 128); | |
399 | }) | |
400 | } | |
401 | #[bench] | |
402 | fn bench_iter_rev(b: &mut test::Bencher) { | |
403 | let v = &[0; 128]; | |
404 | let m: LinkedList<_> = v.iter().cloned().collect(); | |
405 | b.iter(|| { | |
406 | assert!(m.iter().rev().count() == 128); | |
407 | }) | |
408 | } | |
409 | #[bench] | |
410 | fn bench_iter_mut_rev(b: &mut test::Bencher) { | |
411 | let v = &[0; 128]; | |
412 | let mut m: LinkedList<_> = v.iter().cloned().collect(); | |
413 | b.iter(|| { | |
414 | assert!(m.iter_mut().rev().count() == 128); | |
415 | }) | |
416 | } |