// Copyright (c) 2015, 2016, 2017, 2018 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/>
//

//! A library for basic graph data structures and algorithms.

/// Create a node vector associated with a graph.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `idxnodevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = idxnodevec![&g; 0];
/// assert!(g.nodes().all(|u| weights[u] == 0));
/// # }
/// ```
///
/// Convert an existing vector to a `IndexNodeVec`, use `nodevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_nodes()`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_nodes()).collect();
/// let weights = idxnodevec![&g, weights];
/// assert!(g.nodes().all(|u| weights[u] == g.node_id(u)));
/// # }
/// ```
#[macro_export]
macro_rules! idxnodevec {
    ($g:expr; $elem:expr) => {
        $crate::vec::IndexNodeVec::from_vec($g, vec![$elem; $g.num_nodes()])
    };
    ($g:expr, $vec:expr) => {
        $crate::vec::IndexNodeVec::from_vec($g, $vec)
    };
}

/// Create an edge vector associated with a graph.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `idxedgevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = idxedgevec![&g; 0];
/// assert!(g.edges().all(|e| weights[e] == 0));
/// # }
/// ```
///
/// Convert an existing vector to an `IndexEdgeVec`, use `idxedgevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_edges()`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_edges()).collect();
/// let weights = idxedgevec![&g, weights];
/// assert!(g.edges().all(|e| weights[e] == g.edge_id(e)));
/// # }
/// ```
#[macro_export]
macro_rules! idxedgevec {
    ($g:expr; $elem:expr) => {
        $crate::vec::IndexEdgeVec::from_vec($g, vec![$elem; $g.num_edges()])
    };
    ($g:expr, $vec:expr) => {
        $crate::vec::IndexEdgeVec::from_vec($g, $vec)
    };
}

/// Create a biedge vector associated with a network.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `idxbiedgevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, Network, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = idxbiedgevec![&g; 0];
/// assert!(g.edges().all(|e| weights[e] == 0 && weights[g.reverse(e)] == 0));
/// # }
/// ```
///
/// Convert an existing vector to a `IndexBiEdgeVec`, use `idxbiedgevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_edges() * 2`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, Network, IndexNetwork, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_edges() * 2).collect();
/// let weights = idxbiedgevec![&g, weights];
/// assert!(g.edges().all(|e| {
///     let f = g.reverse(e);
///     weights[e] == g.biedge_id(e) && weights[f] == g.biedge_id(f)
/// }));
/// # }
/// ```
#[macro_export]
macro_rules! idxbiedgevec {
    ($g:expr; $elem:expr) => {
        $crate::vec::IndexBiEdgeVec::from_vec($g, vec![$elem; $g.num_edges() * 2])
    };
    ($g:expr, $vec:expr) => {
        $crate::vec::IndexBiEdgeVec::from_vec($g, $vec)
    };
}

/// Create a node vector associated with a `LinkedListGraph`.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `nodevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = nodevec![&g; 0];
/// assert!(g.nodes().all(|u| weights[u] == 0));
/// # }
/// ```
///
/// Convert an existing vector to a `NodeVec`, use `nodevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_nodes()`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_nodes()).collect();
/// let weights = nodevec![&g, weights];
/// assert!(g.nodes().all(|u| weights[u] == g.node_id(u)));
/// # }
/// ```
#[macro_export]
macro_rules! nodevec {
    ($g:expr; $elem:expr) => {
        $crate::NodeVec::from(vec![$elem; $g.num_nodes()])
    };
    ($g:expr, $vec:expr) => {{
        assert_eq!(
            $vec.len(),
            $g.num_nodes(),
            "Vector must have len {} (got: {})",
            $g.num_nodes(),
            $vec.len()
        );
        $crate::NodeVec::from($vec)
    }};
}

/// Create an edge vector associated with a `LinkedListGraph`.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `edgevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = edgevec![&g; 0];
/// assert!(g.edges().all(|e| weights[e] == 0));
/// # }
/// ```
///
/// Convert an existing vector to an `EdgeVec`, use `edgevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_edges()`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_edges()).collect();
/// let weights = edgevec![&g, weights];
/// assert!(g.edges().all(|e| weights[e] == g.edge_id(e)));
/// # }
/// ```
#[macro_export]
macro_rules! edgevec {
    ($g:expr; $elem:expr) => {
        $crate::EdgeVec::from(vec![$elem; $g.num_edges()])
    };
    ($g:expr, $vec:expr) => {{
        assert_eq!(
            $vec.len(),
            $g.num_edges(),
            "Vector must have len {} (got: {})",
            $g.num_edges(),
            $vec.len()
        );
        $crate::EdgeVec::from($vec)
    }};
}

/// Create a biedge vector associated with a `LinkedListGraph`.
///
/// # Example
///
/// Create a vector with all elements set to some value, use `biedgevec![g; x]`
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, Network, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights = biedgevec![&g; 0];
/// assert!(g.edges().all(|e| weights[e] == 0 && weights[g.reverse(e)] == 0));
/// # }
/// ```
///
/// Convert an existing vector to a `BiEdgeVec`, use `biedgevec![g, v]`.
/// Note that the size of `v` must be exactly `g.num_edges() * 2`.
///
/// ```
/// # #[macro_use]
/// # extern crate rs_graph as graph;
/// # use graph::{Graph, IndexGraph, Network, IndexNetwork, LinkedListGraph};
/// # use graph::classes::peterson;
/// #
/// # fn main() {
/// let g = peterson::<LinkedListGraph>();
/// let weights: Vec<_> = (0..g.num_edges() * 2).collect();
/// let weights = biedgevec![&g, weights];
/// assert!(g.edges().all(|e| {
///     let f = g.reverse(e);
///     weights[e] == g.biedge_id(e) && weights[f] == g.biedge_id(f)
/// }));
/// # }
/// ```
#[macro_export]
macro_rules! biedgevec {
    ($g:expr; $elem:expr) => {
        $crate::BiEdgeVec::from(vec![$elem; $g.num_edges() * 2])
    };
    ($g:expr, $vec:expr) => {{
        assert_eq!(
            $vec.len(),
            $g.num_edges() * 2,
            "Vector must have len {} (got: {})",
            $g.num_edges() * 2,
            $vec.len()
        );
        $crate::BiEdgeVec::from($vec)
    }};
}

mod num {
    pub extern crate num_iter as iter;
    pub extern crate num_traits as traits;
}

#[cfg(feature = "failure")]
extern crate failure;
#[cfg(feature = "failure_derive")]
#[macro_use]
extern crate failure_derive;

#[cfg(feature = "serialize")]
extern crate serde;
#[cfg(feature = "serialize")]
#[macro_use]
extern crate serde_derive;

use std::ops::{Index, IndexMut};

// # Data structures

pub mod graph;
pub use self::graph::{BiNumberedEdge, NumberedDigraph, NumberedEdge, NumberedGraph, NumberedNetwork, NumberedNode};
pub use self::graph::{Digraph, Edge, Graph, Network, Node};
pub use self::graph::{IndexDigraph, IndexGraph, IndexNetwork};

pub mod reversedigraph;
pub use self::reversedigraph::{reverse, ReverseDigraph};

pub mod builder;
pub use builder::{Buildable, Builder};

pub mod attributed;
pub use self::attributed::{
    Attributed, AttributedBuilder, AttributedGraph, AttributedNetwork, Attributes, NetworkAttributes,
};

pub mod linkedlistgraph;
pub use self::linkedlistgraph::LinkedListGraph;

/// Graph classes
pub mod classes;

/// The default graph type.
///
/// A linked-list graph with up to 2^31 nodes and edges.
pub type Net = self::LinkedListGraph<u32>;

/// Trait for maps assigning values to nodes of a graph.
pub trait NodeMap<'a, G, T>: Index<G::Node, Output = T>
where
    G: Graph<'a>,
{
}

impl<'a, G, T, I> NodeMap<'a, G, T> for I
where
    G: Graph<'a>,
    I: Index<G::Node, Output = T>,
{
}

/// Trait for mutable maps assigning values to nodes of a graph.
pub trait NodeMapMut<'a, G, T>: NodeMap<'a, G, T> + IndexMut<G::Node, Output = T>
where
    G: Graph<'a>,
{
}

impl<'a, G, T, I> NodeMapMut<'a, G, T> for I
where
    G: Graph<'a>,
    I: IndexMut<G::Node, Output = T>,
{
}

/// Trait for maps assigning values to edges of a graph.
pub trait EdgeMap<'a, G, T>: Index<G::Edge, Output = T>
where
    G: Graph<'a>,
{
}

impl<'a, G, T, I> EdgeMap<'a, G, T> for I
where
    G: Graph<'a>,
    I: Index<G::Edge, Output = T>,
{
}

/// Trait for mutable maps assigning values to edges of a graph.
pub trait EdgeMapMut<'a, G, T>: EdgeMap<'a, G, T> + IndexMut<G::Edge, Output = T>
where
    G: Graph<'a>,
{
}

impl<'a, G, T, I> EdgeMapMut<'a, G, T> for I
where
    G: Graph<'a>,
    I: IndexMut<G::Edge, Output = T>,
{
}

pub mod vec;
pub use vec::{BiEdgeSlice, EdgeSlice, NodeSlice};
pub use vec::{BiEdgeVec, EdgeVec, NodeVec};
pub use vec::{IndexBiEdgeSlice, IndexEdgeSlice, IndexNodeSlice};
pub use vec::{IndexBiEdgeVec, IndexEdgeVec, IndexNodeVec};

// # Algorithms

pub mod algorithms;
pub mod bfs;
pub mod branching;
pub mod dfs;
pub mod maxflow;
pub mod mst;
pub mod shortestpath;

// # Drawing

pub mod draw;

#[cfg(any(feature = "dimacs"))]
pub mod dimacs;
#[cfg(any(feature = "steinlib"))]
pub mod steinlib;