#![warn(missing_docs)]
//! This file implements a data type that implements the trait
//! [`Graph`][super::Graph].  This data type represents graphs using
//! adjacency lists internally.

use std::{
    borrow::{Borrow, BorrowMut},
    ops::{Deref, DerefMut},
};

use crate::{
    builder::{Builder, BuilderMut},
    error::Error,
    ExtGraph, Graph,
};

// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
// struct ALEdge {
//     to: usize,
// }

// impl ALEdge {
//     fn new(to: usize) -> Self {
//         Self { to }
//     }
// }

#[derive(Debug, Clone, Default)]
struct ALNode {
    children: Vec<usize>,
}

impl ALNode {
    fn new(children: Vec<usize>) -> Self {
        Self { children }
    }
}

/// The graph implemented using adjacency lists.
#[derive(Debug, Clone, Default)]
pub struct ALGraph {
    nodes: Vec<ALNode>,
}

impl Graph for ALGraph {
    type Iter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>;

    #[inline]
    fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    #[inline]
    fn nodes_len(&self) -> usize {
        self.nodes.len()
    }

    #[inline]
    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
        match self.nodes.get(node_id) {
            Some(node) => Ok(node.children.iter().copied()),
            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
        }
    }

    #[inline]
    fn degree(&self, node_id: usize) -> Result<usize, Error> {
        match self.nodes.get(node_id) {
            Some(node) => Ok(node.children.len()),
            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
        }
    }

    #[inline]
    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
        match self.nodes.get(node_id) {
            Some(node) => Ok(node.children.is_empty()),
            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
        }
    }

    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
        if !self.has_node(source) {
            Err(Error::IndexOutOfBounds(source, self.nodes_len()))
        } else if !self.has_node(target) {
            Err(Error::IndexOutOfBounds(target, self.nodes_len()))
        } else {
            Ok(self.nodes.get(source).unwrap().children.contains(&target))
        }
    }

    #[inline]
    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
        let graph = builder.build();

        self.nodes = graph.nodes;
    }
}

impl ExtGraph for ALGraph {
    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error> {
        let mut new_node_children = Vec::new();

        for edge_to in edges.into_iter() {
            if !self.has_node(edge_to) {
                return Err(Error::IndexOutOfBounds(edge_to, self.nodes_len()));
            }

            new_node_children.push(edge_to);
        }

        let new_node = ALNode::new(new_node_children);

        self.nodes.push(new_node);

        Ok(self.nodes.len() - 1)
    }
}

impl From<Vec<Vec<usize>>> for ALGraph {
    fn from(adlist: Vec<Vec<usize>>) -> Self {
        Self {
            nodes: adlist.into_iter().map(ALNode::new).collect(),
        }
    }
}

/// A builder that modifies ALGraph in place.
#[derive(Debug)]
pub struct ALGBuilderMut<'a> {
    graph: &'a mut ALGraph,
}

impl<'a> std::ops::Deref for ALGBuilderMut<'a> {
    type Target = ALGraph;

    fn deref(&self) -> &Self::Target {
        self.graph.borrow()
    }
}

impl<'a> std::ops::DerefMut for ALGBuilderMut<'a> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.graph.borrow_mut()
    }
}

impl<'a> BuilderMut for ALGBuilderMut<'a> {
    type Label = ();

    type Graph = ALGraph;

    type ResultBuilder<'b> = ALGBuilderMut<'b>
    where
        Self::Label: 'b;

    fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
        ALGBuilderMut { graph }
    }

    fn add_vertex(&mut self, _label: Self::Label) -> usize {
        self.nodes.push(Default::default());

        self.nodes.len() - 1
    }

    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
        if self.graph.has_edge(source, target)? {
            return Ok(());
        }

        self.graph
            .nodes
            .get_mut(source)
            .unwrap()
            .children
            .push(target);

        Ok(())
    }

    fn append(&mut self, other: Self::Graph) {
        let self_len = self.nodes_len();

        self.graph
            .nodes
            .extend(other.nodes.into_iter().map(|mut node| {
                for child in node.children.iter_mut() {
                    *child += self_len;
                }

                node
            }));
    }

    fn set_label(&mut self, _node_id: usize, _label: Self::Label) -> Result<(), Error> {
        Ok(())
    }

    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
    where
        F: FnMut(Self::Label) -> bool,
    {
        let nodes_len = self.nodes.len();

        let source_children = self
            .nodes
            .get_mut(source)
            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;

        if !(0..nodes_len).contains(&target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        source_children.children.retain(|child| *child != target);

        Ok(())
    }
}

// Builder for this implementation of graph

/// A builder for adjacency list graphs.
#[derive(Debug, Default, Clone)]
pub struct ALGBuilder(ALGraph);

impl Deref for ALGBuilder {
    type Target = ALGraph;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl DerefMut for ALGBuilder {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl Builder for ALGBuilder {
    type Label = ();

    type Result = ALGraph;

    fn with_capacity(size: usize) -> Self {
        Self(ALGraph {
            nodes: Vec::with_capacity(size),
        })
    }

    #[inline]
    fn add_vertex(&mut self) -> usize {
        self.nodes.push(ALNode::default());
        self.nodes.len() - 1
    }

    #[inline]
    fn add_vertices(&mut self, n: usize) {
        self.nodes
            .extend(std::iter::repeat_with(ALNode::default).take(n));
    }

    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
        let nodes_len = self.nodes.len();

        let source_children = self
            .nodes
            .get_mut(source)
            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;

        if !(0..nodes_len).contains(&target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        source_children.children.push(target);

        Ok(())
    }

    /// Remove an edge from the source to the target.
    ///
    /// Since some graphs are labelled, the users are allowed to pass
    /// a predicate to determine if an edge from the source to the
    /// target should be removed.
    ///
    /// # Performance note
    ///
    /// It is possible that the target appears more than once in the
    /// vector of children, so we have to remove every instance of
    /// target.
    ///
    /// Since I do not think builders should be used for performance
    /// critical tasks, this is fine.
    ///
    /// If one desires more performance, maybe
    /// [`ASGraph`][crate::ASGraph] is a good choice.
    ///
    /// Of course, if one just wants to use adjacency list
    /// representation and wants a performant builder, one can
    /// implement a customized builder.
    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
    where
        F: FnMut(Self::Label) -> bool,
    {
        let nodes_len = self.nodes.len();

        let source_children = self
            .nodes
            .get_mut(source)
            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;

        if !(0..nodes_len).contains(&target) {
            return Err(Error::IndexOutOfBounds(target, nodes_len));
        }

        source_children.children.retain(|child| *child != target);

        Ok(())
    }

    fn build(self) -> Self::Result {
        self.0
    }

    fn build_ref(&self) -> Self::Result {
        self.0.clone()
    }
}

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

    #[test]
    fn test_graph_apis() -> Result<(), Error> {
        let mut graph = ALGraph::default();

        assert!(graph.is_empty());

        graph.extend(std::iter::empty())?;

        graph.extend([0].iter().copied())?;
        graph.extend([0, 1].iter().copied())?;
        graph.extend([0, 2].iter().copied())?;
        graph.extend([1, 2].iter().copied())?;
        graph.extend([1, 2, 3].iter().copied())?;

        let graph = graph;

        assert_eq!(graph.nodes_len(), 6);

        assert_eq!(graph.children_of(5)?.collect::<Vec<_>>(), vec![1, 2, 3]);

        assert_eq!(graph.degree(4)?, 2);

        assert!(graph.is_empty_node(0)?);
        assert!(!graph.is_empty_node(1)?);

        assert!(graph.has_edge(3, 2)?);
        assert!(!graph.has_edge(3, 1)?);
        assert_eq!(graph.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6)));

        Ok(())
    }

    #[test]
    fn test_extending_algraph_normal() -> Result<(), Error> {
        let mut graph = ALGraph::default();

        let new = graph.extend(std::iter::empty())?;

        println!("new index = {new}");

        println!("new graph = {graph:?}");

        let new = graph.extend([0].iter().copied())?;

        println!("new index = {new}");

        println!("new graph = {graph:?}");

        let new = graph.extend([0, 1].iter().copied())?;

        println!("new index = {new}");

        println!("new graph = {graph:?}");

        Ok(())
    }

    #[test]
    fn test_extending_algraph_error() -> Result<(), Error> {
        let mut graph = ALGraph::default();

        graph.extend(std::iter::empty())?;

        graph.extend([0].iter().copied())?;

        assert_eq!(
            graph.extend([2].iter().copied()),
            Err(Error::IndexOutOfBounds(2, 2))
        );

        Ok(())
    }
}

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

    #[test]
    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
        let mut builder = ALGBuilder::default();

        // Add five nodes
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();

        println!("five empty nodes: {builder:?}");

        // Link each node to its successor and link the last node with
        // the first one to form a cycle.
        for i in 0..5 {
            builder.add_edge(i, if i == 4 { 0 } else { i + 1 }, ())?;
        }

        println!("a cycle of five nodes: {builder:?}");

        // Remove the link from the last node to the first node.
        builder.remove_edge(4, 0, |_| true)?;

        println!("a line of five nodes: {builder:?}");

        // build a graph

        let graph = builder.build();

        println!("final graph: {graph:?}");

        Ok(())
    }

    #[test]
    fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
        let mut builder = ALGBuilder::default();

        // Add five nodes
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();
        builder.add_vertex();

        println!("five empty nodes: {builder:?}");

        // Errors in add_edge

        println!();
        println!("Testing errors in add_edge:");
        println!();

        assert!(matches!(
            builder.add_edge(0, 5, ()),
            Err(Error::IndexOutOfBounds(5, 5))
        ));

        println!("Right error for an index out of bounds as the target");

        assert!(matches!(
            builder.add_edge(10, 5, ()),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        println!("Right error for an index out of bounds as the source");

        assert!(matches!(
            builder.add_edge(10, 50, ()),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        println!("Right error for both indices out of bounds");

        // Errors in remove_edge

        println!();
        println!("Testing errors in remove_edge:");
        println!();

        assert!(matches!(
            builder.remove_edge(0, 5, |_| true),
            Err(Error::IndexOutOfBounds(5, 5))
        ));

        println!("Right error for an index out of bounds as the target");

        assert!(matches!(
            builder.remove_edge(10, 5, |_| true),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        println!("Right error for an index out of bounds as the source");

        assert!(matches!(
            builder.remove_edge(10, 50, |_| true),
            Err(Error::IndexOutOfBounds(10, 5))
        ));

        println!("Right error for both indices out of bounds");

        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));

        println!("No errors for removing a non-existing edge");

        println!();

        let graph = builder.build();

        println!("final graph: {graph:?}");

        Ok(())
    }
}