/// A simple flat 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
}

/// Nodes themselves are not held onto and used, instead we use a NodeId,
/// only valid in the context of a particular Tree. There is not a great
/// way to enforce this validity that I know of, unfortunately.
#[derive(Copy, Clone)]
pub struct NodeId(usize);

impl<T> Tree<T> {
    /// Create a new Tree with a root element.
    /// You should only make one Tree in any given context.
    /// Otherwise there are safety risks with using the wrong NodeId for a Tree.
    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;
    }
}