#[cfg(feature = "serde")]
use crate::serde_utils::*;
use crate::{Aggregate, GraphError, Meta, Metadata};
use anyhow::{anyhow, Result};
use std::collections::{HashMap, HashSet};
use uuid::Uuid;

/// A node in a graph.
#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(
    feature = "serde",
    derive(serde::Serialize, serde::Deserialize),
    serde(rename_all = "camelCase")
)]
pub struct Node {
    /// Instance metadata.
    pub metadata: Metadata,
    /// ID of the parent of this node, if any.
    #[cfg_attr(
        feature = "serde",
        serde(default, skip_serializing_if = "Option::is_none")
    )]
    pub parent: Option<Uuid>,
    /// IDs of this node's children,
    #[cfg_attr(
        feature = "serde",
        serde(default, skip_serializing_if = "is_empty_vec")
    )]
    pub children: Vec<Uuid>,
    /// Whether this node is a bus node for its parent.
    #[cfg_attr(feature = "serde", serde(default, skip_serializing_if = "is_default"))]
    pub is_bus: bool,
}
impl Node {
    /// Create a new node struct with arguments.
    pub fn new(
        metadata: Option<Metadata>,
        parent: Option<Uuid>,
        children: Option<Vec<Uuid>>,
        is_bus: Option<bool>,
    ) -> Self {
        Node {
            metadata: metadata.unwrap_or_default(),
            parent,
            children: match children {
                None => vec![],
                Some(x) => x,
            },
            is_bus: is_bus.unwrap_or(false),
        }
    }

    /// Whether this node has no parent and is thus a root node.
    pub fn is_root(&self) -> bool {
        self.parent.is_none()
    }

    /// Whether this node has no children and is thus a leaf node.
    pub fn is_leaf(&self) -> bool {
        self.children.is_empty()
    }

    /// Number of children.
    pub fn dim(&self) -> usize {
        self.children.len()
    }
}

impl Meta for Node {
    /// Get node metadata.
    fn get_meta(&self) -> &Metadata {
        &self.metadata
    }
}

#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NodeStoreData {
    nodes: HashMap<Uuid, Node>,
    roots: HashSet<Uuid>,
    leafs: HashSet<Uuid>,
    aggregate: Aggregate,
    depth: Option<usize>,
}
impl HasNodeStore for NodeStoreData {
    /// Get a reference to the node store.
    fn node_store(&self) -> &NodeStoreData {
        self
    }
    /// Get a mutable reference to the node store.
    fn node_store_mut(&mut self) -> &mut NodeStoreData {
        self
    }
}
impl NodeStore for NodeStoreData {}

pub trait HasNodeStore {
    fn node_store(&self) -> &NodeStoreData;
    fn node_store_mut(&mut self) -> &mut NodeStoreData;
}

pub trait NodeStore: HasNodeStore {
    /// The number of nodes in this store.
    fn nodes_len(&self) -> usize {
        self.node_store().nodes.len()
    }

    /// Maximum node depth or height.
    fn max_node_depth(&mut self) -> usize {
        if let Some(depth) = self.node_store().depth {
            return depth;
        }
        let depth = self.calculate_node_depth();
        self.node_store_mut().depth = Some(depth);
        depth
    }

    /// Whether this node store is empty.
    fn is_nodes_empty(&self) -> bool {
        self.nodes_len() == 0
    }

    /// Check whether this store contains a node with the given node ID.
    fn has_node(&self, id: &Uuid) -> bool {
        self.node_store().nodes.contains_key(id)
    }

    /// Add a single node to this store. Setting 'safe' checks whether this node's
    /// references exist and detects cyclic hierarchies.
    fn add_node(&mut self, node: Node, safe: bool) -> Result<Option<Node>> {
        if safe {
            self.check_node(&node)?;
        }
        let id = node.id().to_owned();
        let replaced = self.del_node(&id);
        self.node_store_mut().aggregate.add(node.get_meta());
        if node.is_leaf() {
            self.node_store_mut().leafs.insert(id);
        }
        if node.is_root() {
            self.node_store_mut().roots.insert(id);
        }
        if node.parent.is_some() || !node.children.is_empty() {
            self.node_store_mut().depth = None;
        }
        self.node_store_mut().nodes.insert(id, node);
        Ok(replaced)
    }

    /// Extend this node store with new nodes. Setting 'safe' checks whether all node
    /// references exist and detects cyclic hierarchies after adding them to the store
    /// first.
    fn extend_nodes(&mut self, nodes: Vec<Node>, safe: bool) -> Result<Vec<Node>> {
        let mut replaced = vec![];
        for node in nodes.clone().into_iter() {
            if let Some(node) = self.add_node(node, false)? {
                replaced.push(node);
            }
        }
        if safe {
            for node in nodes.iter() {
                self.check_node(node)?;
            }
        }
        Ok(replaced)
    }

    /// Check whether a node's references exist and it doesn't partake in cyclic
    /// hierarchies.
    fn check_node(&self, node: &Node) -> Result<()> {
        if let Some(parent_id) = &node.parent {
            if !self.has_node(parent_id) {
                return Err(anyhow!(GraphError::NodeNotInStore(parent_id.to_owned())));
            }
        }
        for child_id in node.children.iter() {
            if !self.has_node(child_id) {
                return Err(anyhow!(GraphError::NodeNotInStore(child_id.to_owned())));
            }
        }
        if node.is_bus && node.parent.is_none() {
            return Err(anyhow!(GraphError::BusWithoutParent(node.id().to_owned())));
        }
        // Use query functions in safe mode to detect any cyclic hierarchies.
        // Pretty brute-force, but works.
        self.ascendant_nodes(node.id(), true, true, None, None)?;
        self.descendant_nodes(node.id(), true, true, None, None)?;
        Ok(())
    }

    /// Get a reference to a node.
    fn get_node(&self, id: &Uuid) -> Option<&Node> {
        self.node_store().nodes.get(id)
    }
    /// Get a reference to a node as as result.
    fn get_node_err(&self, id: &Uuid) -> Result<&Node> {
        match self.node_store().nodes.get(id) {
            Some(node) => Ok(node),
            None => Err(anyhow!(GraphError::NodeNotInStore(id.to_owned()))),
        }
    }

    /// Get a mutable reference to a node.
    fn get_node_mut(&mut self, node_id: &Uuid) -> Option<&mut Node> {
        self.node_store_mut().nodes.get_mut(node_id)
    }

    /// Delete node from this store.
    fn del_node(&mut self, node_id: &Uuid) -> Option<Node> {
        let store = self.node_store_mut();
        let deleted = store.nodes.remove(node_id);
        if let Some(deleted) = deleted.as_ref() {
            store.aggregate.subtract(deleted.get_meta());
            store.roots.remove(node_id);
            store.leafs.remove(node_id);
            store.depth = None;
        }
        deleted
    }

    /// Update max node depth.
    fn calculate_node_depth(&self) -> usize {
        self.leaf_ids()
            .iter()
            .filter_map(|id| self.node_depth(id, false, None, None).ok())
            .max()
            .unwrap_or(0)
    }

    /// Get all node IDs in this store.
    fn all_node_ids(&self) -> Vec<&Uuid> {
        self.node_store().nodes.keys().collect()
    }

    /// Get all node IDs in this store.
    fn all_nodes(&self) -> Vec<&Node> {
        self.node_store().nodes.values().collect()
    }

    /// Get all root node IDs in this store.
    fn root_ids(&self) -> Vec<&Uuid> {
        self.node_store().roots.iter().collect()
    }

    /// Get all root nodes in this store.
    fn root_nodes(&self) -> Vec<&Node> {
        self.node_store()
            .roots
            .iter()
            .filter_map(|id| self.get_node(id))
            .collect()
    }

    /// Get all leaf node IDs in this store.
    fn leaf_ids(&self) -> Vec<&Uuid> {
        self.node_store().leafs.iter().collect()
    }

    /// Get all leaf nodes in this store.
    fn leaf_nodes(&self) -> Vec<&Node> {
        self.node_store()
            .leafs
            .iter()
            .filter_map(|id| self.get_node(id))
            .collect()
    }

    /// Set a new parent value for the given child ID. Returns an error if the child
    /// node does not exist in the store. Setting the parent ID to None removes the
    /// parent-child relationship.
    fn set_parent(&mut self, child_id: &Uuid, parent_id: Option<&Uuid>) -> Result<()> {
        // Remove child from current parent.
        if let Some(child) = self.get_node(child_id) {
            if let Some(current_parent_id) = child.parent {
                let add_to_leafs = {
                    if let Some(current_parent) = self.get_node_mut(&current_parent_id) {
                        current_parent.children.retain(|x| x != child_id);
                        current_parent.is_leaf()
                    } else {
                        false
                    }
                };
                if add_to_leafs {
                    self.node_store_mut().leafs.insert(current_parent_id);
                }
            }
        } else {
            return Err(anyhow!(GraphError::NodeNotInStore(child_id.to_owned())));
        }

        // Set new parent value.
        if let Some(parent_id) = parent_id {
            if self.has_node(parent_id) {
                if let Some(child) = self.get_node_mut(child_id) {
                    child.parent = Some(parent_id.to_owned());
                    self.node_store_mut().roots.remove(child_id);
                }
                if let Some(parent) = self.get_node_mut(parent_id) {
                    parent.children.push(child_id.to_owned());
                    self.node_store_mut().leafs.remove(parent_id);
                }
            } else {
                return Err(anyhow!(GraphError::NodeNotInStore(parent_id.to_owned())));
            }
        } else if let Some(child) = self.get_node_mut(child_id) {
            child.parent = None;
            child.is_bus = false;
            self.node_store_mut().roots.insert(*child_id);
        }
        self.node_store_mut().depth = None;
        Ok(())
    }

    /// Set the is_bus value of a given node ID.
    fn set_bus(&mut self, node_id: &Uuid, is_bus: bool) -> Result<()> {
        if let Some(node) = self.get_node_mut(node_id) {
            if is_bus && node.parent.is_none() {
                return Err(anyhow!(GraphError::BusWithoutParent(node_id.to_owned())));
            }
            node.is_bus = is_bus;
        } else {
            return Err(anyhow!(GraphError::NodeNotInStore(node_id.to_owned())));
        }
        Ok(())
    }

    /// Get the bus node IDs that fall directly under the given parent ID.
    fn bus_ids(&self, parent_id: &Uuid) -> Result<Vec<&Uuid>> {
        Ok(self
            .bus_nodes(parent_id)?
            .into_iter()
            .map(|node| node.id())
            .collect())
    }

    /// Get the bus nodes that fall directly under the given parent ID.
    fn bus_nodes(&self, parent_id: &Uuid) -> Result<Vec<&Node>> {
        if let Some(parent) = self.get_node(parent_id) {
            Ok(parent
                .children
                .iter()
                .filter_map(|id| {
                    self.get_node(id)
                        .and_then(|node| if node.is_bus { Some(node) } else { None })
                })
                .collect())
        } else {
            Err(anyhow!(GraphError::NodeNotInStore(parent_id.to_owned())))
        }
    }

    /// Get ascendant node IDs of a given node. Setting `safe` checks for cyclic
    /// hierarchies along the way. `only_root` only includes the final root node.
    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
    /// `height` determines the maximum height at which the ancestor is considered a
    /// root node.
    fn ascendant_ids(
        &self,
        node_id: &Uuid,
        safe: bool,
        only_root: bool,
        root_ids: Option<&HashSet<Uuid>>,
        height: Option<usize>,
    ) -> Result<Vec<&Uuid>> {
        let node = self.get_node_err(node_id)?;
        let mut ascendants = vec![];
        // If no height, return empty.
        if let Some(height) = height {
            if height == 0 {
                return Ok(ascendants);
            }
        }
        // Iteration helpers.
        let mut seen_set = HashSet::<&Uuid>::new();
        let mut height = height;
        let mut parent_id = &node.parent;
        while let Some(id) = parent_id {
            if safe && !seen_set.insert(id) {
                return Err(anyhow!(GraphError::CyclicAscendants(id.to_owned())));
            }
            let parent = self.get_node_err(id)?;
            // If we have an absolute or considered root, add and stop.
            if parent.is_root()
                || height.map(|h| h == 1).unwrap_or(false)
                || root_ids.map(|x| x.contains(id)).unwrap_or(false)
            {
                ascendants.push(id);
                break;
            } else {
                // Otherwise, we have a non-root node.
                if !only_root {
                    // Include intermediate nodes if not only root.
                    ascendants.push(id);
                }
            }
            // Bookkeeping for each iteration.
            if let Some(value) = height {
                let new_height = value - 1;
                height = Some(new_height);
            }
            parent_id = &parent.parent;
        }
        Ok(ascendants)
    }

    /// Get ascendant nodes of a given node. Setting `safe` checks for cyclic
    /// hierarchies along the way. `only_root` only includes the final root node.
    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
    /// `height` determines the maximum height at which the ancestor is considered a
    /// root node.
    fn ascendant_nodes(
        &self,
        node_id: &Uuid,
        safe: bool,
        only_root: bool,
        root_ids: Option<&HashSet<Uuid>>,
        height: Option<usize>,
    ) -> Result<Vec<&Node>> {
        Ok(self
            .ascendant_ids(node_id, safe, only_root, root_ids, height)?
            .into_iter()
            .filter_map(|id| self.get_node(id))
            .collect())
    }

    /// Node depth (i.e. the number of levels that exist above). Setting `safe` checks
    /// for cyclic hierarchies along the way. `root_ids` are nodes to consider as (additional) root nodes in this query.
    /// `height` determines the maximum height at which the ancestor is considered a
    /// root node.
    fn node_depth(
        &self,
        node_id: &Uuid,
        safe: bool,
        root_ids: Option<&HashSet<Uuid>>,
        height: Option<usize>,
    ) -> Result<usize> {
        Ok(self
            .ascendant_ids(node_id, safe, false, root_ids, height)?
            .len())
    }

    /// Get the descendant node IDs of a given node. Setting `safe` checks for cyclic
    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
    /// disallowing it from going any further. `depth` specifies the maximum depth at
    /// which nodes are also considered leaf nodes for this search.
    fn descendant_ids(
        &self,
        node_id: &Uuid,
        safe: bool,
        only_leaf: bool,
        leaf_ids: Option<&HashSet<Uuid>>,
        depth: Option<usize>,
    ) -> Result<Vec<&Uuid>> {
        let node = self.get_node_err(node_id)?;
        let mut descendants = vec![];
        // If no depth, return empty.
        if let Some(depth) = depth {
            if depth == 0 {
                return Ok(descendants);
            }
        }
        // Iteration helpers.
        let mut seen_set = HashSet::<&Uuid>::new();
        let mut depth = depth;
        let mut children: Vec<&Uuid> = node.children.iter().collect();
        let mut offspring: Vec<&Uuid> = vec![];
        // Keep looping over children.
        while let Some(child_id) = children.pop() {
            // If safe check, check whether we've seen this ID already.
            if safe && !seen_set.insert(child_id) {
                return Err(anyhow!(GraphError::CyclicDescendants(child_id.to_owned())));
            }
            let child = self.get_node_err(child_id)?;
            // If this child is an absolute leaf node, add it.
            // If this child is an specified leaf node, add it.
            // Nodes at depth == 1 are also a leaf, add it.
            if child.is_leaf()
                || depth.map(|d| d == 1).unwrap_or(false)
                || leaf_ids.map(|x| x.contains(child_id)).unwrap_or(false)
            {
                descendants.push(child_id);
            } else {
                // Otherwise, we have a non-leaf node.
                if !only_leaf {
                    // Include intermediate nodes if not only leaf.
                    descendants.push(child_id);
                }
                // Add to offspring if we are above 1 or have no limit.
                // This is guaranteed by the nodes at depth == 1 branch.
                offspring.extend(child.children.iter());
            }
            // Add from stack if children are empty.
            if children.is_empty() {
                // Can't continue if there's no stack left.
                if offspring.is_empty() {
                    break;
                }
                // We're done after depth == 1 because the stack won't be refilled.
                depth = depth.map(|d| d - 1);
                children = offspring;
                offspring = vec![];
            }
        }
        Ok(descendants)
    }

    /// Get the descendant nodes of a given node. Setting `safe` checks for cyclic
    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
    /// disallowing it from going any further. `depth` specifies the maximum depth with
    /// respect to the given node ID to search at.
    fn descendant_nodes(
        &self,
        node_id: &Uuid,
        safe: bool,
        only_leaf: bool,
        leaf_ids: Option<&HashSet<Uuid>>,
        depth: Option<usize>,
    ) -> Result<Vec<&Node>> {
        Ok(self
            .descendant_ids(node_id, safe, only_leaf, leaf_ids, depth)?
            .into_iter()
            .filter_map(|id| self.get_node(id))
            .collect())
    }

    /// Node height (i.e. the number of levels that exist below). Setting `safe` checks
    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
    /// disallowing it from going any further. `depth` specifies the maximum depth with
    /// respect to the given node ID to search at.
    fn node_height(
        &self,
        node_id: &Uuid,
        safe: bool,
        depth: Option<usize>,
        leaf_ids: Option<&HashSet<Uuid>>,
    ) -> Result<usize> {
        let node = self.get_node_err(node_id)?;
        let mut height = 0;
        // If no depth, return empty.
        if let Some(depth) = depth {
            if depth == 0 {
                return Ok(height);
            }
        }
        // Iteration helpers.
        let mut seen_set = HashSet::<&Uuid>::new();
        let mut depth = depth;
        let mut children: Vec<&Uuid> = node.children.iter().collect();
        let mut offspring: Vec<&Uuid> = vec![];
        // Keep looping over children.
        while let Some(child_id) = children.pop() {
            // If safe check, check whether we've seen this ID already.
            if safe && !seen_set.insert(child_id) {
                return Err(anyhow!(GraphError::CyclicDescendants(child_id.to_owned())));
            }
            let child = self.get_node_err(child_id)?;
            // If this child is no absolute or considered leaf, extend offspring.
            if !(child.is_leaf()
                || leaf_ids.map(|x| x.contains(child_id)).unwrap_or(false)
                || depth.map(|d| d == 1).unwrap_or(false))
            {
                offspring.extend(child.children.iter());
            }
            // Add from stack if children are empty.
            if children.is_empty() {
                height += 1;
                // Can't continue if there's no stack left.
                if offspring.is_empty() {
                    break;
                }
                // We're done after depth == 1 because the stack won't be refilled.
                depth = depth.map(|d| d - 1);
                children = offspring;
                offspring = vec![];
            }
        }
        Ok(height)
    }

    /// Node width in terms of (optionally specified) leaf nodes. Setting `safe` checks
    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
    /// disallowing it from going any further. `depth` specifies the maximum depth with
    /// respect to the given node ID to search at.
    fn node_width(
        &self,
        node_id: &Uuid,
        safe: bool,
        leaf_ids: Option<&HashSet<Uuid>>,
        depth: Option<usize>,
    ) -> Result<usize> {
        let leaf_ids = leaf_ids.unwrap_or_else(|| &self.node_store().leafs).clone();
        Ok(self
            .descendant_ids(node_id, safe, true, Some(&leaf_ids), depth)?
            .len())
    }

    /// Get the aggregate.
    fn node_aggregate(&self) -> &Aggregate {
        &self.node_store().aggregate
    }
}