1 // Copyright 2012-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 //! A doubly-linked list with owned nodes.
12 //!
13 //! The DList allows pushing and popping elements at either end.
14 //!
15 //! DList implements the trait Deque. It should be imported with `use
16 //! collections::deque::Deque`.
17
18 // DList is constructed like a singly-linked list over the field `next`.
19 // including the last link being None; each Node owns its `next` field.
20 //
21 // Backlinks over DList::prev are raw pointers that form a full chain in
22 // the reverse direction.
23
24 use std::cast;
25 use std::iter::Rev;
26 use std::iter;
27 use std::mem::{replace, swap};
28 use std::ptr;
29
30 use deque::Deque;
31
32 /// A doubly-linked list.
33 pub struct DList<T> {
34 length: uint,
35 list_head: Link<T>,
36 list_tail: Rawlink<Node<T>>,
37 }
38
39 type Link<T> = Option<Box<Node<T>>>;
40 struct Rawlink<T> { p: *mut T }
41
42 struct Node<T> {
43 next: Link<T>,
44 prev: Rawlink<Node<T>>,
45 value: T,
46 }
47
48 /// Double-ended DList iterator
49 pub struct Items<'a, T> {
50 head: &'a Link<T>,
51 tail: Rawlink<Node<T>>,
52 nelem: uint,
53 }
54
55 // FIXME #11820: the &'a Option<> of the Link stops clone working.
56 impl<'a, T> Clone for Items<'a, T> {
57 fn clone(&self) -> Items<'a, T> { *self }
58 }
59
60 /// Double-ended mutable DList iterator
61 pub struct MutItems<'a, T> {
62 list: &'a mut DList<T>,
63 head: Rawlink<Node<T>>,
64 tail: Rawlink<Node<T>>,
65 nelem: uint,
66 }
67
68 /// DList consuming iterator
69 #[deriving(Clone)]
70 pub struct MoveItems<T> {
71 list: DList<T>
72 }
73
74 /// Rawlink is a type like Option<T> but for holding a raw pointer
75 impl<T> Rawlink<T> {
76 /// Like Option::None for Rawlink
77 fn none() -> Rawlink<T> {
78 Rawlink{p: ptr::mut_null()}
79 }
80
81 /// Like Option::Some for Rawlink
82 fn some(n: &mut T) -> Rawlink<T> {
83 Rawlink{p: n}
84 }
85
86 /// Convert the `Rawlink` into an Option value
87 fn resolve_immut(&self) -> Option<&T> {
88 unsafe { self.p.to_option() }
89 }
90
91 /// Convert the `Rawlink` into an Option value
92 fn resolve(&mut self) -> Option<&mut T> {
93 if self.p.is_null() {
94 None
95 } else {
96 Some(unsafe { cast::transmute(self.p) })
97 }
98 }
99
100 /// Return the `Rawlink` and replace with `Rawlink::none()`
101 fn take(&mut self) -> Rawlink<T> {
102 replace(self, Rawlink::none())
103 }
104 }
105
106 impl<T> Clone for Rawlink<T> {
107 #[inline]
108 fn clone(&self) -> Rawlink<T> {
109 Rawlink{p: self.p}
110 }
111 }
112
113 impl<T> Node<T> {
114 fn new(v: T) -> Node<T> {
115 Node{value: v, next: None, prev: Rawlink::none()}
116 }
117 }
118
119 /// Set the .prev field on `next`, then return `Some(next)`
120 fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
121 -> Link<T> {
122 next.prev = prev;
123 Some(next)
124 }
125
126 impl<T> Container for DList<T> {
127 /// O(1)
128 #[inline]
129 fn is_empty(&self) -> bool {
130 self.list_head.is_none()
131 }
132 /// O(1)
133 #[inline]
134 fn len(&self) -> uint {
135 self.length
136 }
137 }
138
139 impl<T> Mutable for DList<T> {
140 /// Remove all elements from the DList
141 ///
142 /// O(N)
143 #[inline]
144 fn clear(&mut self) {
145 *self = DList::new()
146 }
147 }
148
149 // private methods
150 impl<T> DList<T> {
151 /// Add a Node first in the list
152 #[inline]
153 fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
154 match self.list_head {
155 None => {
156 self.list_tail = Rawlink::some(new_head);
157 self.list_head = link_with_prev(new_head, Rawlink::none());
158 }
159 Some(ref mut head) => {
160 new_head.prev = Rawlink::none();
161 head.prev = Rawlink::some(new_head);
162 swap(head, &mut new_head);
163 head.next = Some(new_head);
164 }
165 }
166 self.length += 1;
167 }
168
169 /// Remove the first Node and return it, or None if the list is empty
170 #[inline]
171 fn pop_front_node(&mut self) -> Option<Box<Node<T>>> {
172 self.list_head.take().map(|mut front_node| {
173 self.length -= 1;
174 match front_node.next.take() {
175 Some(node) => self.list_head = link_with_prev(node, Rawlink::none()),
176 None => self.list_tail = Rawlink::none()
177 }
178 front_node
179 })
180 }
181
182 /// Add a Node last in the list
183 #[inline]
184 fn push_back_node(&mut self, mut new_tail: Box<Node<T>>) {
185 match self.list_tail.resolve() {
186 None => return self.push_front_node(new_tail),
187 Some(tail) => {
188 self.list_tail = Rawlink::some(new_tail);
189 tail.next = link_with_prev(new_tail, Rawlink::some(tail));
190 }
191 }
192 self.length += 1;
193 }
194
195 /// Remove the last Node and return it, or None if the list is empty
196 #[inline]
197 fn pop_back_node(&mut self) -> Option<Box<Node<T>>> {
198 self.list_tail.resolve().map_or(None, |tail| {
199 self.length -= 1;
200 self.list_tail = tail.prev;
201 match tail.prev.resolve() {
202 None => self.list_head.take(),
203 Some(tail_prev) => tail_prev.next.take()
204 }
205 })
206 }
207 }
208
209 impl<T> Deque<T> for DList<T> {
210 /// Provide a reference to the front element, or None if the list is empty
211 #[inline]
212 fn front<'a>(&'a self) -> Option<&'a T> {
213 self.list_head.as_ref().map(|head| &head.value)
214 }
215
216 /// Provide a mutable reference to the front element, or None if the list is empty
217 #[inline]
218 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
219 self.list_head.as_mut().map(|head| &mut head.value)
220 }
221
222 /// Provide a reference to the back element, or None if the list is empty
223 #[inline]
224 fn back<'a>(&'a self) -> Option<&'a T> {
225 let tmp = self.list_tail.resolve_immut(); // FIXME: #3511: shouldn't need variable
226 tmp.as_ref().map(|tail| &tail.value)
227 }
228
229 /// Provide a mutable reference to the back element, or None if the list is empty
230 #[inline]
231 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
232 let tmp: Option<&'a mut Node<T>> =
233 self.list_tail.resolve(); // FIXME: #3511: shouldn't need variable
234 tmp.map(|tail| &mut tail.value)
235 }
236
237 /// Add an element first in the list
238 ///
239 /// O(1)
240 fn push_front(&mut self, elt: T) {
241 self.push_front_node(box Node::new(elt))
242 }
243
244 /// Remove the first element and return it, or None if the list is empty
245 ///
246 /// O(1)
247 fn pop_front(&mut self) -> Option<T> {
248 self.pop_front_node().map(|box Node{value, ..}| value)
249 }
250
251 /// Add an element last in the list
252 ///
253 /// O(1)
254 fn push_back(&mut self, elt: T) {
255 self.push_back_node(box Node::new(elt))
256 }
257
258 /// Remove the last element and return it, or None if the list is empty
259 ///
260 /// O(1)
261 fn pop_back(&mut self) -> Option<T> {
262 self.pop_back_node().map(|box Node{value, ..}| value)
263 }
264 }
265
266 impl<T> DList<T> {
267 /// Create an empty DList
268 #[inline]
269 pub fn new() -> DList<T> {
270 DList{list_head: None, list_tail: Rawlink::none(), length: 0}
271 }
272
273 /// Move the last element to the front of the list.
274 ///
275 /// If the list is empty, do nothing.
276 #[inline]
277 pub fn rotate_forward(&mut self) {
278 self.pop_back_node().map(|tail| {
279 self.push_front_node(tail)
280 });
281 }
282
283 /// Move the first element to the back of the list.
284 ///
285 /// If the list is empty, do nothing.
286 #[inline]
287 pub fn rotate_backward(&mut self) {
288 self.pop_front_node().map(|head| {
289 self.push_back_node(head)
290 });
291 }
292
293 /// Add all elements from `other` to the end of the list
294 ///
295 /// O(1)
296 pub fn append(&mut self, mut other: DList<T>) {
297 match self.list_tail.resolve() {
298 None => *self = other,
299 Some(tail) => {
300 // Carefully empty `other`.
301 let o_tail = other.list_tail.take();
302 let o_length = other.length;
303 match other.list_head.take() {
304 None => return,
305 Some(node) => {
306 tail.next = link_with_prev(node, self.list_tail);
307 self.list_tail = o_tail;
308 self.length += o_length;
309 }
310 }
311 }
312 }
313 }
314
315 /// Add all elements from `other` to the beginning of the list
316 ///
317 /// O(1)
318 #[inline]
319 pub fn prepend(&mut self, mut other: DList<T>) {
320 swap(self, &mut other);
321 self.append(other);
322 }
323
324 /// Insert `elt` before the first `x` in the list where `f(x, elt)` is true,
325 /// or at the end.
326 ///
327 /// O(N)
328 pub fn insert_when(&mut self, elt: T, f: |&T, &T| -> bool) {
329 {
330 let mut it = self.mut_iter();
331 loop {
332 match it.peek_next() {
333 None => break,
334 Some(x) => if f(x, &elt) { break }
335 }
336 it.next();
337 }
338 it.insert_next(elt);
339 }
340 }
341
342 /// Merge DList `other` into this DList, using the function `f`.
343 /// Iterate the both DList with `a` from self and `b` from `other`, and
344 /// put `a` in the result if `f(a, b)` is true, else `b`.
345 ///
346 /// O(max(N, M))
347 pub fn merge(&mut self, mut other: DList<T>, f: |&T, &T| -> bool) {
348 {
349 let mut it = self.mut_iter();
350 loop {
351 let take_a = match (it.peek_next(), other.front()) {
352 (_ , None) => return,
353 (None, _ ) => break,
354 (Some(ref mut x), Some(y)) => f(*x, y),
355 };
356 if take_a {
357 it.next();
358 } else {
359 it.insert_next_node(other.pop_front_node().unwrap());
360 }
361 }
362 }
363 self.append(other);
364 }
365
366
367 /// Provide a forward iterator
368 #[inline]
369 pub fn iter<'a>(&'a self) -> Items<'a, T> {
370 Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
371 }
372
373 #[inline]
374 #[deprecated = "replaced by .iter().rev()"]
375 pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
376 self.iter().rev()
377 }
378
379 /// Provide a forward iterator with mutable references
380 #[inline]
381 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
382 let head_raw = match self.list_head {
383 Some(ref mut h) => Rawlink::some(*h),
384 None => Rawlink::none(),
385 };
386 MutItems{
387 nelem: self.len(),
388 head: head_raw,
389 tail: self.list_tail,
390 list: self
391 }
392 }
393
394 #[inline]
395 #[deprecated = "replaced by .mut_iter().rev()"]
396 pub fn mut_rev_iter<'a>(&'a mut self) -> Rev<MutItems<'a, T>> {
397 self.mut_iter().rev()
398 }
399
400
401 /// Consume the list into an iterator yielding elements by value
402 #[inline]
403 pub fn move_iter(self) -> MoveItems<T> {
404 MoveItems{list: self}
405 }
406
407 #[inline]
408 #[deprecated = "replaced by .move_iter().rev()"]
409 pub fn move_rev_iter(self) -> Rev<MoveItems<T>> {
410 self.move_iter().rev()
411 }
412 }
413
414 impl<T: Ord> DList<T> {
415 /// Insert `elt` sorted in ascending order
416 ///
417 /// O(N)
418 #[inline]
419 pub fn insert_ordered(&mut self, elt: T) {
420 self.insert_when(elt, |a, b| a >= b)
421 }
422 }
423
424 #[unsafe_destructor]
425 impl<T> Drop for DList<T> {
426 fn drop(&mut self) {
427 // Dissolve the dlist in backwards direction
428 // Just dropping the list_head can lead to stack exhaustion
429 // when length is >> 1_000_000
430 let mut tail = self.list_tail;
431 loop {
432 match tail.resolve() {
433 None => break,
434 Some(prev) => {
435 prev.next.take(); // release Box<Node<T>>
436 tail = prev.prev;
437 }
438 }
439 }
440 self.length = 0;
441 self.list_head = None;
442 self.list_tail = Rawlink::none();
443 }
444 }
445
446
447 impl<'a, A> Iterator<&'a A> for Items<'a, A> {
448 #[inline]
449 fn next(&mut self) -> Option<&'a A> {
450 if self.nelem == 0 {
451 return None;
452 }
453 self.head.as_ref().map(|head| {
454 self.nelem -= 1;
455 self.head = &head.next;
456 &head.value
457 })
458 }
459
460 #[inline]
461 fn size_hint(&self) -> (uint, Option<uint>) {
462 (self.nelem, Some(self.nelem))
463 }
464 }
465
466 impl<'a, A> DoubleEndedIterator<&'a A> for Items<'a, A> {
467 #[inline]
468 fn next_back(&mut self) -> Option<&'a A> {
469 if self.nelem == 0 {
470 return None;
471 }
472 let tmp = self.tail.resolve_immut(); // FIXME: #3511: shouldn't need variable
473 tmp.as_ref().map(|prev| {
474 self.nelem -= 1;
475 self.tail = prev.prev;
476 &prev.value
477 })
478 }
479 }
480
481 impl<'a, A> ExactSize<&'a A> for Items<'a, A> {}
482
483 impl<'a, A> Iterator<&'a mut A> for MutItems<'a, A> {
484 #[inline]
485 fn next(&mut self) -> Option<&'a mut A> {
486 if self.nelem == 0 {
487 return None;
488 }
489 self.head.resolve().map(|next| {
490 self.nelem -= 1;
491 self.head = match next.next {
492 Some(ref mut node) => Rawlink::some(&mut **node),
493 None => Rawlink::none(),
494 };
495 &mut next.value
496 })
497 }
498
499 #[inline]
500 fn size_hint(&self) -> (uint, Option<uint>) {
501 (self.nelem, Some(self.nelem))
502 }
503 }
504
505 impl<'a, A> DoubleEndedIterator<&'a mut A> for MutItems<'a, A> {
506 #[inline]
507 fn next_back(&mut self) -> Option<&'a mut A> {
508 if self.nelem == 0 {
509 return None;
510 }
511 self.tail.resolve().map(|prev| {
512 self.nelem -= 1;
513 self.tail = prev.prev;
514 &mut prev.value
515 })
516 }
517 }
518
519 impl<'a, A> ExactSize<&'a mut A> for MutItems<'a, A> {}
520
521 /// Allow mutating the DList while iterating
522 pub trait ListInsertion<A> {
523 /// Insert `elt` just after to the element most recently returned by `.next()`
524 ///
525 /// The inserted element does not appear in the iteration.
526 fn insert_next(&mut self, elt: A);
527
528 /// Provide a reference to the next element, without changing the iterator
529 fn peek_next<'a>(&'a mut self) -> Option<&'a mut A>;
530 }
531
532 // private methods for MutItems
533 impl<'a, A> MutItems<'a, A> {
534 fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
535 // Insert before `self.head` so that it is between the
536 // previously yielded element and self.head.
537 //
538 // The inserted node will not appear in further iteration.
539 match self.head.resolve() {
540 None => { self.list.push_back_node(ins_node); }
541 Some(node) => {
542 let prev_node = match node.prev.resolve() {
543 None => return self.list.push_front_node(ins_node),
544 Some(prev) => prev,
545 };
546 let node_own = prev_node.next.take_unwrap();
547 ins_node.next = link_with_prev(node_own, Rawlink::some(ins_node));
548 prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
549 self.list.length += 1;
550 }
551 }
552 }
553 }
554
555 impl<'a, A> ListInsertion<A> for MutItems<'a, A> {
556 #[inline]
557 fn insert_next(&mut self, elt: A) {
558 self.insert_next_node(box Node::new(elt))
559 }
560
561 #[inline]
562 fn peek_next<'a>(&'a mut self) -> Option<&'a mut A> {
563 if self.nelem == 0 {
564 return None
565 }
566 self.head.resolve().map(|head| &mut head.value)
567 }
568 }
569
570 impl<A> Iterator<A> for MoveItems<A> {
571 #[inline]
572 fn next(&mut self) -> Option<A> { self.list.pop_front() }
573
574 #[inline]
575 fn size_hint(&self) -> (uint, Option<uint>) {
576 (self.list.length, Some(self.list.length))
577 }
578 }
579
580 impl<A> DoubleEndedIterator<A> for MoveItems<A> {
581 #[inline]
582 fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
583 }
584
585 impl<A> FromIterator<A> for DList<A> {
586 fn from_iter<T: Iterator<A>>(iterator: T) -> DList<A> {
587 let mut ret = DList::new();
588 ret.extend(iterator);
589 ret
590 }
591 }
592
593 impl<A> Extendable<A> for DList<A> {
594 fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
595 for elt in iterator { self.push_back(elt); }
596 }
597 }
598
599 impl<A: Eq> Eq for DList<A> {
600 fn eq(&self, other: &DList<A>) -> bool {
601 self.len() == other.len() &&
602 iter::order::eq(self.iter(), other.iter())
603 }
604
605 fn ne(&self, other: &DList<A>) -> bool {
606 self.len() != other.len() ||
607 iter::order::ne(self.iter(), other.iter())
608 }
609 }
610
611 impl<A: Ord> Ord for DList<A> {
612 fn lt(&self, other: &DList<A>) -> bool {
613 iter::order::lt(self.iter(), other.iter())
614 }
615 fn le(&self, other: &DList<A>) -> bool {
616 iter::order::le(self.iter(), other.iter())
617 }
618 fn gt(&self, other: &DList<A>) -> bool {
619 iter::order::gt(self.iter(), other.iter())
620 }
621 fn ge(&self, other: &DList<A>) -> bool {
622 iter::order::ge(self.iter(), other.iter())
623 }
624 }
625
626 impl<A: Clone> Clone for DList<A> {
627 fn clone(&self) -> DList<A> {
628 self.iter().map(|x| x.clone()).collect()
629 }
630 }
631
632 #[cfg(test)]
633 mod tests {
634 extern crate test;
635 use self::test::Bencher;
636 use deque::Deque;
637 use rand;
638 use super::{DList, Node, ListInsertion};
639
640 pub fn check_links<T>(list: &DList<T>) {
641 let mut len = 0u;
642 let mut last_ptr: Option<&Node<T>> = None;
643 let mut node_ptr: &Node<T>;
644 match list.list_head {
645 None => { assert_eq!(0u, list.length); return }
646 Some(ref node) => node_ptr = &**node,
647 }
648 loop {
649 match (last_ptr, node_ptr.prev.resolve_immut()) {
650 (None , None ) => {}
651 (None , _ ) => fail!("prev link for list_head"),
652 (Some(p), Some(pptr)) => {
653 assert_eq!(p as *Node<T>, pptr as *Node<T>);
654 }
655 _ => fail!("prev link is none, not good"),
656 }
657 match node_ptr.next {
658 Some(ref next) => {
659 last_ptr = Some(node_ptr);
660 node_ptr = &**next;
661 len += 1;
662 }
663 None => {
664 len += 1;
665 break;
666 }
667 }
668 }
669 assert_eq!(len, list.length);
670 }
671
672 #[test]
673 fn test_basic() {
674 let mut m: DList<Box<int>> = DList::new();
675 assert_eq!(m.pop_front(), None);
676 assert_eq!(m.pop_back(), None);
677 assert_eq!(m.pop_front(), None);
678 m.push_front(box 1);
679 assert_eq!(m.pop_front(), Some(box 1));
680 m.push_back(box 2);
681 m.push_back(box 3);
682 assert_eq!(m.len(), 2);
683 assert_eq!(m.pop_front(), Some(box 2));
684 assert_eq!(m.pop_front(), Some(box 3));
685 assert_eq!(m.len(), 0);
686 assert_eq!(m.pop_front(), None);
687 m.push_back(box 1);
688 m.push_back(box 3);
689 m.push_back(box 5);
690 m.push_back(box 7);
691 assert_eq!(m.pop_front(), Some(box 1));
692
693 let mut n = DList::new();
694 n.push_front(2);
695 n.push_front(3);
696 {
697 assert_eq!(n.front().unwrap(), &3);
698 let x = n.front_mut().unwrap();
699 assert_eq!(*x, 3);
700 *x = 0;
701 }
702 {
703 assert_eq!(n.back().unwrap(), &2);
704 let y = n.back_mut().unwrap();
705 assert_eq!(*y, 2);
706 *y = 1;
707 }
708 assert_eq!(n.pop_front(), Some(0));
709 assert_eq!(n.pop_front(), Some(1));
710 }
711
712 #[cfg(test)]
713 fn generate_test() -> DList<int> {
714 list_from(&[0,1,2,3,4,5,6])
715 }
716
717 #[cfg(test)]
718 fn list_from<T: Clone>(v: &[T]) -> DList<T> {
719 v.iter().map(|x| (*x).clone()).collect()
720 }
721
722 #[test]
723 fn test_append() {
724 {
725 let mut m = DList::new();
726 let mut n = DList::new();
727 n.push_back(2);
728 m.append(n);
729 assert_eq!(m.len(), 1);
730 assert_eq!(m.pop_back(), Some(2));
731 check_links(&m);
732 }
733 {
734 let mut m = DList::new();
735 let n = DList::new();
736 m.push_back(2);
737 m.append(n);
738 assert_eq!(m.len(), 1);
739 assert_eq!(m.pop_back(), Some(2));
740 check_links(&m);
741 }
742
743 let v = vec![1,2,3,4,5];
744 let u = vec![9,8,1,2,3,4,5];
745 let mut m = list_from(v.as_slice());
746 m.append(list_from(u.as_slice()));
747 check_links(&m);
748 let sum = v.append(u.as_slice());
749 assert_eq!(sum.len(), m.len());
750 for elt in sum.move_iter() {
751 assert_eq!(m.pop_front(), Some(elt))
752 }
753 }
754
755 #[test]
756 fn test_prepend() {
757 {
758 let mut m = DList::new();
759 let mut n = DList::new();
760 n.push_back(2);
761 m.prepend(n);
762 assert_eq!(m.len(), 1);
763 assert_eq!(m.pop_back(), Some(2));
764 check_links(&m);
765 }
766
767 let v = vec![1,2,3,4,5];
768 let u = vec![9,8,1,2,3,4,5];
769 let mut m = list_from(v.as_slice());
770 m.prepend(list_from(u.as_slice()));
771 check_links(&m);
772 let sum = u.append(v.as_slice());
773 assert_eq!(sum.len(), m.len());
774 for elt in sum.move_iter() {
775 assert_eq!(m.pop_front(), Some(elt))
776 }
777 }
778
779 #[test]
780 fn test_rotate() {
781 let mut n: DList<int> = DList::new();
782 n.rotate_backward(); check_links(&n);
783 assert_eq!(n.len(), 0);
784 n.rotate_forward(); check_links(&n);
785 assert_eq!(n.len(), 0);
786
787 let v = vec![1,2,3,4,5];
788 let mut m = list_from(v.as_slice());
789 m.rotate_backward(); check_links(&m);
790 m.rotate_forward(); check_links(&m);
791 assert_eq!(v.iter().collect::<Vec<&int>>(), m.iter().collect());
792 m.rotate_forward(); check_links(&m);
793 m.rotate_forward(); check_links(&m);
794 m.pop_front(); check_links(&m);
795 m.rotate_forward(); check_links(&m);
796 m.rotate_backward(); check_links(&m);
797 m.push_front(9); check_links(&m);
798 m.rotate_forward(); check_links(&m);
799 assert_eq!(vec![3,9,5,1,2], m.move_iter().collect());
800 }
801
802 #[test]
803 fn test_iterator() {
804 let m = generate_test();
805 for (i, elt) in m.iter().enumerate() {
806 assert_eq!(i as int, *elt);
807 }
808 let mut n = DList::new();
809 assert_eq!(n.iter().next(), None);
810 n.push_front(4);
811 let mut it = n.iter();
812 assert_eq!(it.size_hint(), (1, Some(1)));
813 assert_eq!(it.next().unwrap(), &4);
814 assert_eq!(it.size_hint(), (0, Some(0)));
815 assert_eq!(it.next(), None);
816 }
817
818 #[test]
819 fn test_iterator_clone() {
820 let mut n = DList::new();
821 n.push_back(2);
822 n.push_back(3);
823 n.push_back(4);
824 let mut it = n.iter();
825 it.next();
826 let mut jt = it.clone();
827 assert_eq!(it.next(), jt.next());
828 assert_eq!(it.next_back(), jt.next_back());
829 assert_eq!(it.next(), jt.next());
830 }
831
832 #[test]
833 fn test_iterator_double_end() {
834 let mut n = DList::new();
835 assert_eq!(n.iter().next(), None);
836 n.push_front(4);
837 n.push_front(5);
838 n.push_front(6);
839 let mut it = n.iter();
840 assert_eq!(it.size_hint(), (3, Some(3)));
841 assert_eq!(it.next().unwrap(), &6);
842 assert_eq!(it.size_hint(), (2, Some(2)));
843 assert_eq!(it.next_back().unwrap(), &4);
844 assert_eq!(it.size_hint(), (1, Some(1)));
845 assert_eq!(it.next_back().unwrap(), &5);
846 assert_eq!(it.next_back(), None);
847 assert_eq!(it.next(), None);
848 }
849
850 #[test]
851 fn test_rev_iter() {
852 let m = generate_test();
853 for (i, elt) in m.iter().rev().enumerate() {
854 assert_eq!((6 - i) as int, *elt);
855 }
856 let mut n = DList::new();
857 assert_eq!(n.iter().rev().next(), None);
858 n.push_front(4);
859 let mut it = n.iter().rev();
860 assert_eq!(it.size_hint(), (1, Some(1)));
861 assert_eq!(it.next().unwrap(), &4);
862 assert_eq!(it.size_hint(), (0, Some(0)));
863 assert_eq!(it.next(), None);
864 }
865
866 #[test]
867 fn test_mut_iter() {
868 let mut m = generate_test();
869 let mut len = m.len();
870 for (i, elt) in m.mut_iter().enumerate() {
871 assert_eq!(i as int, *elt);
872 len -= 1;
873 }
874 assert_eq!(len, 0);
875 let mut n = DList::new();
876 assert!(n.mut_iter().next().is_none());
877 n.push_front(4);
878 n.push_back(5);
879 let mut it = n.mut_iter();
880 assert_eq!(it.size_hint(), (2, Some(2)));
881 assert!(it.next().is_some());
882 assert!(it.next().is_some());
883 assert_eq!(it.size_hint(), (0, Some(0)));
884 assert!(it.next().is_none());
885 }
886
887 #[test]
888 fn test_iterator_mut_double_end() {
889 let mut n = DList::new();
890 assert!(n.mut_iter().next_back().is_none());
891 n.push_front(4);
892 n.push_front(5);
893 n.push_front(6);
894 let mut it = n.mut_iter();
895 assert_eq!(it.size_hint(), (3, Some(3)));
896 assert_eq!(*it.next().unwrap(), 6);
897 assert_eq!(it.size_hint(), (2, Some(2)));
898 assert_eq!(*it.next_back().unwrap(), 4);
899 assert_eq!(it.size_hint(), (1, Some(1)));
900 assert_eq!(*it.next_back().unwrap(), 5);
901 assert!(it.next_back().is_none());
902 assert!(it.next().is_none());
903 }
904
905 #[test]
906 fn test_insert_prev() {
907 let mut m = list_from(&[0,2,4,6,8]);
908 let len = m.len();
909 {
910 let mut it = m.mut_iter();
911 it.insert_next(-2);
912 loop {
913 match it.next() {
914 None => break,
915 Some(elt) => {
916 it.insert_next(*elt + 1);
917 match it.peek_next() {
918 Some(x) => assert_eq!(*x, *elt + 2),
919 None => assert_eq!(8, *elt),
920 }
921 }
922 }
923 }
924 it.insert_next(0);
925 it.insert_next(1);
926 }
927 check_links(&m);
928 assert_eq!(m.len(), 3 + len * 2);
929 assert_eq!(m.move_iter().collect::<Vec<int>>(), vec![-2,0,1,2,3,4,5,6,7,8,9,0,1]);
930 }
931
932 #[test]
933 fn test_merge() {
934 let mut m = list_from([0, 1, 3, 5, 6, 7, 2]);
935 let n = list_from([-1, 0, 0, 7, 7, 9]);
936 let len = m.len() + n.len();
937 m.merge(n, |a, b| a <= b);
938 assert_eq!(m.len(), len);
939 check_links(&m);
940 let res = m.move_iter().collect::<Vec<int>>();
941 assert_eq!(res, vec![-1, 0, 0, 0, 1, 3, 5, 6, 7, 2, 7, 7, 9]);
942 }
943
944 #[test]
945 fn test_insert_ordered() {
946 let mut n = DList::new();
947 n.insert_ordered(1);
948 assert_eq!(n.len(), 1);
949 assert_eq!(n.pop_front(), Some(1));
950
951 let mut m = DList::new();
952 m.push_back(2);
953 m.push_back(4);
954 m.insert_ordered(3);
955 check_links(&m);
956 assert_eq!(vec![2,3,4], m.move_iter().collect::<Vec<int>>());
957 }
958
959 #[test]
960 fn test_mut_rev_iter() {
961 let mut m = generate_test();
962 for (i, elt) in m.mut_iter().rev().enumerate() {
963 assert_eq!((6-i) as int, *elt);
964 }
965 let mut n = DList::new();
966 assert!(n.mut_iter().rev().next().is_none());
967 n.push_front(4);
968 let mut it = n.mut_iter().rev();
969 assert!(it.next().is_some());
970 assert!(it.next().is_none());
971 }
972
973 #[test]
974 fn test_send() {
975 let n = list_from([1,2,3]);
976 spawn(proc() {
977 check_links(&n);
978 assert_eq!(&[&1,&2,&3], n.iter().collect::<Vec<&int>>().as_slice());
979 });
980 }
981
982 #[test]
983 fn test_eq() {
984 let mut n: DList<u8> = list_from([]);
985 let mut m = list_from([]);
986 assert!(n == m);
987 n.push_front(1);
988 assert!(n != m);
989 m.push_back(1);
990 assert!(n == m);
991
992 let n = list_from([2,3,4]);
993 let m = list_from([1,2,3]);
994 assert!(n != m);
995 }
996
997 #[test]
998 fn test_ord() {
999 let n: DList<int> = list_from([]);
1000 let m = list_from([1,2,3]);
1001 assert!(n < m);
1002 assert!(m > n);
1003 assert!(n <= n);
1004 assert!(n >= n);
1005 }
1006
1007 #[test]
1008 fn test_ord_nan() {
1009 let nan = 0.0/0.0;
1010 let n = list_from([nan]);
1011 let m = list_from([nan]);
1012 assert!(!(n < m));
1013 assert!(!(n > m));
1014 assert!(!(n <= m));
1015 assert!(!(n >= m));
1016
1017 let n = list_from([nan]);
1018 let one = list_from([1.0]);
1019 assert!(!(n < one));
1020 assert!(!(n > one));
1021 assert!(!(n <= one));
1022 assert!(!(n >= one));
1023
1024 let u = list_from([1.0,2.0,nan]);
1025 let v = list_from([1.0,2.0,3.0]);
1026 assert!(!(u < v));
1027 assert!(!(u > v));
1028 assert!(!(u <= v));
1029 assert!(!(u >= v));
1030
1031 let s = list_from([1.0,2.0,4.0,2.0]);
1032 let t = list_from([1.0,2.0,3.0,2.0]);
1033 assert!(!(s < t));
1034 assert!(s > one);
1035 assert!(!(s <= one));
1036 assert!(s >= one);
1037 }
1038
1039 #[test]
1040 fn test_fuzz() {
1041 for _ in range(0, 25) {
1042 fuzz_test(3);
1043 fuzz_test(16);
1044 fuzz_test(189);
1045 }
1046 }
1047
1048 #[cfg(test)]
1049 fn fuzz_test(sz: int) {
1050 let mut m: DList<int> = DList::new();
1051 let mut v = vec![];
1052 for i in range(0, sz) {
1053 check_links(&m);
1054 let r: u8 = rand::random();
1055 match r % 6 {
1056 0 => {
1057 m.pop_back();
1058 v.pop();
1059 }
1060 1 => {
1061 m.pop_front();
1062 v.shift();
1063 }
1064 2 | 4 => {
1065 m.push_front(-i);
1066 v.unshift(-i);
1067 }
1068 3 | 5 | _ => {
1069 m.push_back(i);
1070 v.push(i);
1071 }
1072 }
1073 }
1074
1075 check_links(&m);
1076
1077 let mut i = 0u;
1078 for (a, &b) in m.move_iter().zip(v.iter()) {
1079 i += 1;
1080 assert_eq!(a, b);
1081 }
1082 assert_eq!(i, v.len());
1083 }
1084
1085 #[bench]
1086 fn bench_collect_into(b: &mut test::Bencher) {
1087 let v = &[0, ..64];
1088 b.iter(|| {
1089 let _: DList<int> = v.iter().map(|x| *x).collect();
1090 })
1091 }
1092
1093 #[bench]
1094 fn bench_push_front(b: &mut test::Bencher) {
1095 let mut m: DList<int> = DList::new();
1096 b.iter(|| {
1097 m.push_front(0);
1098 })
1099 }
1100
1101 #[bench]
1102 fn bench_push_back(b: &mut test::Bencher) {
1103 let mut m: DList<int> = DList::new();
1104 b.iter(|| {
1105 m.push_back(0);
1106 })
1107 }
1108
1109 #[bench]
1110 fn bench_push_back_pop_back(b: &mut test::Bencher) {
1111 let mut m: DList<int> = DList::new();
1112 b.iter(|| {
1113 m.push_back(0);
1114 m.pop_back();
1115 })
1116 }
1117
1118 #[bench]
1119 fn bench_push_front_pop_front(b: &mut test::Bencher) {
1120 let mut m: DList<int> = DList::new();
1121 b.iter(|| {
1122 m.push_front(0);
1123 m.pop_front();
1124 })
1125 }
1126
1127 #[bench]
1128 fn bench_rotate_forward(b: &mut test::Bencher) {
1129 let mut m: DList<int> = DList::new();
1130 m.push_front(0);
1131 m.push_front(1);
1132 b.iter(|| {
1133 m.rotate_forward();
1134 })
1135 }
1136
1137 #[bench]
1138 fn bench_rotate_backward(b: &mut test::Bencher) {
1139 let mut m: DList<int> = DList::new();
1140 m.push_front(0);
1141 m.push_front(1);
1142 b.iter(|| {
1143 m.rotate_backward();
1144 })
1145 }
1146
1147 #[bench]
1148 fn bench_iter(b: &mut test::Bencher) {
1149 let v = &[0, ..128];
1150 let m: DList<int> = v.iter().map(|&x|x).collect();
1151 b.iter(|| {
1152 assert!(m.iter().len() == 128);
1153 })
1154 }
1155 #[bench]
1156 fn bench_iter_mut(b: &mut test::Bencher) {
1157 let v = &[0, ..128];
1158 let mut m: DList<int> = v.iter().map(|&x|x).collect();
1159 b.iter(|| {
1160 assert!(m.mut_iter().len() == 128);
1161 })
1162 }
1163 #[bench]
1164 fn bench_iter_rev(b: &mut test::Bencher) {
1165 let v = &[0, ..128];
1166 let m: DList<int> = v.iter().map(|&x|x).collect();
1167 b.iter(|| {
1168 assert!(m.iter().rev().len() == 128);
1169 })
1170 }
1171 #[bench]
1172 fn bench_iter_mut_rev(b: &mut test::Bencher) {
1173 let v = &[0, ..128];
1174 let mut m: DList<int> = v.iter().map(|&x|x).collect();
1175 b.iter(|| {
1176 assert!(m.mut_iter().rev().len() == 128);
1177 })
1178 }
1179 }
libcollections/dlist.rs:60:40-60:40 -struct- definition:
/// Double-ended mutable DList iterator
pub struct MutItems<'a, T> {
list: &'a mut DList<T>,
references:- 8385: };
386: MutItems{
387: nelem: self.len(),
--
555: impl<'a, A> ListInsertion<A> for MutItems<'a, A> {
556: #[inline]
libcollections/dlist.rs:32:26-32:26 -struct- definition:
/// A doubly-linked list.
pub struct DList<T> {
length: uint,
references:- 27269: pub fn new() -> DList<T> {
270: DList{list_head: None, list_tail: Rawlink::none(), length: 0}
271: }
--
585: impl<A> FromIterator<A> for DList<A> {
586: fn from_iter<T: Iterator<A>>(iterator: T) -> DList<A> {
--
617: }
618: fn gt(&self, other: &DList<A>) -> bool {
619: iter::order::gt(self.iter(), other.iter())
620: }
621: fn ge(&self, other: &DList<A>) -> bool {
622: iter::order::ge(self.iter(), other.iter())
--
626: impl<A: Clone> Clone for DList<A> {
627: fn clone(&self) -> DList<A> {
628: self.iter().map(|x| x.clone()).collect()
libcollections/dlist.rs:69:19-69:19 -struct- definition:
pub struct MoveItems<T> {
list: DList<T>
}
references:- 9403: pub fn move_iter(self) -> MoveItems<T> {
404: MoveItems{list: self}
405: }
--
570: impl<A> Iterator<A> for MoveItems<A> {
571: #[inline]
--
580: impl<A> DoubleEndedIterator<A> for MoveItems<A> {
581: #[inline]
libcollections/dlist.rs:41:1-41:1 -struct- definition:
struct Node<T> {
next: Link<T>,
prev: Rawlink<Node<T>>,
references:- 19114: fn new(v: T) -> Node<T> {
115: Node{value: v, next: None, prev: Rawlink::none()}
116: }
--
152: #[inline]
153: fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
154: match self.list_head {
--
533: impl<'a, A> MutItems<'a, A> {
534: fn insert_next_node(&mut self, mut ins_node: Box<Node<A>>) {
535: // Insert before `self.head` so that it is between the
libcollections/dlist.rs:38:1-38:1 -NK_AS_STR_TODO- definition:
type Link<T> = Option<Box<Node<T>>>;
struct Rawlink<T> { p: *mut T }
struct Node<T> {
references:- 449: pub struct Items<'a, T> {
50: head: &'a Link<T>,
51: tail: Rawlink<Node<T>>,
--
120: fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
121: -> Link<T> {
122: next.prev = prev;
libcollections/dlist.rs:39:37-39:37 -struct- definition:
type Link<T> = Option<Box<Node<T>>>;
struct Rawlink<T> { p: *mut T }
struct Node<T> {
references:- 1582: fn some(n: &mut T) -> Rawlink<T> {
83: Rawlink{p: n}
84: }
--
108: fn clone(&self) -> Rawlink<T> {
109: Rawlink{p: self.p}
110: }
--
119: /// Set the .prev field on `next`, then return `Some(next)`
120: fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
121: -> Link<T> {
libcollections/dlist.rs:119:60-119:60 -fn- definition:
/// Set the .prev field on `next`, then return `Some(next)`
fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
-> Link<T> {
references:- 6546: let node_own = prev_node.next.take_unwrap();
547: ins_node.next = link_with_prev(node_own, Rawlink::some(ins_node));
548: prev_node.next = link_with_prev(ins_node, Rawlink::some(prev_node));
549: self.list.length += 1;
libcollections/dlist.rs:48:32-48:32 -struct- definition:
/// Double-ended DList iterator
pub struct Items<'a, T> {
head: &'a Link<T>,
references:- 8369: pub fn iter<'a>(&'a self) -> Items<'a, T> {
370: Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail}
371: }
--
447: impl<'a, A> Iterator<&'a A> for Items<'a, A> {
448: #[inline]
--
466: impl<'a, A> DoubleEndedIterator<&'a A> for Items<'a, A> {
467: #[inline]
--
481: impl<'a, A> ExactSize<&'a A> for Items<'a, A> {}