1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

//! A simple forward linked list.
//!
//! It's a linked list. Its not cache friendly, its relatively slow when you
//! think about it, but it allows for O(1) insertion... after the current
//! cursor location, maybe you care about that.
//!
//! # Trivial example
//! ```
//! use fwdlist::List;
//!
//! let mut q = List::new();
//! q.push_back(2);
//! q.push_front(1);
//! q.push_back(3);
//!
//! println!("{:?}", q);
//! for v in q {
//!     println!("{:?}", v);
//! }
//! ```
//!
//! # Using cursors
//!
//! A cursor helps walking the list while modifying its structure. Not to be
//! confused with a mutable iterator, which merely provides mutable access to
//! values of the list.
//!
//! For example, using cursors, we can implement a non-recursive merge-sort by
//! sorting and merging the list by pair of 2, 4, 8, etc...
//!
//! ```
//! extern crate fwdlist;
//!
//! use fwdlist::List;
//! use std::fmt::Debug;
//!
//! fn mklist<I: Iterator>(i: I) -> List<I::Item> {
//!     i.collect::<List<_>>()
//! }
//!
//! fn merge<'c, T>(mut a: List<T>, mut b: List<T>)
//!     -> List<T> where T: Ord + Debug {
//!     use std::cmp::Ordering::*;
//!
//!     let mut r = List::new();
//!     {
//!         let mut a = a.cursor();
//!         let mut b = b.cursor();
//!         let mut o = r.cursor();
//!         loop {
//!             let cmpr = {
//!                 if let (Some(a), Some(b)) = (a.value(), b.value()) {
//!                     a.cmp(b)
//!                 } else {
//!                     break
//!                 }
//!             };
//!             if cmpr == Less {
//!                 o.splice(&mut a.remove_n(1));
//!             } else {
//!                 o.splice(&mut b.remove_n(1));
//!             }
//!         }
//!         o.splice(&mut a.truncate());
//!         o.splice(&mut b.truncate());
//!     }
//!     r
//! }
//!
//! fn merge_sort<T>(mut l: List<T>) -> List<T> where T: Ord + Debug {
//!     let mut run_len = 1;
//!     let max_run_len = l.len();
//!     while run_len < max_run_len {
//!         let mut tail = l;
//!         l = List::new();
//!         let mut cl = l.cursor();
//!
//!         while !tail.is_empty() {
//!             let mut a = tail;
//!             let mut b = a.cursor().split(run_len);
//!             tail = b.cursor().split(run_len);
//!             cl.splice(&mut merge(a,b));
//!         }
//!         run_len *= 2;
//!     }
//!     return l;
//! }
//!
//! fn main() {
//!     const LMAX: usize = 30;
//!     let mut l = mklist((LMAX/2..LMAX).rev());
//!     l.extend(mklist(0..LMAX/2));
//!     println!("-> {:?}", l);
//!     let l = merge_sort(l);
//!     println!("-> {:?}", l);
//!     assert_eq!(l, mklist(0..LMAX));
//! }
//! ```
//!
//! Happy hacking!

#![cfg_attr(feature = "bench", feature(test))]

pub use crate::intoiter::ListIntoIter;
pub use crate::iter::ListIter;
pub use crate::itermut::ListIterMut;

mod cursor;
mod intoiter;
mod iter;
mod itermut;
mod ops;

/// A simply linked list.
pub struct List<T> {
    len: usize,
    head: Link<T>,
}

/// A cursor to navigate the list and reshape it.
///
/// Conceptually, a cursor moves between nodes, think the cursor of your text
/// editor.
///
/// ## Cursor by example
///
/// ```
/// use fwdlist::List;
///
/// let mut q: List<_> = (0..5).collect();
/// let mut c = q.cursor();
/// ```
/// So given the list `[0,1,2,3,4]`, the cursor `c`, represented by `|`
/// initially points to the first node:
///
/// ```plain
///  |0 1 2 3 4
/// ```
/// After advancing the cursor once `c.advance()`:
///
/// ```plain
///   0|1 2 3 4
/// ```
/// And after Advancing the cursor 4 times `c.nth(4)`:
///
/// ```plain
///   0 1 2 3 4|
/// ```
///
/// # Modifying the structure of the list
///
/// A cursor let you modify the list after its position (the `tail`). A cursor
/// is really an abstraction of a mutable pointer to the next node of the list.
///
/// With a cursor, you can truncate the list, insert and removes nodes, etc.
///
pub struct Cursor<'a, T> {
    next_link: &'a mut Link<T>,
    list_len: &'a mut usize,
    position: usize,
}

type Link<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Link<T>,
}

impl<T> Node<T> {
    fn new_boxed(value: T, next: Link<T>) -> Box<Node<T>> {
        Box::new(Node { value, next })
    }

    fn take(self) -> (T, Link<T>) {
        (self.value, self.next)
    }

    fn take_mut(&mut self) -> (&mut T, &mut Link<T>) {
        (&mut self.value, &mut self.next)
    }
}