#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>

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

using namespace origin;
using namespace std;

typedef undirected_adjacency_matrix<char, int> graph_type;
typedef typename graph_type::vertex_descriptor vertex_descriptor;

template<typename Graph>
void print_graph(Graph const& g) {
  for(unsigned int cnt = 0; cnt < g.order();  ++cnt) {
    std::cerr << "vertex " << cnt << '\n';
    auto rng = out_edges(g, cnt);
    for(auto i = rng.begin(); i != rng.end(); ++i) {
      std::cerr << "   -> " << *opposite(g,*i, cnt) << " via edge "
                //<< i.iter.row << ", " << i.iter.position << '\n';
                << **i << '\n';
    }
  }
}

void test_undirected_adjacency_matrix()
{
  {
    const unsigned int num_vertices = 4;
    graph_type g(num_vertices);
    assert(g.order() == num_vertices);
    assert(g.size() == 0);
    assert(g.capacity() == num_vertices * (num_vertices + 1) / 2);
    assert(g.null() == false);
    assert(g.empty() == false);
  }
  {
    // Test an actual graph.
    const unsigned int num_vertices = 5;
    graph_type g(num_vertices);
    // Set vertices
    for(unsigned int i = 0; i < num_vertices; ++i) {
      g[graph_::vertex_t(i)] = 'a' + i;
    }
    // Set edges. All 8 of them. There are 8 edges. Count them
    g.add_edge(0,4, 7);
    g.add_edge(0,3,-3);
    g.add_edge(0,2, 5);
    g.add_edge(3,1, 1);
    g.add_edge(3,2,-4);
    g.add_edge(1,1, 2);
    g.add_edge(1,2, 1);
    g.add_edge(2,2, 8);
    assert(g.size() == 8);

    // List adjacent vertices and incident edges
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " is adjacenct to:";
      auto vertices_about_v = g.adjacent_vertices(i);
      for(;vertices_about_v.begin() != vertices_about_v.end();
          ++vertices_about_v._begin)
      { cout << ' ' << g[*vertices_about_v.begin()]; }
      cout << '\n';
    }
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " is incedent to:";
      auto edges_about_v = g.incident_edges(i);
      for(;edges_about_v.begin() != edges_about_v.end(); ++edges_about_v._begin)
      { cout << ' ' << **edges_about_v.begin(); }
      cout << '\n';
    }
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " has the out edges:";
      auto edges_about_v = g.out_edges(i);
      for(;edges_about_v.begin() != edges_about_v.end(); ++edges_about_v._begin)
      { cout << ' ' << **edges_about_v.begin(); }
      cout << '\n';
    }
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " has the in edges:";
      auto edges_about_v = g.out_edges(i);
      for(;edges_about_v.begin() != edges_about_v.end(); ++edges_about_v._begin)
      { cout << ' ' << **edges_about_v.begin(); }
      cout << '\n';
    }
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " ends its iteration at:";
      auto edges_about_v = g.incident_edges(i);
      for(;edges_about_v.begin() != edges_about_v.end(); ++edges_about_v._begin)
      { cout << ' ' << **edges_about_v.end(); }
      cout << '\n';
    }

    print_graph(g);

    // Remove all edges connected to vertex b (1), which has 3 edges
    g.remove_edges(1);
    cerr << g.size() << '\n'; //assert(g.size() == 8 - 3);
    for(unsigned int i = 0; i < g.order(); ++i) {
      cout << "Vertex " << (char)('a' + i) << " is adjacenct to:";
      auto vertices_about_v = g.adjacent_vertices(i);
      for(;vertices_about_v.begin() != vertices_about_v.end();
           ++vertices_about_v._begin)
      { cout << ' ' << g[*vertices_about_v.begin()]; }
      cout << '\n';
    }
  }
  {
    // Test all functions
    graph_type g(5);
    g.add_edge(0,4, 7);
    g.add_edge(0,3,-3);
    g.add_edge(0,2, 5);
    g.add_edge(3,1, 1);
    g.add_edge(3,2,-4);
    g.add_edge(1,1, 2);
    g.add_edge(1,2, 1);
    g.add_edge(2,2, 8);

    graph_type const& h = g;

   h.vertices();
   h.incident_edges(vertex_descriptor(1));
  }
}

int main()
{
  test_undirected_adjacency_matrix();

  return 0;
}