pub use self::error::TreeError;
use slab;
use std::ops::{Index, IndexMut};
use crate::tree::traversal::Traversable;
use crate::types::{Children, DefaultIndexType, IndexType, NodeIndex, Tgf, Values, ValueType};
#[cfg(test)]
mod tests;
pub mod error;
pub trait GenericForest<V, Ix = DefaultIndexType>: Traversable<V, Ix>
where
V: ValueType,
Ix: IndexType,
{
fn insert(&mut self, value: V) -> NodeIndex<Ix>;
fn insert_child(
&mut self,
parent: NodeIndex<Ix>,
value: V,
) -> Result<NodeIndex<Ix>, TreeError<Ix>>;
fn insert_child_at(
&mut self,
parent: NodeIndex<Ix>,
pos: usize,
value: V,
) -> Result<NodeIndex<Ix>, TreeError<Ix>>;
fn remove(&mut self, node: NodeIndex<Ix>) -> Result<V, TreeError<Ix>>;
fn remove_subtree(&mut self, node: NodeIndex<Ix>)
-> Result<Vec<(NodeIndex, V)>, TreeError<Ix>>;
fn set_as_child(
&mut self,
parent: NodeIndex<Ix>,
child: NodeIndex<Ix>,
) -> Result<(), TreeError<Ix>>;
fn set_as_child_at(
&mut self,
parent: NodeIndex<Ix>,
child: NodeIndex<Ix>,
pos: usize,
) -> Result<(), TreeError<Ix>>;
fn remove_as_child(&mut self, node: NodeIndex<Ix>) -> Result<(), TreeError<Ix>>;
}
#[derive(Debug, Clone)]
struct Node<V>
where
V: ValueType,
{
value: V,
child_count: usize,
context: NodeContext,
}
impl<V> Node<V>
where
V: ValueType,
{
fn new(value: V) -> Self {
Node {
value,
child_count: 0,
context: NodeContext::new(),
}
}
}
#[derive(Copy, Clone, Debug)]
struct NodeContext {
parent: Option<NodeIndex>,
first_child: Option<NodeIndex>,
last_child: Option<NodeIndex>,
prev_sibling: Option<NodeIndex>,
next_sibling: Option<NodeIndex>,
}
impl NodeContext {
fn new() -> Self {
NodeContext {
parent: None,
first_child: None,
last_child: None,
prev_sibling: None,
next_sibling: None,
}
}
}
struct ChildIterator<'slf, V>
where
V: ValueType,
{
forest: &'slf Forest<V>,
current: Option<NodeIndex>,
}
impl<'slf, V> ChildIterator<'slf, V>
where
V: 'slf + ValueType,
{
fn new(forest: &'slf Forest<V>, node: NodeIndex) -> Self {
ChildIterator {
forest,
current: forest
.arena
.get(node.index())
.and_then(|n| n.context.first_child),
}
}
}
impl<'slf, V> Iterator for ChildIterator<'slf, V>
where
V: 'slf + ValueType,
{
type Item = NodeIndex;
fn next(&mut self) -> Option<NodeIndex> {
let ret = self.current;
match ret {
Some(n) => {
self.current = self.forest.arena[n.index()].context.next_sibling;
ret
}
None => None,
}
}
}
#[derive(Clone, Debug)]
pub struct Forest<V>
where
V: ValueType,
{
arena: slab::Slab<Node<V>>,
roots: Vec<NodeIndex>,
}
impl<V> Forest<V>
where
V: ValueType,
{
pub fn new(size: usize) -> Self {
Forest {
arena: slab::Slab::with_capacity(size),
roots: Vec::new(),
}
}
pub fn first_child(&self, parent: NodeIndex) -> Option<NodeIndex> {
self.arena
.get(parent.index())
.and_then(|p| p.context.first_child)
}
pub fn last_child(&self, parent: NodeIndex) -> Option<NodeIndex> {
self.arena
.get(parent.index())
.and_then(|p| p.context.last_child)
}
pub fn prev_sibling(&self, node: NodeIndex) -> Option<NodeIndex> {
self.arena
.get(node.index())
.and_then(|n| n.context.prev_sibling)
}
pub fn next_sibling(&self, node: NodeIndex) -> Option<NodeIndex> {
self.arena
.get(node.index())
.and_then(|n| n.context.next_sibling)
}
pub fn roots(&self) -> &Vec<NodeIndex> {
&self.roots
}
}
impl<'slf, V> Children<'slf> for Forest<V>
where
V: 'slf + ValueType,
{
fn children(&'slf self, node: NodeIndex) -> Box<dyn Iterator<Item=NodeIndex> + 'slf> {
Box::new(ChildIterator::new(self, node))
}
}
impl<V> Index<NodeIndex> for Forest<V>
where
V: ValueType,
{
type Output = V;
fn index(&self, index: NodeIndex) -> &V {
&self.arena[index.index()].value
}
}
impl<V> IndexMut<NodeIndex> for Forest<V>
where
V: ValueType,
{
fn index_mut(&mut self, index: NodeIndex) -> &mut V {
&mut self.arena[index.index()].value
}
}
impl<V> Traversable<V> for Forest<V>
where
V: ValueType,
{
fn root(&self, node: NodeIndex) -> Option<NodeIndex> {
if let Some(_n) = self.arena.get(node.index()) {
let mut child = node;
while let Some(parent) = self.arena[child.index()].context.parent {
child = parent;
}
return Some(child);
}
None
}
fn value(&self, node: NodeIndex) -> Option<&V> {
self.arena.get(node.index()).map(|n| &n.value)
}
fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V> {
self.arena.get_mut(node.index()).map(|n| &mut n.value)
}
fn parent(&self, node: NodeIndex) -> Option<NodeIndex> {
self.arena.get(node.index()).and_then(|n| n.context.parent)
}
fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex> {
ChildIterator::new(self, node).nth(pos)
}
fn child_count(&self, node: NodeIndex) -> usize {
self.arena.get(node.index()).map_or(0, |n| n.child_count)
}
fn node_count(&self) -> usize {
self.arena.len()
}
}
impl<'slf, V> Values<'slf, V> for Forest<V>
where
V: 'slf + ValueType,
{
fn values(&'slf self) -> Box<dyn Iterator<Item=(NodeIndex, &'slf V)> + 'slf> {
Box::new(self.arena.iter().map(|(i, v)| (NodeIndex(i), &v.value)))
}
}
impl<V> GenericForest<V> for Forest<V>
where
V: ValueType,
{
fn insert(&mut self, value: V) -> NodeIndex {
let node = NodeIndex(self.arena.insert(Node::new(value)));
self.roots.push(node);
node
}
fn insert_child(&mut self, parent: NodeIndex, value: V) -> Result<NodeIndex, TreeError> {
if !self.arena.contains(parent.index()) {
return Err(TreeError::invalid_node_index("insert_child()", parent));
}
let child = NodeIndex(self.arena.insert(Node::new(value)));
match self.arena[parent.index()].context.last_child {
Some(last) => {
self.arena[last.index()].context.next_sibling = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
self.arena[child.index()].context.prev_sibling = Some(last);
}
None => {
self.arena[parent.index()].context.first_child = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
}
self.arena[child.index()].context.parent = Some(parent);
self.arena[parent.index()].child_count += 1;
Ok(child)
}
fn insert_child_at(
&mut self,
parent: NodeIndex,
pos: usize,
value: V,
) -> Result<NodeIndex, TreeError> {
if !self.arena.contains(parent.index()) {
return Err(TreeError::invalid_node_index("insert_child_at()", parent));
}
let child = NodeIndex(self.arena.insert(Node::new(value)));
let mut prev = None;
let mut next = self.arena[parent.index()].context.first_child;
let mut i = 0;
while i < pos {
match next {
Some(n) => {
prev = next;
next = self.arena[n.index()].context.next_sibling;
i += 1;
}
None => {
break;
}
}
}
match (prev, next) {
(None, Some(n)) => {
self.arena[n.index()].context.prev_sibling = Some(child);
self.arena[parent.index()].context.first_child = Some(child);
}
(Some(p), Some(n)) => {
self.arena[n.index()].context.prev_sibling = Some(child);
self.arena[p.index()].context.next_sibling = Some(child);
}
(Some(p), None) => {
self.arena[p.index()].context.next_sibling = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
(None, None) => {
self.arena[parent.index()].context.first_child = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
}
self.arena[child.index()].context.parent = Some(parent);
self.arena[child.index()].context.prev_sibling = prev;
self.arena[child.index()].context.next_sibling = next;
self.arena[parent.index()].child_count += 1;
Ok(child)
}
fn remove(&mut self, node: NodeIndex) -> Result<V, TreeError> {
if !self.arena.contains(node.index()) {
return Err(TreeError::invalid_node_index("remove()", node));
}
let context = self.arena[node.index()].context;
match context.parent {
Some(parent) => {
match (
context.first_child,
context.last_child,
context.prev_sibling,
context.next_sibling,
) {
(Some(first), Some(last), Some(prev), Some(next)) => {
self.arena[prev.index()].context.next_sibling = Some(first);
self.arena[next.index()].context.prev_sibling = Some(last);
self.arena[first.index()].context.prev_sibling = Some(prev);
self.arena[last.index()].context.next_sibling = Some(next);
}
(Some(first), Some(last), Some(prev), None) => {
self.arena[parent.index()].context.last_child = Some(last);
self.arena[first.index()].context.prev_sibling = Some(prev);
self.arena[prev.index()].context.next_sibling = Some(first);
}
(Some(first), Some(last), None, Some(next)) => {
self.arena[parent.index()].context.first_child = Some(first);
self.arena[last.index()].context.next_sibling = Some(next);
self.arena[next.index()].context.prev_sibling = Some(last);
}
(Some(first), Some(last), None, None) => {
self.arena[parent.index()].context.first_child = Some(first);
self.arena[parent.index()].context.last_child = Some(last);
}
(None, None, Some(prev), Some(next)) => {
self.arena[prev.index()].context.next_sibling = Some(next);
self.arena[next.index()].context.prev_sibling = Some(prev);
}
(None, None, Some(prev), None) => {
self.arena[parent.index()].context.last_child = Some(prev);
self.arena[prev.index()].context.next_sibling = None;
}
(None, None, None, Some(next)) => {
self.arena[parent.index()].context.first_child = Some(next);
self.arena[next.index()].context.prev_sibling = None;
}
(None, None, None, None) => {
self.arena[parent.index()].context.first_child = None;
self.arena[parent.index()].context.last_child = None;
}
_ => panic!("remove(): first and last child indices are incorrect"),
}
let mut child = self.arena[node.index()].context.first_child;
while let Some(c) = child {
child = self.arena[c.index()].context.next_sibling;
self.arena[c.index()].context.parent = Some(parent);
}
self.arena[parent.index()].child_count -= 1;
self.arena[parent.index()].child_count += self.arena[node.index()].child_count;
}
None => {
self.roots.retain(|&r| r != node);
let mut child = self.arena[node.index()].context.first_child;
while let Some(c) = child {
child = self.arena[c.index()].context.next_sibling;
self.arena[c.index()].context.parent = None;
self.arena[c.index()].context.prev_sibling = None;
self.arena[c.index()].context.next_sibling = None;
self.roots.push(c);
}
}
}
Ok(self.arena.remove(node.index()).value)
}
fn remove_subtree(&mut self, node: NodeIndex) -> Result<Vec<(NodeIndex, V)>, TreeError> {
if self.remove_as_child(node).is_err() {
return Err(TreeError::invalid_node_index("remove_subtree()", node));
}
let mut stack = Vec::with_capacity(self.arena[node.index()].child_count + 1);
let mut ret = Vec::with_capacity(stack.capacity());
stack.push(node);
while let Some(parent) = stack.pop() {
let mut child = self.arena[parent.index()].context.last_child;
while let Some(c) = child {
stack.push(c);
child = self.arena[c.index()].context.prev_sibling;
}
ret.push((parent, self.arena.remove(parent.index()).value));
}
self.roots.retain(|&r| r != node);
Ok(ret)
}
fn set_as_child(&mut self, parent: NodeIndex, child: NodeIndex) -> Result<(), TreeError> {
if !self.arena.contains(parent.index()) {
return Err(TreeError::invalid_node_index("set_as_child()", parent));
}
if !self.arena.contains(child.index()) {
return Err(TreeError::invalid_node_index("set_as_child()", child));
}
if self.arena[child.index()].context.parent.is_some() {
return Err(TreeError::expected_root_node("set_as_child()", child));
}
if self.root(parent) == Some(child) {
return Err(TreeError::expected_non_ancestor_node(
"set_as_child()",
parent,
child,
));
}
match self.arena[parent.index()].context.last_child {
Some(last) => {
self.arena[last.index()].context.next_sibling = Some(child);
self.arena[child.index()].context.prev_sibling = Some(last);
self.arena[parent.index()].context.last_child = Some(child);
}
None => {
self.arena[parent.index()].context.first_child = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
}
self.arena[child.index()].context.parent = Some(parent);
self.arena[parent.index()].child_count += 1;
self.roots.retain(|&r| r != child);
Ok(())
}
fn set_as_child_at(
&mut self,
parent: NodeIndex,
child: NodeIndex,
pos: usize,
) -> Result<(), TreeError> {
if !self.arena.contains(parent.index()) {
return Err(TreeError::invalid_node_index("set_as_child_at()", parent));
}
if !self.arena.contains(child.index()) {
return Err(TreeError::invalid_node_index("set_as_child_at()", child));
}
if self.arena[child.index()].context.parent.is_some() {
return Err(TreeError::expected_root_node("set_as_child_at()", child));
}
if self.root(parent) == Some(child) {
return Err(TreeError::expected_non_ancestor_node(
"set_as_child_at()",
parent,
child,
));
}
let mut prev = None;
let mut next = self.arena[parent.index()].context.first_child;
let mut i = 0;
while i < pos {
match next {
Some(n) => {
prev = next;
next = self.arena[n.index()].context.next_sibling;
i += 1;
}
None => {
break;
}
}
}
match (prev, next) {
(None, Some(n)) => {
self.arena[n.index()].context.prev_sibling = Some(child);
self.arena[parent.index()].context.first_child = Some(child);
}
(Some(p), Some(n)) => {
self.arena[n.index()].context.prev_sibling = Some(child);
self.arena[p.index()].context.next_sibling = Some(child);
}
(Some(p), None) => {
self.arena[p.index()].context.next_sibling = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
(None, None) => {
self.arena[parent.index()].context.first_child = Some(child);
self.arena[parent.index()].context.last_child = Some(child);
}
}
self.arena[child.index()].context.parent = Some(parent);
self.arena[child.index()].context.prev_sibling = prev;
self.arena[child.index()].context.next_sibling = next;
self.arena[parent.index()].child_count += 1;
self.roots.retain(|&r| r != child);
Ok(())
}
fn remove_as_child(&mut self, node: NodeIndex) -> Result<(), TreeError> {
if !self.arena.contains(node.index()) {
return Err(TreeError::invalid_node_index("remove_as_child()", node));
}
let context = self.arena[node.index()].context;
if let Some(parent) = context.parent {
match (context.prev_sibling, context.next_sibling) {
(Some(prev), Some(next)) => {
self.arena[prev.index()].context.next_sibling = Some(next);
self.arena[next.index()].context.prev_sibling = Some(prev);
}
(Some(prev), None) => {
self.arena[prev.index()].context.next_sibling = None;
self.arena[parent.index()].context.last_child = Some(prev);
}
(None, Some(next)) => {
self.arena[next.index()].context.prev_sibling = None;
self.arena[parent.index()].context.first_child = Some(next);
}
(None, None) => {
self.arena[parent.index()].context.first_child = None;
self.arena[parent.index()].context.last_child = None;
}
}
self.arena[parent.index()].child_count -= 1;
self.roots.push(node);
}
self.arena[node.index()].context = NodeContext {
parent: None,
first_child: context.first_child,
last_child: context.last_child,
prev_sibling: None,
next_sibling: None,
};
Ok(())
}
}
impl<V> Tgf for Forest<V>
where
V: ValueType,
{
fn to_tgf(&self) -> String {
let mut nodes = String::from("");
let mut edges = String::from("");
let iter = self.arena.iter();
for (index, node) in iter {
nodes.push_str(format!("{}", index).as_str());
nodes.push_str(" [K = ");
nodes.push_str(format!("{}", index).as_str());
nodes.push_str(", V = ");
nodes.push_str(format!("{:?}", node.value).as_str());
nodes.push_str("]\n");
for child in self.children(NodeIndex(index)).enumerate() {
edges.push_str(format!("{}", index).as_str());
edges.push_str(" ");
edges.push_str(format!("{}", child.1.index()).as_str());
edges.push_str(" ");
edges.push_str(format!("{}", child.0).as_str());
edges.push_str("\n");
}
}
nodes.push_str("#\n");
nodes.push_str(edges.as_str());
nodes
}
}