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) } }