#ifndef MT4Q3_H
#define MT4Q3_H
///////////////////////////////////////////////////////////////
// MT4Q3.h - Graph Iterator                                  //
//                                                           //
// Jim Fawcett, CSE687 - Object Oriented Design, Spring 2012 //
///////////////////////////////////////////////////////////////
/*
 * To Do:
 * - add markings for vertices
 * - Depth First Search
 * - Strong Components, Topological Sorting
 * - Find disconnected graph partitions
 */
#include <vector>

///////////////////////////////////////////////////////////////
// Vertex class

template<typename V, typename E>  // not required for answer
class Vertex
{
public:
  typedef std::pair<int, E> Edge;
  Vertex(V v) : _v(v), _id(count++) {}
  void add(Edge& edge) { edges.push_back(edge); }
  Vertex(const Vertex& v) { edges = v.edges; _v = v._v; _id = v._id; }
  Vertex& operator=(const Vertex& v) 
  { 
    if(this == &v) return *this;
    edges = v.edges; _v = v._v; _id = v._id;
    return *this; 
  }
  Edge& operator[](size_t i) { return edges[i]; }
  Edge operator[](size_t i) const { return edges[i]; }
  V& value() { return _v; }
  size_t id() 
  { 
    return _id; 
  }
  size_t size() { return edges.size(); }
private:
  std::vector<Edge> edges;
  V _v;
  size_t _id;
  static size_t count;
};

template<typename V, typename E>
size_t Vertex<V,E>::count = 0;

///////////////////////////////////////////////////////////////
// Graph class

template<typename V, typename E>
class Graph
{
public:
  // next three lines satisfy first requirement
  typename typedef std::vector< Vertex<V,E> >::iterator iterator;
  iterator begin() { return adj.begin(); }
  iterator end() { return adj.end(); }
  Vertex<V,E>& operator[](size_t i) { return adj[i]; }
  Vertex<V,E> operator[](size_t i) const { return adj[i]; }
  void addVertex(Vertex<V,E> v) { adj.push_back(v); }
  void addEdge(E eval, Vertex<V,E>& parent, Vertex<V,E>& child);
  size_t findVertexById(size_t id);
  size_t size() { return adj.size(); }
private:
  std::vector< Vertex<V,E> > adj;
};

template<typename V, typename E>
typename size_t Graph<V,E>::findVertexById(size_t id)
{
  for(size_t i=0; i<adj.size(); ++i)
    if(adj[i].id() == id)
      return i;
  return adj.size();
}

template<typename V, typename E>
void Graph<V,E>::addEdge(E eVal, Vertex<V,E>& parent, Vertex<V,E>& child)
{
  size_t childIndex = findVertexById(child.id());
  if(childIndex == adj.size())
    throw std::exception("no edge child");
  size_t parentIndex = findVertexById(parent.id());
  if(parentIndex == adj.size())
    throw std::exception("no edge parent");
  Vertex<V,E>::Edge e;
  e.first = childIndex;
  e.second = eVal;
  adj[parentIndex].add(e);
}

///////////////////////////////////////////////////////////////
// Display class

template<typename V, typename E>
class Display
{
public:
  typedef Graph<V,E> graph;
  typedef Vertex<V,E> vertex;
  typedef std::pair<int,E> edge;

  // this function satisfies second requirement
  static std::vector< Vertex<V,E> > vertsWithNoParents(graph& g)
  {
    std::vector<size_t> parentCount;
    graph::iterator iter = g.begin();
    while(iter != g.end())
    {
      parentCount.push_back(0);
      ++iter;
    }
    iter = g.begin();
    while(iter != g.end())
    {
      vertex v = *iter;
      for(size_t i=0; i<v.size(); ++i)
      {
        edge e = v[i];
        parentCount[e.first]++;
      }
      ++iter;
    }
    std::vector<vertex> noParents;
    for(size_t j=0; j<g.size(); ++j)
      if(parentCount[j] == 0)
        noParents.push_back(g[j]);
    return noParents;
  }

  static void show(graph& g)
  {
    graph::iterator iter = g.begin();
    while(iter != g.end())
    {
      vertex v = *iter;
      std::cout << "\n  vertex id = " << v.id() << ", value = " << (v.value()).c_str();
      for(size_t i=0; i<v.size(); ++i)
      {
        vertex::Edge edge = v[i];
        std::cout << "\n    edge points to vertex with id = " << g[edge.first].id();
        std::cout << " and value = " << g[edge.first].value().c_str();
        std::cout << ", edge value = " << (edge.second).c_str();
      }
      ++iter;
    }
  }
};

#endif