extern crate fnv;
extern crate onevec;
extern crate parking_lot;

#[macro_use]
pub mod macros;

pub mod arena;
pub mod node_arena;

pub use node_arena::NodeArena;

use std::iter::FusedIterator;
use std::ops::{Deref, DerefMut};
use std::sync::Arc;

use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};

use arena::{Arena, Id};

#[derive(Default, Debug, Copy, Clone)]
struct NodeMeta {
    parent: Option<Id>,
    first_child: Option<Id>,
    last_child: Option<Id>,
    next_sibling: Option<Id>,
    prev_sibling: Option<Id>,
}

/// A node entry, stored in the NodeArena.
///
/// Currently there aren't many things you can do with it.
#[derive(Debug)]
pub struct NodeEntry<T> {
    meta: NodeMeta,
    data: Arc<RwLock<T>>,
}

impl<T> Clone for NodeEntry<T> {
    fn clone(&self) -> NodeEntry<T> {
        NodeEntry {
            meta: self.meta,
            data: self.data.clone(),
        }
    }
}

impl<T> NodeEntry<T> {
    fn new(data: T) -> NodeEntry<T> {
        NodeEntry {
            meta: Default::default(),
            data: Arc::new(RwLock::new(data)),
        }
    }
}

/// A reference to the tree node.
///
/// It has an [Id](::arena::Id), and the reference-counted data.
///
/// Most of the functions will block until there are no
/// more writers, holding the `RwLock`.
/// There may be more than one reader to the data, though.
#[derive(Debug)]
pub struct Node<T> {
    data: Arc<RwLock<T>>,
    id: Id,
}

impl<T> Clone for Node<T> {
    fn clone(&self) -> Node<T> {
        Node {
            data: self.data.clone(),
            id: self.id,
        }
    }
}

impl<T> Node<T> {
    /// Creates a new node in the provided arena.
    pub fn new(data: T, arena: &NodeArena<T>) -> Node<T> {
        let entry = NodeEntry::new(data);
        let data = entry.data.clone();
        let id = arena.write().insert(entry.clone());

        Node { data, id }
    }

    /// Returns a handle, dereferencing to the node data.
    ///
    /// This function will block until there are no more writers.
    pub fn read<'a>(&'a self) -> impl Deref<Target = T> + 'a {
        self.data.read()
    }

    /// Returns a mutable handle, dereferencing to the node data.
    ///
    /// This function will block until there are no more writers
    /// and readers.
    pub fn write<'a>(&'a self) -> impl DerefMut<Target = T> + 'a {
        self.data.write()
    }

    fn meta_ref<'a>(&'a self, arena: &'a NodeArena<T>) -> impl Deref<Target = NodeMeta> + 'a {
        RwLockReadGuard::map(arena.read_guard(), |a| &a[self.id].meta)
    }

    fn meta_mut<'a>(&'a self, arena: &'a NodeArena<T>) -> impl DerefMut<Target = NodeMeta> + 'a {
        RwLockWriteGuard::map(arena.write_guard(), |a| &mut a[self.id].meta)
    }

    fn meta_ref_r<'a>(&'a self, arena: &'a Arena<NodeEntry<T>>) -> &'a NodeMeta {
        &arena[self.id].meta
    }

    // fn meta_mut_r<'a>(&'a self, arena: &'a mut Arena<NodeEntry<T>>) -> &'a mut NodeMeta {
    //     &mut arena[self.id].meta
    // }

    fn from_id(id: Id, arena: &NodeArena<T>) -> Node<T> {
        let entry = &arena.read()[id];

        Node {
            id: id,
            data: entry.data.clone(),
        }
    }

    fn from_id_r(id: Id, arena: &Arena<NodeEntry<T>>) -> Node<T> {
        let entry = &arena[id];

        Node {
            id: id,
            data: entry.data.clone(),
        }
    }

    /// Returns node's parent, if any.
    pub fn parent(&self, arena: &NodeArena<T>) -> Option<Node<T>> {
        self.meta_ref(arena).parent.map(|v| Node::from_id(v, arena))
    }

    /// Returns node's first child, if any.
    pub fn first_child(&self, arena: &NodeArena<T>) -> Option<Node<T>> {
        self.meta_ref(arena)
            .first_child
            .map(|v| Node::from_id(v, arena))
    }

    /// Returns node's last child, if any.
    pub fn last_child(&self, arena: &NodeArena<T>) -> Option<Node<T>> {
        self.meta_ref(arena)
            .last_child
            .map(|v| Node::from_id(v, arena))
    }

    /// Returns node's next sibling, if any.
    pub fn next_sibling(&self, arena: &NodeArena<T>) -> Option<Node<T>> {
        self.meta_ref(arena)
            .next_sibling
            .map(|v| Node::from_id(v, arena))
    }

    /// Returns node's previous sibling, if any.
    pub fn prev_sibling(&self, arena: &NodeArena<T>) -> Option<Node<T>> {
        self.meta_ref(arena)
            .prev_sibling
            .map(|v| Node::from_id(v, arena))
    }

    /// Returns an iterator over node's children.
    pub fn children<'a>(&self, arena: &'a NodeArena<T>) -> Children<'a, T> {
        Children {
            first: self.meta_ref(arena).first_child,
            last: self.meta_ref(arena).last_child,
            arena: arena.read_guard(),
        }
    }

    /// Returns an iterator over node's ancestors.
    pub fn ancestors<'a>(&self, arena: &'a NodeArena<T>) -> Ancestors<'a, T> {
        Ancestors {
            parent: self.meta_ref(arena).parent,
            arena: arena.read_guard(),
        }
    }

    /// Returns an iterator over node's ancestors, including itself.
    pub fn siblings<'a>(&self, arena: &'a NodeArena<T>) -> Siblings<'a, T> {
        if let Some(parent) = self.parent(arena) {
            let meta = &parent.meta_ref(arena);

            Siblings {
                first: meta.first_child,
                last: meta.last_child,
                arena: arena.read_guard(),
            }
        } else {
            Siblings {
                first: None,
                last: None,
                arena: arena.read_guard(),
            }
        }
    }

    /// Returns an iterator over node's descendants, including itself, in NLR depth-first order.
    pub fn depth_first_traverse<'a>(&'a self, arena: &'a NodeArena<T>) -> DFTraverse<'a, T> {
        DFTraverse {
            node: Some(self.id),
            root: self.id,
            arena: arena.read_guard()
        }
    }

    /// Detachs a node from it's parent.
    ///
    /// If node does not have a parent, does nothing.
    pub fn detach(&self, arena: &NodeArena<T>) {
        let next_sibling = self.meta_ref(arena).next_sibling;
        let prev_sibling = self.meta_ref(arena).prev_sibling;

        let parent = self.meta_mut(arena).parent.take();

        let parent = match parent {
            Some(v) => v,
            None => return,
        };

        let entry = &mut arena.write()[parent];

        let was_first = entry
            .meta
            .first_child
            .map(|v| v == self.id)
            .unwrap_or(false);

        if was_first {
            entry.meta.first_child = next_sibling;
        }

        let was_last = entry.meta.last_child.map(|v| v == self.id).unwrap_or(false);

        if was_last {
            entry.meta.last_child = prev_sibling;
        }
    }

    /// Appends a new child to node, e.g. after the existing children.
    ///
    /// If the parent node did not have any children before,
    /// this operation is the same as [prepend](Node::prepend).
    pub fn append(&self, node: &Node<T>, arena: &NodeArena<T>) {
        node.detach(arena);
        node.meta_mut(arena).parent = Some(self.id);

        let old = self.meta_ref(arena).last_child;

        if let Some(old) = old {
            node.meta_mut(arena).prev_sibling = Some(old);

            let entry = &mut arena.write()[old];
            entry.meta.next_sibling = Some(node.id);
        }

        let is_first = self.meta_ref(arena).first_child.is_none();

        if is_first {
            self.meta_mut(arena).first_child = Some(node.id);
        }

        self.meta_mut(arena).last_child = Some(node.id);
    }

    /// Prepends a new child to node, e.g. before the existing children.
    ///
    /// If the parent node did not have any children before,
    /// this operation is the same as [append](Node::append).
    pub fn prepend(&self, node: &Node<T>, arena: &NodeArena<T>) {
        node.detach(arena);
        node.meta_mut(arena).parent = Some(self.id);

        let old = self.meta_ref(arena).first_child;

        if let Some(old) = old {
            node.meta_mut(arena).next_sibling = Some(old);

            let entry = &mut arena.write()[old];
            entry.meta.prev_sibling = Some(node.id);
        }

        let is_last = self.meta_ref(arena).last_child.is_none();

        if is_last {
            self.meta_mut(arena).last_child = Some(node.id);
        }

        self.meta_mut(arena).first_child = Some(node.id);
    }

    /// Returns true, if a node points to the same data as the other one.
    pub fn ptr_eq(&self, other: &Node<T>) -> bool {
        Arc::ptr_eq(&self.data, &other.data)
    }
}

macro_rules! impl_iter {
    ($name:ident, $next:ident, $prev:ident) => {
        impl<'a, T: 'a> Iterator for $name<'a, T> {
            type Item = Node<T>;

            fn next(&mut self) -> Option<Self::Item> {
                let id = match self.first {
                    _ if self.last.is_none() => return None,
                    Some(v) => v,
                    None => return None,
                };

                let node = Node::from_id_r(id, &self.arena);

                self.first = node.meta_ref_r(&self.arena).$next;

                if let Some(last) = self.last {
                    let entry = &self.arena[last];

                    let stop = entry
                        .meta
                        .$next
                        .and_then(|a| self.first.map(|b| (a, b)))
                        .filter(|(a, b)| a == b)
                        .is_some();

                    if stop {
                        self.first = None;
                    }
                }

                Some(node)
            }
        }

        impl<'a, T: 'a> DoubleEndedIterator for $name<'a, T> {
            fn next_back(&mut self) -> Option<Self::Item> {
                let id = match self.last {
                    _ if self.first.is_none() => return None,
                    Some(v) => v,
                    None => return None,
                };

                let node = Node::from_id_r(id, &self.arena);

                self.last = node.meta_ref_r(&self.arena).$prev;

                if let Some(first) = self.first {
                    let entry = &self.arena[first];

                    let stop = entry
                        .meta
                        .$prev
                        .and_then(|a| self.last.map(|b| (a, b)))
                        .filter(|(a, b)| a == b)
                        .is_some();

                    if stop {
                        self.last = None;
                    }
                }

                Some(node)
            }
        }

        impl<'a, T> FusedIterator for $name<'a, T> {}
    };
}

/// An iterator over node children.
pub struct Children<'a, T: 'a> {
    first: Option<Id>,
    last: Option<Id>,
    arena: RwLockReadGuard<'a, Arena<NodeEntry<T>>>,
}

impl_iter!(Children, next_sibling, prev_sibling);

/// An iterator over node siblings, including itself.
pub struct Siblings<'a, T: 'a> {
    first: Option<Id>,
    last: Option<Id>,
    arena: RwLockReadGuard<'a, Arena<NodeEntry<T>>>,
}

impl_iter!(Siblings, next_sibling, prev_sibling);

/// An iterator over node ancestors.
pub struct Ancestors<'a, T: 'a> {
    parent: Option<Id>,
    arena: RwLockReadGuard<'a, Arena<NodeEntry<T>>>,
}

impl<'a, T: 'a> Iterator for Ancestors<'a, T> {
    type Item = Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let parent = match self.parent {
            Some(v) => v,
            None => return None,
        };

        let node = Node::from_id_r(parent, &self.arena);

        self.parent = node.meta_ref_r(&self.arena).parent;

        Some(node)
    }
}

/// An iterator over node descendants, including itself, in NLR depth-first order.
pub struct DFTraverse<'a, T: 'a> {
    node: Option<Id>,
    root: Id,
    arena: RwLockReadGuard<'a, Arena<NodeEntry<T>>>
}

impl<'a, T: 'a> Iterator for DFTraverse<'a, T> {
    type Item = Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let node = match self.node {
            Some(v) => v,
            None => return None
        };

        if let Some(first_child) = self.arena[node].meta.first_child {
            self.node = Some(first_child);
        } else {
            while self.node.and_then(|v| self.arena[v].meta.next_sibling).is_none() {
                if self.node.filter(|&v| v == self.root).is_some() {
                    self.node = None;
                    return Some(Node::from_id_r(node, &self.arena));
                }

                self.node = self.node.and_then(|v| self.arena[v].meta.parent);
            }

            self.node = self.node.and_then(|v| self.arena[v].meta.next_sibling);
        }

        Some(Node::from_id_r(node, &self.arena))
    }
}

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

    #[test]
    fn read_write() {
        let ref arena = NodeArena::new();

        let a = Node::new(5, arena);

        assert_eq!(*a.read(), 5);
        *a.write() += 5;
        assert_eq!(*a.read(), 10);
    }

    #[test]
    fn parent() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child = Node::new(20, arena);

        assert!(child.parent(arena).is_none());
        root.append(&child, arena);
        assert!(child.parent(arena).unwrap().ptr_eq(&root));
        child.detach(&arena);
        assert!(child.parent(arena).is_none());
    }

    #[test]
    fn children_append() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);

        assert!(root.first_child(arena).is_none());
        assert!(root.last_child(arena).is_none());

        root.append(&child_a, arena);
        root.append(&child_b, arena);

        assert!(root.first_child(arena).unwrap().ptr_eq(&child_a));
        assert!(root.last_child(arena).unwrap().ptr_eq(&child_b));
    }

    #[test]
    fn children_prepend() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);

        root.prepend(&child_a, arena);
        root.prepend(&child_b, arena);

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);

        root.prepend(&child_a, arena);
        root.prepend(&child_b, arena);

        assert!(root.first_child(arena).unwrap().ptr_eq(&child_b));
        assert!(root.last_child(arena).unwrap().ptr_eq(&child_a));
    }

    #[test]
    fn children_iter() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);
        let child_c = Node::new(40, arena);

        root.append(&child_a, arena);
        root.append(&child_b, arena);
        root.append(&child_c, arena);

        let mut iter = root.children(arena);

        assert!(iter.next().unwrap().ptr_eq(&child_a));
        assert!(iter.next().unwrap().ptr_eq(&child_b));
        assert!(iter.next().unwrap().ptr_eq(&child_c));
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn children_iter_double_ended() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);
        let child_c = Node::new(40, arena);
        let child_d = Node::new(50, arena);
        let child_e = Node::new(60, arena);

        root.append(&child_a, arena);
        root.append(&child_b, arena);
        root.append(&child_c, arena);
        root.append(&child_d, arena);
        root.append(&child_e, arena);

        let mut iter = root.children(arena);

        assert!(iter.next().unwrap().ptr_eq(&child_a));
        assert!(iter.next_back().unwrap().ptr_eq(&child_e));
        assert!(iter.next().unwrap().ptr_eq(&child_b));
        assert!(iter.next_back().unwrap().ptr_eq(&child_d));
        assert!(iter.next().unwrap().ptr_eq(&child_c));
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next_back().is_none());
    }

    #[test]
    fn siblings() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);

        root.append(&child_a, arena);
        root.append(&child_b, arena);

        assert!(child_a.next_sibling(arena).unwrap().ptr_eq(&child_b));
        assert!(child_b.prev_sibling(arena).unwrap().ptr_eq(&child_a));
    }

    #[test]
    fn ancestors() {
        let ref arena = NodeArena::new();

        let grandparent = Node::new(10, arena);
        let parent = Node::new(20, arena);
        let child = Node::new(30, arena);
        let grandchild = Node::new(40, arena);

        child.append(&grandchild, arena);
        parent.append(&child, arena);
        grandparent.append(&parent, arena);

        let mut iter = grandchild.ancestors(arena);

        assert!(iter.next().unwrap().ptr_eq(&child));
        assert!(iter.next().unwrap().ptr_eq(&parent));
        assert!(iter.next().unwrap().ptr_eq(&grandparent));
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn siblings_iter() {
        let ref arena = NodeArena::new();

        let root = Node::new(10, arena);
        let child_a = Node::new(20, arena);
        let child_b = Node::new(30, arena);
        let child_c = Node::new(40, arena);

        root.append(&child_a, arena);
        root.append(&child_b, arena);
        root.append(&child_c, arena);

        let mut iter = child_b.siblings(arena);
        assert!(iter.next().unwrap().ptr_eq(&child_a));
        assert!(iter.next_back().unwrap().ptr_eq(&child_c));
        assert!(iter.next().unwrap().ptr_eq(&child_b));
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next_back().is_none());
    }

    #[test]
    fn traversal() {
        let ref arena = NodeArena::new();

        let root = tree!(arena, 1 => [2 => [3, 4], 5 => [6]]);

        let elements = root
            .depth_first_traverse(arena)
            .map(|v| *v.read())
            .collect::<Vec<_>>();

        let expected = vec![1, 2, 3, 4, 5, 6];

        assert_eq!(elements, expected);
    }
}