use failure::{bail, Fail, Fallible};
#[cfg(feature = "par_iter")]
use rayon::prelude::*;
use std::{
fmt, mem,
num::NonZeroUsize,
ops::{Index, IndexMut},
};
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug, Hash)]
#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
pub struct NodeId {
index1: NonZeroUsize,
}
impl fmt::Display for NodeId {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.index1)
}
}
#[derive(Debug, Fail)]
pub enum NodeError {
#[fail(display = "Can not append a node to itself")]
AppendSelf,
#[fail(display = "Can not prepend a node to itself")]
PrependSelf,
#[fail(display = "Can not insert a node before itself")]
InsertBeforeSelf,
#[fail(display = "Can not insert a node after itself")]
InsertAfterSelf,
#[fail(display = "First child is already set")]
FirstChildAlreadySet,
#[fail(display = "Previous sibling is already set")]
PreviousSiblingAlreadySet,
#[fail(display = "Next sibling is already set")]
NextSiblingAlreadySet,
#[fail(display = "Previous sibling not equal current node")]
PreviousSiblingNotSelf,
#[fail(display = "Next sibling not equal current node")]
NextSiblingNotSelf,
#[fail(display = "First child not equal current node")]
FirstChildNotSelf,
#[fail(display = "Last child not equal current node")]
LastChildNotSelf,
#[fail(display = "Previous sibling is not set")]
PreviousSiblingNotSet,
#[fail(display = "Next sibling is not set")]
NextSiblingNotSet,
#[fail(display = "First child is not set")]
FirstChildNotSet,
#[fail(display = "Last child is not set")]
LastChildNotSet,
}
#[derive(PartialEq, Clone, Debug)]
#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
#[cfg_attr(feature = "derive-eq", derive(Eq))]
pub struct Node<T> {
parent: Option<NodeId>,
previous_sibling: Option<NodeId>,
next_sibling: Option<NodeId>,
first_child: Option<NodeId>,
last_child: Option<NodeId>,
removed: bool,
pub data: T,
}
impl<T> fmt::Display for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if let Some(parent) = self.parent {
write!(f, "parent: {}; ", parent)?;
} else {
write!(f, "no parent; ")?;
}
if let Some(previous_sibling) = self.previous_sibling {
write!(f, "previous sibling: {}; ", previous_sibling)?;
} else {
write!(f, "no previous sibling; ")?;
}
if let Some(next_sibling) = self.next_sibling {
write!(f, "next sibling: {}; ", next_sibling)?;
} else {
write!(f, "no next sibling; ")?;
}
if let Some(first_child) = self.first_child {
write!(f, "first child: {}; ", first_child)?;
} else {
write!(f, "no first child; ")?;
}
if let Some(last_child) = self.last_child {
write!(f, "last child: {}; ", last_child)?;
} else {
write!(f, "no last child; ")?;
}
Ok(())
}
}
#[derive(PartialEq, Clone, Debug)]
#[cfg_attr(feature = "deser", derive(Deserialize, Serialize))]
#[cfg_attr(feature = "derive-eq", derive(Eq))]
pub struct Arena<T> {
nodes: Vec<Node<T>>,
}
impl<T> Arena<T> {
pub fn new() -> Arena<T> {
Arena { nodes: Vec::new() }
}
pub fn new_node(&mut self, data: T) -> NodeId {
let next_index1 = NonZeroUsize::new(self.nodes.len().wrapping_add(1))
.expect("Too many nodes in the arena");
self.nodes.push(Node {
parent: None,
first_child: None,
last_child: None,
previous_sibling: None,
next_sibling: None,
removed: false,
data,
});
NodeId::from_non_zero_usize(next_index1)
}
pub fn count(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.count() == 0
}
pub fn get(&self, id: NodeId) -> Option<&Node<T>> {
self.nodes.get(id.index0())
}
pub fn get_mut(&mut self, id: NodeId) -> Option<&mut Node<T>> {
self.nodes.get_mut(id.index0())
}
pub fn iter(&self) -> std::slice::Iter<Node<T>> {
self.nodes.iter()
}
}
#[cfg(feature = "par_iter")]
impl<T: Sync> Arena<T> {
pub fn par_iter(&self) -> rayon::slice::Iter<Node<T>> {
self.nodes.par_iter()
}
}
trait GetPairMut<T> {
fn get_tuple_mut(&mut self, a: usize, b: usize)
-> Option<(&mut T, &mut T)>;
}
impl<T> GetPairMut<T> for Vec<T> {
fn get_tuple_mut(
&mut self,
a: usize,
b: usize,
) -> Option<(&mut T, &mut T)> {
if a == b {
return None;
}
let (xs, ys) = self.split_at_mut(std::cmp::max(a, b));
if a < b {
Some((&mut xs[a], &mut ys[0]))
} else {
Some((&mut ys[0], &mut xs[b]))
}
}
}
impl<T> Index<NodeId> for Arena<T> {
type Output = Node<T>;
fn index(&self, node: NodeId) -> &Node<T> {
&self.nodes[node.index0()]
}
}
impl<T> IndexMut<NodeId> for Arena<T> {
fn index_mut(&mut self, node: NodeId) -> &mut Node<T> {
&mut self.nodes[node.index0()]
}
}
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
}
pub fn is_removed(&self) -> bool {
self.removed
}
}
impl NodeId {
fn index0(self) -> usize {
self.index1.get() - 1
}
pub fn new(index0: usize) -> Self {
let index1 = NonZeroUsize::new(index0.wrapping_add(1))
.expect("Attempt to create `NodeId` from `usize::max_value()`");
NodeId { index1 }
}
pub fn from_non_zero_usize(index1: NonZeroUsize) -> Self {
NodeId { index1 }
}
pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<T> {
Ancestors {
arena,
node: Some(self),
}
}
pub fn preceding_siblings<T>(
self,
arena: &Arena<T>,
) -> PrecedingSiblings<T> {
PrecedingSiblings {
arena,
node: Some(self),
}
}
pub fn following_siblings<T>(
self,
arena: &Arena<T>,
) -> FollowingSiblings<T> {
FollowingSiblings {
arena,
node: Some(self),
}
}
pub fn children<T>(self, arena: &Arena<T>) -> Children<T> {
Children {
arena,
node: arena[self].first_child,
}
}
pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<T> {
ReverseChildren {
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,
root: self,
next: Some(NodeEdge::Start(self)),
}
}
pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<T> {
ReverseTraverse {
arena,
root: self,
next: Some(NodeEdge::End(self)),
}
}
pub fn detach<T>(self, arena: &mut Arena<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;
}
}
pub fn append<T>(
self,
new_child: NodeId,
arena: &mut Arena<T>,
) -> Fallible<()> {
new_child.detach(arena);
let last_child_opt;
{
if let Some((self_borrow, new_child_borrow)) =
arena.nodes.get_tuple_mut(self.index0(), new_child.index0())
{
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 {
if self_borrow.first_child.is_some() {
bail!(NodeError::FirstChildAlreadySet);
}
self_borrow.first_child = Some(new_child);
}
} else {
bail!(NodeError::AppendSelf);
}
}
if let Some(last_child) = last_child_opt {
if arena[last_child].next_sibling.is_some() {
bail!(NodeError::NextSiblingAlreadySet);
}
arena[last_child].next_sibling = Some(new_child);
}
Ok(())
}
pub fn prepend<T>(
self,
new_child: NodeId,
arena: &mut Arena<T>,
) -> Fallible<()> {
new_child.detach(arena);
let first_child_opt;
{
if let Some((self_borrow, new_child_borrow)) =
arena.nodes.get_tuple_mut(self.index0(), new_child.index0())
{
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 {
self_borrow.last_child = Some(new_child);
if self_borrow.first_child.is_some() {
bail!(NodeError::FirstChildAlreadySet);
}
}
} else {
bail!(NodeError::PrependSelf);
}
}
if let Some(first_child) = first_child_opt {
if arena[first_child].previous_sibling.is_some() {
bail!(NodeError::PreviousSiblingAlreadySet);
}
arena[first_child].previous_sibling = Some(new_child);
}
Ok(())
}
pub fn insert_after<T>(
self,
new_sibling: NodeId,
arena: &mut Arena<T>,
) -> Fallible<()> {
new_sibling.detach(arena);
let next_sibling_opt;
let parent_opt;
{
if let Some((self_borrow, new_sibling_borrow)) =
arena.nodes.get_tuple_mut(self.index0(), new_sibling.index0())
{
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);
}
} else {
bail!(NodeError::InsertAfterSelf);
}
}
if let Some(next_sibling) = next_sibling_opt {
if let Some(previous_sibling) = arena[next_sibling].previous_sibling
{
if previous_sibling != self {
bail!(NodeError::PreviousSiblingNotSelf);
}
} else {
bail!(NodeError::PreviousSiblingNotSet);
}
arena[next_sibling].previous_sibling = Some(new_sibling);
} else if let Some(parent) = parent_opt {
if let Some(last_child) = arena[parent].last_child {
if last_child != self {
bail!(NodeError::LastChildNotSelf);
}
} else {
bail!(NodeError::LastChildNotSet);
}
arena[parent].last_child = Some(new_sibling);
}
Ok(())
}
pub fn insert_before<T>(
self,
new_sibling: NodeId,
arena: &mut Arena<T>,
) -> Fallible<()> {
new_sibling.detach(arena);
let previous_sibling_opt;
let parent_opt;
{
if let Some((self_borrow, new_sibling_borrow)) =
arena.nodes.get_tuple_mut(self.index0(), new_sibling.index0())
{
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);
}
} else {
bail!(NodeError::InsertBeforeSelf);
}
}
if let Some(previous_sibling) = previous_sibling_opt {
if let Some(next_sibling) = arena[previous_sibling].next_sibling {
if next_sibling != self {
bail!(NodeError::NextSiblingNotSelf);
}
} else {
bail!(NodeError::NextSiblingNotSet);
}
arena[previous_sibling].next_sibling = Some(new_sibling);
} else if let Some(parent) = parent_opt {
if let Some(first_child) = arena[parent].first_child {
if first_child != self {
bail!(NodeError::FirstChildNotSelf);
}
} else {
bail!(NodeError::FirstChildNotSet);
}
arena[parent].first_child = Some(new_sibling);
}
Ok(())
}
pub fn remove<T>(self, arena: &mut Arena<T>) -> Fallible<()> {
for child in self.children(arena).collect::<Vec<_>>() {
arena[child].parent = arena[self].parent
}
let (previous_sibling, next_sibling, first_child, last_child) = {
let node = &mut arena[self];
(
node.previous_sibling.take(),
node.next_sibling.take(),
node.first_child.take(),
node.last_child.take(),
)
};
if let (Some(previous_sibling), Some(first_child)) =
(previous_sibling, first_child)
{
arena[previous_sibling].next_sibling = Some(first_child);
arena[first_child].previous_sibling = Some(previous_sibling);
}
if let (Some(next_sibling), Some(last_child)) =
(next_sibling, last_child)
{
arena[next_sibling].previous_sibling = Some(last_child);
arena[last_child].next_sibling = Some(next_sibling);
}
self.detach(arena);
{
let mut_self = &mut arena[self];
mut_self.first_child = None;
mut_self.last_child = None;
mut_self.removed = true;
}
Ok(())
}
}
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)),
},
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)),
},
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,
}
}
}