use core::cmp::Ordering;
use core::iter;
use core::num::NonZeroUsize;
use crate::node::{FrozenNode, HotNode, Node};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum DftEvent<T> {
Open(T),
Close(T),
}
impl<T> DftEvent<T> {
#[inline]
#[must_use]
pub fn into_value(self) -> T {
match self {
Self::Open(v) => v,
Self::Close(v) => v,
}
}
#[inline]
#[must_use]
pub fn as_value(&self) -> &T {
match self {
Self::Open(v) => v,
Self::Close(v) => v,
}
}
#[inline]
#[must_use]
pub fn as_value_mut(&mut self) -> &mut T {
match self {
Self::Open(v) => v,
Self::Close(v) => v,
}
}
#[must_use]
pub fn map<F, U>(self, f: F) -> DftEvent<U>
where
F: FnOnce(T) -> U,
{
match self {
Self::Open(v) => DftEvent::Open(f(v)),
Self::Close(v) => DftEvent::Close(f(v)),
}
}
#[inline]
#[must_use]
pub fn into_open(self) -> Option<T> {
match self {
Self::Open(v) => Some(v),
Self::Close(_) => None,
}
}
#[inline]
#[must_use]
pub fn into_close(self) -> Option<T> {
match self {
Self::Open(_) => None,
Self::Close(v) => Some(v),
}
}
}
macro_rules! impl_dft_event_methods_for_node {
($ty_node:ident) => {
impl<T> DftEvent<$ty_node<T>> {
#[must_use]
pub fn next(&self) -> Option<Self> {
let next = match self {
Self::Open(current) => {
match current.first_child() {
Some(child) => Self::Open(child),
None => Self::Close(current.clone()),
}
}
Self::Close(current) => {
match current.next_sibling() {
Some(next_sib) => Self::Open(next_sib),
None => Self::Close(current.parent()?),
}
}
};
Some(next)
}
#[must_use]
pub fn close_current(&self) -> Option<$ty_node<T>> {
let mut depth = 0_usize;
loop {
match self.next()? {
Self::Open(_) => depth += 1,
Self::Close(node) if depth == 0 => return Some(node),
Self::Close(_) => depth -= 1,
}
}
}
#[must_use]
pub fn prev(&self) -> Option<Self> {
let prev = match self {
Self::Close(current) => {
match current.last_child() {
Some(child) => Self::Close(child),
None => Self::Open(current.clone()),
}
}
Self::Open(current) => {
match current.prev_sibling() {
Some(prev_sib) => Self::Close(prev_sib),
None => Self::Open(current.parent()?),
}
}
};
Some(prev)
}
}
};
}
impl_dft_event_methods_for_node!(Node);
impl_dft_event_methods_for_node!(FrozenNode);
impl_dft_event_methods_for_node!(HotNode);
#[derive(Debug)]
pub struct DepthFirstTraverser<T> {
next: Option<(DftEvent<Node<T>>, Node<T>)>,
}
impl<T> Clone for DepthFirstTraverser<T> {
#[inline]
fn clone(&self) -> Self {
Self {
next: self.next.clone(),
}
}
}
impl<T> DepthFirstTraverser<T> {
#[inline]
#[must_use]
pub fn with_start(next: Option<Node<T>>) -> Self {
Self {
next: next.map(|node| (DftEvent::Open(node.clone()), node)),
}
}
#[inline]
#[must_use]
pub fn with_next_event(start: Node<T>, next: Option<DftEvent<Node<T>>>) -> Self {
Self {
next: next.map(|next| (next, start)),
}
}
#[inline]
#[must_use]
pub fn peek(&self) -> Option<&DftEvent<Node<T>>> {
self.next.as_ref().map(|(ev, _node)| ev)
}
pub fn close_current(&mut self) -> Option<Node<T>> {
let mut depth = 0_usize;
loop {
match self.next()? {
DftEvent::Open(_) => depth += 1,
DftEvent::Close(node) if depth == 0 => return Some(node),
DftEvent::Close(_) => depth -= 1,
}
}
}
}
impl<T> Iterator for DepthFirstTraverser<T> {
type Item = DftEvent<Node<T>>;
fn next(&mut self) -> Option<Self::Item> {
let (next_ev, start) = self.next.take()?;
self.next = match &next_ev {
DftEvent::Close(next_close) if next_close.ptr_eq(&start) => None,
_ => next_ev.next().map(|next_of_next| (next_of_next, start)),
};
Some(next_ev)
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self.next.as_ref() {
Some((DftEvent::Open(_), _)) => (2, None),
Some((DftEvent::Close(next), start)) => {
if Node::ptr_eq(next, start) {
(1, Some(1))
} else {
(1, None)
}
}
None => (0, Some(0)),
}
}
}
impl<T> iter::FusedIterator for DepthFirstTraverser<T> {}
#[derive(Debug)]
pub struct ReverseDepthFirstTraverser<T> {
next: Option<(DftEvent<Node<T>>, Node<T>)>,
}
impl<T> Clone for ReverseDepthFirstTraverser<T> {
#[inline]
fn clone(&self) -> Self {
Self {
next: self.next.clone(),
}
}
}
impl<T> ReverseDepthFirstTraverser<T> {
#[inline]
#[must_use]
pub fn with_start(next: Option<Node<T>>) -> Self {
Self {
next: next.map(|node| (DftEvent::Close(node.clone()), node)),
}
}
#[inline]
#[must_use]
pub fn with_next_event(start: Node<T>, next: Option<DftEvent<Node<T>>>) -> Self {
Self {
next: next.map(|next| (next, start)),
}
}
#[inline]
#[must_use]
pub fn peek(&self) -> Option<&DftEvent<Node<T>>> {
self.next.as_ref().map(|(ev, _node)| ev)
}
}
impl<T> Iterator for ReverseDepthFirstTraverser<T> {
type Item = DftEvent<Node<T>>;
fn next(&mut self) -> Option<Self::Item> {
let (next_ev, start) = self.next.take()?;
self.next = match &next_ev {
DftEvent::Open(next_open) if next_open.ptr_eq(&start) => None,
_ => next_ev.prev().map(|next_of_next| (next_of_next, start)),
};
Some(next_ev)
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self.next.as_ref() {
Some((DftEvent::Close(_), _)) => (2, None),
Some((DftEvent::Open(next), start)) => {
if Node::ptr_eq(next, start) {
(1, Some(1))
} else {
(1, None)
}
}
None => (0, Some(0)),
}
}
}
impl<T> iter::FusedIterator for ReverseDepthFirstTraverser<T> {}
#[derive(Debug)]
pub struct StableDepthFirstTraverser<T> {
next: Option<(<Self as Iterator>::Item, <Self as Iterator>::Item)>,
}
impl<T> Clone for StableDepthFirstTraverser<T> {
#[inline]
fn clone(&self) -> Self {
Self {
next: self.next.clone(),
}
}
}
impl<T> StableDepthFirstTraverser<T> {
#[must_use]
pub fn with_toplevel(next: Option<FrozenNode<T>>) -> Self {
Self {
next: next.map(|node| (DftEvent::Open(node.clone()), DftEvent::Close(node))),
}
}
#[inline]
#[must_use]
pub fn with_first_last_event(
first: DftEvent<FrozenNode<T>>,
last: DftEvent<FrozenNode<T>>,
) -> Self {
Self {
next: Some((first, last)),
}
}
#[inline]
#[must_use]
pub fn peek(&self) -> Option<&DftEvent<FrozenNode<T>>> {
self.next.as_ref().map(|(next, _next_back)| next)
}
#[inline]
#[must_use]
pub fn peek_back(&self) -> Option<&DftEvent<FrozenNode<T>>> {
self.next.as_ref().map(|(_next, next_back)| next_back)
}
pub fn close_current(&mut self) -> Option<FrozenNode<T>> {
let mut depth = 0_usize;
loop {
match self.next()? {
DftEvent::Open(_) => depth += 1,
DftEvent::Close(node) if depth == 0 => return Some(node),
DftEvent::Close(_) => depth -= 1,
}
}
}
}
impl<T> Iterator for StableDepthFirstTraverser<T> {
type Item = DftEvent<FrozenNode<T>>;
fn next(&mut self) -> Option<Self::Item> {
let (next, next_back) = self.next.take()?;
self.next = next.next().map(|next_of_next| (next_of_next, next_back));
Some(next)
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self.next.as_ref() {
Some((DftEvent::Open(next), DftEvent::Open(next_back)))
| Some((DftEvent::Close(next), DftEvent::Close(next_back)))
if FrozenNode::ptr_eq(next, next_back) =>
{
(1, Some(1))
}
Some((_, _)) => (2, None),
None => (0, Some(0)),
}
}
}
impl<T> DoubleEndedIterator for StableDepthFirstTraverser<T> {
fn next_back(&mut self) -> Option<Self::Item> {
let (next, next_back) = self.next.take()?;
self.next = next_back
.prev()
.map(|prev_of_next_back| (next, prev_of_next_back));
Some(next_back)
}
}
impl<T> iter::FusedIterator for StableDepthFirstTraverser<T> {}
#[derive(Debug)]
pub struct StableShallowDepthFirstTraverser<T> {
#[allow(clippy::type_complexity)]
next: Option<(
DftEvent<(FrozenNode<T>, usize)>,
DftEvent<(FrozenNode<T>, usize)>,
)>,
depth_ignore: Option<NonZeroUsize>,
}
impl<T> Clone for StableShallowDepthFirstTraverser<T> {
#[inline]
fn clone(&self) -> Self {
Self {
next: self.next.clone(),
depth_ignore: self.depth_ignore,
}
}
}
impl<T> StableShallowDepthFirstTraverser<T> {
#[must_use]
pub fn with_toplevel(next: Option<FrozenNode<T>>, max_depth: Option<usize>) -> Self {
let depth_ignore = max_depth.and_then(|max| NonZeroUsize::new(max.wrapping_add(1)));
Self {
next: next.map(|node| {
(
DftEvent::Open((node.clone(), 0)),
DftEvent::Close((node, 0)),
)
}),
depth_ignore,
}
}
#[inline]
#[must_use]
pub fn peek(&self) -> Option<&DftEvent<(FrozenNode<T>, usize)>> {
self.next.as_ref().map(|(next, _next_back)| next)
}
#[inline]
#[must_use]
pub fn peek_back(&self) -> Option<&DftEvent<(FrozenNode<T>, usize)>> {
self.next.as_ref().map(|(_next, next_back)| next_back)
}
#[inline]
#[must_use]
pub fn max_depth(&self) -> usize {
self.depth_ignore
.map_or(usize::MAX, |ignore| ignore.get() - 1)
}
pub fn close_current(&mut self) -> Option<(FrozenNode<T>, usize)> {
let mut depth = 0_usize;
loop {
match self.next()? {
DftEvent::Open(_) => depth += 1,
DftEvent::Close(v) if depth == 0 => return Some(v),
DftEvent::Close(_) => depth -= 1,
}
}
}
#[must_use]
fn next_of_next_forward(&mut self) -> Option<DftEvent<(FrozenNode<T>, usize)>> {
let (next, next_back) = self.next.as_ref()?;
match (next, next_back) {
(DftEvent::Open((next, depth)), DftEvent::Open((next_back, depth_back)))
| (DftEvent::Close((next, depth)), DftEvent::Close((next_back, depth_back)))
if FrozenNode::ptr_eq(next, next_back) =>
{
debug_assert_eq!(
depth, depth_back,
"[validity] the identical node should be at the same place"
);
return None;
}
_ => {}
}
let next_of_next = match next {
DftEvent::Open((next, depth)) => {
if *depth == self.max_depth() {
return Some(DftEvent::Close((next.clone(), *depth)));
}
match next.first_child() {
Some(child) => DftEvent::Open((child, *depth + 1)),
None => DftEvent::Close((next.clone(), *depth)),
}
}
DftEvent::Close((next, depth)) => {
match next.next_sibling() {
Some(next_sib) => DftEvent::Open((next_sib, *depth)),
None => DftEvent::Close((next.parent()?, *depth - 1)),
}
}
};
Some(next_of_next)
}
#[must_use]
fn next_of_next_backward(&mut self) -> Option<DftEvent<(FrozenNode<T>, usize)>> {
let (next, next_back) = self.next.as_ref()?;
match (next, next_back) {
(DftEvent::Open((next, depth)), DftEvent::Open((next_back, depth_back)))
| (DftEvent::Close((next, depth)), DftEvent::Close((next_back, depth_back)))
if FrozenNode::ptr_eq(next, next_back) =>
{
debug_assert_eq!(
depth, depth_back,
"[validity] the identical node should be at the same place"
);
return None;
}
_ => {}
}
let next_of_next_backward = match next_back {
DftEvent::Close((next, depth)) => {
if *depth == self.max_depth() {
return Some(DftEvent::Open((next.clone(), *depth)));
}
match next.last_child() {
Some(child) => DftEvent::Close((child, *depth + 1)),
None => DftEvent::Open((next.clone(), *depth)),
}
}
DftEvent::Open((next, depth)) => {
match next.prev_sibling() {
Some(prev_sib) => DftEvent::Close((prev_sib, *depth)),
None => DftEvent::Open((next.parent()?, *depth - 1)),
}
}
};
Some(next_of_next_backward)
}
}
impl<T> Iterator for StableShallowDepthFirstTraverser<T> {
type Item = DftEvent<(FrozenNode<T>, usize)>;
fn next(&mut self) -> Option<Self::Item> {
let _ = self.next.as_ref()?;
let next_of_next = self.next_of_next_forward();
let (next, next_back) = self.next.take()?;
self.next = next_of_next.map(|next_of_next| (next_of_next, next_back));
Some(next)
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (next, next_back) = match &self.next {
Some((next, next_back)) => (next, next_back),
None => return (0, Some(0)),
};
match (next, next_back) {
(DftEvent::Open((next, depth)), DftEvent::Open((next_back, depth_back))) => {
if FrozenNode::ptr_eq(next, next_back) {
debug_assert_eq!(
depth, depth_back,
"[validity] the identical node should be at the same place"
);
return (1, Some(1));
}
let min = match depth.cmp(depth_back) {
Ordering::Greater => depth - depth_back + 3,
Ordering::Equal => 3,
Ordering::Less => depth_back - depth + 1,
};
(min, None)
}
(DftEvent::Close((next, depth)), DftEvent::Close((next_back, depth_back))) => {
if FrozenNode::ptr_eq(next, next_back) {
debug_assert_eq!(
depth, depth_back,
"[validity] the identical node should be at the same place"
);
return (1, Some(1));
}
let min = match depth.cmp(depth_back) {
Ordering::Greater => depth - depth_back + 1,
Ordering::Equal => 3,
Ordering::Less => depth_back - depth + 3,
};
(min, None)
}
(DftEvent::Open((next, depth)), DftEvent::Close((next_back, depth_back))) => {
let min = match depth.cmp(depth_back) {
Ordering::Greater => depth - depth_back + 2,
Ordering::Equal if FrozenNode::ptr_eq(next, next_back) => return (2, Some(2)),
Ordering::Equal => 4,
Ordering::Less => depth_back - depth + 2,
};
(min, None)
}
(DftEvent::Close((_, depth)), DftEvent::Open((_, depth_back))) => {
let min = match depth.cmp(depth_back) {
Ordering::Greater => depth - depth_back + 2,
Ordering::Equal => 2,
Ordering::Less => depth_back - depth + 2,
};
(min, None)
}
}
}
}
impl<T> DoubleEndedIterator for StableShallowDepthFirstTraverser<T> {
fn next_back(&mut self) -> Option<Self::Item> {
let _ = self.next.as_ref()?;
let next_of_next_back = self.next_of_next_backward();
let (next, next_back) = self.next.take()?;
self.next = next_of_next_back.map(|next_of_next_back| (next, next_of_next_back));
Some(next_back)
}
}
impl<T> iter::FusedIterator for StableShallowDepthFirstTraverser<T> {}