1 files changed, 133 insertions, 0 deletions
diff --git a/src/tree.rs b/src/tree.rs
new file mode 100644
index 0000000..02dc749
--- /dev/null
+++ b/src/tree.rs
@@ -0,0 +1,133 @@
+/// A simple append-only tree data structure. Represented as a Vec.
+pub struct Tree<T>(Vec<Node<T>>);
+
+/// The associated Node to the Tree.
+/// Somewhat optimized for memory usage rather than CPU cycles.
+/// firstborn is accessed as oldest_child and youngest_child is computed.
+pub struct Node<T> {
+    parent: Option<NodeId>,
+    previous_sibling: Option<NodeId>,
+    next_sibling: Option<NodeId>,
+    firstborn: Option<NodeId>,
+    data: T
+}
+
+#[derive(Copy, Clone)]
+pub struct NodeId(usize);
+
+impl<T> Tree<T> {
+    /// Create a new Tree with a root element.
+    pub fn new(data: T) -> Tree<T> {
+        Tree(vec![Node {
+            parent: None, previous_sibling: None,
+            next_sibling: None, firstborn: None,
+            data
+        }])
+    }
+
+    /// Get a raw Node for viewing familial relations.
+    /// This unwrap() should be safe with one Tree
+    /// instance as NodeIds may not be directly constructed.
+    fn get(&self, id: NodeId) -> &Node<T> {
+        &self.0[id.0]
+    }
+
+    /// Get a raw Node for modifying familial relations.
+    /// This unwrap() should be safe with one Tree
+    /// instance as NodeIds may not be directly constructed.
+    fn get_mut(&mut self, id: NodeId) -> &mut Node<T> {
+        &mut self.0[id.0]
+    }
+
+    /// Get the data associated with a Node.
+    pub fn data(&mut self, id: NodeId) -> &mut T {
+        &mut self.get_mut(id).data
+    }
+
+    /// Get the data associated with a Node.
+    // pub fn data(&self, id: NodeId) -> Option<T> {
+    //     match self.0.get(id.0) {
+    //         Some(Node{ data, .. }) => Some(*data),
+    //         None => None
+    //     }
+    // }
+
+    /// Get the root node of the Tree.
+    pub fn root(&self) -> NodeId { NodeId(0) }
+
+    /// Get the root node(s) of the Tree.
+    // pub fn root(&self) -> Vec<NodeId> {
+    //     let mut roots = Vec::new();
+    //     for (i, node) in self.0.iter().enumerate() {
+    //         if let Node{ parent, .. } = node && let None = parent {
+    //             roots.push(NodeId(i));
+    //         }
+    //     }
+    //     return roots;
+    // }
+
+    /// Get all the direct children of a Node.
+    pub fn children(&self, id: NodeId) -> Vec<NodeId> {
+        let mut result = Vec::new();
+        if let Some(node) = self.0.get(id.0) {
+            let mut child = node.firstborn;
+            while let Some(id) = child {
+                result.push(id);
+                child = self.0.get(id.0).map(|x| x.next_sibling).flatten();
+            }
+        }
+        return result;
+    }
+
+    /// Get the eldest child of a Node.
+    pub fn eldest_child(&self, id: NodeId) -> Option<NodeId> {
+        self.get(id).firstborn
+    }
+
+    /// Get the youngest child of a Node.
+    pub fn youngest_child(&self, id: NodeId) -> Option<NodeId> {
+        let mut result = None;
+        if let Some(node) = self.0.get(id.0) {
+            let mut child = node.firstborn;
+            while let Some(id) = child {
+                result = Some(id);
+                child = self.0.get(id.0).map(|x| x.next_sibling).flatten();
+            }
+        }
+        return result;
+    }
+
+    /// Get the previous sibling of a Node.
+    pub fn previous_sibling(&self, id: NodeId) -> Option<NodeId> {
+        self.get(id).parent
+    }
+
+    /// Get the next sibling of a Node.
+    pub fn next_sibling(&self, id: NodeId) -> Option<NodeId> {
+        self.get(id).parent
+    }
+
+    /// Get the parent of a Node.
+    pub fn parent(&self, id: NodeId) -> Option<NodeId> {
+        self.get(id).parent
+    }
+
+    /// Add a Node as a direct child of another Node in the tree.
+    pub fn add_child(&mut self, parent: NodeId, data: T) -> NodeId {
+        let id = NodeId(self.0.len() - 1);
+        let previous_sibling = self.youngest_child(parent);
+        if let Some(node) = previous_sibling {
+            self.get_mut(node).next_sibling = Some(id);
+        } else {
+            self.get_mut(parent).firstborn = Some(id);
+        }
+        self.0.push(Node {
+            parent: Some(parent),
+            previous_sibling,
+            next_sibling: None,
+            firstborn: None,
+            data: data
+        });
+        return id;
+    }
+}