Crate fwdlist

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!

Structs

Cursor	A cursor to navigate the list and reshape it.
List	A simply linked list.
ListIntoIter	Iterator consuming a list.
ListIter	Read-only iterator over a list.
ListIterMut	Mutable iterator over a list.