//
// imag - the personal information management suite for the commandline
// Copyright (C) 2015-2020 Matthias Beyer <mail@beyermatthias.de> and contributors
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; version
// 2.1 of the License.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//

use std::iter::FromIterator;

use failure::Fallible as Result;

pub struct Tree<T: Sized> {
    elements: Vec<TreeElement<T>>
}

impl<T: Sized> Tree<T> {

    pub fn new() -> Self {
        Tree { elements: Vec::new() }
    }

    pub fn with_capacity(cap: usize) -> Self {
        Tree { elements: Vec::with_capacity(cap) }
    }

    pub fn add_node(&mut self, t: T) {
        self.elements.push(TreeElement {
            parent_idx: None,
            childs_indexes: Vec::new(),
            element: t
        });
    }

    pub fn build_tree<ID, IG>(&mut self, ig: IG) -> TreeBuilder<T, ID, IG>
        where ID: PartialEq + Sized,
              IG: IdGetter<T, ID = ID>
    {
        TreeBuilder(self, ig)
    }
}

impl<A> FromIterator<A> for Tree<A>
    where A: Sized
{
    fn from_iter<T>(iter: T) -> Self
    where
        T: IntoIterator<Item = A>
    {
        Tree { elements: Vec::from_iter(iter.into_iter().map(|e| TreeElement::new(e))) }
    }
}


struct TreeElement<T> {
    pub parent_idx: Option<usize>,
    pub childs_indexes: Vec<usize>,
    pub element: T
}

impl<T> PartialEq<TreeElement<T>> for TreeElement<T>
    where T: PartialEq
{
    fn eq(&self, other: &TreeElement<T>) -> bool {
        self.element == other.element
    }
}

impl<T> TreeElement<T> {
    fn new(t: T) -> Self {
        TreeElement {
            parent_idx: None,
            childs_indexes: Vec::new(),
            element: t
        }
    }
}


pub trait IdGetter<T>
    where T: Sized,
{
    type ID: PartialEq + Sized;

    fn get_id_for_node(&self, node: &T)      -> Result<Self::ID>;
    fn get_id_for_parent_of(&self, node: &T) -> Result<Option<Self::ID>>;
}

pub struct TreeBuilder<'a, T, ID, IG>(&'a mut Tree<T>, IG)
    where T: Sized,
          ID: PartialEq + Sized,
          IG: IdGetter<T, ID = ID>;

impl<'a, T, ID, IG> TreeBuilder<'a, T, ID, IG>
    where T: Sized,
          ID: PartialEq + Sized,
          IG: IdGetter<T, ID = ID>
{
    pub fn build(&mut self) -> Result<()> {
        let mut i = 0;
        while let Some(node) = self.0.elements.get(i) {
            if let Some(parent_id) = self.1.get_id_for_parent_of(&node.element)? {
                if let Some(parent_idx) = self.find_node_idx(&parent_id)? {
                    if let Some(parent) = self.0.elements.get_mut(parent_idx) {
                        parent.childs_indexes.push(i);
                    }

                    if let Some(child) = self.0.elements.get_mut(i) {
                        child.parent_idx = Some(parent_idx);
                    }
                }
            }

            i += 1
        }

        Ok(())
    }

    fn find_node_idx<'t>(&'t self, search_id: &IG::ID) -> Result<Option<usize>> {
        let mut i = 0;

        while let Some(node) = self.0.elements.get(i) {
            let id = self.1.get_id_for_node(&node.element)?;
            if id == *search_id {
                return Ok(Some(i))
            }

            i += 1
        }

        return Ok(None)
    }
}

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

    #[test]
    fn test_insertion() {
        let mut tree = Tree::new();
        (1..100).for_each(|i| {
            tree.add_node(i);
        });

        assert!((1..100).all(|i| tree.elements.iter().any(|e| e.element == i)));
    }

    #[test]
    fn test_insertion_and_linking() {
        let mut tree = Tree::new();
        (1..100).for_each(|i| tree.add_node(i));

        struct IdGetterImpl;
        impl IdGetter<usize> for IdGetterImpl {
            type ID = usize;

            fn get_id_for_node(&self, node: &usize)      -> Result<Self::ID> {
                Ok(*node)
            }

            fn get_id_for_parent_of(&self, node: &usize) -> Result<Option<Self::ID>> {
                if *node > 1 {
                    Ok(Some(*node - 1))
                } else {
                    Ok(None)
                }
            }
        }


        let r = tree.build_tree::<usize, IdGetterImpl>(IdGetterImpl)
            .build();

        assert!(r.is_ok());
    }

}