-
-
Save jonalmeida/0fd38ff490a6d4aa5485 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()); | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#![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