
extern crate petgraph;
#[macro_use] extern crate quickcheck;
extern crate itertools;
extern crate serde_json;
extern crate bincode;
#[macro_use] extern crate defmac;

use std::collections::HashSet;
use std::fmt::Debug;
use std::iter::FromIterator;

use itertools::{Itertools, repeat_n};
use itertools::assert_equal;

use petgraph::prelude::*;
use petgraph::EdgeType;
use petgraph::graph::{node_index, edge_index, IndexType};
use petgraph::visit::EdgeRef;
use petgraph::visit::NodeIndexable;
use petgraph::visit::IntoEdgeReferences;

// graphs are the equal, down to graph indices
// this is a strict notion of graph equivalence:
//
// * Requires equal node and edge indices, equal weights
// * Does not require: edge for node order
pub fn assert_graph_eq<N, N2, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>, h: &Graph<N2, E, Ty, Ix>)
    where N: PartialEq<N2> + Debug, N2: PartialEq<N2> + Debug, E: PartialEq + Debug,
          Ty: EdgeType,
          Ix: IndexType,
{
    assert_eq!(g.node_count(), h.node_count());
    assert_eq!(g.edge_count(), h.edge_count());

    // same node weigths
    assert_equal(g.raw_nodes().iter().map(|n| &n.weight),
                 h.raw_nodes().iter().map(|n| &n.weight));

    // same edge weigths
    assert_equal(g.raw_edges().iter().map(|n| &n.weight),
                 h.raw_edges().iter().map(|n| &n.weight));

    for e1 in g.edge_references() {
        let (a2, b2) = h.edge_endpoints(e1.id()).unwrap();
        assert_eq!(e1.source(), a2);
        assert_eq!(e1.target(), b2);
    }

    for index in g.node_indices() {
        let outgoing1 = <HashSet<_>>::from_iter(g.neighbors(index));
        let outgoing2 = <HashSet<_>>::from_iter(h.neighbors(index));
        assert_eq!(outgoing1, outgoing2);
        let incoming1 = <HashSet<_>>::from_iter(g.neighbors_directed(index, Incoming));
        let incoming2 = <HashSet<_>>::from_iter(h.neighbors_directed(index, Incoming));
        assert_eq!(incoming1, incoming2);
    }
}

// graphs are the equal, down to graph indices
// this is a strict notion of graph equivalence:
//
// * Requires equal node and edge indices, equal weights
// * Does not require: edge for node order
pub fn assert_stable_graph_eq<N, E>(g: &StableGraph<N, E>, h: &StableGraph<N, E>)
    where N: PartialEq + Debug, E: PartialEq + Debug,
{
    assert_eq!(g.node_count(), h.node_count());
    assert_eq!(g.edge_count(), h.edge_count());

    // same node weigths
    assert_equal(
        (0..g.node_bound()).map(|i| g.node_weight(node_index(i))),
        (0..h.node_bound()).map(|i| h.node_weight(node_index(i))));

    let last_edge_g = g.edge_references().next_back();
    let last_edge_h = h.edge_references().next_back();

    assert_eq!(last_edge_g.is_some(), last_edge_h.is_some());
    if let (Some(lg), Some(lh)) = (last_edge_g, last_edge_h) {
        let lgi = lg.id().index();
        let lhi = lh.id().index();
        // same edge weigths
        assert_equal(
            (0..lgi).map(|i| g.edge_weight(edge_index(i))),
            (0..lhi).map(|i| h.edge_weight(edge_index(i))));
    }

    for e1 in g.edge_references() {
        let (a2, b2) = h.edge_endpoints(e1.id()).unwrap();
        assert_eq!(e1.source(), a2);
        assert_eq!(e1.target(), b2);
    }

    for index in g.node_indices() {
        let outgoing1 = <HashSet<_>>::from_iter(g.neighbors(index));
        let outgoing2 = <HashSet<_>>::from_iter(h.neighbors(index));
        assert_eq!(outgoing1, outgoing2);
        let incoming1 = <HashSet<_>>::from_iter(g.neighbors_directed(index, Incoming));
        let incoming2 = <HashSet<_>>::from_iter(h.neighbors_directed(index, Incoming));
        assert_eq!(incoming1, incoming2);
    }
}


fn make_graph<Ty, Ix>() -> Graph<&'static str, i32, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    let mut g = Graph::default();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");
    let d = g.add_node("D");
    let e = g.add_node("E");
    let f = g.add_node("F");
    g.extend_with_edges(&[
        (a, b, 7),
        (c, a, 9),
        (a, d, 14),
        (b, c, 10),
        (d, c, 2),
        (d, e, 9),
        (b, f, 15),
        (c, f, 11),
        (e, f, 6),
    ]);
    // Remove a node to make the structure a bit more interesting
    g.remove_node(d);
    g
}

fn make_stable_graph<Ty, Ix>() -> StableGraph<&'static str, i32, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    let mut g = StableGraph::default();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");
    let d = g.add_node("D");
    let e = g.add_node("E");
    let f = g.add_node("F");
    g.extend_with_edges(&[
        (a, b, 7),
        (c, a, 9),
        (a, d, 14),
        (b, c, 10),
        (d, c, 2),
        (d, e, 9),
        (b, f, 15),
        (c, f, 11),
        (e, f, 6),
    ]);
    // Remove a node to make the structure a bit more interesting
    g.remove_node(d);
    g
}

// json macros
defmac!(tojson ref g => serde_json::to_string(g).unwrap());
defmac!(fromjson ref data => serde_json::from_str(data).unwrap());
defmac!(rejson ref g => fromjson!(tojson!(g)));

#[test]
fn json_graph_str_i32() {
    let g1: DiGraph<_, _> = make_graph();
    let g2: Graph<String, i32> = rejson!(g1);
    assert_graph_eq(&g1, &g2);
    assert_graph_eq(&g2, &g1);
}

#[test]
fn json_graph_nils() {
    let g1 = make_graph().map(|_, _| (), |_, _| ());

    let g2: Graph<(), ()> = rejson!(g1);
    assert_graph_eq(&g1, &g2);
    assert_graph_eq(&g2, &g1);
}

const DIGRAPH_NILS: &str = r#"{
    "nodes":[null,null,null,null,null],
    "edge_property": "directed",
    "edges":[[0,1,null],[2,0,null],[1,3,null],[1,2,null],[2,3,null],[4,3,null]]
    }"#;

const DIGRAPH_NILS_INDEX_OOB: &str = r#"{
    "nodes":[null,null,null,null,null],
    "edge_property": "directed",
    "edges":[[0,1,null],[2,5,null],[1,3,null],[1,2,null],[2,3,null],[4,3,null]]
    }"#;

const DIGRAPH_NILS_INDEX_OUTSIDE_U8: &str = r#"{
    "nodes":[null,null,null,null,null],
    "edge_property": "directed",
    "edges":[[0,1,null],[2,300,null],[1,3,null],[1,2,null],[2,3,null],[4,3,null]]
    }"#;

const DIGRAPH_STRI32: &str = r#"{
    "nodes":["A","B","C","D","E","F"],
    "edge_property": "directed",
    "edges":[[0,1,7],[2,0,9],[0,3,14],[1,2,10],[3,2,2],[3,4,9],[1,5,15],[2,5,11],[4,5,6]]
    }"#;


type DiGraphNils = DiGraph<(), ()>;
type UnGraphNils = UnGraph<(), ()>;
type DiGraphNilsU8 = DiGraph<(), (), u8>;
type DiGraphStrI32 = DiGraph<String, i32>;

#[test]
fn from_json_digraph_nils() {
    let _: DiGraphNils = fromjson!(DIGRAPH_NILS);
}

#[test]
#[should_panic(expected="edge property mismatch")]
fn from_json_graph_nils_edge_property_mismatch() {
    let _: UnGraphNils = fromjson!(DIGRAPH_NILS);
}

#[test]
#[should_panic(expected="does not exist")]
fn from_json_graph_nils_index_oob() {
    let _: DiGraphNils = fromjson!(DIGRAPH_NILS_INDEX_OOB);
}

#[test]
#[should_panic(expected="expected u8")]
fn from_json_graph_nils_index_too_large() {
    let _: DiGraphNilsU8 = fromjson!(DIGRAPH_NILS_INDEX_OUTSIDE_U8);
}

#[test]
fn from_json_graph_directed_str_i32() {
    let _: DiGraphStrI32 = fromjson!(DIGRAPH_STRI32);
}

#[test]
#[should_panic(expected="expected unit")]
fn from_json_graph_from_edge_type_1() {
    let _: DiGraphNils = fromjson!(DIGRAPH_STRI32);
}

#[test]
#[should_panic(expected="expected a string")]
fn from_json_graph_from_edge_type_2() {
    let _: DiGraphStrI32 = fromjson!(DIGRAPH_NILS);
}

#[test]
fn from_json_digraph_str_i32() {
    let g4nodes = ["A","B","C","D","E","F"];
    let g4edges = [[0,1,7],[2,0,9],[0,3,14],[1,2,10],[3,2,2],[3,4,9],[1,5,15],[2,5,11],[4,5,6]];

    type GSI = DiGraph<String, i32>;
    type GSISmall = DiGraph<String, i32, u8>;

    let g4: GSI = fromjson!(DIGRAPH_STRI32);

    for ni in g4.node_indices() {
        assert_eq!(&g4nodes[ni.index()], &g4[ni]);
    }
    for e in g4.edge_references() {
        let edge_data = g4edges[e.id().index()];

        let (s, t) = g4.edge_endpoints(e.id()).unwrap();
        assert_eq!(edge_data[0] as usize, s.index());
        assert_eq!(edge_data[1] as usize, t.index());

        assert_eq!(edge_data[2], g4[e.id()]);
    }

    let _g4small: GSISmall = fromjson!(DIGRAPH_STRI32);
}

#[test]
fn from_json_nodes_too_big() {
    // ensure we fail if node or edge count exceeds index max
    use serde_json::from_str;

    let j1_big = &format!("{}{}{}",
                          r#"
                          {"nodes": [
                          "#,
                          repeat_n(0, 300).format(", "),
                          r#"
                          ],
                          "edge_property": "directed",
                          "edges": []
                          }
                          "#);

    type G8 = DiGraph<i32, (), u8>;
    type G16 = DiGraph<i32, (), u16>;
    type G32 = DiGraph<i32, (), u32>;
    type G64 = DiGraph<i32, (), usize>;

    type H1 = DiGraph<i32, i32>;

    assert!(from_str::<G8>(j1_big).is_err());
    let _: G16 = fromjson!(j1_big); // assert
    let _: G32 = fromjson!(j1_big); // assert
    let _: G64 = fromjson!(j1_big); // assert

    // other edge weight is also ok -- because it has no edges
    let _: H1 = fromjson!(j1_big); // assert
}

#[test]
fn from_json_edges_too_big() {
    // ensure we fail if node or edge count exceeds index max
    use serde_json::from_str;

    let j1_big = format!("{}{}{}",
                         r#"
                         {"nodes": [0],
                         "edge_property": "directed",
                         "edges": ["#,
                         repeat_n("[0, 0, 1]", (1 << 16) - 1).format(", "),
                         "]}");

    type G8 = DiGraph<i32, i32, u8>;
    type G16 = DiGraph<i32, i32, u16>;
    type G32 = DiGraph<i32, i32, u32>;
    type G64 = DiGraph<i32, i32, usize>;

    assert!(from_str::<G8>(&j1_big).is_err());
    assert!(from_str::<G16>(&j1_big).is_err());
    let _: G32 = fromjson!(j1_big); // assert
    let _: G64 = fromjson!(j1_big); // assert
}

#[test]
fn json_stable_graph_str() {
    let g1 = make_stable_graph();

    let g2: StableGraph<String, i32> = rejson!(g1);

    // map &str -> String
    let g1 = g1.map(|_, s| s.to_string(), |_, &w| w);
    assert_stable_graph_eq(&g1, &g2);
}

#[test]
fn json_stable_graph_nils() {
    let g1 = make_stable_graph().map(|_, _| (), |_, _| ());
    let g2 = rejson!(g1);
    assert_stable_graph_eq(&g1, &g2);
}


// bincode macros
defmac!(encode ref g => bincode::serialize(g).unwrap());
defmac!(decode ref data => bincode::deserialize(data).unwrap());
defmac!(recode ref g => decode!(encode!(g)));

#[test]
fn bincode_stablegraph_to_graph_i32_0() {
    let g1 = StableGraph::<i32, i32>::new();
    let g2: Graph<i32, i32> = recode!(g1);
    assert_graph_eq(&g2, &Graph::<i32, i32>::default());
}

#[test]
fn bincode_graph_to_stablegraph_i32_0() {
    let g1 = Graph::<i32, i32>::new();
    let g2: StableGraph<i32, i32> = recode!(g1);
    assert_stable_graph_eq(&g2, &StableGraph::<i32, i32>::default());
}

#[test]
fn bincode_graph_to_graph_i32_1() {
    let mut g1 = Graph::<i32, i32>::new();
    let x = 1729;
    g1.add_node(x);
    let g2: Graph<i32, i32> = recode!(g1);

    assert_graph_eq(&g1, &g2);
}

#[test]
fn bincode_stablegraph_added2_removed2() {
    // from quickcheck failure case:
    // StableGraph { Ty: "Directed", node_count: 4, edge_count: 1, edges: (0,
    // 2), node weights: {0: -55, 2: 83, 3: -12, 5: -2}, edge weights: {0: 75},
    //   free_node: NodeIndex(1), free_edge: EdgeIndex(4294967295) }
    let mut g1 = StableGraph::<i32, i32>::new();
    let x = 1729;
    let a = g1.add_node(x);
    let b = g1.add_node(x + 1);
    g1.remove_node(a);
    g1.remove_node(b);
    let g2: StableGraph<i32, i32> = recode!(g1);

    assert_stable_graph_eq(&g1, &g2);
}

#[test]
fn bincode_stablegraph_added3_removed2() {
    // from quickcheck failure case:
    // StableGraph { Ty: "Directed", node_count: 1, edge_count: 0, node weights:
    // {2: -87}, edge weights: {}, free_node: NodeIndex(3), free_edge:
    // EdgeIndex(3) }
    let mut g1 = StableGraph::<i32, i32>::new();
    let x = 1729;
    let a = g1.add_node(x);
    let b = g1.add_node(x + 1);
    let _c = g1.add_node(x + 2);
    g1.remove_node(a);
    g1.remove_node(b);
    let g2: StableGraph<i32, i32> = recode!(g1);

    assert_stable_graph_eq(&g1, &g2);
}

#[test]
fn bincode_stablegraph_to_graph_i32_1() {
    let mut g1 = StableGraph::<i32, i32>::new();
    let x = 1729;
    g1.add_node(x);
    let g2: Graph<i32, i32> = recode!(g1);

    assert_eq!(g2.node_count(), 1);
    assert_eq!(g2.edge_count(), 0);
    assert_eq!(g2[node_index(0)], x);
}

quickcheck! {
    fn json_graph_to_stablegraph_to_graph(g1: Graph<i32, i32>) -> () {
        let sg: StableGraph<i32, i32> = rejson!(g1);
        let g2: Graph<i32, i32> = rejson!(sg);
        assert_graph_eq(&g1, &g2);
    }

    fn json_stablegraph_to_stablegraph(g1: StableGraph<i32, i32>) -> () {
        let sg: StableGraph<i32, i32> = rejson!(g1);
        assert_stable_graph_eq(&g1, &sg);
    }

    fn json_graph_to_bigger_graph(g1: DiGraph<i32, i32, u16>) -> () {
        let g2: DiGraph<i32, i32, usize> = rejson!(g1);
        let g3: DiGraph<i32, i32, u16> = rejson!(g2);
        assert_graph_eq(&g1, &g3);
    }

    fn bincode_graph_to_graph_nils(g1: Graph<(), ()>) -> () {
        let g2: Graph<(), ()> = recode!(g1);
        assert_graph_eq(&g1, &g2);
    }

    fn bincode_graph_to_stablegraph_to_graph_nils(g1: Graph<(), ()>) -> () {
        let data = encode!(g1);
        let sg: StableGraph<(), ()> = decode!(data);
        let data2 = encode!(sg);
        let g2: Graph<(), ()> = decode!(data2);
        assert_eq!(data, data2);
        assert_graph_eq(&g1, &g2);
    }

    fn bincode_graph_to_stablegraph_to_graph_u16(g1: DiGraph<i32, i32, u16>) -> () {
        let data = encode!(g1);
        let sg: StableDiGraph<i32, i32, u16> = decode!(data);
        let data2 = encode!(sg);
        let g2: DiGraph<i32, i32, u16> = decode!(data2);
        assert_eq!(data, data2);
        assert_graph_eq(&g1, &g2);
    }

    fn bincode_stablegraph_to_stablegraph(g1: StableGraph<i32, i32>) -> () {
        let g2: StableGraph<i32, i32> = recode!(g1);
        assert_stable_graph_eq(&g1, &g2);
    }
}