#![allow(clippy::match_bool)]
use std::collections::VecDeque;
use std::marker::PhantomData;
use std::mem;
use crate::Arena;
use crate::node::Node;
use crate::token::Token;
#[derive(Clone, Copy, PartialEq, Eq)]
pub (crate) enum Branch {
Sibling,
Child,
None
}
#[derive(Clone, Copy)]
pub enum TraversalOrder {
Pre,
Post,
Level
}
pub (crate) fn preorder_next<T>(mut node_token: Token,
root: Token,
mut branch: Branch,
arena: &Arena<T>)
-> (Option<Token>, Branch) {
loop {
let node = match arena.get(node_token) {
Some(n) => n,
None => panic!("Invalid token")
};
match branch {
Branch::None => panic!("Unreachable arm. Check code."), Branch::Child => match node.first_child {
Some(token) => break (Some(token), Branch::Child),
None => match node_token == root {
true => break (None, Branch::None),
false => branch = Branch::Sibling
}
},
Branch::Sibling => match node.next_sibling {
Some(token) => break (Some(token), Branch::Child),
None => match node.parent {
None => break (None, Branch::None),
Some(parent) => match parent == root {
true => break (None, Branch::None),
false => {
node_token = parent;
branch = Branch::Sibling;
}
}
}
}
}
}
}
pub (crate) fn postorder_next<T>(mut node_token: Token,
root: Token,
mut branch: Branch,
arena: &Arena<T>)
-> (Option<Token>, Branch) {
let mut switch_branch = true;
loop {
let node = match arena.get(node_token) {
Some(n) => n,
None => panic!("Invalid token")
};
match branch {
Branch::None => break (None, Branch::None),
Branch::Child => match node.first_child {
Some(token) => {
node_token = token;
switch_branch = false;
},
None => match switch_branch {
false => break (Some(node_token), Branch::Sibling),
true => match node_token == root {
true => break (Some(root), Branch::None), false => branch = Branch::Sibling,
}
}
},
Branch::Sibling => match node.next_sibling {
Some(token) => {
switch_branch = false;
node_token = token;
branch = Branch::Child;
},
None => match node.parent {
None => break (None, Branch::Child),
Some(parent) => match parent == root {
true => break (Some(root), Branch::None),
false => break (Some(parent), Branch::Sibling)
}
}
}
}
}
}
#[allow(clippy::type_complexity)]
pub (crate) fn depth_first_tokens_next<'a, T>(
iter: &mut SubtreeTokens<'a, T>,
func: fn(Token, Token, Branch, &Arena<T>) -> (Option<Token>, Branch)
) -> Option<Token> {
match iter.node_token {
None => None,
Some(token) => match iter.arena.get(token) {
None => panic!("Stale token: {:?} is not found in \
the arena. Check code", token),
Some(_) => {
let (next_node, branch) = func(
token,
iter.subtree_root,
iter.branch,
iter.arena
);
iter.node_token = next_node;
iter.branch = branch;
Some(token)
}
}
}
}
pub (crate) fn breadth_first_tokens_next<'a, T> (iter: &mut SubtreeTokens<'a, T>)
-> Option<Token> {
match iter.curr_level.pop_front() {
Some(token) => {
iter.next_level.extend(token.children_tokens(iter.arena));
Some(token)
},
None => match iter.next_level.is_empty() {
true => None,
false => {
mem::swap(&mut iter.curr_level, &mut iter.next_level);
iter.next()
}
}
}
}
pub struct SubtreeTokens<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) subtree_root: Token,
pub (crate) node_token: Option<Token>,
pub (crate) branch: Branch,
pub (crate) curr_level: VecDeque<Token>,
pub (crate) next_level: VecDeque<Token>,
pub (crate) next: fn(&mut SubtreeTokens<T>) -> Option<Token>
}
impl<'a, T> Iterator for SubtreeTokens<'a, T> {
type Item = Token;
fn next(&mut self) -> Option<Token> { (self.next)(self) }
}
pub struct Subtree<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) iter: SubtreeTokens<'a, T>
}
impl<'a, T> Iterator for Subtree<'a, T> {
type Item = &'a Node<T>;
fn next(&mut self) -> Option<&'a Node<T>> {
match self.iter.next() {
Some(node_token) => self.arena.get(node_token),
None => None
}
}
}
pub struct SubtreeMut<'a, T: 'a> {
pub (crate) arena: *mut Arena<T>,
pub (crate) iter: SubtreeTokens<'a, T>,
pub (crate) marker: PhantomData<&'a mut T>
}
impl<'a, T> Iterator for SubtreeMut<'a, T> {
type Item = &'a mut Node<T>;
fn next(&mut self) -> Option<&'a mut Node<T>> {
match self.iter.next() {
None => None,
Some(node_token) => {
let arena = unsafe { self.arena.as_mut().unwrap() };
match arena.get_mut(node_token) {
Some(node) => Some(node),
None => None
}
}
}
}
}
unsafe impl<T: Sync> Sync for SubtreeMut<'_, T> {}
unsafe impl<T: Send> Send for SubtreeMut<'_, T> {}
pub struct FollowingSiblingTokens<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) node_token: Option<Token>
}
pub struct PrecedingSiblingTokens<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) node_token: Option<Token>
}
pub struct ChildrenTokens<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) node_token: Option<Token>
}
pub struct AncestorTokens<'a, T> {
pub (crate) arena: &'a Arena<T>,
pub (crate) node_token: Option<Token>
}
pub struct PrecedingSiblings<'a, T> {
pub (crate) token_iter: PrecedingSiblingTokens<'a, T>
}
pub struct FollowingSiblings<'a, T> {
pub (crate) token_iter: FollowingSiblingTokens<'a, T>
}
pub struct Children<'a, T> {
pub (crate) token_iter: ChildrenTokens<'a, T>
}
pub struct Ancestors<'a, T> {
pub (crate) token_iter: AncestorTokens<'a, T>
}
pub struct PrecedingSiblingsMut<'a, T: 'a> {
pub (crate) arena: *mut Arena<T>,
pub (crate) node_token: Option<Token>,
pub (crate) marker: PhantomData<&'a mut T>
}
pub struct FollowingSiblingsMut<'a, T: 'a> {
pub (crate) arena: *mut Arena<T>,
pub (crate) node_token: Option<Token>,
pub (crate) marker: PhantomData<&'a mut T>
}
pub struct ChildrenMut<'a, T: 'a> {
pub (crate) arena: *mut Arena<T>,
pub (crate) node_token: Option<Token>,
pub (crate) marker: PhantomData<&'a mut T>
}
pub struct AncestorsMut<'a, T: 'a> {
pub (crate) arena: *mut Arena<T>,
pub (crate) node_token: Option<Token>,
pub (crate) marker: PhantomData<&'a mut T>
}
macro_rules! iterator {
(@token struct $name:ident > $field:ident) => {
impl<'a, T> Iterator for $name<'a, T> {
type Item = Token;
fn next(&mut self) -> Option<Token> {
match self.node_token {
None => None,
Some(token) => match self.arena.get(token) {
None => panic!("Stale token: {:?} is not found in \
the arena. Check code", token),
Some(curr_node) => {
self.node_token = curr_node.$field;
Some(token)
}
}
}
}
}
};
(@node struct $name:ident) => {
impl<'a, T> Iterator for $name<'a, T> {
type Item = &'a Node<T>;
fn next(&mut self) -> Option<&'a Node<T>> {
match self.token_iter.next() {
Some(node_token) => self.token_iter.arena.get(node_token),
None => None
}
}
}
};
(@mut struct $name:ident > $field:ident) => {
impl<'a, T> Iterator for $name<'a, T> {
type Item = &'a mut Node<T>;
fn next(&mut self) -> Option<&'a mut Node<T>> {
match self.node_token {
None => None,
Some(curr_node_token) => {
let arena = unsafe { self.arena.as_mut().unwrap() };
match arena.get_mut(curr_node_token) {
None => None,
Some(curr_node) => {
self.node_token = curr_node.$field;
Some(curr_node)
}
}
}
}
}
}
unsafe impl<T: Sync> Sync for $name<'_, T> {}
unsafe impl<T: Send> Send for $name<'_, T> {}
}
}
iterator!(@token struct FollowingSiblingTokens > next_sibling);
iterator!(@token struct PrecedingSiblingTokens > previous_sibling);
iterator!(@token struct ChildrenTokens > next_sibling);
iterator!(@token struct AncestorTokens > parent);
iterator!(@node struct PrecedingSiblings);
iterator!(@node struct FollowingSiblings);
iterator!(@node struct Children);
iterator!(@node struct Ancestors);
iterator!(@mut struct PrecedingSiblingsMut > previous_sibling);
iterator!(@mut struct FollowingSiblingsMut > next_sibling);
iterator!(@mut struct ChildrenMut > next_sibling);
iterator!(@mut struct AncestorsMut > parent);