#[cfg(feature = "no_std")]
use std::prelude::*;

use std::fmt;
use std::ops::{Index, IndexMut};

use compile::{Token, Range};

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(usize);
impl From<usize> for NodeId {
    fn from(id: usize) -> Self {
        NodeId(id)
    }
}
impl From<NodeId> for usize {
    fn from(id: NodeId) -> usize {
        id.0
    }
}

#[derive(Clone)]
pub struct Node {
    pub token: Token,
    pub range: Range,
    pub parent: Option<NodeId>,
    pub next_sibling: Option<NodeId>,
    pub child: Option<NodeId>
}
impl Node {
    pub fn children<'a>(&self, arena: &'a Tree) -> NodeIter<'a> {
        NodeIter(arena, self.child)
    }
}
impl fmt::Debug for Node {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?} {:?}", self.token, self.range)?;
        Ok(())
    }
}

pub struct NodeIter<'a>(&'a Tree, Option<NodeId>);
impl<'a> Iterator for NodeIter<'a> {
    type Item = NodeId;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(next) = self.1 {
            self.1 = self.0[next].next_sibling;
            Some(next)
        } else {
            None
        }
    }
}

pub struct Checkpoint {
    cursor: Option<NodeId>
}

#[derive(Default)]
pub struct TreeBuilder {
    arena: Vec<Node>,
    parent: Option<NodeId>,
    cursor: Option<NodeId>
}
impl TreeBuilder {
    fn insert(&mut self, token: Token, range: Range) -> NodeId {
        let id = NodeId::from(self.arena.len());
        self.arena.push(Node {
            token,
            range,
            parent: self.parent,
            next_sibling: None,
            child: None
        });
        if let Some(prev) = self.cursor {
            self.arena[usize::from(prev)].next_sibling = Some(id);
        }
        if let Some(parent) = self.parent {
            self.arena[usize::from(parent)].child = self.arena[usize::from(parent)].child.or(Some(id));
        }
        id
    }
    pub fn leaf(&mut self, token: Token, range: Range) {
        self.cursor = Some(self.insert(token, range));
    }
    pub fn start_internal(&mut self, token: Token, range: Range) {
        self.parent = Some(self.insert(token, range));
        self.cursor = None;
    }
    pub fn finish_internal(&mut self) {
        self.cursor = self.parent;
        self.parent = self.parent.and_then(|parent| self.arena[usize::from(parent)].parent);
    }
    pub fn checkpoint(&self) -> Checkpoint {
        Checkpoint {
            cursor: self.cursor
        }
    }
    pub fn start_internal_at(&mut self, checkpoint: Checkpoint, token: Token, range: Range) {
        let parent = if let Some(from) = checkpoint.cursor {
            let id = NodeId::from(self.arena.len());
            self.arena.push(Node {
                token,
                range,
                parent: self.parent,
                next_sibling: None,
                child: self.arena[usize::from(from)].next_sibling
            });
            self.arena[usize::from(from)].next_sibling = Some(id);
            id
        } else if let Some(parent) = self.parent {
            let id = NodeId::from(self.arena.len());
            self.arena.push(Node {
                token,
                range,
                parent: self.parent,
                next_sibling: None,
                child: self.arena[usize::from(parent)].child
            });
            self.arena[usize::from(parent)].child = Some(id);
            id
        } else {
            let id = NodeId::from(self.arena.len());
            self.arena.push(Node {
                token,
                range,
                parent: None,
                next_sibling: None,
                child: self.cursor
            });
            id
        };
        // Update parent
        let mut next = self.arena[usize::from(parent)].child;
        while let Some(node) = next {
            let node = &mut self.arena[usize::from(node)];
            next = node.next_sibling;
            node.parent = Some(parent);
        }
        self.parent = Some(parent);
        self.cursor = None;
    }
    pub fn finish(self) -> Tree {
        assert!(self.cursor.is_some(), "no item");
        let cursor = self.cursor.unwrap();

        Tree {
            arena: self.arena.into_boxed_slice(),
            root: cursor
        }
    }
}

#[derive(Clone)]
pub struct Tree {
    pub arena: Box<[Node]>,
    pub root: NodeId
}
impl Index<NodeId> for Tree {
    type Output = Node;
    fn index(&self, index: NodeId) -> &Node {
        &self.arena[usize::from(index)]
    }
}
impl IndexMut<NodeId> for Tree {
    fn index_mut(&mut self, index: NodeId) -> &mut Node {
        &mut self.arena[usize::from(index)]
    }
}
impl fmt::Debug for Tree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut next = Some(self.root);
        let mut nested: usize = 0;
        'outer: while let Some(id) = next {
            let node = &self[id];
            writeln!(f, "{:indent$}{:?}", "", node, indent = nested * 2)?;
            if node.child.is_some() {
                nested += 1;
                next = node.child;
            } else {
                let mut me = Some(node);
                while me.map(|me| me.next_sibling.is_none()).unwrap_or(false) {
                    match nested.checked_sub(1) {
                        Some(new) => nested = new,
                        None => break 'outer
                    }
                    me = me.unwrap().parent.map(|id| &self[id]);
                }
                next = me.and_then(|me| me.next_sibling);
            }
        }
        Ok(())
    }
}

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

    fn sanity_check(tree: &Tree) {
        let mut next = Some(tree.root);
        let mut parent = None;
        while let Some(id) = next {
            let node = &tree[id];
            assert_eq!(parent, node.parent);

            if let Some(child) = node.child {
                next = Some(child);
                parent = Some(id);
            } else {
                let mut node = Some(id);
                while node.map(|node| tree[node].next_sibling.is_none()).unwrap_or(false) {
                    node = tree[node.unwrap()].parent;
                }
                next = node.and_then(|node| tree[node].next_sibling);
                parent = node.and_then(|node| tree[node].parent);
            }
        }
    }

    #[test]
    fn simple_builder() {
        let mut builder = TreeBuilder::default();
        builder.start_internal(Token::Root, Range(1, Some(1)));
            builder.start_internal(Token::Alternative, Range(1, Some(1)));
                builder.leaf(Token::Start, Range(1, Some(1)));
                builder.start_internal(Token::Group(1), Range(1, Some(1)));
                    builder.start_internal(Token::Alternative, Range(1, Some(1)));
                        builder.leaf(Token::Any, Range(1, Some(1)));
                    builder.finish_internal();
                builder.finish_internal();
            builder.finish_internal();
            builder.start_internal(Token::Alternative, Range(1, Some(1)));
                builder.leaf(Token::End, Range(1, Some(1)));
            builder.finish_internal();
        builder.finish_internal();

        let tree = builder.finish();
        sanity_check(&tree);

        assert_eq!(
            format!("{:?}", tree),
            "\
Root 1..1
  Alternative 1..1
    ^ 1..1
    Group(1) 1..1
      Alternative 1..1
        . 1..1
  Alternative 1..1
    $ 1..1
"
        );
    }
    #[test]
    fn builder_checkpoint() {
        let mut builder = TreeBuilder::default();
        builder.start_internal(Token::Root, Range(1, Some(1)));
            let mut alternation = builder.checkpoint();
                builder.leaf(Token::Start, Range(1, Some(1)));
                let group = builder.checkpoint();
                    builder.start_internal(Token::Alternative, Range(1, Some(1)));
                        builder.leaf(Token::Any, Range(1, Some(1)));
                    builder.finish_internal();
                builder.start_internal_at(group, Token::Group(1), Range(1, Some(1)));
                builder.finish_internal();
            builder.start_internal_at(alternation, Token::Alternative, Range(1, Some(1)));
            builder.finish_internal();
            alternation = builder.checkpoint();
                builder.leaf(Token::End, Range(1, Some(1)));
            builder.start_internal_at(alternation, Token::Alternative, Range(1, Some(1)));
            builder.finish_internal();
        builder.finish_internal();

        let tree = builder.finish();
        sanity_check(&tree);

        assert_eq!(
            format!("{:?}", tree),
            "\
Root 1..1
  Alternative 1..1
    ^ 1..1
    Group(1) 1..1
      Alternative 1..1
        . 1..1
  Alternative 1..1
    $ 1..1
"
        );
    }
}