#include <iostream>
#include <string>

#include <origin/graph/adjacency_vector.hpp>
#include <origin/graph/adjacency_matrix.hpp>

using namespace std;
using namespace origin;

void test_vector() {
  typedef adjacency_vector<char, int> Graph;
  typedef Graph::vertex_descriptor Vertex;

  { // Test vertex descriptor subtypes.
    using namespace origin::graph_;
    vertex_t v = -1u;
    edge_t e = -1u;
    std::size_t n = v.get();
    assert(vertex_t(n) == v);
    e = 3;
    assert(edge_t(3) == e);
    // e = v; // OK -- should fail!
  }

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

  { // 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));
  }

  { // 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);
  }

  { // 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";
    */
  }
}

void test_matrix() {
  typedef adjacency_matrix<char, int> Graph;
  typedef Graph::vertex_descriptor Vertex;
  typedef Graph::edge_descriptor Edge;

  {
    Graph g(5);
    assert(g.order() == 5);
    assert(g.size() == 0);
    assert(!g.edge(2, 2));
    Edge e = g.add_edge(2, 2, 5);
    assert(!g.empty());
    assert(g.size() == 1);
    assert(g.edge(2, 2));
    assert(g[e] == 5);
    g.remove_edge(e);
    assert(g.empty());
    assert(!g.edge(2, 2));
  }

  {
    size_t const N = 5;
    Graph g(N);
    for(size_t i = 1; i < N; ++i)
      g.add_edge(0, i);
    assert(g.order() == N);
    assert(g.size() == N - 1);
    g.remove_edges(0);
    assert(g.size() == 0);
  }
}

int main() {
  test_vector();
  test_matrix();
}