use super::*;
use std::collections::HashMap; // TODO, switch to fxhash for increased speed

impl<'a, 'k> Navigator<'a, 'k> {
    /// Construct a new `Navigator`.
    ///
    /// `Navigator` borrows a [`Kserd`] as a root. It flattens the structure into a vector using a
    /// depth-first approach, and creates navigational links between `Kserd` nodes like parent and children.
    ///
    /// [`Kserd`]: crate::Kserd
    pub fn new(root: &'a Kserd<'k>) -> Self {
        #[derive(Default)]
        struct Info {
            parent: Option<usize>,
            value_idx_in_parent: Option<usize>,
            key_idx_in_parent: Option<usize>,
        };

        let mut stack = vec![(Info::default(), root)];

        let mut inner = Vec::new();

        // first populate parent links

        while let Some((info, node)) = stack.pop() {
            let len = inner.len();

            let Info {
                parent,
                value_idx_in_parent,
                key_idx_in_parent,
            } = info;

            inner.push(NodeInner {
                kserd: node,
                idx: len,
                parent,
                value_idx_in_parent,
                key_idx_in_parent,
                value_children: Vec::new(),
                key_children: Vec::new(),
            });

            let parent = Some(len);

            match &node.val {
                Value::Tuple(v) => {
                    for i in (0..v.len()).rev() {
                        stack.push((
                            Info {
                                parent,
                                value_idx_in_parent: Some(i),
                                ..Info::default()
                            },
                            &v[i],
                        ))
                    }
                }
                Value::Cntr(v) => {
                    for (i, n) in v.values().enumerate().rev() {
                        stack.push((
                            Info {
                                parent,
                                value_idx_in_parent: Some(i),
                                ..Info::default()
                            },
                            n,
                        ));
                    }
                }
                Value::Seq(v) => {
                    for i in (0..v.len()).rev() {
                        stack.push((
                            Info {
                                parent,
                                value_idx_in_parent: Some(i),
                                ..Info::default()
                            },
                            &v[i],
                        ));
                    }
                }
                Value::Map(v) => {
                    for (i, kvp) in v.iter().enumerate().rev() {
                        // push the value first (as it's reversed.)
                        stack.push((
                            Info {
                                parent,
                                value_idx_in_parent: Some(i),
                                ..Info::default()
                            },
                            kvp.1,
                        ));
                        stack.push((
                            Info {
                                parent,
                                key_idx_in_parent: Some(i),
                                ..Info::default()
                            },
                            kvp.0,
                        ));
                    }
                }
                _ => (),
            }
        }

        // second, link the children to the parent
        struct Info2 {
            idx: usize,
            value_idx_in_parent: Option<usize>,
            key_idx_in_parent: Option<usize>,
        };

        let mut parent_map = HashMap::with_capacity(inner.len());

        for child in inner.iter() {
            if let Some(parent) = child.parent {
                parent_map
                    .entry(parent)
                    .or_insert_with(Vec::new)
                    .push(Info2 {
                        idx: child.idx,
                        value_idx_in_parent: child.value_idx_in_parent,
                        key_idx_in_parent: child.key_idx_in_parent,
                    });
            }
        }

        for (parent, info_vec) in parent_map {
            let mut value_children = info_vec
                .iter()
                .filter_map(|x| x.value_idx_in_parent.map(|y| (y, x.idx)))
                .collect::<Vec<(usize, usize)>>();

            value_children.sort_by_key(|x| x.0);

            inner
                .get_mut(parent)
                .unwrap()
                .value_children
                .extend(value_children.into_iter().map(|x| x.1));

            // repeat for keys

            let mut key_children = info_vec
                .iter()
                .filter_map(|x| x.key_idx_in_parent.map(|y| (y, x.idx)))
                .collect::<Vec<(usize, usize)>>();

            key_children.sort_by_key(|x| x.0);

            inner
                .get_mut(parent)
                .unwrap()
                .key_children
                .extend(key_children.into_iter().map(|x| x.1));
        }

        let ret = Self { inner };

        debug_assert!(
            validate(&ret).unwrap_or(false),
            "navigator construction invalid"
        );

        ret
    }

    /// The root node, that same as the `Kserd` which was seeded as the root.
    ///
    /// Same as index `0`.
    ///
    /// # Example
    /// ```rust
    /// # use kserd::*;
    /// use kserd::nav::*;
    ///
    /// let kserd = Kserd::new_num(3.14);
    /// let nav = Navigator::new(&kserd);
    ///
    /// assert_eq!(nav.root().index(), 0);
    /// assert_eq!(nav.root().kserd(), &kserd);
    /// ```
    pub fn root<'nav: 'node, 'node>(&'nav self) -> Node<'a, 'k, 'nav, 'node> {
        let node = self.inner.first().unwrap();

        Node { node, nav: self }
    }

    /// Get a node at an index.
    ///
    /// The `Navigator` flattens the tree structure into a vector using a depth-first approach. Use
    /// the index to quickly obtain a node.
    ///
    /// # Example
    /// ```rust
    /// # use kserd::*;
    /// use kserd::nav::*;
    ///
    /// let kserd = Kserd::new_map(vec![
    ///     (Kserd::new_num(1), Kserd::new_num(2)),
    ///     (Kserd::new_num(3), Kserd::new_num(4)),
    /// ]);
    ///
    /// let nav = Navigator::new(&kserd);
    ///
    /// let get = |idx| nav.get(idx).map(|x| x.kserd());
    ///
    /// assert_eq!(get(1), Some(&Kserd::new_num(1)));
    /// assert_eq!(get(2), Some(&Kserd::new_num(2)));
    /// assert_eq!(get(3), Some(&Kserd::new_num(3)));
    /// assert_eq!(get(4), Some(&Kserd::new_num(4)));
    /// ```
    pub fn get<'nav: 'node, 'node>(&'nav self, index: usize) -> Option<Node<'a, 'k, 'nav, 'node>> {
        self.inner.get(index).map(|node| Node { node, nav: self })
    }

    /// The number of nodes.
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// The navigator has no nodes.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Iterate over the nodes in depth-first order.
    ///
    /// # Example
    /// ```rust
    /// # use kserd::*;
    /// use kserd::nav::*;
    ///
    /// let kserd = Kserd::new_map(vec![
    ///     (Kserd::new_num(1), Kserd::new_num(2)),
    ///     (Kserd::new_num(3), Kserd::new_num(4)),
    /// ]);
    ///
    /// let nav = Navigator::new(&kserd);
    ///
    /// let mut nodes = nav.nodes();
    ///
    /// let mut next = || nodes.next().map(|x| x.kserd());
    ///
    /// next(); // skip the root (hard to equality check)
    ///
    /// assert_eq!(next(), Some(&Kserd::new_num(1)));
    /// assert_eq!(next(), Some(&Kserd::new_num(2)));
    /// assert_eq!(next(), Some(&Kserd::new_num(3)));
    /// assert_eq!(next(), Some(&Kserd::new_num(4)));
    /// ```
    pub fn nodes<'nav>(&'nav self) -> NodeIter<'a, 'k, 'nav> {
        NodeIter {
            iter: self.inner.iter(),
            nav: self,
        }
    }
}

impl<'a, 'k, 'nav> Iterator for NodeIter<'a, 'k, 'nav> {
    type Item = Node<'a, 'k, 'nav, 'nav>;

    fn next(&mut self) -> Option<Node<'a, 'k, 'nav, 'nav>> {
        self.iter.next().map(|node| Node {
            node,
            nav: self.nav,
        })
    }
}

#[cfg(not(debug_assertions))]
fn validate(_: &Navigator) -> Option<bool> {
    Some(true)
}

#[cfg(debug_assertions)]
#[allow(clippy::all)]
fn validate(navigator: &Navigator) -> Option<bool> {
    let v = &navigator.inner;

    if v.first()?.parent.is_some() {
        panic!("first element should be root");
    }

    if v.iter().filter(|x| x.parent.is_none()).count() != 1 {
        panic!("only one root should exist");
    }

    for i in 0..v.len() {
        let node = v.get(i)?;
        if node.idx != i {
            panic!("node index should match its index in the vector");
        }
    }

    // check index in parent matches
    for node in v {
        if let Some(parent) = node.parent {
            let parent = v.get(parent)?;

            if let Some(idx) = node.value_idx_in_parent {
                match &parent.kserd.val {
                    Value::Tuple(v) => assert_eq!(v.get(idx)?, node.kserd),
                    Value::Seq(v) => assert_eq!(v.get(idx)?, node.kserd),
                    Value::Cntr(v) => assert_eq!(v.values().nth(idx)?, node.kserd),
                    Value::Map(v) => assert_eq!(v.values().nth(idx)?, node.kserd),
                    _ => (),
                }
            }

            if let Some(idx) = node.key_idx_in_parent {
                if let Value::Map(v) = &parent.kserd.val {
                    assert_eq!(v.keys().nth(idx)?, node.kserd);
                }
            }

            match &parent.kserd.val {
                Value::Tuple(_) | Value::Seq(_) | Value::Cntr(_) | Value::Map(_) => (),
                _ => assert!(node.value_idx_in_parent.is_none()),
            }

            match &parent.kserd.val {
                Value::Map(_) => (),
                _ => assert!(node.key_idx_in_parent.is_none()),
            }
        }
    }

    // check children
    for node in v {
        match &node.kserd.val {
            Value::Tuple(l) => {
                assert_eq!(l.len(), node.value_children.len());
                assert_eq!(0, node.key_children.len());
                for i in 0..l.len() {
                    assert_eq!(v.get(*node.value_children.get(i)?)?.kserd, l.get(i)?);
                }
            }
            Value::Seq(l) => {
                assert_eq!(l.len(), node.value_children.len());
                assert_eq!(0, node.key_children.len());
                for i in 0..l.len() {
                    assert_eq!(v.get(*node.value_children.get(i)?)?.kserd, l.get(i)?);
                }
            }
            Value::Cntr(l) => {
                assert_eq!(l.len(), node.value_children.len());
                assert_eq!(0, node.key_children.len());
                for i in 0..l.len() {
                    assert_eq!(
                        v.get(*node.value_children.get(i)?)?.kserd,
                        l.values().nth(i)?
                    );
                }
            }
            Value::Map(l) => {
                assert_eq!(l.len(), node.value_children.len());
                assert_eq!(l.len(), node.key_children.len());
                for i in 0..l.len() {
                    assert_eq!(v.get(*node.key_children.get(i)?)?.kserd, l.keys().nth(i)?);
                    assert_eq!(
                        v.get(*node.value_children.get(i)?)?.kserd,
                        l.values().nth(i)?
                    );
                }
            }
            _ => {
                assert_eq!(0, node.value_children.len());
                assert_eq!(0, node.key_children.len());
            }
        }
    }

    Some(true)
}

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

    #[test]
    fn check_navigator_linear_order_tuple() {
        // going to gaurantee that navigator.nodes() comes in depth-first order of nested structure
        let kserd = Kserd::with_id(
            "0",
            Value::Tuple(vec![
                Kserd::with_id(
                    "1",
                    Value::Tuple(vec![Kserd::with_id("2", Value::Unit).unwrap()]),
                )
                .unwrap(),
                Kserd::with_id("3", Value::Unit).unwrap(),
                Kserd::with_id(
                    "4",
                    Value::Tuple(vec![Kserd::with_id("5", Value::Unit).unwrap()]),
                )
                .unwrap(),
            ]),
        )
        .unwrap();

        let nav = Navigator::new(&kserd);

        assert_eq!(
            nav.inner
                .iter()
                .map(|x| x.kserd.id().unwrap())
                .collect::<Vec<_>>(),
            &["0", "1", "2", "3", "4", "5"]
        );
    }

    #[test]
    fn check_navigator_linear_order_cntr() {
        // going to gaurantee that navigator.nodes() comes in depth-first order of nested structure
        let kserd = Kserd::with_id(
            "0",
            Value::new_cntr(vec![
                (
                    "a",
                    Kserd::with_id(
                        "1",
                        Value::new_cntr(vec![("a", Kserd::with_id("2", Value::Unit).unwrap())])
                            .unwrap(),
                    )
                    .unwrap(),
                ),
                ("b", Kserd::with_id("3", Value::Unit).unwrap()),
                (
                    "c",
                    Kserd::with_id(
                        "4",
                        Value::new_cntr(vec![("a", Kserd::with_id("5", Value::Unit).unwrap())])
                            .unwrap(),
                    )
                    .unwrap(),
                ),
            ])
            .unwrap(),
        )
        .unwrap();

        let nav = Navigator::new(&kserd);

        assert_eq!(
            nav.inner
                .iter()
                .map(|x| x.kserd.id().unwrap())
                .collect::<Vec<_>>(),
            &["0", "1", "2", "3", "4", "5"]
        );
    }

    #[test]
    fn check_navigator_linear_order_seq() {
        // going to gaurantee that navigator.nodes() comes in depth-first order of nested structure
        let kserd = Kserd::with_id(
            "0",
            Value::Seq(vec![
                Kserd::with_id(
                    "1",
                    Value::Seq(vec![Kserd::with_id("2", Value::Unit).unwrap()]),
                )
                .unwrap(),
                Kserd::with_id("3", Value::Unit).unwrap(),
                Kserd::with_id(
                    "4",
                    Value::Seq(vec![Kserd::with_id("5", Value::Unit).unwrap()]),
                )
                .unwrap(),
            ]),
        )
        .unwrap();

        let nav = Navigator::new(&kserd);

        assert_eq!(
            nav.inner
                .iter()
                .map(|x| x.kserd.id().unwrap())
                .collect::<Vec<_>>(),
            &["0", "1", "2", "3", "4", "5"]
        );
    }

    #[test]
    fn check_navigator_linear_order_map() {
        // going to gaurantee that navigator.nodes() comes in depth-first order of nested structure
        let kserd = Kserd::with_id(
            "0",
            Value::new_map(vec![
                (
                    Kserd::with_id("1", Value::new_num(0)).unwrap(),
                    Kserd::with_id(
                        "2",
                        Value::new_map(vec![(
                            Kserd::with_id("3", Value::Unit).unwrap(),
                            Kserd::with_id("4", Value::Unit).unwrap(),
                        )]),
                    )
                    .unwrap(),
                ),
                (
                    Kserd::with_id("5", Value::new_num(1)).unwrap(),
                    Kserd::with_id("6", Value::Unit).unwrap(),
                ),
                (
                    Kserd::with_id(
                        "7",
                        Value::new_map(vec![(
                            Kserd::with_id("8", Value::Unit).unwrap(),
                            Kserd::with_id("9", Value::Unit).unwrap(),
                        )]),
                    )
                    .unwrap(),
                    Kserd::with_id(
                        "10",
                        Value::new_map(vec![(
                            Kserd::with_id("11", Value::Unit).unwrap(),
                            Kserd::with_id("12", Value::Unit).unwrap(),
                        )]),
                    )
                    .unwrap(),
                ),
            ]),
        )
        .unwrap();

        let nav = Navigator::new(&kserd);

        assert_eq!(
            nav.root()
                .key_children()
                .map(|x| x.kserd().id().unwrap().to_string())
                .collect::<Vec<_>>(),
            ["1", "5", "7"]
                .iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
        );

        assert_eq!(nav.len(), 13);

        assert_eq!(
            nav.inner
                .iter()
                .map(|x| x.kserd.id().unwrap())
                .collect::<Vec<_>>(),
            &["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12"]
        );
    }

    #[test]
    fn empty_test() {
        let kserd = Kserd::new_unit();
        let nav = Navigator::new(&kserd);
        assert_eq!(nav.is_empty(), false);
    }
}