#![deny(missing_docs)]
pub enum BuildError<T> {
Incomplete(Sapling<T>),
MultipleRoots(Sapling<T>),
}
impl<T> std::fmt::Debug for BuildError<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
Self::Incomplete(_) => write!(f, "Incomplete"),
Self::MultipleRoots(_) => write!(f, "MultipleRoots"),
}
}
}
impl<T> std::fmt::Display for BuildError<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
Self::Incomplete(_) => write!(f, "Incomplete tree structure"),
Self::MultipleRoots(_) => write!(f, "Multiple roots in tree"),
}
}
}
impl<T> std::error::Error for BuildError<T> {}
#[derive(Debug, PartialEq, Copy, Clone)]
pub enum ValidationError {
Empty,
MultipleRoots,
IllegalStructure,
}
impl std::fmt::Display for ValidationError {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
Self::Empty => write!(f, "Empty vertex slice"),
Self::MultipleRoots => write!(f, "Multiple roots in vertex slice"),
Self::IllegalStructure => write!(f, "Vertex with invalid length"),
}
}
}
impl std::error::Error for ValidationError {}
#[derive(Debug, Clone, Copy)]
pub struct Vertex<T> {
len: usize,
data: T,
}
impl<T> Vertex<T> {
pub fn new(data: T, len: usize) -> Self {
Vertex { data, len }
}
}
#[derive(Debug)]
pub struct Sapling<T> {
path: Vec<usize>,
verts: Vec<Vertex<T>>,
}
impl<T> Sapling<T> {
pub fn new() -> Self {
Sapling {
path: Vec::new(),
verts: Vec::new(),
}
}
pub fn with_capacity(len: usize, depth: Option<usize>) -> Self {
Sapling {
path: Vec::with_capacity(depth.unwrap_or(0)),
verts: Vec::with_capacity(len),
}
}
pub fn push(&mut self, data: T) {
self.path.push(self.verts.len());
self.verts.push(Vertex { len: 0, data });
}
pub fn push_leaf(&mut self, data: T) {
self.verts.push(Vertex { len: 0, data });
}
pub fn push_tree(&mut self, tree: Tree<T>) -> Sapling<T> {
let mut sap = tree.into_sapling();
self.verts.append(&mut sap.verts);
sap.clear();
sap
}
pub fn push_polytree(&mut self, tree: PolyTree<T>) -> Sapling<T> {
let mut sap = tree.into_sapling();
self.verts.append(&mut sap.verts);
sap.clear();
sap
}
pub fn push_node(&mut self, node: Node<T>)
where
T: Clone,
{
self.verts.extend_from_slice(node.verts);
}
pub fn peek(&self) -> Option<&T> {
let i = *self.path.last()?;
Some(&self.verts[i].data)
}
pub fn pop(&mut self) -> Option<&T> {
let i = self.path.pop()?;
self.verts[i].len = self.verts.len() - i - 1;
Some(&self.verts[i].data)
}
pub fn pop_all(&mut self) {
while let Some(i) = self.path.pop() {
self.verts[i].len = self.verts.len() - i - 1;
}
}
pub fn pop_as_leaf(&mut self) -> Option<&T> {
let i = self.path.pop()?;
Some(&self.verts[i].data)
}
pub fn pop_as_leaf_all(&mut self) {
self.path.clear();
}
pub fn clear(&mut self) {
self.path.clear();
self.verts.clear();
}
pub fn is_empty(&self) -> bool {
self.verts.is_empty()
}
pub fn is_ready(&self) -> bool {
self.path.is_empty() && !self.verts.is_empty()
}
pub fn build(self) -> Result<Tree<T>, BuildError<T>> {
if !self.is_ready() {
return Err(BuildError::Incomplete(self));
}
if self.verts[0].len < self.verts.len() - 1 {
return Err(BuildError::MultipleRoots(self));
}
Ok(Tree {
path: self.path,
verts: self.verts,
})
}
pub fn build_polytree(self) -> Result<PolyTree<T>, BuildError<T>> {
if !self.is_ready() {
return Err(BuildError::Incomplete(self));
}
Ok(PolyTree {
path: self.path,
verts: self.verts,
})
}
}
impl<T> Default for Sapling<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct Tree<T> {
path: Vec<usize>,
verts: Vec<Vertex<T>>,
}
#[allow(clippy::len_without_is_empty)]
impl<T> Tree<T> {
pub fn as_node(&self) -> Node<T> {
Node {
rank: 0,
verts: &self.verts[..],
}
}
pub fn get(&self, rank: usize) -> Option<Node<T>> {
if rank >= self.verts.len() {
return None;
}
Some(Node {
rank,
verts: &self.verts[..],
})
}
pub fn len(&self) -> usize {
self.verts.len()
}
pub fn into_sapling(self) -> Sapling<T> {
Sapling {
path: self.path,
verts: self.verts,
}
}
}
#[derive(Debug)]
pub struct PolyTree<T> {
path: Vec<usize>,
verts: Vec<Vertex<T>>,
}
#[allow(clippy::len_without_is_empty)]
impl<T> PolyTree<T> {
pub fn roots(&self) -> Children<T> {
Children {
top: 0,
bottom: self.verts.len(),
verts: &self.verts[..],
}
}
pub fn get(&self, rank: usize) -> Option<Node<T>> {
if rank >= self.verts.len() {
return None;
}
Some(Node {
rank,
verts: &self.verts[..],
})
}
pub fn len(&self) -> usize {
self.verts.len()
}
pub fn into_sapling(self) -> Sapling<T> {
Sapling {
path: self.path,
verts: self.verts,
}
}
}
#[derive(Debug)]
pub struct Node<'a, T> {
rank: usize,
verts: &'a [Vertex<T>],
}
impl<'a, T> Node<'a, T> {
pub fn from(verts: &[Vertex<T>]) -> Result<Node<T>, ValidationError> {
if verts.is_empty() {
return Err(ValidationError::Empty);
}
if verts[0].len != verts.len() - 1 {
return Err(ValidationError::MultipleRoots);
}
let mut path = Vec::new();
for (i, val) in verts.iter().enumerate() {
while path.last() == Some(&i) {
path.pop();
}
let scope = i + val.len + 1;
if path.last().map(|head| *head < scope) == Some(true) {
return Err(ValidationError::IllegalStructure);
}
path.push(scope);
}
Ok(Node { rank: 0, verts })
}
pub unsafe fn from_unchecked(verts: &[Vertex<T>]) -> Node<T> {
Node { rank: 0, verts }
}
pub fn data(self) -> &'a T {
&self.verts[self.rank].data
}
pub fn rank(self) -> usize {
self.rank
}
pub fn len(self) -> usize {
self.verts[self.rank].len
}
pub fn is_empty(self) -> bool {
self.verts[self.rank].len == 0
}
pub fn get(self, rank: usize) -> Option<Node<'a, T>> {
if rank >= self.verts.len() {
return None;
}
Some(Node {
rank,
verts: self.verts,
})
}
pub fn parent(self) -> Option<Node<'a, T>> {
self.ancestors().next()
}
pub fn children(self) -> Children<'a, T> {
Children::from(self)
}
pub fn descendants(self) -> Descendants<'a, T> {
Descendants::from(self)
}
pub fn ancestors(self) -> Ancestors<'a, T> {
Ancestors::from(self)
}
pub fn as_slice(self) -> &'a [Vertex<T>] {
self.verts
}
pub fn isolated(self) -> Node<'a, T> {
Node {
rank: 0,
verts: &self.verts[self.rank..=self.rank + self.verts[self.rank].len],
}
}
pub fn into_tree(self) -> Tree<T>
where
T: Clone,
{
let mut verts = Vec::new();
verts.extend_from_slice(self.verts);
Tree {
path: Vec::new(),
verts,
}
}
}
impl<'a, T> Copy for Node<'a, T> {}
impl<'a, T> Clone for Node<'a, T> {
fn clone(&self) -> Self {
*self
}
}
#[derive(Debug)]
pub struct Children<'a, T> {
top: usize,
bottom: usize,
verts: &'a [Vertex<T>],
}
impl<'a, T> Children<'a, T> {
pub fn from(node: Node<'a, T>) -> Self {
Children {
top: node.rank() + 1,
bottom: node.rank() + node.len() + 1,
verts: node.verts,
}
}
}
impl<'a, T> Iterator for Children<'a, T> {
type Item = Node<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
if self.top >= self.bottom {
return None;
}
let ret = Node {
rank: self.top,
verts: self.verts,
};
self.top += self.verts[self.top].len + 1;
Some(ret)
}
fn size_hint(&self) -> (usize, Option<usize>) {
if self.top >= self.bottom {
(0, Some(0))
} else {
(1, Some(self.bottom - self.top))
}
}
}
#[derive(Debug)]
pub struct Descendants<'a, T> {
top: usize,
bottom: usize,
verts: &'a [Vertex<T>],
}
impl<'a, T> Descendants<'a, T> {
pub fn from(node: Node<'a, T>) -> Self {
Descendants {
top: node.rank() + 1,
bottom: node.rank() + node.len() + 1,
verts: node.verts,
}
}
}
impl<'a, T> Iterator for Descendants<'a, T> {
type Item = Node<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
if self.top >= self.bottom {
return None;
}
let ret = Node {
rank: self.top,
verts: self.verts,
};
self.top += 1;
Some(ret)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.top += n;
self.next()
}
fn last(mut self) -> Option<Self::Item> {
self.next_back()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len(), Some(self.len()))
}
fn count(self) -> usize {
self.len()
}
}
impl<'a, T> DoubleEndedIterator for Descendants<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.top >= self.bottom {
return None;
}
self.bottom -= 1;
Some(Node {
rank: self.bottom,
verts: self.verts,
})
}
}
impl<'a, T> ExactSizeIterator for Descendants<'a, T> {
fn len(&self) -> usize {
self.bottom - self.top
}
}
#[derive(Debug)]
pub struct Ancestors<'a, T> {
top: usize,
bottom: usize,
verts: &'a [Vertex<T>],
}
impl<'a, T> Ancestors<'a, T> {
pub fn from(node: Node<'a, T>) -> Self {
Ancestors {
top: 0,
bottom: node.rank(),
verts: node.verts,
}
}
}
impl<'a, T> Iterator for Ancestors<'a, T> {
type Item = Node<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
if self.top >= self.bottom {
return None;
}
for i in (self.top..self.bottom).rev() {
if self.bottom <= i + self.verts[i].len {
self.bottom = i;
return Some(Node {
rank: i,
verts: self.verts,
});
}
}
None
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.top - self.bottom))
}
fn count(self) -> usize {
self.rev().count()
}
fn last(mut self) -> Option<Self::Item> {
self.next_back()
}
}
impl<'a, T> DoubleEndedIterator for Ancestors<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
let mut i = self.top;
while i < self.bottom {
let len = self.verts[i].len;
if i + len < self.bottom {
i += len + 1;
} else {
self.top = i + 1;
return Some(Node {
rank: i,
verts: self.verts,
});
}
}
None
}
}