#![cfg_attr(test_threads, feature(scoped))]
#![allow(dead_code)]
use std::mem;
use std::ops::{Index, IndexMut};
use std::ops::{Deref, DerefMut};
use std::collections::LinkedList;
impl<T> Deref for Node<T>{
type Target = T;
fn deref(&self) -> &T{
self.data.as_ref().unwrap()
}
}
impl<T> DerefMut for Node<T>{
fn deref_mut(&mut self) -> &mut T{
self.data.as_mut().unwrap()
}
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(PartialEq, Eq, Copy, Clone, Debug)]
pub struct NodeId {
index: usize,
generation: usize,
}
impl NodeId {
pub fn id(&self) -> usize{
self.index
}
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(Clone)]
pub struct Node<T> {
parent: Option<NodeId>,
previous_sibling: Option<NodeId>,
next_sibling: Option<NodeId>,
first_child: Option<NodeId>,
last_child: Option<NodeId>,
id: NodeId,
data: Option<T>,
}
impl<T> Node<T>{
pub fn id(&self) -> NodeId{
self.id
}
pub fn data(&self) -> &T{
self.data.as_ref().unwrap()
}
pub fn data_mut(&mut self) -> &mut T{
self.data.as_mut().unwrap()
}
}
impl<T> From<Node<T>> for NodeId{
fn from(node: Node<T>) -> NodeId{
node.id
}
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(Clone)]
pub struct Arena<T> {
nodes: Vec<Node<T>>,
free: LinkedList<usize>,
}
impl<T> Arena<T> {
pub fn new() -> Arena<T> {
Arena {
nodes: Vec::new(),
free: LinkedList::new(),
}
}
pub fn new_node(&mut self, data: T) -> NodeIdMut<T>{
let next_free = self.free.pop_front();
let id;
if let Some(idx) = next_free{
id = NodeId {
index: idx,
generation: self.nodes[idx].id.generation + 1
};
mem::forget(mem::replace(&mut self.nodes[idx], Node {
parent: None,
first_child: None,
last_child: None,
previous_sibling: None,
next_sibling: None,
data: Some(data),
id: id,
}));
}else{
let next_index = self.nodes.len();
id = NodeId {
index: next_index,
generation: 0
};
self.nodes.push(Node {
parent: None,
first_child: None,
last_child: None,
previous_sibling: None,
next_sibling: None,
data: Some(data),
id: id,
});
}
NodeIdMut{
id,
arena: self
}
}
pub fn get(&self, id: NodeId) -> NodeIdRef<T>{
NodeIdRef{
arena: self,
id,
}
}
pub fn get_mut(&mut self, id: NodeId) -> NodeIdMut<T>{
NodeIdMut{
arena: self,
id,
}
}
pub fn contains(&self, id: NodeId) -> bool{
self.nodes[id.index].id.generation == id.generation &&
self.nodes[id.index].data.is_some()
}
pub fn remove<N: Into<NodeId>>(&mut self, id: N) -> Result<T,()>{
let id = id.into();
if self.contains(id){
if self.nodes[id.index].parent().is_some(){
for c in id.children(self).collect::<Vec<_>>(){
id.insert_after(c, self);
}
}else{
for c in id.children(self).collect::<Vec<_>>(){
c.detach(self);
}
}
id.detach(self);
let ret = mem::replace(&mut self.nodes[id.index].data, None).unwrap();
self.free.push_back(id.index);
Ok(ret)
}else{
Err(())
}
}
pub fn remove_tree<N: Into<NodeId>>(&mut self, id: N) -> Result<(),()>{
let id = id.into();
if self.contains(id){
if self.nodes[id.index].first_child().is_some(){
for c in id.children(self).collect::<Vec<_>>(){
self.remove_tree(c)?;
}
}else{
self.remove(id)?;
}
Ok(())
}else{
Err(())
}
}
pub fn all_nodes<'a>(&'a self) -> Box<dyn Iterator<Item=&'a Node<T>> + 'a>{
Box::new(self.nodes.iter().filter(|node| node.data.is_some()))
}
pub fn all_nodes_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item=&'a mut Node<T>> + 'a>{
Box::new(self.nodes.iter_mut().filter(|node| node.data.is_some()))
}
pub fn into_vec(self) -> Vec<Node<T>>{
self.nodes.into_iter().filter(|n| n.data.is_some()).collect()
}
}
pub struct NodeIdMut<'a, T: 'a>{
id: NodeId,
arena: &'a mut Arena<T>
}
impl<'a, T: 'a> NodeIdMut<'a, T>{
pub fn id(&self) -> NodeId{
self.id
}
pub fn append<N: Into<NodeId>>(self, new_node: N) -> NodeIdMut<'a, T>{
let new_node = new_node.into();
self.id.append(new_node, self.arena)
}
pub fn append_new(self, new_data: T) -> NodeIdMut<'a, T>{
self.id.append_new(new_data, self.arena)
}
pub fn prepend<N: Into<NodeId>>(self, new_node: N) -> NodeIdMut<'a, T>{
let new_node = new_node.into();
self.id.prepend(new_node, self.arena)
}
pub fn prepend_new(self, new_data: T) -> NodeIdMut<'a, T>{
self.id.append_new(new_data, self.arena)
}
pub fn insert_after<N: Into<NodeId>>(self, new_node: N) -> NodeIdMut<'a, T>{
let new_node = new_node.into();
self.id.insert_after(new_node, self.arena)
}
pub fn insert_after_new(self, new_data: T) -> NodeIdMut<'a, T>{
self.id.insert_after_new(new_data, self.arena)
}
pub fn insert_before<N: Into<NodeId>>(self, new_node: N) -> NodeIdMut<'a, T>{
let new_node = new_node.into();
self.id.insert_before(new_node, self.arena)
}
pub fn insert_before_new(self, new_data: T) -> NodeIdMut<'a, T>{
self.id.insert_before_new(new_data, self.arena)
}
pub fn ancestors(self) -> Ancestors<'a,T> {
Ancestors {
arena: self.arena,
node: Some(self.id),
}
}
pub fn preceding_siblings(self) -> PrecedingSiblings<'a,T> {
PrecedingSiblings {
arena: self.arena,
node: Some(self.id),
}
}
pub fn following_siblings(self) -> FollowingSiblings<'a,T> {
FollowingSiblings {
arena: self.arena,
node: Some(self.id),
}
}
pub fn children(self) -> Children<'a,T> {
Children {
arena: self.arena,
node: self.arena[self.id].first_child,
}
}
pub fn reverse_children(self) -> ReverseChildren<'a,T> {
ReverseChildren {
arena: self.arena,
node: self.arena[self.id].last_child,
}
}
pub fn descendants(self) -> Descendants<'a,T> {
Descendants(self.traverse())
}
pub fn traverse(self) -> Traverse<'a,T> {
Traverse {
arena: self.arena,
root: self.id,
next: Some(NodeEdge::Start(self.id)),
}
}
pub fn reverse_traverse(self) -> ReverseTraverse<'a,T> {
ReverseTraverse {
arena: self.arena,
root: self.id,
next: Some(NodeEdge::End(self.id)),
}
}
}
impl<'a,T> From<NodeIdMut<'a,T>> for NodeId{
fn from(node: NodeIdMut<'a,T>) -> NodeId{
node.id()
}
}
impl<'a, T: 'a> Deref for NodeIdMut<'a,T>{
type Target = Node<T>;
fn deref(&self) -> &Node<T>{
&self.arena[self.id]
}
}
impl<'a, T: 'a> DerefMut for NodeIdMut<'a,T>{
fn deref_mut(&mut self) -> &mut Node<T>{
&mut self.arena[self.id]
}
}
pub struct NodeIdRef<'a, T: 'a>{
id: NodeId,
arena: &'a Arena<T>
}
impl<'a, T: 'a> NodeIdRef<'a, T>{
pub fn id(&self) -> NodeId{
self.id
}
pub fn ancestors(&self) -> Ancestors<T> {
Ancestors {
arena: self.arena,
node: Some(self.id),
}
}
pub fn preceding_siblings(&self) -> PrecedingSiblings<T> {
PrecedingSiblings {
arena: self.arena,
node: Some(self.id),
}
}
pub fn following_siblings(&self) -> FollowingSiblings<T> {
FollowingSiblings {
arena: self.arena,
node: Some(self.id),
}
}
pub fn children(&self) -> Children<T> {
Children {
arena: self.arena,
node: self.arena[self.id].first_child,
}
}
pub fn reverse_children(&self) -> ReverseChildren<T> {
ReverseChildren {
arena: self.arena,
node: self.arena[self.id].last_child,
}
}
pub fn descendants(&self) -> Descendants<T> {
Descendants(self.traverse())
}
pub fn traverse(&self) -> Traverse<T> {
Traverse {
arena: self.arena,
root: self.id,
next: Some(NodeEdge::Start(self.id)),
}
}
pub fn reverse_traverse(&self) -> ReverseTraverse<T> {
ReverseTraverse {
arena: self.arena,
root: self.id,
next: Some(NodeEdge::End(self.id)),
}
}
}
impl<'a,T> From<NodeIdRef<'a,T>> for NodeId{
fn from(node: NodeIdRef<'a,T>) -> NodeId{
node.id
}
}
impl<'a, T: 'a> Deref for NodeIdRef<'a,T>{
type Target = Node<T>;
fn deref(&self) -> &Node<T>{
&self.arena[self.id]
}
}
trait GetPairMut<T> {
fn get_pair_mut(&mut self, a: usize, b: usize, same_index_error_message: &'static str)
-> (&mut T, &mut T);
}
impl<T> GetPairMut<T> for Vec<T> {
fn get_pair_mut(&mut self, a: usize, b: usize, same_index_error_message: &'static str)
-> (&mut T, &mut T) {
if a == b {
panic!(same_index_error_message)
}
unsafe {
let self2 = mem::transmute_copy::<&mut Vec<T>, &mut Vec<T>>(&self);
(&mut self[a], &mut self2[b])
}
}
}
impl<T> Index<NodeId> for Arena<T> {
type Output = Node<T>;
fn index(&self, node: NodeId) -> &Node<T> {
assert!(self.contains(node));
&self.nodes[node.index]
}
}
impl<T> IndexMut<NodeId> for Arena<T> {
fn index_mut(&mut self, node: NodeId) -> &mut Node<T> {
assert!(self.contains(node));
&mut self.nodes[node.index]
}
}
impl<T> Node<T> {
pub fn parent(&self) -> Option<NodeId> { self.parent }
pub fn first_child(&self) -> Option<NodeId> { self.first_child }
pub fn last_child(&self) -> Option<NodeId> { self.last_child }
pub fn previous_sibling(&self) -> Option<NodeId> { self.previous_sibling }
pub fn next_sibling(&self) -> Option<NodeId> { self.next_sibling }
}
impl NodeId {
pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<T> {
Ancestors {
arena: arena,
node: Some(self),
}
}
pub fn preceding_siblings<T>(self, arena: &Arena<T>) -> PrecedingSiblings<T> {
PrecedingSiblings {
arena: arena,
node: Some(self),
}
}
pub fn following_siblings<T>(self, arena: &Arena<T>) -> FollowingSiblings<T> {
FollowingSiblings {
arena: arena,
node: Some(self),
}
}
pub fn children<T>(self, arena: &Arena<T>) -> Children<T> {
Children {
arena: arena,
node: arena[self].first_child,
}
}
pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<T> {
ReverseChildren {
arena: arena,
node: arena[self].last_child,
}
}
pub fn descendants<T>(self, arena: &Arena<T>) -> Descendants<T> {
Descendants(self.traverse(arena))
}
pub fn traverse<T>(self, arena: &Arena<T>) -> Traverse<T> {
Traverse {
arena: arena,
root: self,
next: Some(NodeEdge::Start(self)),
}
}
pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<T> {
ReverseTraverse {
arena: arena,
root: self,
next: Some(NodeEdge::End(self)),
}
}
pub fn detach<T>(self, arena: &mut Arena<T>) -> NodeIdMut<T> {
let (parent, previous_sibling, next_sibling) = {
let node = &mut arena[self];
(node.parent.take(), node.previous_sibling.take(), node.next_sibling.take())
};
if let Some(next_sibling) = next_sibling {
arena[next_sibling].previous_sibling = previous_sibling;
} else if let Some(parent) = parent {
arena[parent].last_child = previous_sibling;
}
if let Some(previous_sibling) = previous_sibling {
arena[previous_sibling].next_sibling = next_sibling;
} else if let Some(parent) = parent {
arena[parent].first_child = next_sibling;
}
NodeIdMut{
id: self,
arena
}
}
pub fn append<T>(self, new_child: NodeId, arena: &mut Arena<T>) -> NodeIdMut<T> {
new_child.detach(arena);
let last_child_opt;
{
let (self_borrow, new_child_borrow) = arena.nodes.get_pair_mut(
self.index, new_child.index, "Can not append a node to itself");
new_child_borrow.parent = Some(self);
last_child_opt = mem::replace(&mut self_borrow.last_child, Some(new_child));
if let Some(last_child) = last_child_opt {
new_child_borrow.previous_sibling = Some(last_child);
} else {
debug_assert!(self_borrow.first_child.is_none());
self_borrow.first_child = Some(new_child);
}
}
if let Some(last_child) = last_child_opt {
debug_assert!(arena[last_child].next_sibling.is_none());
arena[last_child].next_sibling = Some(new_child);
}
NodeIdMut{
id: new_child,
arena
}
}
pub fn append_new<T>(self, new_data: T, arena: &mut Arena<T>) -> NodeIdMut<T> {
let new_node = arena.new_node(new_data).id();
self.append(new_node, arena)
}
pub fn prepend<T>(self, new_child: NodeId, arena: &mut Arena<T>) -> NodeIdMut<T> {
new_child.detach(arena);
let first_child_opt;
{
let (self_borrow, new_child_borrow) = arena.nodes.get_pair_mut(
self.index, new_child.index, "Can not prepend a node to itself");
new_child_borrow.parent = Some(self);
first_child_opt = mem::replace(&mut self_borrow.first_child, Some(new_child));
if let Some(first_child) = first_child_opt {
new_child_borrow.next_sibling = Some(first_child);
} else {
debug_assert!(&self_borrow.first_child.is_none());
self_borrow.last_child = Some(new_child);
}
}
if let Some(first_child) = first_child_opt {
debug_assert!(arena[first_child].previous_sibling.is_none());
arena[first_child].previous_sibling = Some(new_child);
}
NodeIdMut{
id: new_child,
arena
}
}
pub fn prepend_new<T>(self, new_data: T, arena: &mut Arena<T>) -> NodeIdMut<T> {
let new_node = arena.new_node(new_data).id();
self.prepend(new_node, arena)
}
pub fn insert_after<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) -> NodeIdMut<T> {
new_sibling.detach(arena);
let next_sibling_opt;
let parent_opt;
{
let (self_borrow, new_sibling_borrow) = arena.nodes.get_pair_mut(
self.index, new_sibling.index, "Can not insert a node after itself");
parent_opt = self_borrow.parent;
new_sibling_borrow.parent = parent_opt;
new_sibling_borrow.previous_sibling = Some(self);
next_sibling_opt = mem::replace(&mut self_borrow.next_sibling, Some(new_sibling));
if let Some(next_sibling) = next_sibling_opt {
new_sibling_borrow.next_sibling = Some(next_sibling);
}
}
if let Some(next_sibling) = next_sibling_opt {
debug_assert!(arena[next_sibling].previous_sibling.unwrap() == self);
arena[next_sibling].previous_sibling = Some(new_sibling);
} else if let Some(parent) = parent_opt {
debug_assert!(arena[parent].last_child.unwrap() == self);
arena[parent].last_child = Some(new_sibling);
}
NodeIdMut{
id: new_sibling,
arena
}
}
pub fn insert_after_new<T>(self, new_data: T, arena: &mut Arena<T>) -> NodeIdMut<T> {
let new_node = arena.new_node(new_data).id();
self.insert_after(new_node, arena)
}
pub fn insert_before<T>(self, new_sibling: NodeId, arena: &mut Arena<T>) -> NodeIdMut<T> {
new_sibling.detach(arena);
let previous_sibling_opt;
let parent_opt;
{
let (self_borrow, new_sibling_borrow) = arena.nodes.get_pair_mut(
self.index, new_sibling.index, "Can not insert a node before itself");
parent_opt = self_borrow.parent;
new_sibling_borrow.parent = parent_opt;
new_sibling_borrow.next_sibling = Some(self);
previous_sibling_opt = mem::replace(&mut self_borrow.previous_sibling, Some(new_sibling));
if let Some(previous_sibling) = previous_sibling_opt {
new_sibling_borrow.previous_sibling = Some(previous_sibling);
}
}
if let Some(previous_sibling) = previous_sibling_opt {
debug_assert!(arena[previous_sibling].next_sibling.unwrap() == self);
arena[previous_sibling].next_sibling = Some(new_sibling);
} else if let Some(parent) = parent_opt {
debug_assert!(arena[parent].first_child.unwrap() == self);
arena[parent].first_child = Some(new_sibling);
}
NodeIdMut{
id: new_sibling,
arena
}
}
pub fn insert_before_new<T>(self, new_data: T, arena: &mut Arena<T>) -> NodeIdMut<T> {
let new_node = arena.new_node(new_data).id();
self.insert_before(new_node, arena)
}
}
macro_rules! impl_node_iterator {
($name: ident, $next: expr) => {
impl<'a, T> Iterator for $name<'a, T> {
type Item = NodeId;
fn next(&mut self) -> Option<NodeId> {
match self.node.take() {
Some(node) => {
self.node = $next(&self.arena[node]);
Some(node)
}
None => None
}
}
}
}
}
pub struct Ancestors<'a, T: 'a> {
arena: &'a Arena<T>,
node: Option<NodeId>,
}
impl_node_iterator!(Ancestors, |node: &Node<T>| node.parent);
pub struct PrecedingSiblings<'a, T: 'a> {
arena: &'a Arena<T>,
node: Option<NodeId>,
}
impl_node_iterator!(PrecedingSiblings, |node: &Node<T>| node.previous_sibling);
pub struct FollowingSiblings<'a, T: 'a> {
arena: &'a Arena<T>,
node: Option<NodeId>,
}
impl_node_iterator!(FollowingSiblings, |node: &Node<T>| node.next_sibling);
pub struct Children<'a, T: 'a> {
arena: &'a Arena<T>,
node: Option<NodeId>,
}
impl_node_iterator!(Children, |node: &Node<T>| node.next_sibling);
pub struct ReverseChildren<'a, T: 'a> {
arena: &'a Arena<T>,
node: Option<NodeId>,
}
impl_node_iterator!(ReverseChildren, |node: &Node<T>| node.previous_sibling);
pub struct Descendants<'a, T: 'a>(Traverse<'a, T>);
impl<'a, T> Iterator for Descendants<'a, T> {
type Item = NodeId;
fn next(&mut self) -> Option<NodeId> {
loop {
match self.0.next() {
Some(NodeEdge::Start(node)) => return Some(node),
Some(NodeEdge::End(_)) => {}
None => return None
}
}
}
}
#[derive(Debug, Clone)]
pub enum NodeEdge<T> {
Start(T),
End(T),
}
pub struct Traverse<'a, T: 'a> {
arena: &'a Arena<T>,
root: NodeId,
next: Option<NodeEdge<NodeId>>,
}
impl<'a, T> Iterator for Traverse<'a, T> {
type Item = NodeEdge<NodeId>;
fn next(&mut self) -> Option<NodeEdge<NodeId>> {
match self.next.take() {
Some(item) => {
self.next = match item {
NodeEdge::Start(node) => {
match self.arena[node].first_child {
Some(first_child) => Some(NodeEdge::Start(first_child)),
None => Some(NodeEdge::End(node.clone()))
}
}
NodeEdge::End(node) => {
if node == self.root {
None
} else {
match self.arena[node].next_sibling {
Some(next_sibling) => Some(NodeEdge::Start(next_sibling)),
None => match self.arena[node].parent {
Some(parent) => Some(NodeEdge::End(parent)),
None => None
}
}
}
}
};
Some(item)
}
None => None
}
}
}
pub struct ReverseTraverse<'a, T: 'a> {
arena: &'a Arena<T>,
root: NodeId,
next: Option<NodeEdge<NodeId>>,
}
impl<'a, T> Iterator for ReverseTraverse<'a, T> {
type Item = NodeEdge<NodeId>;
fn next(&mut self) -> Option<NodeEdge<NodeId>> {
match self.next.take() {
Some(item) => {
self.next = match item {
NodeEdge::End(node) => {
match self.arena[node].last_child {
Some(last_child) => Some(NodeEdge::End(last_child)),
None => Some(NodeEdge::Start(node.clone()))
}
}
NodeEdge::Start(node) => {
if node == self.root {
None
} else {
match self.arena[node].previous_sibling {
Some(previous_sibling) => Some(NodeEdge::End(previous_sibling)),
None => match self.arena[node].parent {
Some(parent) => Some(NodeEdge::Start(parent)),
None => None
}
}
}
}
};
Some(item)
}
None => None
}
}
}
#[cfg(test_threads)]
#[test]
fn threaded() {
use std::thread;
let arena = &mut Arena::new();
let root = arena.new_node("".to_string());;
root.append(arena.new_node("b".to_string()), arena);
root.prepend(arena.new_node("a".to_string()), arena);
root.append(arena.new_node("c".to_string()), arena);
macro_rules! collect_data {
($iter: expr) => { $iter.map(|node| &*arena[node].data).collect::<Vec<&str>>() }
}
let thread_1 = thread::scoped(|| collect_data!(root.children(arena)));
let thread_2 = thread::scoped(|| collect_data!(root.reverse_children(arena)));
assert_eq!(thread_1.join(), ["a", "b", "c"]);
assert_eq!(thread_2.join(), ["c", "b", "a"]);
}