|
#![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);*/ |
|
} |
|
//} |