#include <iostream>

#include <origin/graph/directed_graph.hpp>
#include <origin/graph/undirected_graph.hpp>

using namespace origin;
using namespace std;

template<typename Node, typename Linkage = basic_linkage<Node>>
void test_node_list() {
  node_list<Node, Linkage> l;

  assert(l.empty());
  assert(l.size() == 0);
  Node p;
  l.insert(&p);
  assert(!l.empty());
  assert(l.size() == 1);
  assert(l.front() == &p);
  assert(l.back() == &p);
  l.remove(&p);
  assert(l.empty());
  assert(l.front() == 0);

  size_t const N = 5;
  Node nodes[N];
  for(size_t i = 0; i < N; ++i) {
    l.insert(&nodes[i]);
  }
  assert(l.size() == N);
  for(size_t i = 0; i < N; ++i) {
    l.remove(&nodes[i]);
  }
  assert(l.empty());
}

template<typename Graph>
void test_directed_graph() {
  typedef typename Graph::vertex_descriptor Vertex;
  typedef typename Graph::edge_descriptor Edge;

  { // Test the addition and removal of a single vertex.
    Graph g;
    assert(g.null());
    assert(g.empty());
    Vertex v = g.add_vertex();
    assert(v != 0);
    assert(!g.null());
    assert(g.order() == 1);
    g.remove_vertex(v);
    assert(g.order() == 0);
    assert(g.null());
  }

  { // Test the addition and removal of edges
    Graph g;
    Vertex u = g.add_vertex();
    Vertex v = g.add_vertex();
    assert(g.order() == 2);
    assert(g.size() == 0);
    Edge e = g.add_edge(u, v);
    assert(g.size() == 1);
    assert(!g.empty());
    assert(g.source(e) == u);
    assert(g.target(e) == v);
    assert(g.out_degree(u) == 1);
    assert(g.in_degree(v) == 1);
    assert(g.edge(u, v));
    assert(!g.edge(v, u));
    g.remove_edge(e);
    assert(g.empty());
  }

  { // Test the addition and removal of multi-edges
    Graph g;
    Vertex u = g.add_vertex();
    Vertex v = g.add_vertex();
    Vertex w = g.add_vertex();
    g.add_edge(u, v);
    g.add_edge(u, v);
    g.add_edge(u, w);
    assert(g.size() == 3);
    assert(g.out_degree(u) == 3);
    assert(g.in_degree(v) == 2);
    assert(g.edge(u, v));
    assert(g.edge(u, w));
    assert(!g.edge(v, u));
    assert(!g.edge(w, u));
    assert(!g.edge(v, w));
    assert(!g.edge(w, v));
    g.remove_edges(u, v);
    assert(g.size() == 1);
    assert(g.out_degree(u) == 1);
    assert(g.in_degree(v) == 0);
    assert(g.in_degree(w) == 1);
  }

  { // Test the detaching of a vertex.
    // Generate an SN (Star N) with all edges leading out.
    Graph g;
    size_t const N = 5;
    Vertex verts[N];
    for(size_t i = 0; i < N; ++i)
      verts[i] = g.add_vertex();
    for(size_t i = 1; i < N; ++i)
      g.add_edge(verts[0], verts[i]);
    assert(g.order() == N);
    assert(g.size() == N - 1);
    assert(g.out_degree(verts[0]) == N - 1);
    for(size_t i = 1; i < N; ++i)
      assert(g.in_degree(verts[1]) == 1);
    g.remove_edges(verts[0]);
    assert(g.empty());
  }

  { // Test the creation and removal of loops
    Graph g;
    Vertex v = g.add_vertex();
    Edge e = g.add_edge(v, v);
    assert(g.order() == 1);
    assert(g.size() == 1);
    assert(g.out_degree(v) == 1);
    assert(g.in_degree(v) == 1);
    g.remove_edge(e);
    assert(g.empty());

    g.add_edge(v, v);
    g.remove_edges(v, v);
    assert(g.empty());

    g.add_edge(v, v);
    g.remove_edges(v);
    assert(g.empty());
  }

  { // Test iterators
    // Generate an SN (Star N) with all edges leading out.
    Graph g;
    size_t const N = 5;
    Vertex verts[N];
    for(size_t i = 0; i < N; ++i)
      verts[i] = g.add_vertex('a' + i);
    for(size_t i = 1; i < N; ++i)
      g.add_edge(verts[0], verts[i], i);

    assert(std::distance(g.vertices().begin(), g.vertices().end()) == int(N));
    assert(std::distance(g.edges().begin(), g.edges().end()) == int(N - 1));

    /*
    cout << "vertices: ";
    for(auto i = begin(g.vertices()); i != end(g.vertices()); ++i) {
      cout << g.value(*i) << " ";
    }
    cout << "\n";
    cout << "edges: ";
    for(auto i = begin(g.edges()); i != end(g.edges()); ++i) {
      cout << g.value(*i) << " ";
    }
    cout << "\n";
    cout << "out edges(0): ";
    for(auto i = begin(g.out_edges(verts[0])); i != end(g.out_edges(verts[0])); ++i) {
      cout << g.value(*i) << " ";
    }
    cout << "\n";
    cout << "in edges(1): ";
    for(auto i = begin(g.in_edges(verts[1])); i != end(g.in_edges(verts[1])); ++i) {
      cout << g.value(*i) << " ";
    }
    cout << "\n";
    */
  }
}

template<typename Graph>
void test_undirected_graph() {
  typedef typename Graph::vertex_descriptor Vertex;
  typedef typename Graph::edge_descriptor Edge;

  { // Test the addition and removal of a single vertex.
    Graph g;
    assert(g.null());
    assert(g.empty());
    Vertex v = g.add_vertex();
    assert(v != 0);
    assert(!g.null());
    assert(g.order() == 1);
    g.remove_vertex(v);
    assert(g.order() == 0);
    assert(g.null());
  }

  { // Test the addition and removal of edges
    Graph g;
    Vertex u = g.add_vertex();
    Vertex v = g.add_vertex();
    assert(g.order() == 2);
    assert(g.size() == 0);
    Edge e = g.add_edge(u, v);
    assert(g.size() == 1);
    assert(!g.empty());
    assert(g.source(e) == u);
    assert(g.target(e) == v);
    assert(g.degree(u) == 1);
    assert(g.arc(u, v));
    assert(!g.arc(v, u));
    assert(g.edge(u, v));
    assert(g.edge(v, u));
    g.remove_edge(e);
    assert(g.empty());
  }

  { // Test the addition and removal of multi-edges
    Graph g;
    Vertex u = g.add_vertex();
    Vertex v = g.add_vertex();
    Vertex w = g.add_vertex();
    g.add_edge(u, v);
    g.add_edge(u, v);
    g.add_edge(u, w);
    assert(g.size() == 3);
    assert(g.degree(u) == 3);
    assert(g.degree(v) == 2);
    assert(g.degree(w) == 1);
    assert(g.arc(u, v) && !g.arc(v, u));
    assert(g.edge(u, v) && g.edge(v, u));
    g.remove_edges(u, v);
    assert(g.size() == 1);
    assert(g.degree(u) == 1);
    assert(g.degree(v) == 0);
    assert(g.degree(w) == 1);
  }

  { // Test the addition and removal of a loop.
    Graph g;
    Vertex v = g.add_vertex();
    Edge e = g.add_edge(v, v);
    assert(g.order() == 1);
    assert(g.size() == 1);
    assert(g.degree(v) == 2);

    auto ir = g.incident_edges(v);
    assert(std::distance(ir.begin(), ir.end()) == 2);

    g.remove_edge(e);
    assert(g.size() == 0);
  }

  { // Test iterators
    // Generate an SN (Star N) with all edges leading out.
    Graph g;
    size_t const N = 5;
    Vertex verts[N];
    for(size_t i = 0; i < N; ++i)
      verts[i] = g.add_vertex('a' + i);
    for(size_t i = 1; i < N; ++i)
      g.add_edge(verts[0], verts[i], i);

    assert(g.edge(verts[0], verts[2]));
    assert(g.edge(verts[2], verts[0]));

    assert(std::distance(g.vertices().begin(), g.vertices().end()) == int(N));
    assert(std::distance(g.edges().begin(), g.edges().end()) == int(N - 1));

    /*
    cout << "vertices: ";
    for(auto i = g.vertices().begin(); i != g.vertices().end(); ++i) {
      cout << g[*i] << " ";
    }
    cout << "\n";
    cout << "edges: ";
    for(auto i = g.edges().begin(); i != g.edges().end(); ++i) {
      cout << g[*i] << " ";
    }
    cout << "\n";
    {
      cout << "incident edges(0): ";
      auto ir = g.incident_edges(verts[0]);
      for(auto i = ir.begin(); i != ir.end(); ++i) {
        cout << g[*i] << " ";
      }
    }
    cout << "\n";
    {
      cout << "incident edges(1): ";
      auto ir = g.incident_edges(verts[1]);
      for(auto i = ir.begin(); i != ir.end(); ++i) {
        cout << g[*i] << " ";
      }
      cout << "\n";
    }
  */
  }
}


int main() {

  test_directed_graph<directed_graph<char, int>>();
  test_undirected_graph<undirected_graph<char, int>>();

  return 0;
}