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