#ifndef GRAPH_H
#define GRAPH_H

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

using namespace std;

#include "point.h"
#include "tplane.h"
#include "binheap.h"

template <typename T> class Graph;
template <typename T> struct Vertex;
template <typename T> class vCompare;
template <typename T> ostream& operator <<(ostream& s, const Vertex<T>& rhs);

template <typename T>
struct Vertex{
   T p;
   int edges;
   double dist;
   bool visited;
   bool onqueue;
   Vertex* path;
   int graphpos;
   int bheappos;
   bool processed;

   vector<Vertex* > adj;
   vector<Vertex* > child;

      
   Vertex(int gpos=1, T inp=NULL, int n=20000) : \
      p(inp),
      edges(0),
      adj(),
      visited(false),
      processed(false),
      dist(INFINITY),
      path(NULL),
      graphpos(gpos),
      bheappos(0) {adj.reserve(n);}
      
   Vertex(T inp=NULL) : \
      p(inp),
      edges(0),
      adj(),
      visited(false),
      processed(false),
      onqueue(false),
      dist(INFINITY),
      path(NULL),
      graphpos(0),
      bheappos(0) { adj.reserve(20000); }
   
   const Vertex<T>& operator=(const Vertex &rhs) {
      if (this != &rhs) {
         p = rhs.p;
         edges = rhs.adj.size();
// adj.clear();
         adj.resize(rhs.adj.size());
   
         for(int i=0; i<(int)rhs.adj.size(); ++i) adj[i] = rhs.adj[i];
         visited = rhs.visited;
         processed = rhs.processed;
         onqueue = rhs.onqueue;
         dist = rhs.dist;
         path = rhs.path;
//    child.clear();
   
         for(int i=0; i<(int)rhs.child.size(); ++i) child.push_back(rhs.child[i]);
         graphpos = rhs.graphpos;
         bheappos = rhs.bheappos;
      }
      return *this;
   }

   bool operator==(Vertex& rhs) { return( dist == rhs.dist); }
   bool operator<(Vertex& rhs)  { return( dist < rhs.dist);  }
   bool operator<(Vertex* rhs)  { return( dist < rhs->dist); }
   bool operator>(Vertex& rhs)  { return( dist > rhs.dist);  }
   bool operator>(Vertex* rhs)  { return( dist > rhs->dist); }

   friend ostream& operator<< <>(ostream& s, const Vertex& rhs);
   friend ostream& operator<<(ostream& s, Vertex* rhs) { return(s << (*rhs)); }

// Distance functions for arbitrary types.

   double distance(Vertex<T>& rhs) {return p->distance(rhs.p);}
   double distance(Vertex<T>* rhs) {return p->distance(rhs->p);}
};

template <typename T>
ostream& operator<<(ostream& s, const struct Vertex<T>& rhs) {
   s << rhs.p;
   if(rhs.processed) s << " T "; else s << " F ";
   if(rhs.onqueue) s << " on "; else s << " off ";
   s << "d_v = " << (float)rhs.dist;
   s << std::endl;
   return s;
}


template <typename T>
class vCompare{
   public:
      bool operator()(Vertex<T>* v1, Vertex<T>* v2) {return (*v1) < (*v2);}
};

template <typename T> class Graph;
template <typename T> 
class Graph {
   public:
      Graph() : vertexMap() {};

      void addVertex(int i, T p, int n);
      void addEdge(int i, T p1, int j, T p2);
      void addEdge(int i, int j);
      int prims(int isp, double rho);
      
      void path(int ip, T dp, vector<T> *p);
//    void consistency();
//    void rconsistency(Vertex<T> *v);
      void dfs(vector<T> *p);
      void rdfs(Vertex<T> *v, vector<T> *p);
      void edges(vector<T> *p);
      void bfsedges(Vertex<T> *v, vector<T> *p);
      void resize(int n)   {vertexMap.resize(n,0);}

      void clear();
      void clearMSF();

      bool empty()         {return vertexMap.empty();}
      
      
   private:
      vector<Vertex<T>* >  vertexMap;
      vector<Vertex<T>* >  mstRoot;
      Vertex<T>*           getVertex(T p);
      binheap<TangentPlane>  bh;
};
#endif