/*
 * Copyright (c) 2017-2020 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program 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
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

//! Traits for graph data structures.
//!
//! The traits for graph data structures provide an additional level
//! of information about (the edges of) the graph. There are three
//! levels:
//!
//! 1. `Graph`: an undirected graph, edges have no defined source or
//!     sink.
//! 2. `Digraph`: a directed graph, each edge has a designated source
//!     and a designated sink node. Furthermore, there is the concept
//!     of "outgoing" and "incoming" edges. A `Digraph` is also a
//!     `Graph`, which basically means ignoring the direction
//!     information of the edges.

use crate::adjacencies::{InEdges, Neighbors, OutEdges};

pub mod refs;

/// Base information of a graph.
pub trait GraphType<'a> {
    /// Type of a node.
    type Node: 'a + Copy + Eq;

    /// Type of an edge.
    type Edge: 'a + Copy + Eq;
}

/// A (finite) graph with a known number of nodes and edges.
///
/// Finite graphs also provide access to the list of all nodes and edges.
pub trait GraphSize<'a>: GraphType<'a> {
    /// Type of an iterator over all nodes.
    type NodeIter: 'a + Iterator<Item = Self::Node>;

    /// Type of an iterator over all edges.
    type EdgeIter: 'a + Iterator<Item = Self::Edge>;

    /// Return the number of nodes in the graph.
    fn num_nodes(&self) -> usize;
    /// Return the number of edges in the graph.
    fn num_edges(&self) -> usize;

    /// Return an iterator over all nodes.
    fn nodes(&'a self) -> Self::NodeIter;

    /// Return an iterator over all edges.
    ///
    /// This iterator traverses only the forward edges.
    fn edges(&'a self) -> Self::EdgeIter;
}

pub struct NeighIter<'a, G>(&'a G, Option<G::Neigh>)
where
    G: Undirected<'a>;

impl<'a, G> Iterator for NeighIter<'a, G>
where
    G: Undirected<'a>,
{
    type Item = (G::Edge, G::Node);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(it) = self.1.take() {
            let ev = self.0.get_neigh(&it);
            self.1 = self.0.next_neigh(it);
            Some(ev)
        } else {
            None
        }
    }
}

/// A graph with list access to undirected incident edges.
pub trait Undirected<'a>: GraphSize<'a> {
    /// Type of a graph iterator over all incident edges.
    type Neigh: 'a + Clone;

    /// Return the nodes connected by an edge.
    ///
    /// The order of the nodes is undefined.
    fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node);

    /// Return an iterator over the edges adjacent to some node.
    fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh>;

    /// Advance the iterator to the next adjacent edge.
    fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh>;

    /// Return the edge and neighboring node of an iterator.
    fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node);

    /// Return an iterator over the edges adjacent to some node.
    fn neighs(&'a self, u: Self::Node) -> NeighIter<Self>
    where
        Self: Sized,
    {
        NeighIter(self, self.first_neigh(u))
    }

    /// Return access to the neighbors via an `Adjacencies` trait.
    ///
    /// This is the same as calling `Neighbors(&g)` on the graph.
    fn neighbors(&'a self) -> Neighbors<'a, Self>
    where
        Self: Sized,
    {
        Neighbors(self)
    }
}

/// A directed edge.
///
/// A directed edge is either incoming or outgoing.
pub trait DirectedEdge {
    /// The underlying edge.
    type Edge;

    /// Whether the edge is incoming.
    fn is_incoming(&self) -> bool;

    /// Whether the edge is outgoing.
    fn is_outgoing(&self) -> bool {
        !self.is_incoming()
    }

    /// The underlying edge.
    fn edge(&self) -> Self::Edge;
}

/// Iterator over outgoing (directed) edges.
pub struct OutEdgeIter<'a, G>(pub &'a G, pub Option<G::OutEdge>)
where
    G: Directed<'a>;

impl<'a, G> Iterator for OutEdgeIter<'a, G>
where
    G: Directed<'a>,
{
    type Item = (G::Edge, G::Node);
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.1.take().map(|it| {
            let ev = self.0.get_out(&it);
            self.1 = self.0.next_out(it);
            ev
        })
        // if let Some(it) = self.1.take() {
        //     let ev = self.0.get_out(&it);
        //     self.1 = self.0.next_out(it);
        //     Some(ev)
        // } else {
        //     None
        // }
    }
}

/// Iterator over outgoing (directed) edges.
pub struct InEdgeIter<'a, G>(&'a G, Option<G::InEdge>)
where
    G: Directed<'a>;

impl<'a, G> Iterator for InEdgeIter<'a, G>
where
    G: Directed<'a>,
{
    type Item = (G::Edge, G::Node);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(it) = self.1.take() {
            let ev = self.0.get_in(&it);
            self.1 = self.0.next_in(it);
            Some(ev)
        } else {
            None
        }
    }
}

/// Iterator over incident (directed) edges.
pub struct IncidentEdgeIter<'a, G>(&'a G, Option<G::IncidentEdge>)
where
    G: Directed<'a>;

impl<'a, G> Iterator for IncidentEdgeIter<'a, G>
where
    G: Directed<'a>,
{
    type Item = (G::DirectedEdge, G::Node);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(it) = self.1.take() {
            let ev = self.0.get_incident(&it);
            self.1 = self.0.next_incident(it);
            Some(ev)
        } else {
            None
        }
    }
}

/// A graph with list access to directed incident edges.
///
/// Note that each directed graph is also an undirected graph
/// by simply ignoring the direction of each edge. Hence, each
/// type implementing `Directed` must also implement `Undirected`.
///
/// This trait adds a few additional methods to explicitely access the
/// direction information of an edge. In particular, the direction
/// information can be used in the following ways:
///
///  - The `src` and `snk` methods return the source and sink nodes of
///    an edge.
///  - The iterators `outedges` and `inedges` iterate only over edges
///    leaving or entering a certain node, respectively.
pub trait Directed<'a>: Undirected<'a> {
    /// Type of a graph iterator over edges leaving a node.
    type OutEdge: 'a + Clone;

    /// Type of a graph iterator over edges entering a node.
    type InEdge: 'a + Clone;

    /// Type of an iterator over all incident edges.
    type IncidentEdge: 'a + Clone;

    /// Type of a directed edge.
    type DirectedEdge: 'a + DirectedEdge<Edge = Self::Edge> + Copy + Eq;

    /// Return the source node of an edge.
    fn src(&'a self, e: Self::Edge) -> Self::Node;

    /// Return the sink node of an edge.
    fn snk(&'a self, e: Self::Edge) -> Self::Node;

    /// Return an iterator over the edges leaving a node.
    fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge>;

    /// Advance the iterator to the next outgoing edge.
    fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge>;

    /// Return the edge and sink node of an outgoing edge iterator.
    fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node);

    /// Return an iterator over the outgoing edges of a node.
    fn outedges(&'a self, u: Self::Node) -> OutEdgeIter<'a, Self>
    where
        Self: Sized,
    {
        OutEdgeIter(self, self.first_out(u))
    }

    /// Return access to the outgoing arcs via an `Adjacencies` trait.
    ///
    /// This is the same as calling `OutEdges(&g)` on the graph.
    fn outgoing(&'a self) -> OutEdges<'a, Self>
    where
        Self: Sized,
    {
        OutEdges(self)
    }

    /// Return an iterator over the edges entering a node.
    fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge>;

    /// Advance the iterator to the next incoming edge.
    fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge>;

    /// Return the edge and sink node of an incoming edge iterator.
    fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node);

    /// Return an iterator over the incoming edges of a node.
    fn inedges(&'a self, u: Self::Node) -> InEdgeIter<'a, Self>
    where
        Self: Sized,
    {
        InEdgeIter(self, self.first_in(u))
    }

    /// Return access to the incoming arcs via an `Adjacencies` trait.
    ///
    /// This is the same as calling `InEdges(&g)` on the graph.
    fn incoming(&'a self) -> InEdges<'a, Self>
    where
        Self: Sized,
    {
        InEdges(self)
    }

    /// Return an iterator over the edges entering a node.
    fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge>;

    /// Advance the iterator to the next incoming edge.
    fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge>;

    /// Return the edge and sink node of an incoming edge iterator.
    fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node);

    /// Return access to all incident edges of a node.
    fn incident_edges(&'a self, u: Self::Node) -> IncidentEdgeIter<'a, Self>
    where
        Self: Sized,
    {
        IncidentEdgeIter(self, self.first_incident(u))
    }
}

/// A trait for general undirected, sized graphs.
pub trait Graph<'a>: GraphSize<'a> + Undirected<'a> {}

impl<'a, G> Graph<'a> for G where G: GraphSize<'a> + Undirected<'a> {}

/// A trait for general directed, sized graphs.
pub trait Digraph<'a>: Graph<'a> + Directed<'a> {}

impl<'a, G> Digraph<'a> for G where G: GraphSize<'a> + Directed<'a> {}

/// An item that has an index.
pub trait Indexable {
    fn index(&self) -> usize;
}

/// Associates nodes and edges with unique ids.
pub trait IndexGraph<'a>: Graph<'a> {
    /// Return a unique id associated with a node.
    fn node_id(&self, u: Self::Node) -> usize;

    /// Return the node associated with the given id.
    ///
    /// The method panics if the id is invalid.
    fn id2node(&'a self, id: usize) -> Self::Node;

    /// Return a unique id associated with an edge.
    ///
    /// The returned id is the same for the edge and its reverse edge.
    fn edge_id(&self, e: Self::Edge) -> usize;

    /// Return the edge associated with the given id.
    ///
    /// The method returns the forward edge.
    ///
    /// The method panics if the id is invalid.
    fn id2edge(&'a self, id: usize) -> Self::Edge;
}

/// A `Digraph` that is also an `IndexGraph`.
pub trait IndexDigraph<'a>: IndexGraph<'a> + Digraph<'a> {}

impl<'a, T> IndexDigraph<'a> for T where T: IndexGraph<'a> + Digraph<'a> {}

/// Marker trait for graphs with directly numbered nodes and edges.
pub trait NumberedGraph<'a>: Graph<'a>
where
    <Self as GraphType<'a>>::Node: Indexable,
    <Self as GraphType<'a>>::Edge: Indexable,
{
}

impl<'a, G> NumberedGraph<'a> for G
where
    G: Graph<'a>,
    G::Node: Indexable,
    G::Edge: Indexable,
{
}

/// Marker trait for digraphs with directly numbered nodes and edges.
pub trait NumberedDigraph<'a>: NumberedGraph<'a> + Digraph<'a>
where
    <Self as GraphType<'a>>::Node: Indexable,
    <Self as GraphType<'a>>::Edge: Indexable,
{
}

impl<'a, G> NumberedDigraph<'a> for G
where
    G: Digraph<'a> + NumberedGraph<'a>,
    G::Node: Indexable,
    G::Edge: Indexable,
{
}

impl<'a, 'g: 'a, G> GraphType<'a> for &'g G
where
    G: GraphType<'g>,
{
    type Node = G::Node;

    type Edge = G::Edge;
}

impl<'a, 'g: 'a, G> GraphSize<'a> for &'g G
where
    G: GraphSize<'g>,
{
    type NodeIter = G::NodeIter;

    type EdgeIter = G::EdgeIter;

    fn num_nodes(&self) -> usize {
        (*self).num_nodes()
    }

    fn num_edges(&self) -> usize {
        (*self).num_edges()
    }

    fn nodes(&'a self) -> Self::NodeIter {
        (*self).nodes()
    }

    fn edges(&'a self) -> Self::EdgeIter {
        (*self).edges()
    }
}

impl<'a, 'g: 'a, G> Undirected<'a> for &'g G
where
    G: Undirected<'g>,
{
    type Neigh = G::Neigh;

    fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
        (*self).enodes(e)
    }

    fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh> {
        (*self).first_neigh(u)
    }

    fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh> {
        (*self).next_neigh(it)
    }

    fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
        (*self).get_neigh(it)
    }
}

impl<'a, 'g: 'a, G> IndexGraph<'a> for &'g G
where
    G: IndexGraph<'g>,
{
    fn node_id(&self, u: Self::Node) -> usize {
        (*self).node_id(u)
    }

    fn id2node(&'a self, id: usize) -> Self::Node {
        (*self).id2node(id)
    }

    fn edge_id(&self, e: Self::Edge) -> usize {
        (*self).edge_id(e)
    }

    fn id2edge(&'a self, id: usize) -> Self::Edge {
        (*self).id2edge(id)
    }
}

impl<'a, 'g: 'a, G> Directed<'a> for &'g G
where
    G: Directed<'g>,
{
    type OutEdge = G::OutEdge;

    type InEdge = G::InEdge;

    type IncidentEdge = G::IncidentEdge;

    type DirectedEdge = G::DirectedEdge;

    fn src(&'a self, e: Self::Edge) -> Self::Node {
        (*self).src(e)
    }

    fn snk(&'a self, e: Self::Edge) -> Self::Node {
        (*self).snk(e)
    }

    fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge> {
        (*self).first_out(u)
    }

    fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge> {
        (*self).next_out(it)
    }

    fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
        (*self).get_out(it)
    }

    fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge> {
        (*self).first_in(u)
    }

    fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge> {
        (*self).next_in(it)
    }

    fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
        (*self).get_in(it)
    }

    fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge> {
        (*self).first_incident(u)
    }

    fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
        (*self).next_incident(it)
    }

    fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
        (*self).get_incident(it)
    }
}

impl<'a, G> refs::GraphSizeRef<'a> for &'a G
where
    G: GraphSize<'a>,
{
    fn nodes(&self) -> Self::NodeIter {
        (*self).nodes()
    }

    fn edges(&self) -> Self::EdgeIter {
        (*self).edges()
    }
}

impl<'a, G> refs::UndirectedRef<'a> for &'a G
where
    G: Undirected<'a>,
{
    fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
        (*self).enodes(e)
    }

    fn first_neigh(&self, u: Self::Node) -> Option<Self::Neigh> {
        (*self).first_neigh(u)
    }

    fn next_neigh(&self, it: Self::Neigh) -> Option<Self::Neigh> {
        (*self).next_neigh(it)
    }

    fn get_neigh(&self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
        (*self).get_neigh(it)
    }
}

impl<'a, G> refs::DirectedRef<'a> for &'a G
where
    G: Directed<'a>,
{
    fn src(&self, u: Self::Edge) -> Self::Node {
        (*self).src(u)
    }

    fn snk(&self, u: Self::Edge) -> Self::Node {
        (*self).snk(u)
    }

    fn first_out(&self, u: Self::Node) -> Option<Self::OutEdge> {
        (*self).first_out(u)
    }

    fn next_out(&self, it: Self::OutEdge) -> Option<Self::OutEdge> {
        (*self).next_out(it)
    }

    fn get_out(&self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
        (*self).get_out(it)
    }

    fn first_in(&self, u: Self::Node) -> Option<Self::InEdge> {
        (*self).first_in(u)
    }

    fn next_in(&self, it: Self::InEdge) -> Option<Self::InEdge> {
        (*self).next_in(it)
    }

    fn get_in(&self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
        (*self).get_in(it)
    }

    fn first_incident(&self, u: Self::Node) -> Option<Self::IncidentEdge> {
        (*self).first_incident(u)
    }

    fn next_incident(&self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
        (*self).next_incident(it)
    }

    fn get_incident(&self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
        (*self).get_incident(it)
    }
}

impl<'a, G> refs::IndexGraphRef<'a> for &'a G
where
    G: IndexGraph<'a>,
{
    fn id2node(&self, id: usize) -> Self::Node {
        (*self).id2node(id)
    }

    fn id2edge(&self, id: usize) -> Self::Edge {
        (*self).id2edge(id)
    }
}