1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

use std::fmt::{Debug, Display, Formatter};
use std::num::NonZeroUsize;

use crate::iter::*;
use crate::prelude::*;

/// A node ID into the internal tree.
///
/// # Important:
///
/// Is not checked that the [NodeId] was not from *another* tree.
///
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct NodeId(NonZeroUsize);

impl NodeId {
    pub fn from_index(n: usize) -> Self {
        NodeId(NonZeroUsize::new(n + 1).unwrap())
    }

    pub fn to_index(self) -> usize {
        self.0.get() - 1
    }
}

impl Display for NodeId {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write! {f, "NodeId({})", self.0}
    }
}

impl From<usize> for NodeId {
    fn from(x: usize) -> Self {
        NodeId::from_index(x)
    }
}

impl From<NodeId> for usize {
    fn from(x: NodeId) -> Self {
        x.to_index()
    }
}

/// An immutable view of the [Self::data] in the [Tree] with their [NodeId].
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Node<'a, T: 'a> {
    /// Node ID.
    pub id: NodeId,
    /// Data.
    pub data: &'a T,
    /// Tree containing the node.
    pub(crate) tree: &'a Tree<T>,
}

impl<T: Debug> Node<'_, T> {
    pub fn level(&self) -> usize {
        self.tree.level[self.id.to_index()]
    }
    pub fn parent(&self) -> usize {
        self.tree.parent[self.id.to_index()]
    }

    /// An [Iterator] of the parents from this [Node].
    pub fn parents(&self) -> ParentIter<'_, T> {
        ParentIter {
            parent: self.parent(),
            node: self.id,
            tree: self.tree,
        }
    }

    /// An [Iterator] of the children from this [Node].
    pub fn children(&self) -> ChildrenIter<'_, T> {
        ChildrenIter::new(self.id, self.tree)
    }

    /// An [Iterator] of the siblings from this [Node].
    pub fn siblings(&self) -> SiblingsIter<'_, T> {
        SiblingsIter {
            pos: 0,
            level: self.level(),
            node: self.id,
            tree: self.tree,
        }
    }
}

impl<T: Debug> Debug for Node<'_, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write! {f, "{:?}:{:?}", self.id, self.data}
    }
}

impl<T: Display> Display for Node<'_, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write! {f, "{}", self.data}
    }
}

/// A mutable view of the [Self::data] in the [Tree] with their [NodeId].
#[derive(PartialEq, Eq, PartialOrd, Ord)]
pub struct NodeMut<'a, T: 'a> {
    /// Node ID.
    pub id: NodeId,
    /// Data.
    pub data: &'a mut T,
}

impl<T: Debug> Debug for NodeMut<'_, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write! {f, "{:?}:{:?}", self.id, self.data}
    }
}

impl<T: Display> Display for NodeMut<'_, T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write! {f, "{}", self.data}
    }
}

/// A mutable reference in the [Tree] of the [NodeId].
#[derive(Debug)]
pub struct TreeMut<'a, T: 'a> {
    /// Node ID.
    pub id: NodeId,
    /// Node ID of the parent.
    pub parent: NodeId,
    /// Tree containing the node.
    pub tree: &'a mut Tree<T>,
}

impl<'a, T: Debug + 'a> TreeMut<'a, T> {
    pub fn get_parent_level(&self) -> usize {
        self.tree.get_level(self.parent)
    }

    /// Create a new [Node<T>], record the parent & the loop, and continue to
    /// return [NodeMut<T>] so you can add more in a builder pattern
    pub fn push(&mut self, data: T) -> TreeMut<T>
    where
        T: Debug,
    {
        let id = self.append(data);
        self.tree._make_tree_mut(id, id)
    }

    /// Create a new [Node<T>], record the parent & the loop, and
    /// return the created [NodeId]
    pub fn append(&mut self, data: T) -> NodeId
    where
        T: Debug,
    {
        let level = self.get_parent_level() + 1;

        self.tree.push_with_level(data, level, self.parent)
    }
}