dlist.rs

use list::Node;

mod list {
    use std::mem;

    #[derive(Show)]    
    pub struct Node<T> {
        pub data: T,
        prev: Option<Box<Node<T>>>,
        next: Option<Box<Node<T>>>
    }
    
    impl<T> Node<T> {
        pub fn new(data: T) -> Node<T> {
            Node { data: data, prev: None, next: None }
        }
    
        pub fn insert_after(&mut self, mut new: Box<Node<T>>) -> Option<Box<Node<T>>> {
            mem::swap(&mut new.next, &mut self.next);
            mem::replace(&mut self.next, Some(new))
        }
    
        pub fn insert_before(&mut self, mut new: Box<Node<T>>) -> Option<Box<Node<T>>> {
            mem::swap(&mut new.prev, &mut self.prev);
            mem::replace(&mut self.prev, Some(new))
        }

        pub fn remove_after(&mut self) -> Option<Box<Node<T>>> {
            match self.next.take() {
                Some(mut next) => {
                    mem::swap(&mut self.next, &mut next.next);
                    Some(next)
                },
                None => None,
            }
        }

        pub fn remove_before(&mut self) -> Option<Box<Node<T>>> {
            match self.prev.take() {
                Some(mut prev) => {
                    mem::swap(&mut self.prev, &mut prev.prev);
                    Some(prev)
                },
                None => None,
            }
        }

        pub fn next(&mut self) -> Option<&mut T> {
            let Node { ref mut data, ref mut prev, ref mut next } = *self;
            match *next {
                Some(ref mut next) => {
                    mem::swap(&mut next.data, data);
                    {
                        let mut next = &mut **next;
                        mem::swap(&mut next.next, &mut next.prev);
                    }
                    mem::swap(&mut next.prev, prev);
                },
                None => return None,
            }
            mem::swap(prev, next);
            Some(data)
        }

        pub fn prev(&mut self) -> Option<&mut T> {
            let Node { ref mut data, ref mut prev, ref mut next } = *self;
            match *prev {
                Some(ref mut prev) => {
                    mem::swap(&mut prev.data, data);
                    {
                        let mut prev = &mut **prev;
                        mem::swap(&mut prev.next, &mut prev.prev);
                    }
                    mem::swap(&mut prev.next, next);
                },
                None => return None
            }
            mem::swap(prev, next);
            Some(data)
        }
    }
}

fn main() {
    let mut list = Node::new(0i8);
    list.insert_before(box Node::new(-1));
    list.insert_after(box Node::new(1));
    while let Some(_) = list.next() {
        println!("{}", list);
    }
    list.insert_before(box Node::new(2));
    while let Some(_) = list.prev() {
        println!("{}", list.remove_before());
        println!("{}", list);
    }
    println!("{}", list.remove_after());
}

zipper.rs

#![feature(globs)]

extern crate arena;

use arena::TypedArena;
use std::mem;

#[deriving(Show)]
pub struct ShmQueue<'a, T: 'a> {
    prev: Option<&'a mut ShmNode<'a, T>>,
    next: Option<&'a mut ShmNode<'a, T>>,
}

#[deriving(Show)]
pub struct ShmNode<'a, T: 'a> {
    next: Option<&'a mut ShmNode<'a, T>>,
    inner_: T,
}

impl<'a, T> ShmNode<'a, T> {
    pub fn new(inner: T) -> ShmNode<'a, T> {
        ShmNode {
            next: None,
            inner_: inner,
        }
    }
}

impl<'a, T> Deref<T> for ShmNode<'a, T> {
    fn deref(&self) -> &T {
        &self.inner_
    }
}

impl<'a, T> DerefMut<T> for ShmNode<'a, T> {
    fn deref_mut(&mut self) -> &mut T {
        &mut self.inner_
    }
}

// Singly linked list of queues.  Each queue is a pair of (head of queue, reversed tail of queue).
//
// To iterate forward through the list, you select pairs of elements (Head, Tail).
// In particular, you begin with (None, Some(Elem_0)) to start at the beginning or
// (Some(Elem_0), Some(Elem_{n-1})) to start at the end.
//
// Elem_0          Elem_{n-2} ...
// |                ^
// v                |
// Elem_{n-1}----> Elem_1
//
// While iterating, you modify the list by swapping out your Head and Tail for their successors (or
// ancestors, if you are iterating in reverse).  If Head or Tail

impl<'a, T: ::std::fmt::Show> ShmQueue<'a, T> {
    pub fn new() -> ShmQueue<'a, T> {
        ShmQueue {
            prev: None,
            next: None,
        }
    }

    pub fn next(&mut self) -> bool {
        match self.next {
            Some(ref mut next) => mem::swap(&mut self.prev, &mut next.next),
            None => return false
        }
        match self.prev {
            Some(ref mut next) => mem::swap(&mut self.next, &mut next.next),
            None => {
                mem::swap(&mut self.next, &mut self.prev);
                match self.prev {
                    Some(ref mut next) => mem::swap(&mut self.next, &mut next.next),
                    None => return false
                }
            }
        }
        if self.next.is_none() {
            mem::swap(&mut self.next, &mut self.prev);
        }
        true
    }

    pub fn rev(&mut self) {
        if let Some(ref mut next) = self.next {
            mem::swap(&mut self.prev, &mut next.next);
        }
        if self.next.is_none() {
            mem::swap(&mut self.next, &mut self.prev);
        }
    }

    pub fn insert(&mut self, node: &'a mut ShmNode<'a, T>) -> bool {
        enum Action { Next, Reverse };
        let mut action;
        // Only add one element at a time.
        node.next = None;
        match self.next {
            None => match self.prev {
                None => {
                    // Empty queue
                    // Add the node as next.
                    self.next = Some(node);
                    return true;
                },
                Some(_) => {
                    // Don't handle this for the time being.
                    return false;
                },
            },
            Some(ref mut tail) => {
                match self.prev {
                    None => {
                        // No prev, so the next element is the last in the queue.
                        match tail.next {
                            None => {
                                // Only a single element in the queue.  So just
                                // //append it.  This follows the first => last
                                // prepend it.  This follows the first => last
                                // pattern.
                                //tail.next = Some(node);
                                self.prev = Some(node);
                                // However, make sure we keep the new
                                // node at the front of the queue.
                                // action = Action::Next;
                                return true;
                            },
                            Some(/*ref mut head*/_) => {
                                // At least two elements in the queue, head and
                                // tail (tail being reversed in direction from
                                // head): TAIL => HEAD => ...
                                // We want the new node's next pointer to be the
                                // old head pointer, since it is the prior element
                                // in the list: NODE => HEAD => ..., TAIL
                                node.next = tail.next.take();
                                // Now we need TAIL to be the previous element in
                                // the list: TAIL => NODE => HEAD => ...
                                tail.next = Some(node);
                                // Finally, we reverse the list and advance to keep
                                // the new node at the front of the queue.
                                
                                //action = Action::Reverse;
                                return true;
                                
                                //=action = Action::Next;
                                // The only problem is that this will cause us to
                                // forget about the TAIL, so instead we stick it
                                // in prev.  Since we were previously at the start
                                // of the list (otherwise prev would not have been
                                // None), we know we will only hit TAIL when we
                                // reach the end, which is entirely appropriate.
                                // And our next pointer (tail) needs to be node.
                                // So we swap 
                                //self.prev = tail.take();
                                //mem::replace(node.next, Some(
                                //let mut last = mem::replace(node.next, Some(tail));
                                //let mut tail = mem::replace(tail, None);
                                //node.next = mem::re
                                // We know that tail is still the correct
                                // element, but we want to change the head of
                                // tail to start with our new element, so we
                                // have: HEAD => NODE, TAIL => ...
                                //let mut next = mem::replace(head, node);
                                // Now the new node's next pointer needs to point
                                // to the old head pointer, since it is the prior
                                // element in the list.  But this would form a
                                // cycle: HEAD => NODE => HEAD => NODE, ...
                                // 
                                // TAIL => NODE => HEAD => ...
                                // old tail's tail, since it is the prior
                                // element in the list.  But the old tail is
                                // actually the last element in the list, so
                                //return false;
                            }
                        }
                    },
                    Some(/*ref mut head*/_) => {
                        // At least two elements in the queue, head and
                        // tail (tail being reversed in direction from
                        // head): HEAD => ..., TAIL => ...
                        // We want the new node's next pointer to be the
                        // old head pointer, since it is the prior element
                        // in the list: NODE => HEAD => ..., TAIL => ...
                        
                        node.next = self.prev.take();
                        
                        // Now we need TAIL to be the previous element in
                        // the list: TAIL => NODE => HEAD => ..., ...
                        //tail.next = Some(node);
                        self.prev = 
                        
                        //self.prev = mem::replace(self.next, node.next);
                        return false;
                        
                        // Finally, we reverse the list to keep the new node
                        // at the front of the queue, then continue.
                        //action = Action::Next;
                        return true;
                        //=action = Action::Next;
                        // The only problem is that this will cause us to
                        // forget about the TAIL, so instead we stick it
                        // in prev.  Since we were previously at the start
                        // of the list (otherwise prev would not have been
                        // None), we know we will only hit TAIL when we
                        // reach the end, which is entirely appropriate.
                        // And our next pointer (tail) needs to be node.
                        // So we swap 
                        //self.prev = tail.take();
                        //mem::replace(node.next, Some(
                        //let mut last = mem::replace(node.next, Some(tail));
                        //let mut tail = mem::replace(tail, None);
                        //node.next = mem::re
                        // We know that tail is still the correct
                        // element, but we want to change the head of
                        // tail to start with our new element, so we
                        // have: HEAD => NODE, TAIL => ...
                        //let mut next = mem::replace(head, node);
                        // Now the new node's next pointer needs to point
                        // to the old head pointer, since it is the prior
                        // element in the list.  But this would form a
                        // cycle: HEAD => NODE => HEAD => NODE, ...
                        // 
                        // TAIL => NODE => HEAD => ...
                        // old tail's tail, since it is the prior
                        // element in the list.  But the old tail is
                        // actually the last element in the list, so
                        //return false;
                        // TODO
                        //return false;
                    },
                }
            },
        }
        match action {
            Action::Next => {
                //self.next();
                self.rev();
                return true;
            },
            Action::Reverse => {
                //self.rev();
                //self.next();
                //self.rev();
                return true;
            }
        }
    }
}

//mod tests {
    /*use arena::TypedArena;
    use super::{
        ShmNode,
        ShmQueue,
    };*/

    
    fn main() {
        let mut queue = ShmQueue::<u8>::new();

        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(3);
        let mut c = ShmNode::new(2);
        a.next = Some(&mut c);
        queue.next = Some(&mut a);
        queue.prev = Some(&mut b);*/

        // 0

        // 1
        /*let mut a = ShmNode::new(1);
        queue.next = Some(&mut a);*/
        /*let ref mut n = ShmNode::new(1);
        queue.insert(n);*/

        // 2
        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(2);
        a.next = Some(&mut b);
        queue.next = Some(&mut a);*/
        /*let ref mut n = ShmNode::new(1);
        queue.insert(n);
        queue.rev();
        let ref mut n = ShmNode::new(2);
        queue.insert(n);*/

        // 3
        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(3);
        let mut c = ShmNode::new(2);
        b.next = Some(&mut c);
        a.next = Some(&mut b);
        queue.next = Some(&mut a);*/

        // 4
        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(4);
        let mut c = ShmNode::new(2);
        let mut d = ShmNode::new(3);
        c.next = Some(&mut d);
        b.next = Some(&mut c);
        a.next = Some(&mut b);
        queue.next = Some(&mut a);*/

        // 5
        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(5);
        let mut c = ShmNode::new(2);
        let mut d = ShmNode::new(4);
        let mut e = ShmNode::new(3);
        d.next = Some(&mut e);
        c.next = Some(&mut d);
        b.next = Some(&mut c);
        a.next = Some(&mut b);
        queue.next = Some(&mut a);*/

        // 6
        /*let mut a = ShmNode::new(1);
        let mut b = ShmNode::new(6);
        let mut c = ShmNode::new(2);
        let mut d = ShmNode::new(5);
        let mut e = ShmNode::new(3);
        let mut f = ShmNode::new(4);
        e.next = Some(&mut f);
        d.next = Some(&mut e);
        c.next = Some(&mut d);
        b.next = Some(&mut c);
        a.next = Some(&mut b);
        queue.next = Some(&mut a);*/

        // n
        let nodes = TypedArena::new();
        for i in range(0u8, 5)/*.rev()*/ {
            println!("Before inserting {}: {}: {}",
                     i, queue.next.as_ref().map( |p| &***p), queue);
            if !queue.insert(nodes.alloc(ShmNode::new(i))) {
                break;
            }
        }

        println!("Forward:\n{}: {}", queue.next.as_ref().map( |p| &***p), queue);
        for _ in range(0u8, 100) {
            if !queue.next() { break }
            println!("{}: {}", queue.next.as_ref().map( |p| &***p), queue);
            //queue.prev();
            //println!("{}: {}", queue.prev.as_ref().map( |p| &***p), queue);
            //queue.next();
        }
        println!("{}", queue);
        //queue.prev();
        /*println!("Reverse:\n{}", queue);
        while queue.prev() {
            println!("{}", queue);
        }
        println!("{}", queue);*/
    }
//}