fwdlist 0.2.0

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
}

#[inline(never)]
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));
}