atree/

token.rs

#![allow(clippy::match_bool)]
use std::collections::VecDeque;
use std::marker::PhantomData;
use std::num::NonZeroUsize;
use std::mem::MaybeUninit;

use crate::Error;
use crate::iter::*;
use crate::node::Node;
use crate::arena::Arena;

/// A `Token` is a handle to a node in the arena.
#[derive(Clone, Copy, Eq, PartialEq, Debug, Hash)]
pub struct Token {
    pub (crate) index: NonZeroUsize
}

fn node_operation<T>(
    self_token: Token,
    arena: &mut Arena<T>,
    other_token: Token,
    func: fn(Token, &mut Arena<T>, T) -> Token
) -> Result<(), Error> {
    // only a placeholder to get around some trait requirements so I can
    // reuse code. The uninitialized data will be removed so no risk here.
    let dummy_data: T = unsafe { MaybeUninit::zeroed().assume_init() };
    let token = func(self_token, arena, dummy_data);
    token.replace_node(arena, other_token)?;
    arena.remove(token);  // remove uninitialized data
    Ok(())
}

impl Token {
    /// Checks whether a given node is actually a leaf.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    pub fn is_leaf<T>(self, arena: &Arena<T>) -> bool {
        match arena.get(self) {
            None => panic!("Invalid token"),
            Some(node) => node.is_leaf()
        }
    }

    /// Creates a new node with the given data and append to the given node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let next_node_token = root_token.append(&mut arena, "Germanic");
    /// next_node_token.append(&mut arena, "Romance");
    /// let mut subtree = root_token.subtree(&arena, TraversalOrder::Pre);
    ///
    /// assert_eq!(subtree.next().unwrap().data, "Indo-European");
    /// assert_eq!(subtree.next().unwrap().data, "Germanic");
    /// assert_eq!(subtree.next().unwrap().data, "Romance");
    /// ```
    pub fn append<T>(self, arena: &mut Arena<T>, data: T) -> Token {
        let new_node_token = arena.allocator.head();
        let previous_sibling = match self.children_mut(arena).last() {
            None => {
                // children_mut will have checked indexability so this will not
                // fail
                arena[self].first_child = Some(new_node_token);
                None
            },
            Some(last_child) => {
                last_child.next_sibling = Some(new_node_token);
                Some(last_child.token)
            }
        };

        let node = Node {
            data,
            token: new_node_token,
            parent: Some(self),
            previous_sibling,
            next_sibling: None,
            first_child: None
        };
        arena.set(new_node_token, node);
        new_node_token
    }

    /// Creates a new node with the given data and sets as the previous sibling
    /// of the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let child2 = root_token.append(&mut arena, "Germanic");
    /// let child4 = root_token.append(&mut arena, "Slavic");
    /// child2.append(&mut arena, "English");
    /// // insert in between children 2 and 4
    /// let child3 = child4.insert_before(&mut arena, "Romance");
    /// // insert before child 2
    /// let child1 = child2.insert_before(&mut arena, "Celtic");
    ///
    /// let subtree: Vec<_> = root_token.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data)
    ///     .collect();
    /// assert_eq!(&["Indo-European", "Celtic", "Germanic", "English", "Romance", "Slavic"],
    ///            &subtree[..]);
    /// ```
    pub fn insert_before<T>(self, arena: &mut Arena<T>, data: T) -> Token {
        let new_node_token = arena.allocator.head();
        let (self_parent, self_previous_sibling) = match arena.get(self) {
            None => panic!("Invalid token"),
            Some(node) => (node.parent, node.previous_sibling)
        };
        arena[self].previous_sibling = Some(new_node_token);  // already checked
        let previous_sibling = match self_previous_sibling {
            Some(sibling) => match arena.get_mut(sibling) {
                None => panic!("Corrupt arena"),
                Some(ref mut node) => {
                    node.next_sibling = Some(new_node_token);
                    Some(sibling)
                }
            },
            None => match self_parent {
                None => panic!("Cannot insert as the previous sibling of the \
                                root node"),
                Some(p) => match arena.get_mut(p) {
                    None => panic!("Corrupt arena"),
                    Some(ref mut node) => {
                        node.first_child = Some(new_node_token);
                        None
                    }
                }
            }
        };

        let node = Node {
            data,
            token: new_node_token,
            parent: self_parent,
            previous_sibling,
            next_sibling: Some(self),
            first_child: None
        };
        arena.set(new_node_token, node);
        new_node_token
    }

    /// Set a node in the arena as the next sibling of the given node. Returns
    /// error if the "other node" is not a root node of a tree (as in it already
    /// has a parent and/or siblings).
    ///
    /// **Note**: for performance reasons, this operation does not check whether
    /// the "self" node is in fact a descendant of the other tree. A cyclic
    /// graph may result.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// // root node that we will attach subtrees to
    /// let root_data = "Indo-European";
    /// let (mut arena, root) = Arena::with_data(root_data);
    ///
    /// let germanic = root.append(&mut arena, "Germanic");
    /// let scots = germanic.append(&mut arena, "German");
    /// let english = germanic.append(&mut arena, "English");
    ///
    /// let romance = arena.new_node("Romance");
    /// let french = romance.append(&mut arena, "French");
    /// let spanish = romance.append(&mut arena, "Spanish");
    ///
    /// germanic.insert_node_after(&mut arena, romance);
    ///
    /// let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("Indo-European"));
    /// assert_eq!(iter.next(), Some("Germanic"));
    /// assert_eq!(iter.next(), Some("German"));
    /// assert_eq!(iter.next(), Some("English"));
    /// assert_eq!(iter.next(), Some("Romance"));
    /// assert_eq!(iter.next(), Some("French"));
    /// assert_eq!(iter.next(), Some("Spanish"));
    /// assert!(iter.next().is_none())
    /// ```
    pub fn insert_node_after<T>(self, arena: &mut Arena<T>, other: Token)
        -> Result<(), Error> {
        node_operation(self, arena, other, Token::insert_after)
    }

    /// Set a node in the arena as the previous sibling of the given node.
    /// Returns error if the "other node" is not a root node of a tree (as in it
    /// already has a parent and/or siblings).
    ///
    /// **Note**: for performance reasons, this operation does not check whether
    /// the "self" node is in fact a descendant of the other tree. A cyclic
    /// graph may result.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// // root node that we will attach subtrees to
    /// let root_data = "Indo-European";
    /// let (mut arena, root) = Arena::with_data(root_data);
    ///
    /// let germanic = root.append(&mut arena, "Germanic");
    /// let scots = germanic.append(&mut arena, "German");
    /// let english = germanic.append(&mut arena, "English");
    ///
    /// let romance = arena.new_node("Romance");
    /// let french = romance.append(&mut arena, "French");
    /// let spanish = romance.append(&mut arena, "Spanish");
    ///
    /// germanic.insert_node_before(&mut arena, romance);
    ///
    /// let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("Indo-European"));
    /// assert_eq!(iter.next(), Some("Romance"));
    /// assert_eq!(iter.next(), Some("French"));
    /// assert_eq!(iter.next(), Some("Spanish"));
    /// assert_eq!(iter.next(), Some("Germanic"));
    /// assert_eq!(iter.next(), Some("German"));
    /// assert_eq!(iter.next(), Some("English"));
    /// assert!(iter.next().is_none())
    /// ```
    pub fn insert_node_before<T>(self, arena: &mut Arena<T>, other: Token)
        -> Result<(), Error> {
        node_operation(self, arena, other, Token::insert_before)
    }

    /// Creates a new node with the given data and sets as the next sibling of
    /// the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let child1 = root_token.append(&mut arena, "Romance");
    /// let child3 = root_token.append(&mut arena, "Germanic");
    /// child1.append(&mut arena, "French");
    /// // insert betwern children 1 and 4
    /// let child2 = child1.insert_after(&mut arena, "Celtic");
    /// // insert after child 3
    /// child3.insert_after(&mut arena, "Slavic");
    ///
    /// let subtree: Vec<_> = root_token.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data)
    ///     .collect();
    /// assert_eq!(&["Indo-European", "Romance", "French", "Celtic", "Germanic", "Slavic"],
    ///            &subtree[..]);
    /// ```
    pub fn insert_after<T>(self, arena: &mut Arena<T>, data: T) -> Token {
        let new_node_token = arena.allocator.head();
        let (self_parent, self_next_sibling) = match arena.get(self) {
            None => panic!("Invalid token"),
            Some(node) => (node.parent, node.next_sibling)
        };
        arena[self].next_sibling = Some(new_node_token);  // already checked
        let next_sibling = match self_next_sibling {
            None => None,
            Some(sibling) => match arena.get_mut(sibling) {
                None => panic!("Corrupt arena"),
                Some(ref mut node) => {
                    node.previous_sibling = Some(new_node_token);
                    Some(sibling)
                }
            },
        };

        let node = Node {
            data,
            token: new_node_token,
            parent: self_parent,
            previous_sibling: Some(self),
            next_sibling,
            first_child: None
        };
        arena.set(new_node_token, node);
        new_node_token
    }

    /// Attaches a different tree in the arena to a node. Returns error if the
    /// "root node" of the other tree is not really a root node (as in it
    /// already has a parent and/or siblings). To attach a tree from a different
    /// arena, use [`copy_and_append_subtree`] instead.
    ///
    /// **Note**: for performance reasons, this operation does not check whether
    /// the "self" node is in fact a descendant of the other tree. A cyclic
    /// graph may result.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// // root node that we will attach subtrees to
    /// let root_data = "Indo-European";
    /// let (mut arena, root) = Arena::with_data(root_data);
    ///
    /// // the Germanic branch
    /// let germanic = arena.new_node("Germanic");
    /// let west = germanic.append(&mut arena, "West");
    /// let scots = west.append(&mut arena, "Scots");
    /// let english = west.append(&mut arena, "English");
    ///
    /// // the Romance branch
    /// let romance = arena.new_node("Romance");
    /// let french = romance.append(&mut arena, "French");
    /// let italian = romance.append(&mut arena, "Italian");
    ///
    /// // attach subtrees
    /// root.append_node(&mut arena, romance).unwrap();
    /// root.append_node(&mut arena, germanic).unwrap();
    ///
    /// let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("Indo-European"));
    /// assert_eq!(iter.next(), Some("Romance"));
    /// assert_eq!(iter.next(), Some("French"));
    /// assert_eq!(iter.next(), Some("Italian"));
    /// assert_eq!(iter.next(), Some("Germanic"));
    /// assert_eq!(iter.next(), Some("West"));
    /// assert_eq!(iter.next(), Some("Scots"));
    /// assert_eq!(iter.next(), Some("English"));
    /// assert!(iter.next().is_none())
    /// ```
    ///
    /// [`copy_and_append_subtree`]: struct.Arena.html#method.copy_and_append_subtree
    pub fn append_node<T>(self, arena: &mut Arena<T>, other: Self)
        -> Result<(), Error> {
        node_operation(self, arena, other, Token::append)
    }

    /// Detaches the given node and its descendants into its own tree while
    /// keeping it in the same arena. To detach and allocate the subtree into its
    /// own arena, use [`split_at`] instead.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// // root node that we will attach subtrees to
    /// let root_data = "Indo-European";
    /// let (mut arena, root) = Arena::with_data(root_data);
    ///
    /// // the Germanic branch
    /// let germanic = root.append(&mut arena, "Germanic");
    /// let west = germanic.append(&mut arena, "West");
    /// let scots = west.append(&mut arena, "Scots");
    /// let english = west.append(&mut arena, "English");
    ///
    /// // detach the west branch from the main tree
    /// west.detach(&mut arena);
    ///
    /// // the west branch is gone from the original tree
    /// let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("Indo-European"));
    /// assert_eq!(iter.next(), Some("Germanic"));
    /// assert!(iter.next().is_none());
    ///
    /// // it exists on its own
    /// let mut iter = west.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("West"));
    /// assert_eq!(iter.next(), Some("Scots"));
    /// assert_eq!(iter.next(), Some("English"));
    /// assert!(iter.next().is_none());
    /// ```
    ///
    /// [`split_at`]: struct.Arena.html#method.split_at
    pub fn detach<T>(self, arena: &mut Arena<T>) {
        let (parent, previous_sibling, next_sibling) = match arena.get_mut(self) {
            None => panic!("Invalid token"),
            Some(node) => {
                let parent = node.parent;
                let previous_sibling = node.previous_sibling;
                let next_sibling = node.next_sibling;
                node.parent = None;
                node.previous_sibling = None;
                node.next_sibling = None;
                (parent, previous_sibling, next_sibling)
            }
        };

        match previous_sibling {
            Some(token) => match arena.get_mut(token) {
                None => panic!("Corrupt arena"),
                Some(node) => node.next_sibling = next_sibling
            },
            None => if let Some(token) = parent {
                match arena.get_mut(token) {
                    None => panic!("Corrupt arena"),
                    Some(n) => n.first_child = next_sibling
                }
            }
        }

        if let Some(token) = next_sibling {
            match arena.get_mut(token) {
                None => panic!("Corrupt arena"),
                Some(node) => node.previous_sibling = previous_sibling
            }
        }
    }

    /// Replace the subtree of self with the subtree of other. Does not remove
    /// self or its descendants but simply makes it a standalone tree within the
    /// arena.
    ///
    /// **Note**: for performance reasons, this operation does not check whether
    /// the "other" node is in fact a descendant of the parent tree of self. A
    /// cyclic graph may result.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// // root node that we will attach subtrees to
    /// let root_data = "Indo-European";
    /// let (mut arena, root) = Arena::with_data(root_data);
    ///
    /// // the Germanic branch
    /// let germanic = root.append(&mut arena, "Germanic");
    /// let west = germanic.append(&mut arena, "West");
    /// let scots = west.append(&mut arena, "Scots");
    /// let english = west.append(&mut arena, "English");
    ///
    /// // the slavic branch
    /// let slavic = root.append(&mut arena, "Slavic");
    /// let polish = slavic.append(&mut arena, "Polish");
    /// let russian = slavic.append(&mut arena, "Russian");
    ///
    /// // the Romance branch
    /// let romance = arena.new_node("Romance");
    /// let french = romance.append(&mut arena, "French");
    /// let italian = romance.append(&mut arena, "Italian");
    ///
    /// // replace_node germanic with romance
    /// germanic.replace_node(&mut arena, romance).unwrap();
    ///
    /// let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    ///     .map(|x| x.data);
    /// assert_eq!(iter.next(), Some("Indo-European"));
    /// assert_eq!(iter.next(), Some("Romance"));
    /// assert_eq!(iter.next(), Some("French"));
    /// assert_eq!(iter.next(), Some("Italian"));
    /// assert_eq!(iter.next(), Some("Slavic"));
    /// assert_eq!(iter.next(), Some("Polish"));
    /// assert_eq!(iter.next(), Some("Russian"));
    /// assert!(iter.next().is_none());
    /// ```
    pub fn replace_node<T>(self, arena: &mut Arena<T>, other: Token)
        -> Result<(), Error> {
        let self_node = match arena.get(self) {
            None => panic!("Invalid token"),
            Some(n) => n
        };
        let parent = self_node.parent;
        let previous_sibling = self_node.previous_sibling;
        let next_sibling = self_node.next_sibling;

        let other_node = match arena.get_mut(other) {
            None => panic!("Invalid token"),
            Some(n) => n
        };

        // check that the other node is really a root node of its own
        match (other_node.previous_sibling,
               other_node.next_sibling,
               other_node.parent) {
            (None, None, None) => (),
            _ => return Err(Error::NotARootNode)
        }

        // replace_node the self node with the other node
        other_node.parent = parent;
        other_node.next_sibling = next_sibling;
        other_node.previous_sibling = previous_sibling;

        let self_node = &mut arena[self];  // indexability has been checked
        self_node.parent = None;
        self_node.previous_sibling = None;
        self_node.next_sibling = None;

        // update previous_sibling, next_sibling and parent of the self node
        match previous_sibling {
            Some(sibling) => match arena.get_mut(sibling) {
                None => panic!("Corrupt arena"),
                Some(node) => node.next_sibling = Some(other)
            },
            None => if let Some(p) = parent {
                match arena.get_mut(p) {
                    None => panic!("Corrupt arena"),
                    Some(node) => node.first_child = Some(other)
                }
            }
        }

        if let Some(sibling) = next_sibling {
            match arena.get_mut(sibling) {
                None => panic!("Corrupt arena"),
                Some(node) => node.previous_sibling = Some(other)
            }
        }

        Ok(())
    }

    /// Returns an iterator of tokens of ancestor nodes.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let child_token = root_token.append(&mut arena, "Germanic");
    /// let grandchild_token = child_token.append(&mut arena, "English");
    /// let mut ancestors_tokens = grandchild_token.ancestors_tokens(&arena);
    ///
    /// assert_eq!(ancestors_tokens.next(), Some(child_token));
    /// assert_eq!(ancestors_tokens.next(), Some(root_token));
    /// assert!(ancestors_tokens.next().is_none());
    /// ```
    pub fn ancestors_tokens<'a, T>(self, arena: &'a Arena<T>)
        -> AncestorTokens<'a, T> {
        let parent = match arena.get(self) {
            Some(n) => n.parent,
            None => panic!("Invalid token")
        };
        AncestorTokens { arena, node_token: parent }
    }

    /// Returns an iterator of tokens of siblings preceding the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let first_child_token = root_token.append(&mut arena, "Germanic");
    /// let second_child_token = root_token.append(&mut arena, "Romance");
    /// let third_child_token = root_token.append(&mut arena, "Slavic");
    /// root_token.append(&mut arena, "Hellenic");
    ///
    /// let mut sibling_tokens = third_child_token.preceding_siblings_tokens(&arena);
    /// assert_eq!(sibling_tokens.next(), Some(second_child_token));
    /// assert_eq!(sibling_tokens.next(), Some(first_child_token));
    /// assert!(sibling_tokens.next().is_none());
    /// ```
    pub fn preceding_siblings_tokens<'a, T>(self, arena: &'a Arena<T>)
        -> PrecedingSiblingTokens<'a, T> {
        let previous_sibling = match arena.get(self) {
            Some(n) => n.previous_sibling,
            None => panic!("Invalid token")
        };
        PrecedingSiblingTokens { arena, node_token: previous_sibling }
    }

    /// Returns an iterator of tokens of siblings following the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, "Romance");
    /// let second_child_token = root_token.append(&mut arena, "Germanic");
    /// let third_child_token = root_token.append(&mut arena, "Slavic");
    /// let fourth_child_token = root_token.append(&mut arena, "Hellenic");
    ///
    /// let mut sibling_tokens = second_child_token.following_siblings_tokens(&arena);
    /// assert_eq!(sibling_tokens.next(), Some(third_child_token));
    /// assert_eq!(sibling_tokens.next(), Some(fourth_child_token));
    /// assert!(sibling_tokens.next().is_none());
    /// ```
    pub fn following_siblings_tokens<'a, T>(self, arena: &'a Arena<T>)
        -> FollowingSiblingTokens<'a, T> {
        let next_sibling = match arena.get(self) {
            Some(n) => n.next_sibling,
            None => panic!("Invalid token")
        };
        FollowingSiblingTokens { arena, node_token: next_sibling }
    }

    /// Returns an iterator of tokens of child nodes in the order of insertion.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let first_child_token = root_token.append(&mut arena, "Romance");
    /// let second_child_token = root_token.append(&mut arena, "Germanic");
    /// let third_child_token = root_token.append(&mut arena, "Slavic");
    /// let fourth_child_token = root_token.append(&mut arena, "Hellenic");
    ///
    /// let mut children_tokens = root_token.children_tokens(&arena);
    /// assert_eq!(children_tokens.next(), Some(first_child_token));
    /// assert_eq!(children_tokens.next(), Some(second_child_token));
    /// assert_eq!(children_tokens.next(), Some(third_child_token));
    /// assert_eq!(children_tokens.next(), Some(fourth_child_token));
    /// assert!(children_tokens.next().is_none());
    /// ```
    pub fn children_tokens<'a, T>(self, arena: &'a Arena<T>)
        -> ChildrenTokens<'a, T> {
        let first_child = match arena.get(self) {
            Some(n) => n.first_child,
            None => panic!("Invalid token")
        };
        ChildrenTokens { arena, node_token: first_child }
    }

    /// Returns an iterator of references of ancestor nodes.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let child_token = root_token.append(&mut arena, "Germanic");
    /// let grandchild_token = child_token.append(&mut arena, "Swedish");
    /// let mut ancestors = grandchild_token.ancestors(&arena);
    ///
    /// assert_eq!(ancestors.next().unwrap().data, "Germanic");
    /// assert_eq!(ancestors.next().unwrap().data, "Indo-European");
    /// assert!(ancestors.next().is_none());
    /// ```
    pub fn ancestors<'a, T>(self, arena: &'a Arena<T>) -> Ancestors<'a, T> {
        Ancestors { token_iter: self.ancestors_tokens(arena) }
    }

    /// Returns an iterator of references of sibling nodes preceding the current
    /// node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, "Romance");
    /// root_token.append(&mut arena, "Germanic");
    /// let third_child_token = root_token.append(&mut arena, "Slavic");
    /// root_token.append(&mut arena, "Celtic");
    ///
    /// let mut siblings = third_child_token.preceding_siblings(&arena);
    /// assert_eq!(siblings.next().unwrap().data, "Germanic");
    /// assert_eq!(siblings.next().unwrap().data, "Romance");
    /// assert!(siblings.next().is_none());
    /// ```
    pub fn preceding_siblings<'a, T>(self, arena: &'a Arena<T>)
        -> PrecedingSiblings<'a, T> {
        PrecedingSiblings { token_iter: self.preceding_siblings_tokens(arena) }
    }

    /// Returns an iterator of references of sibling nodes following the current
    /// node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, "Romance");
    /// let second_child_token = root_token.append(&mut arena, "Germanic");
    /// root_token.append(&mut arena, "Slavic");
    /// root_token.append(&mut arena, "Hellenic");
    ///
    /// let mut siblings = second_child_token.following_siblings(&arena);
    /// assert_eq!(siblings.next().unwrap().data, "Slavic");
    /// assert_eq!(siblings.next().unwrap().data, "Hellenic");
    /// assert!(siblings.next().is_none());
    /// ```
    pub fn following_siblings<'a, T>(self, arena: &'a Arena<T>)
        -> FollowingSiblings<'a, T> {
        FollowingSiblings { token_iter: self.following_siblings_tokens(arena) }
    }

    /// Returns an iterator of child node references in the order of insertion.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let first_child_token = root_token.append(&mut arena, "Germanic");
    /// let second_child_token = root_token.append(&mut arena, "Romance");
    /// let third_child_token = root_token.append(&mut arena, "Slavic");
    /// let fourth_child_token = root_token.append(&mut arena, "Celtic");
    ///
    /// let mut children = root_token.children(&arena);
    /// assert_eq!(children.next().unwrap().data, "Germanic");
    /// assert_eq!(children.next().unwrap().data, "Romance");
    /// assert_eq!(children.next().unwrap().data, "Slavic");
    /// assert_eq!(children.next().unwrap().data, "Celtic");
    /// assert!(children.next().is_none());
    /// ```
    pub fn children<'a, T>(self, arena: &'a Arena<T>) -> Children<'a, T> {
        Children { token_iter: self.children_tokens(arena) }
    }

    /// Returns an iterator of mutable ancestor node references.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = 1usize;
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let child_token = root_token.append(&mut arena, 2usize);
    /// let grandchild_token = child_token.append(&mut arena, 3usize);
    /// let great_grandchild_token = grandchild_token.append(&mut arena, 4usize);
    /// let ggreat_grandchild_token = great_grandchild_token.append(&mut arena, 5usize);
    ///
    /// for x in ggreat_grandchild_token.ancestors_mut(&mut arena) {
    ///     x.data += 2;
    /// }
    ///
    /// let mut ancestors = ggreat_grandchild_token.ancestors(&arena);
    /// assert_eq!(ancestors.next().unwrap().data, 6usize);
    /// assert_eq!(ancestors.next().unwrap().data, 5usize);
    /// assert_eq!(ancestors.next().unwrap().data, 4usize);
    /// assert_eq!(ancestors.next().unwrap().data, 3usize);
    /// assert!(ancestors.next().is_none());
    /// ```
    pub fn ancestors_mut<'a, T>(self, arena: &'a mut Arena<T>)
        -> AncestorsMut<'a, T> {
        AncestorsMut {
            arena: arena as *mut Arena<T>,
            node_token: Some(self),
            marker: PhantomData::default()
        }
    }

    /// Returns an iterator of mutable references of sibling nodes that follow
    /// the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = 1usize;
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, 2usize);
    /// let second_child_token = root_token.append(&mut arena, 3usize);
    /// root_token.append(&mut arena, 4usize);
    /// root_token.append(&mut arena, 5usize);
    ///
    /// for x in second_child_token.following_siblings_mut(&mut arena) {
    ///     x.data += 2;
    /// }
    ///
    /// let mut children = root_token.children(&arena);
    /// assert_eq!(children.next().unwrap().data, 2usize);
    /// assert_eq!(children.next().unwrap().data, 3usize);
    /// assert_eq!(children.next().unwrap().data, 6usize);
    /// assert_eq!(children.next().unwrap().data, 7usize);
    /// assert!(children.next().is_none());
    /// ```
    pub fn following_siblings_mut<'a, T>(self, arena: &'a mut Arena<T>)
        -> FollowingSiblingsMut<'a, T> {
        let next_sibling = match arena.get(self) {
            Some(n) => n.next_sibling,
            None => panic!("Invalid token")
        };
        FollowingSiblingsMut {
            arena: arena as *mut Arena<T>,
            node_token: next_sibling,
            marker: PhantomData::default()
        }
    }

    /// Returns an iterator of mutable references of sibling nodes that precede
    /// the current node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = 1usize;
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, 2usize);
    /// root_token.append(&mut arena, 3usize);
    /// root_token.append(&mut arena, 4usize);
    /// let fourth_child_token = root_token.append(&mut arena, 5usize);
    ///
    /// for x in fourth_child_token.preceding_siblings_mut(&mut arena) {
    ///     x.data += 5;
    /// }
    ///
    /// let mut children = root_token.children(&arena);
    /// assert_eq!(children.next().unwrap().data, 7usize);
    /// assert_eq!(children.next().unwrap().data, 8usize);
    /// assert_eq!(children.next().unwrap().data, 9usize);
    /// assert_eq!(children.next().unwrap().data, 5usize);
    /// assert!(children.next().is_none());
    /// ```
    pub fn preceding_siblings_mut<'a, T>(self, arena: &'a mut Arena<T>)
        -> PrecedingSiblingsMut<'a, T> {
        let previous_sibling = match arena.get(self) {
            Some(n) => n.previous_sibling,
            None => panic!("Invalid token")
        };
        PrecedingSiblingsMut {
            arena: arena as *mut Arena<T>,
            node_token: previous_sibling,
            marker: PhantomData::default()
        }
    }

    /// Returns an iterator of mutable references of child nodes in the order of
    /// insertion.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    ///
    /// let root_data = 1usize;
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, 2usize);
    /// root_token.append(&mut arena, 3usize);
    /// let third_child_token = root_token.append(&mut arena, 4usize);
    /// root_token.append(&mut arena, 5usize);
    /// let grandchild = third_child_token.append(&mut arena, 10usize);
    ///
    /// for x in root_token.children_mut(&mut arena) {
    ///     x.data += 10;
    /// }
    ///
    /// let mut children = root_token.children(&arena);
    /// assert_eq!(children.next().unwrap().data, 12);
    /// assert_eq!(children.next().unwrap().data, 13);
    /// assert_eq!(children.next().unwrap().data, 14);
    /// assert_eq!(children.next().unwrap().data, 15);
    /// assert_eq!(arena.get(grandchild).unwrap().data, 10);
    /// assert!(children.next().is_none());
    /// ```
    pub fn children_mut<'a, T>(self, arena: &'a mut Arena<T>)
        -> ChildrenMut<'a, T> {
        let first_child = match arena.get(self) {
            Some(n) => n.first_child,
            None => panic!("Invalid token")
        };
        ChildrenMut {
            arena: arena as *mut Arena<T>,
            node_token: first_child,
            marker: PhantomData::default()
        }
    }

    /// Returns an iterator of tokens of subtree nodes of the given node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// let first_child = root_token.append(&mut arena, "Romance");
    /// let second_child = root_token.append(&mut arena, "Germanic");
    /// let third_child = root_token.append(&mut arena, "Slavic");
    /// let first_grandchild = second_child.append(&mut arena, "English");
    /// let second_grandchild = second_child.append(&mut arena, "Icelandic");
    /// let fourth_child = root_token.append(&mut arena, "Celtic");
    ///
    /// let mut subtree = root_token.subtree_tokens(&arena, TraversalOrder::Pre);
    /// assert_eq!(subtree.next(), Some(root_token));
    /// assert_eq!(subtree.next(), Some(first_child));
    /// assert_eq!(subtree.next(), Some(second_child));
    /// assert_eq!(subtree.next(), Some(first_grandchild));
    /// assert_eq!(subtree.next(), Some(second_grandchild));
    /// assert_eq!(subtree.next(), Some(third_child));
    /// assert_eq!(subtree.next(), Some(fourth_child));
    /// assert!(subtree.next().is_none());
    ///
    /// let mut subtree = second_grandchild.subtree_tokens(&arena, TraversalOrder::Pre);
    /// assert_eq!(subtree.next(), Some(second_grandchild));
    /// assert!(subtree.next().is_none());
    /// ```
    pub fn subtree_tokens<'a, T>(self, arena: &'a Arena<T>, order: TraversalOrder)
        -> SubtreeTokens<'a, T> {
        let preord_tokens_next = |iter: &mut SubtreeTokens<T>| 
            depth_first_tokens_next(iter, preorder_next);
        let postord_tokens_next = |iter: &mut SubtreeTokens<T>| 
            depth_first_tokens_next(iter, postorder_next);
        match order {
            TraversalOrder::Pre => SubtreeTokens {
                arena,
                subtree_root: self,
                node_token: Some(self),
                branch: Branch::Child,
                curr_level: VecDeque::new(),  // unused field
                next_level: VecDeque::new(),  // unused field
                next: preord_tokens_next
            },
            TraversalOrder::Post => {
                let (node_token, branch) =
                    postorder_next(self, self, Branch::Child, arena);
                SubtreeTokens {
                    arena,
                    subtree_root: self,
                    node_token,
                    branch,
                    curr_level: VecDeque::new(),  // unused field
                    next_level: VecDeque::new(),  // unused field
                    next: postord_tokens_next
                }
            },
            TraversalOrder::Level => {
                SubtreeTokens {
                    arena,
                    subtree_root: self,  // unused field
                    node_token: None,  // unused field
                    branch: Branch::None,  // unused field
                    curr_level: std::iter::once(self).collect(),
                    next_level: VecDeque::new(),
                    next: breadth_first_tokens_next
                }
            }
        }
    }

    /// Returns an iterator of references of subtree nodes of the given node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = "Indo-European";
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, "Romance");
    /// root_token.append(&mut arena, "Germanic");
    /// let third_child = root_token.append(&mut arena, "Slavic");
    /// root_token.append(&mut arena, "Celtic");
    /// third_child.append(&mut arena, "Polish");
    /// third_child.append(&mut arena, "Slovakian");
    ///
    /// let mut subtree = root_token.subtree(&arena, TraversalOrder::Pre);
    /// assert_eq!(subtree.next().unwrap().data, "Indo-European");
    /// assert_eq!(subtree.next().unwrap().data, "Romance");
    /// assert_eq!(subtree.next().unwrap().data, "Germanic");
    /// assert_eq!(subtree.next().unwrap().data, "Slavic");
    /// assert_eq!(subtree.next().unwrap().data, "Polish");
    /// assert_eq!(subtree.next().unwrap().data, "Slovakian");
    /// assert_eq!(subtree.next().unwrap().data, "Celtic");
    /// assert!(subtree.next().is_none());
    /// ```
    pub fn subtree<'a, T>(self, arena: &'a Arena<T>, order: TraversalOrder)
        -> Subtree<'a, T> {
        Subtree {
            arena,
            iter: self.subtree_tokens(arena, order)
        }
    }

    /// Returns an iterator of mutable references of subtree nodes of the given
    /// node.
    ///
    /// # Panics:
    ///
    /// Panics if the token does not correspond to a node in the arena.
    ///
    /// # Examples:
    ///
    /// ```
    /// use atree::Arena;
    /// use atree::iter::TraversalOrder;
    ///
    /// let root_data = 1usize;
    /// let (mut arena, root_token) = Arena::with_data(root_data);
    ///
    /// root_token.append(&mut arena, 2usize);
    /// root_token.append(&mut arena, 3usize);
    /// let third_child = root_token.append(&mut arena, 4usize);
    /// root_token.append(&mut arena, 5usize);
    /// third_child.append(&mut arena, 10usize);
    /// third_child.append(&mut arena, 20usize);
    ///
    /// for x in root_token.subtree_mut(&mut arena, TraversalOrder::Pre) {
    ///     x.data += 100;
    /// }
    ///
    /// let mut subtree = root_token.subtree(&arena, TraversalOrder::Pre);
    /// assert_eq!(subtree.next().unwrap().data, 101);
    /// assert_eq!(subtree.next().unwrap().data, 102);
    /// assert_eq!(subtree.next().unwrap().data, 103);
    /// assert_eq!(subtree.next().unwrap().data, 104);
    /// assert_eq!(subtree.next().unwrap().data, 110);
    /// assert_eq!(subtree.next().unwrap().data, 120);
    /// assert_eq!(subtree.next().unwrap().data, 105);
    /// assert!(subtree.next().is_none());
    /// ```
    pub fn subtree_mut<'a, T>(self, arena: &'a mut Arena<T>, order: TraversalOrder)
        -> SubtreeMut<'a, T> {
        SubtreeMut {
            arena: arena as *mut Arena<T>,
            iter: self.subtree_tokens(arena, order),
            marker: PhantomData::default()
        }
    }

    /// Removes all descendants of the current node.
    pub (crate) fn remove_descendants<T>(self, arena: &mut Arena<T>) {
        // This will not silently fail since postorder_next will panic if self
        // isn't valid.  This won't do anything if self has no descendants, but
        // that's the intended behavior.
        if let (Some(mut token), mut branch) =
            postorder_next(self, self, Branch::Child, arena) {
            while branch != Branch::None {
                let (t, b) = postorder_next(token, self, branch, arena);
                arena.allocator.remove(token);  // should not fail (not here anyway)
                token = t.unwrap();
                branch = b;
            }
            arena[self].first_child = None;
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    #[allow(clippy::cognitive_complexity)]
    fn replace_node() {
        // root node that we will attach subtrees to
        let root_data = "Indo-European";
        let (mut arena, root) = Arena::with_data(root_data);
       
        // the Germanic branch
        let germanic = root.append(&mut arena, "Germanic");
        let west = germanic.append(&mut arena, "West");
        west.append(&mut arena, "Scots");
        west.append(&mut arena, "English");
       
        // the slavic branch
        let slavic = root.append(&mut arena, "Slavic");
        slavic.append(&mut arena, "Polish");
        slavic.append(&mut arena, "Russian");
       
        let mut iter = root.subtree(&arena, TraversalOrder::Pre)
            .map(|x| x.data);
        assert_eq!(iter.next(), Some("Indo-European"));
        assert_eq!(iter.next(), Some("Germanic"));
        assert_eq!(iter.next(), Some("West"));
        assert_eq!(iter.next(), Some("Scots"));
        assert_eq!(iter.next(), Some("English"));
        assert_eq!(iter.next(), Some("Slavic"));
        assert_eq!(iter.next(), Some("Polish"));
        assert_eq!(iter.next(), Some("Russian"));
        assert!(iter.next().is_none());

        // the Romance branch
        let romance = arena.new_node("Romance");
        romance.append(&mut arena, "French");
        romance.append(&mut arena, "Italian");
       
        // replace_node germanic with romance
        germanic.replace_node(&mut arena, romance).unwrap();
       
        let mut iter = root.subtree(&arena, TraversalOrder::Pre)
            .map(|x| x.data);
        assert_eq!(iter.next(), Some("Indo-European"));
        assert_eq!(iter.next(), Some("Romance"));
        assert_eq!(iter.next(), Some("French"));
        assert_eq!(iter.next(), Some("Italian"));
        assert_eq!(iter.next(), Some("Slavic"));
        assert_eq!(iter.next(), Some("Polish"));
        assert_eq!(iter.next(), Some("Russian"));
        assert!(iter.next().is_none());

        // How about the other way around (replacing the slavic branch instead
        slavic.replace_node(&mut arena, germanic).unwrap();

        let mut iter = root.subtree(&arena, TraversalOrder::Pre)
            .map(|x| x.data);
        assert_eq!(iter.next(), Some("Indo-European"));
        assert_eq!(iter.next(), Some("Romance"));
        assert_eq!(iter.next(), Some("French"));
        assert_eq!(iter.next(), Some("Italian"));
        assert_eq!(iter.next(), Some("Germanic"));
        assert_eq!(iter.next(), Some("West"));
        assert_eq!(iter.next(), Some("Scots"));
        assert_eq!(iter.next(), Some("English"));
        assert!(iter.next().is_none());
    }

    #[test]
    fn subtree_tokens_postord() {
        let root_data = 1usize;
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        let first_child = root_token.append(&mut arena, 2usize);
        let second_child = root_token.append(&mut arena, 3usize);
        let third_child = root_token.append(&mut arena, 4usize);
        let first_grandchild = first_child.append(&mut arena, 0usize);
        let fourth_child = root_token.append(&mut arena, 5usize);
        let second_grandchild = second_child.append(&mut arena, 10usize);
        let third_grandchild = second_child.append(&mut arena, 20usize);
        let great_grandchild = third_grandchild.append(&mut arena, 20usize);
       
        let mut subtree = root_token.subtree_tokens(&arena, TraversalOrder::Post);
        assert_eq!(subtree.next(), Some(first_grandchild));
        assert_eq!(subtree.next(), Some(first_child));
        assert_eq!(subtree.next(), Some(second_grandchild));
        assert_eq!(subtree.next(), Some(great_grandchild));
        assert_eq!(subtree.next(), Some(third_grandchild));
        assert_eq!(subtree.next(), Some(second_child));
        assert_eq!(subtree.next(), Some(third_child));
        assert_eq!(subtree.next(), Some(fourth_child));
        assert_eq!(subtree.next(), Some(root_token));
        assert!(subtree.next().is_none());
       
        let mut subtree = great_grandchild.subtree_tokens(&arena, TraversalOrder::Post);
        assert_eq!(subtree.next(), Some(great_grandchild));
        assert!(subtree.next().is_none());
    }

    #[test]
    fn subtree_tokens_levelord() {
        let root_data = 1usize;
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        let first_child = root_token.append(&mut arena, 2usize);
        let second_child = root_token.append(&mut arena, 3usize);
        let third_child = root_token.append(&mut arena, 4usize);
        let first_grandchild = second_child.append(&mut arena, 10usize);
        let second_grandchild = second_child.append(&mut arena, 20usize);
        let fourth_child = root_token.append(&mut arena, 5usize);
       
        let mut subtree = root_token.subtree_tokens(&arena, TraversalOrder::Level);
        assert_eq!(subtree.next(), Some(root_token));
        assert_eq!(subtree.next(), Some(first_child));
        assert_eq!(subtree.next(), Some(second_child));
        assert_eq!(subtree.next(), Some(third_child));
        assert_eq!(subtree.next(), Some(fourth_child));
        assert_eq!(subtree.next(), Some(first_grandchild));
        assert_eq!(subtree.next(), Some(second_grandchild));
        assert!(subtree.next().is_none());
       
        let mut subtree = second_grandchild.subtree_tokens(&arena, TraversalOrder::Level);
        assert_eq!(subtree.next(), Some(second_grandchild));
        assert!(subtree.next().is_none());
    }

    #[test]
    fn subtree_postord() {
        let root_data = "Indo-European";
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        root_token.append(&mut arena, "Romance");
        root_token.append(&mut arena, "Germanic");
        let third_child = root_token.append(&mut arena, "Celtic");
        root_token.append(&mut arena, "Slavic");
        third_child.append(&mut arena, "Ulster");
        third_child.append(&mut arena, "Gaulish");
       
        let mut subtree = root_token.subtree(&arena, TraversalOrder::Post);
        assert_eq!(subtree.next().unwrap().data, "Romance");
        assert_eq!(subtree.next().unwrap().data, "Germanic");
        assert_eq!(subtree.next().unwrap().data, "Ulster");
        assert_eq!(subtree.next().unwrap().data, "Gaulish");
        assert_eq!(subtree.next().unwrap().data, "Celtic");
        assert_eq!(subtree.next().unwrap().data, "Slavic");
        assert_eq!(subtree.next().unwrap().data, "Indo-European");
        assert!(subtree.next().is_none());
    }

    #[test]
    fn subtree_levelord() {
        let root_data = "Indo-European";
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        root_token.append(&mut arena, "Romance");
        root_token.append(&mut arena, "Germanic");
        let third_child = root_token.append(&mut arena, "Slavic");
        root_token.append(&mut arena, "Hellenic");
        third_child.append(&mut arena, "Russian");
        third_child.append(&mut arena, "Ukrainian");
       
        let mut subtree = root_token.subtree(&arena, TraversalOrder::Level);
        assert_eq!(subtree.next().unwrap().data, "Indo-European");
        assert_eq!(subtree.next().unwrap().data, "Romance");
        assert_eq!(subtree.next().unwrap().data, "Germanic");
        assert_eq!(subtree.next().unwrap().data, "Slavic");
        assert_eq!(subtree.next().unwrap().data, "Hellenic");
        assert_eq!(subtree.next().unwrap().data, "Russian");
        assert_eq!(subtree.next().unwrap().data, "Ukrainian");
        assert!(subtree.next().is_none());
    }

    #[test]
    fn subtree_postord_mut() {
        let root_data = 1usize;
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        root_token.append(&mut arena, 2usize);
        root_token.append(&mut arena, 3usize);
        let third_child = root_token.append(&mut arena, 4usize);
        root_token.append(&mut arena, 5usize);
        third_child.append(&mut arena, 10usize);
        third_child.append(&mut arena, 20usize);
       
        for x in root_token.subtree_mut(&mut arena, TraversalOrder::Post) {
            x.data += 100;
        }
       
        let mut subtree = root_token.subtree(&arena, TraversalOrder::Post);
        assert_eq!(subtree.next().unwrap().data, 102);
        assert_eq!(subtree.next().unwrap().data, 103);
        assert_eq!(subtree.next().unwrap().data, 110);
        assert_eq!(subtree.next().unwrap().data, 120);
        assert_eq!(subtree.next().unwrap().data, 104);
        assert_eq!(subtree.next().unwrap().data, 105);
        assert_eq!(subtree.next().unwrap().data, 101);
        assert!(subtree.next().is_none());
    }

    #[test]
    fn subtree_levelord_mut() {
        let root_data = 1usize;
        let (mut arena, root_token) = Arena::with_data(root_data);
       
        root_token.append(&mut arena, 2usize);
        root_token.append(&mut arena, 3usize);
        let third_child = root_token.append(&mut arena, 4usize);
        root_token.append(&mut arena, 5usize);
        third_child.append(&mut arena, 10usize);
        third_child.append(&mut arena, 20usize);
       
        for x in root_token.subtree_mut(&mut arena, TraversalOrder::Level) {
            x.data += 100;
        }
       
        let mut subtree = root_token.subtree(&arena, TraversalOrder::Level);
        assert_eq!(subtree.next().unwrap().data, 101);
        assert_eq!(subtree.next().unwrap().data, 102);
        assert_eq!(subtree.next().unwrap().data, 103);
        assert_eq!(subtree.next().unwrap().data, 104);
        assert_eq!(subtree.next().unwrap().data, 105);
        assert_eq!(subtree.next().unwrap().data, 110);
        assert_eq!(subtree.next().unwrap().data, 120);
        assert!(subtree.next().is_none());
    }

    #[test]
    fn remove_descendants() {
        let root_data = 1usize;
        let (mut arena, root_token) = Arena::with_data(root_data);

        let first_child = root_token.append(&mut arena, 2usize);
        let second_child = root_token.append(&mut arena, 3usize);
        let third_child = root_token.append(&mut arena, 4usize);
        let fourth_child = root_token.append(&mut arena, 5usize);
        let grandchild_1 = third_child.append(&mut arena, 10usize);
        third_child.append(&mut arena, 20usize);
        grandchild_1.append(&mut arena, 100usize);

        assert_eq!(arena.node_count(), 8);

        third_child.remove_descendants(&mut arena);

        let mut subtree = root_token.subtree_tokens(&arena, TraversalOrder::Pre);
        assert_eq!(subtree.next(), Some(root_token));
        assert_eq!(subtree.next(), Some(first_child));
        assert_eq!(subtree.next(), Some(second_child));
        assert_eq!(subtree.next(), Some(third_child));
        assert_eq!(subtree.next(), Some(fourth_child));
        assert!(subtree.next().is_none());

        println!("{:?}", arena.allocator);
        assert_eq!(arena.node_count(), 5);
    }
}