#![warn(missing_docs)]
//! This file implements a data type that implements the trait
//! [`Graph`][super::Graph].  This data type represents graphs using
//! adjacency sets internally.
//!
//! I need this because the derivatives languages should not allow
//! duplications of languages, so it is more convenient if the
//! underlying graph type **cannot** represent duplicate edges.

use super::{ExtGraph, Graph};
use crate::error::Error;

// If one wants to use another implementation for a set, import that
// as Set, and nothing else needs to be changed, ideally.
use std::collections::{hash_set::Iter, HashSet as Set};

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

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

#[derive(Debug, Clone, Default)]
struct ASNode {
    children: Set<ASEdge>,
}

impl ASNode {
    fn new(children: Set<ASEdge>) -> Self {
        Self { children }
    }
}

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

/// A delegation of iterators.
///
/// This is here to avoid using a boxed pointer, in order to save some
/// allocations.
pub struct ASIter<'a> {
    iter: Iter<'a, ASEdge>,
}

impl<'a> Iterator for ASIter<'a> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|edge| edge.to)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<'a> ExactSizeIterator for ASIter<'a> {
    fn len(&self) -> usize {
        self.iter.len()
    }
}

impl Graph for ASGraph {
    type Iter<'a> = ASIter<'a>;

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

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

    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
        match self.nodes.get(node_id) {
            Some(node) => {
                let iter = node.children.iter();
                Ok(Self::Iter { iter })
            }
            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())),
        }
    }

    #[inline]
    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(&ASEdge::new(target)))
        }
    }
}

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

        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.insert(ASEdge::new(edge_to));
        }

        let new_node = ASNode::new(new_node_children);

        self.nodes.push(new_node);

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

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

    #[test]
    fn test_graph_apis() -> Result<(), Error> {
        let mut graph = ASGraph::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::<Set<_>>(), {
            let mut set = Set::default();
            set.insert(1);
            set.insert(3);
            set.insert(2);
            set
        });

        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 = ASGraph::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 = ASGraph::default();

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

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

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

        Ok(())
    }
}