#ifndef GRAPH_H
#define GRAPH_H
/////////////////////////////////////////////////////////////////
// Graph.h - directed graph structure                          //
// ver 1.0                                                     //
// ----------------------------------------------------------- //
// copyright © Jim Fawcett, 2012                               //
// All rights granted provided that this notice is retained    //
// ----------------------------------------------------------- //
// Jim Fawcett, CST 4-187, Syracuse University, 315 443 3948   //
// Summer Projects, 2012                                       //
// Win7, Visual Studio 2010                                    //
/////////////////////////////////////////////////////////////////
/*
 * Package Operations:
 * ===================
 * This package provides classes supporting representations of
 * directed graphs.  It provides the classes:
 * - Graph:
 *     Build and search directed graphs
 * - Vertex:
 *     Represent graph vertices.  Holds an instance of a V type
 *     and a collection of pairs where each pair refers to a
 *     child vertex and holds an instance of an E type
 * - IFunctor:
 *     Interface for functors used by searching algorithms
 * - WalkFunctor
 *     Implements IFunctor for Depth First Search
 * - Display
 *     Implements IFunctor for displaying graph
 * The package also provides the global functions:
 * - dfs:
 *     Depth First Search navigation, applying a supplied 
 *     functor to each visited node
 * - foreach:
 *     Accepts a graph and a functor, then applies the 
 *     functor to each vertex in the graph
 */

#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include "..\LibUtils\LibUtils.h"

namespace DirectedGraph
{
  /////////////////////////////////////////////////////////////////
  // Vertex class

  template<typename V, typename E>
  class Vertex
  {
  public:
    // Edge holds:
    // - integer index into its child's position in graph adj vector
    // - Instance of the Edge's E type
    using Edge = std::pair<size_t, E>;

    // constructor accepts integer id and value of V type
    Vertex(size_t id, V v) : _v(v), _id(id) {}
    void add(Edge& edge) { edges.push_back(edge); }

    // access child vertices
    Edge& operator[](size_t i) { return edges[i]; }
    Edge operator[](size_t i) const { return edges[i]; }
    size_t size() { return edges.size(); }

    // value returns vertex's information payload
    V& value() { return _v; }

    // ids Should be unique as they are used for graph searches
    // and for user interpretation.  Graph doesn't ensure that.
    // Algorithms use a vertex's position in the graph adj as a
    // unique, by construction, identifier.
    size_t id() { return _id; }

    // Vertex visited state is used for graph traversal
    bool& visited() { return visited_; }
  private:
    std::vector<Edge> edges;
    V _v;
    size_t _id;
    bool visited_;
  };

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

  template<typename V, typename E>
  class Graph
  {
  public:
    // graph traversal
    using iterator = typename std::vector< Vertex<V,E> >::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 resetVisited();

    // building graphs
    void addVertex(Vertex<V,E> v) { adj.push_back(v); }
    void addEdge(E eval, Vertex<V,E>& parent, Vertex<V,E>& child);

    // searching graphs
    size_t findVertexById(size_t id);
    size_t findVertexByValue(const V& v);

    // graph properties
    size_t size() { return adj.size(); }
    std::string& name() { return name_; }
  private:
    std::string name_;
    std::vector< Vertex<V,E> > adj;
  };

  //----< find vertex by its user defined id >---------------------

  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();
  }
  //----< find first vertex in graph adj with value v >------------

  template<typename V, typename E>
  typename size_t Graph<V,E>::findVertexByValue(const V& v)
  {
    for(size_t i=0; i<adj.size(); ++i)
      if(adj[i].value() == v)
        return i;
    return adj.size();
  }
  //----< add edge directed from parent to child vertices >--------

  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);
  }
  //----< reset all vertices visited state to false >--------------

  template <typename V, typename E>
  void Graph<V,E>::resetVisited()
  {
    for(size_t i=0; i<adj.size(); ++i)
      adj[i].visited() = false;
  }

  /////////////////////////////////////////////////////////////////
  // Functor Interface

  template <typename V, typename E>
  struct IFunctor
  {
    virtual void operator()(Vertex<V,E>& v)=0;
  };

  /////////////////////////////////////////////////////////////////
  // Walk Functor - displays visited vertices' ids

  template <typename V, typename E>
  struct WalkFunctor : public IFunctor<V,E>
  {
    WalkFunctor() { std::cout << "\n  "; }
    ~WalkFunctor() { std::cout << "\n"; }
    virtual void operator()(Vertex<V,E>& v)
    {
      std::cout << v.id() << " ";
    }
  };

  //---------------------------------------------------------------
  // Depth First Search (dfs) helper function

  template <typename V, typename E>
  void walk(Graph<V,E>& g, Vertex<V,E>& v, IFunctor<V,E>& functor)
  {
    v.visited() = true;
    functor(v);
    for(size_t i=0; i<v.size(); ++i)
    {
      size_t childIndex = v[i].first;
      if(!g[childIndex].visited())
        walk(g, g[childIndex], functor);
    }
  }
  //---------------------------------------------------------------
  // Depth First Search (dfs) - applies functor to each vertex

  template <typename V, typename E>
  void dfs(Graph<V,E>& g, IFunctor<V,E>& functor, size_t startid=0)
  {
    g.resetVisited();
    if(startid != 0)
    {
      size_t startIndex = g.findVertexById(startid);
      walk(g,g[startIndex], functor);
    }
    for(size_t i=0; i<g.size(); ++i)
    {
      if(!g[i].visited())
        walk(g, g[i], functor);
    }
  }
  //-------------------------------------------------------------
  // Linear Visitation

  template <typename V, typename E>
  void foreach(Graph<V,E>& g, IFunctor<V,E>& functor)
  {
    for(size_t i=0; i<g.size(); ++i)
      functor(g[i]);
  }
  ///////////////////////////////////////////////////////////////
  // Display Functor - accepts a graph and displays vertex details

  template <typename V, typename E>
  class Display : public IFunctor<V,E>
  {
  public:
    Display(Graph<V,E>& g) : g_(g) {}

    void operator()(Vertex<V,E>& v)
    {
      std::cout 
        << "\n  Vertex id = " << LibUtils::toString(v.id()).c_str() 
        << ", value = " << LibUtils::toString(v.value()).c_str();
      for(size_t i=0; i<v.size(); ++i)
      {
        size_t childIndex = v[i].first;
        Vertex<V,E> child = g_[childIndex];
        E edgeValue = v[i].second;
        std::cout
          << "\n    Edge points to Vertex with id = " 
          << LibUtils::toString(child.id()) << ", Edge value = " 
          << LibUtils::toString(edgeValue);
      }
    }
  private:
    Graph<V,E>& g_;
  };
}

#endif