Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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());
}
#![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);*/
}
//}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.