#ifndef SIMPLESTGRAPH_H
#define SIMPLESTGRAPH_H
///////////////////////////////////////////////////////////
// MT3Q5.h -- from Handouts/CSE687/code/GraphHelp

#include <vector>

template <typename V, typename E>
class vertex
{
public:
  class edge
  {
  public:
    edge(vertex<V,E>& vtx, const E& e, size_t num);
    E& value();
    size_t id();
    vertex<V,E>& vert() { return *pVertex; }
  private:
    vertex<V,E>* pVertex;
    E value_;
    size_t num_;
  };
  vertex(const V& value, size_t num);
  void addEdge(typename const vertex<V,E>::edge& ed) { edges.push_back(ed); }
  edge& operator[](size_t n);
  size_t size() { return edges.size(); }
  V& value();
  size_t id();
private:
  std::vector< edge > edges;
  size_t num_;
  V value_;
};

template <typename V, typename E>
vertex<V,E>::vertex(const V &value, size_t num) : value_(value), num_(num)
{
}
//----< return vertex value >------------------------------

template <typename V, typename E>
V& vertex<V,E>::value() { return value_; }

//----< return vertex id >----------------------------------

template <typename V, typename E>
size_t vertex<V,E>::id() { return num_; }

//----< index operator >-------------------------------------

template <typename V, typename E>
typename vertex<V,E>::edge& vertex<V,E>::operator[](size_t n)
{
  if(n<0 || edges.size()<=n)
    throw std::invalid_argument("index out of range");
  return edges[n];
}
//----< edge constructor >-----------------------------------

template <typename V, typename E>
vertex<V,E>::edge::edge(vertex<V,E>& vtx, const E& value, size_t num) 
  : pVertex(&vtx), value_(value), num_(num)
{
}
//----< return E reference >-----------------------------------

template <typename V, typename E>
E& vertex<V,E>::edge::value() { return value_; }

//----< return edge id >-----------------------------------

template <typename V, typename E>
size_t vertex<V,E>::edge::id() { return num_; }

////////////////////////////////////////////////////////////////////////
// graph class

template <typename V, typename E, typename S = Quiet>
class graph
{
public:
  typedef std::vector<vertex<V,E>*> PtrsToVerts;
  typedef S policy_type;
  typedef V vertex_valuetype;
  typedef E edge_valuetype;
  typedef vertex<V,E> vertex_type;
  typedef graph<V,E,S> graph_type;
  typename typedef std::vector< vertex<V,E>* >::iterator iterator;
  graph() {}
  ~graph();
  void addVertex(vertex<V,E>& vtx);
  vertex<V,E>& operator[](size_t n);
  size_t size() { return ptrsToVerts.size(); }
  iterator findVertexWithValue(const V& v);
  PtrsToVerts findVerticesWithValue(const V& v);
  iterator begin();
  iterator end();
private:
  graph(const graph<V,E,S>& g);
  graph<V,E,S>& operator=(const graph<V,E,S>& g);
  PtrsToVerts ptrsToVerts;
};

template <typename V, typename E, typename S>
graph<V,E,S>::~graph()
{
  // define all the vertices in graph on the heap, then
  // uncomment these lines
    for(size_t i=0; i<ptrsToVerts.size(); ++i)
      delete ptrsToVerts[i];
}

template <typename V, typename E, typename S>
void graph<V,E,S>::addVertex(vertex<V,E> &vtx) 
{ 
  ptrsToVerts.push_back(&vtx); 
}

template <typename V, typename E, typename S>
vertex<V,E>& graph<V,E,S>::operator[](size_t n)
{
  if(n<0 || ptrsToVerts.size()<=n)
    throw std::invalid_argument("graph index out of range");
  return *ptrsToVerts[n];
}

template <typename V, typename E, typename S>
typename graph<V,E,S>::iterator graph<V,E,S>::begin()
{
  return ptrsToVerts.begin();
}

template <typename V, typename E, typename S>
typename graph<V,E,S>::iterator graph<V,E,S>::end()
{
  return ptrsToVerts.end();
}

template <typename V, typename E, typename S>
typename graph<V,E,S>::iterator graph<V,E,S>::findVertexWithValue(const V& v)
{
  iterator iter;
  S s;  // display policy
  for(iter=ptrsToVerts.begin(); iter!=ptrsToVerts.end(); ++iter)
  {
    s(iter);
    if((*iter)->value() == v)
      return iter;
  }
  return iter;
}

template <typename V, typename E, typename S>
typename graph<V,E,S>::PtrsToVerts 
graph<V,E,S>::findVerticesWithValue(const V& v)
{
  PtrsToVerts collect;
  iterator iter;
  S s;  // display policy
  for(iter=ptrsToVerts.begin(); iter!=ptrsToVerts.end(); ++iter)
  {
    s(iter);
    if((*iter)->value() == v)
      collect.push_back(*iter);
  }
  return collect;
}

template <typename G>
typename G::PtrsToVerts 
findVerticesWithValue(G& g, typename const G::vertex_valuetype& v)
{
  G::PtrsToVerts collection;
  typename G::iterator iter;
  G::policy_type p;  // display policy
  for(iter=g.begin(); iter!=g.end(); ++iter)
  {
    p(iter);
    if((*iter)->value() == v)
      collection.push_back(*iter);
  }
  return collection;
}

template <typename V, typename E>
class Verbose
{
public:
  void operator()(typename graph<V,E,Verbose>::iterator iter)
  {
    std::cout << "\n  visited vertex with value " << (*iter)->value();
  }
};

template <typename V, typename E>
class Quiet
{
public:
  void operator()(typename graph<V,E,Quiet>::iterator iter) {}
};


#endif