#![allow(dead_code)]
use std::cell::Cell;
#[derive(Debug)]
pub struct Node<'a, T: 'a> {
parent: Cell<Option<&'a Node<'a, T>>>,
previous_sibling: Cell<Option<&'a Node<'a, T>>>,
next_sibling: Cell<Option<&'a Node<'a, T>>>,
first_child: Cell<Option<&'a Node<'a, T>>>,
last_child: Cell<Option<&'a Node<'a, T>>>,
pub data: T,
}
fn same_ref<T>(a: &T, b: &T) -> bool {
let a: *const T = a;
let b: *const T = b;
a == b
}
impl<'a, T> Node<'a, T> {
pub fn new(data: T) -> Node<'a, T> {
Node {
parent: Cell::new(None),
first_child: Cell::new(None),
last_child: Cell::new(None),
previous_sibling: Cell::new(None),
next_sibling: Cell::new(None),
data: data,
}
}
pub fn parent(&self) -> Option<&'a Node<'a, T>> {
self.parent.get()
}
pub fn first_child(&self) -> Option<&'a Node<'a, T>> {
self.first_child.get()
}
pub fn last_child(&self) -> Option<&'a Node<'a, T>> {
self.last_child.get()
}
pub fn previous_sibling(&self) -> Option<&'a Node<'a, T>> {
self.previous_sibling.get()
}
pub fn next_sibling(&self) -> Option<&'a Node<'a, T>> {
self.next_sibling.get()
}
pub fn same_node(&self, other: &Node<'a, T>) -> bool {
same_ref(self, other)
}
pub fn ancestors(&'a self) -> Ancestors<'a, T> {
Ancestors(Some(self))
}
pub fn preceding_siblings(&'a self) -> PrecedingSiblings<'a, T> {
PrecedingSiblings(Some(self))
}
pub fn following_siblings(&'a self) -> FollowingSiblings<'a, T> {
FollowingSiblings(Some(self))
}
pub fn children(&'a self) -> Children<'a, T> {
Children(self.first_child.get())
}
pub fn reverse_children(&'a self) -> ReverseChildren<'a, T> {
ReverseChildren(self.last_child.get())
}
pub fn descendants(&'a self) -> Descendants<'a, T> {
Descendants(self.traverse())
}
pub fn traverse(&'a self) -> Traverse<'a, T> {
Traverse {
root: self,
next: Some(NodeEdge::Start(self)),
}
}
pub fn reverse_traverse(&'a self) -> ReverseTraverse<'a, T> {
ReverseTraverse {
root: self,
next: Some(NodeEdge::End(self)),
}
}
pub fn detach(&self) {
let parent = self.parent.take();
let previous_sibling = self.previous_sibling.take();
let next_sibling = self.next_sibling.take();
if let Some(next_sibling) = next_sibling {
next_sibling.previous_sibling.set(previous_sibling);
} else if let Some(parent) = parent {
parent.last_child.set(previous_sibling);
}
if let Some(previous_sibling) = previous_sibling {
previous_sibling.next_sibling.set(next_sibling);
} else if let Some(parent) = parent {
parent.first_child.set(next_sibling);
}
}
pub fn append(&'a self, new_child: &'a Node<'a, T>) {
new_child.detach();
new_child.parent.set(Some(self));
if let Some(last_child) = self.last_child.take() {
new_child.previous_sibling.set(Some(last_child));
debug_assert!(last_child.next_sibling.get().is_none());
last_child.next_sibling.set(Some(new_child));
} else {
debug_assert!(self.first_child.get().is_none());
self.first_child.set(Some(new_child));
}
self.last_child.set(Some(new_child));
}
pub fn prepend(&'a self, new_child: &'a Node<'a, T>) {
new_child.detach();
new_child.parent.set(Some(self));
if let Some(first_child) = self.first_child.take() {
debug_assert!(first_child.previous_sibling.get().is_none());
first_child.previous_sibling.set(Some(new_child));
new_child.next_sibling.set(Some(first_child));
} else {
debug_assert!(self.first_child.get().is_none());
self.last_child.set(Some(new_child));
}
self.first_child.set(Some(new_child));
}
pub fn insert_after(&'a self, new_sibling: &'a Node<'a, T>) {
new_sibling.detach();
new_sibling.parent.set(self.parent.get());
new_sibling.previous_sibling.set(Some(self));
if let Some(next_sibling) = self.next_sibling.take() {
debug_assert!(same_ref(next_sibling.previous_sibling.get().unwrap(), self));
next_sibling.previous_sibling.set(Some(new_sibling));
new_sibling.next_sibling.set(Some(next_sibling));
} else if let Some(parent) = self.parent.get() {
debug_assert!(same_ref(parent.last_child.get().unwrap(), self));
parent.last_child.set(Some(new_sibling));
}
self.next_sibling.set(Some(new_sibling));
}
pub fn insert_before(&'a self, new_sibling: &'a Node<'a, T>) {
new_sibling.detach();
new_sibling.parent.set(self.parent.get());
new_sibling.next_sibling.set(Some(self));
if let Some(previous_sibling) = self.previous_sibling.take() {
new_sibling.previous_sibling.set(Some(previous_sibling));
debug_assert!(same_ref(previous_sibling.next_sibling.get().unwrap(), self));
previous_sibling.next_sibling.set(Some(new_sibling));
} else if let Some(parent) = self.parent.get() {
debug_assert!(same_ref(parent.first_child.get().unwrap(), self));
parent.first_child.set(Some(new_sibling));
}
self.previous_sibling.set(Some(new_sibling));
}
}
macro_rules! axis_iterator {
(#[$attr:meta] $name: ident: $next: ident) => {
#[$attr]
#[derive(Debug)]
pub struct $name<'a, T: 'a>(Option<&'a Node<'a, T>>);
impl<'a, T> Iterator for $name<'a, T> {
type Item = &'a Node<'a, T>;
fn next(&mut self) -> Option<&'a Node<'a, T>> {
match self.0.take() {
Some(node) => {
self.0 = node.$next.get();
Some(node)
}
None => None
}
}
}
}
}
axis_iterator! {
#[doc = "An iterator of references to the ancestors a given node."]
Ancestors: parent
}
axis_iterator! {
#[doc = "An iterator of references to the siblings before a given node."]
PrecedingSiblings: previous_sibling
}
axis_iterator! {
#[doc = "An iterator of references to the siblings after a given node."]
FollowingSiblings: next_sibling
}
axis_iterator! {
#[doc = "An iterator of references to the children of a given node."]
Children: next_sibling
}
axis_iterator! {
#[doc = "An iterator of references to the children of a given node, in reverse order."]
ReverseChildren: previous_sibling
}
#[derive(Debug)]
pub struct Descendants<'a, T: 'a>(Traverse<'a, T>);
impl<'a, T> Iterator for Descendants<'a, T> {
type Item = &'a Node<'a, T>;
fn next(&mut self) -> Option<&'a Node<'a, T>> {
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),
}
macro_rules! traverse_iterator {
(#[$attr:meta] $name: ident: $first_child: ident, $next_sibling: ident) => {
#[$attr]
#[derive(Debug)]
pub struct $name<'a, T: 'a> {
root: &'a Node<'a, T>,
next: Option<NodeEdge<&'a Node<'a, T>>>,
}
impl<'a, T> Iterator for $name<'a, T> {
type Item = NodeEdge<&'a Node<'a, T>>;
fn next(&mut self) -> Option<NodeEdge<&'a Node<'a, T>>> {
match self.next.take() {
Some(item) => {
self.next = match item {
NodeEdge::Start(node) => {
match node.$first_child.get() {
Some(child) => Some(NodeEdge::Start(child)),
None => Some(NodeEdge::End(node))
}
}
NodeEdge::End(node) => {
if node.same_node(self.root) {
None
} else {
match node.$next_sibling.get() {
Some(sibling) => Some(NodeEdge::Start(sibling)),
None => match node.parent.get() {
Some(parent) => Some(NodeEdge::End(parent)),
None => None
}
}
}
}
};
Some(item)
}
None => None
}
}
}
}
}
traverse_iterator! {
#[doc = "An iterator of the start and end edges of a given node and its descendants, in tree order."]
Traverse: first_child, next_sibling
}
traverse_iterator! {
#[doc = "An iterator of the start and end edges of a given node and its descendants, in reverse tree order."]
ReverseTraverse: last_child, previous_sibling
}
#[cfg(test)]
extern crate typed_arena;
#[test]
fn it_works() {
struct DropTracker<'a>(&'a Cell<u32>);
impl<'a> Drop for DropTracker<'a> {
fn drop(&mut self) {
self.0.set(self.0.get() + 1);
}
}
let drop_counter = Cell::new(0);
{
let mut new_counter = 0;
let arena = typed_arena::Arena::new();
let mut new = || {
new_counter += 1;
arena.alloc(Node::new((new_counter, DropTracker(&drop_counter))))
};
let a = new(); a.append(new()); a.append(new()); a.prepend(new()); let b = new(); b.append(a);
a.insert_before(new()); a.insert_before(new()); a.insert_after(new()); a.insert_after(new()); let c = new(); b.append(c);
assert_eq!(drop_counter.get(), 0);
c.previous_sibling.get().unwrap().detach();
assert_eq!(drop_counter.get(), 0);
assert_eq!(b.descendants().map(|node| node.data.0).collect::<Vec<_>>(), [
5, 6, 7, 1, 4, 2, 3, 9, 10
]);
}
assert_eq!(drop_counter.get(), 10);
}