// listspawn.rs - Parallelized List Map

struct Node {
    head : int,
    tail : Option<~Node>
}

type List = Option<~Node> ;

trait Map {
    fn mapr(&self, extern fn(int) -> int) -> List;
}

impl Map for List {
    fn mapr(&self, f: extern fn(int) -> int) -> List { 
         match(*self) {
            None => None,
            // need the ref here to keep the matched variable type borrowed
            Some(ref node) => { 
                let (port, chan) : (Port<int>, Chan<int>) = stream();
                // v1: let newtail = node.tail.mapr(f);
                let val = node.head;
                do spawn {
                    let res = f(val);
                    chan.send(res);
                }
                let newtail = node.tail.mapr(f); // needs to move here!
                // println("waiting for recv..."); 
                let newval = port.recv();
                // println(fmt!("got it: %d", newval));
                Some(~Node{ head: newval, tail: newtail })
            }
        }
    }
}

impl ToStr for List {
    fn to_str(&self) -> ~str { 
        fn elements_to_str(n: &~Node) -> ~str {
            match (n.tail) {
                None => fmt!("%?", n.head),
                Some(ref tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
            }
        }
        
        match(*self) {
            None => ~"Null",
            Some(ref n) => fmt!("[%s]", elements_to_str(n)) 
        }
    }
}

fn collatz_steps(n: int) -> int {
    if n == 1 {
        0
    } else {
        1 + collatz_steps(if n % 2 == 0 { n / 2 } else { 3*n + 1 })
    }
}

fn find_collatz(k: int) -> int {
    // Returns the minimum value, n, with Collatz stopping time >= k.
    let mut n = 1;
    while collatz_steps(n) < k { n += 1; }
    n
}

fn test_list(n: int, x: int) -> List {
    if n == 0 {
        None
    } else {
        Some(~Node{head: x, tail: test_list(n - 1, x + 1)})
    }
}

fn main() {
    // Need more elements to keep more cores busy...
    let lst0 = test_list(16, 565);
    println(lst0.to_str());
    let lst1 = lst0.mapr(find_collatz);
    println(lst1.to_str());
}