/*
 * Copyright (c) 2018, 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/>
 */

//! Abstraction of neighboring edges.
//!
//! This module implements the arguably simplest representation of a graph: for
//! each node the list of adjacent edges and nodes. No further information like
//! the number of nodes or edges in a graph is available.
//!
//! The purpose of the trait `Adjacencies` is therefore to abstract over the concept
//! if adjacent edges and nodes. Standard examples are "all edges" (in the
//! undirected sense), "incoming edges" and "outgoing edges" represented by the structs
//! `Neighbors`, `InEdges` and `OutEdges`.
//!
//! Some algorithms (e.g. breadth-first search or depth-first search) can be
//! described in terms of adjacencies only.
//!
//! # Example
//!
//! ```
//! use rs_graph::classes;
//! use rs_graph::Net;
//! use rs_graph::traits::*;
//! use rs_graph::adjacencies::*;
//!
//! let g = classes::peterson::<Net>();
//!
//! let neighs = Neighbors(&g);
//! let neighs = neighs.filter(|&(e, _)| {
//!   let (u,v) = g.enodes(e);
//!   (g.node_id(u) < 5) == (g.node_id(v) < 5)
//! });
//! for u in g.nodes() {
//!     assert_eq!(neighs.neighs(u).count(), 2);
//! }
//! ```

use crate::traits::{Directed, GraphType, Undirected};

/// Iterator over incident edges.
pub struct IncidenceIter<'a: 'g, 'g, G>(pub &'g G, pub Option<G::Incidence>)
where
    G: Adjacencies<'a>;

impl<'a: 'g, 'g, G> Iterator for IncidenceIter<'a, 'g, G>
where
    G: Adjacencies<'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(&it);
            self.1 = self.0.next(it);
            ev
        })
    }
}

pub trait Adjacencies<'a>: GraphType<'a> {
    type Incidence: 'a + Clone;

    fn first(&self, u: Self::Node) -> Option<Self::Incidence>;

    fn next(&self, it: Self::Incidence) -> Option<Self::Incidence>;

    fn get(&self, it: &Self::Incidence) -> (Self::Edge, Self::Node);

    fn neighs<'g>(&'g self, u: Self::Node) -> IncidenceIter<'a, 'g, Self>
    where
        Self: Sized,
    {
        IncidenceIter(self, self.first(u))
    }

    fn filter<P>(self, predicate: P) -> FilterAdjacencies<Self, P>
    where
        Self: Sized,
        P: for<'r> Fn(&'r (Self::Edge, Self::Node)) -> bool,
    {
        FilterAdjacencies(self, predicate)
    }
}

pub struct FilterAdjacencies<A, P>(A, P);

#[derive(Clone)]
pub struct Filtered<I>(I);

impl<'a, A, P> GraphType<'a> for FilterAdjacencies<A, P>
where
    A: Adjacencies<'a>,
{
    type Node = A::Node;
    type Edge = A::Edge;
}

impl<'a, A, P> Adjacencies<'a> for FilterAdjacencies<A, P>
where
    A: Adjacencies<'a>,
    P: 'a + Clone + for<'r> Fn(&'r (A::Edge, A::Node)) -> bool,
{
    type Incidence = Filtered<A::Incidence>;

    fn first(&self, u: Self::Node) -> Option<Self::Incidence> {
        let mut cur = self.0.first(u);
        while let Some(it) = cur {
            if (self.1)(&self.0.get(&it)) {
                return Some(Filtered(it));
            }
            cur = self.0.next(it);
        }
        None
    }

    fn next(&self, it: Self::Incidence) -> Option<Self::Incidence> {
        let mut cur = self.0.next(it.0);
        while let Some(it) = cur {
            if (self.1)(&self.0.get(&it)) {
                return Some(Filtered(it));
            }
            cur = self.0.next(it);
        }
        None
    }

    fn get(&self, it: &Self::Incidence) -> (Self::Edge, Self::Node) {
        self.0.get(&it.0)
    }
}

/// Neighbor access over all adjacent (undirected) edges.
pub struct Neighbors<'g, G>(pub &'g G);

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

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

    fn first(&self, u: Self::Node) -> Option<Self::Incidence> {
        self.0.first_neigh(u)
    }

    fn next(&self, it: Self::Incidence) -> Option<Self::Incidence> {
        self.0.next_neigh(it)
    }

    fn get(&self, it: &Self::Incidence) -> (Self::Edge, Self::Node) {
        self.0.get_neigh(it)
    }
}

/// Neighbor access over all outgoing edges of a `Digraph`.
pub struct OutEdges<'g, G>(pub &'g G);

impl<'a, 'g: 'a, G> GraphType<'a> for OutEdges<'g, G>
where
    G: Directed<'g>,
{
    type Node = G::Node;
    type Edge = G::Edge;
}

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

    fn first(&self, u: Self::Node) -> Option<Self::Incidence> {
        self.0.first_out(u)
    }

    fn next(&self, it: Self::Incidence) -> Option<Self::Incidence> {
        self.0.next_out(it)
    }

    fn get(&self, it: &Self::Incidence) -> (Self::Edge, Self::Node) {
        self.0.get_out(it)
    }
}

/// Neighbor access over all outgoing edges of a `Digraph`.
pub struct InEdges<'g, G>(pub &'g G);

impl<'a, 'g: 'a, G> GraphType<'a> for InEdges<'g, G>
where
    G: Directed<'g>,
{
    type Node = G::Node;
    type Edge = G::Edge;
}

impl<'a, 'g: 'a, G> Adjacencies<'a> for InEdges<'g, G>
where
    G: Directed<'g>,
{
    type Incidence = G::InEdge;

    fn first(&self, u: Self::Node) -> Option<Self::Incidence> {
        self.0.first_in(u)
    }

    fn next(&self, it: Self::Incidence) -> Option<Self::Incidence> {
        self.0.next_in(it)
    }

    fn get(&self, it: &Self::Incidence) -> (Self::Edge, Self::Node) {
        self.0.get_in(it)
    }
}

/// Implement Adjacencies for references.
impl<'a, A> Adjacencies<'a> for &'a A
where
    A: Adjacencies<'a>,
{
    type Incidence = A::Incidence;

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

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

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