//
// Graph implementation
//

#ifndef __GRAPH
#define __GRAPH

#include <iostream>
#include <fstream>
#include "bstree.h"


//
// Class representing a edge
//
template <class K, class E>
class GraphEdge {
 public:
  int id; 
  int from; int to;
  K To; E data;
};


//
// Class representing a node inside a graph
//
template <class K, class N, class E>
class GraphNode {
 public:
  int id;
  N data; K Alias;
  bool Visited;
  BSTree< GraphEdge<K, E> > Adjacent;
};


//
// Simple Graph Implementation
//
template <class K, class N, class E>
class Graph {

  int count;
  BSTree< GraphNode<K, N, E> > Nodes;
 
 public:
  Graph () { count = 1; }
  ~Graph () { }

  // Node Manipulation
  bool InsertNode (K key);
  bool InsertNode (K key, N& info);
  bool DeleteNode (K key);
  bool DeleteNode (K key, N& info);

  // Edge Manipulation
  bool InsertEdge (K i, K j) 
    { return InsertEdge2 (i, j) && InsertEdge2 (j, i); }
  bool InsertEdge (K i, K j, E& e) 
    { return InsertEdge2 (i, j, e) && InsertEdge2 (j, i, e); }
  bool DeleteEdge (K i, K j) 
    { return DeleteEdge2 (i, j) && DeleteEdge2 (j, i); }
  bool DeleteEdge (K i, K j, E& e) 
    { return DeleteEdge2 (i, j, e) && DeleteEdge2 (j, i, e); }

  // Real Edge Manipulation
 private:
  bool InsertEdge2 (K, K);
  bool InsertEdge2 (K, K, E&);
  bool DeleteEdge2 (K, K);
  bool DeleteEdge2 (K, K, E&);

 public:
  //Search
  GraphNode<K, N, E>* Search (K i);

  // Traverse 
  bool DFS (K start, bool (*Visit) (K&, int));
  
 private:
  bool DFS (K start, bool (*Visit) (K&, int), int);

 public:
  // Additional functions for saving/restoring to/from a file
  bool Save (const char *) const;
  bool Read (const char *);

  // Print
  friend ostream& operator << <> (ostream&, Graph&);

};


//
// Node Manipulation
//
template <class K, class N, class E>
bool Graph<K, N, E>::InsertNode (K i)
{
  GraphNode<K, N, E> info;

  info.Alias = i; 
  info.id = count++;
  return Nodes.Insert (info);
}

template <class K, class N, class E>
bool Graph<K, N, E>::DeleteNode (K i)
{
  GraphNode<K, N, E> info;

  info.Alias = i;
  return Nodes.Delete (info);
}

template <class K, class N, class E>
bool Graph<K, N, E>::InsertNode (K i, N& n)
{
  GraphNode<K, N, E> info;

  info.data = n;
  info.Alias = i; 
  return Nodes.Insert (info);
}

template <class K, class N, class E>
bool Graph<K, N, E>::DeleteNode (K i, N& n)
{
  GraphNode<K, N, E> info;

  info.data = n;
  info.Alias = i;
  if (Nodes.Delete (info))
    {
      n = info.data;
      return true;
    }
  return false;
}


//
// Edge Manipulation
//
template <class K, class N, class E>
bool Graph<K, N, E>::InsertEdge2 (K i, K j)
{
  GraphNode<K, N, E> info1, info2, *i1 = &info1;

  info1.Alias = i; 
  if (Nodes.Search (i1))
    {
      info2.Alias = j; 
      if (Nodes.Search (info2))
	{
	  GraphEdge<K, E> info; 
	  info.to = info2.id;
	  info.To = j; 
	  return i1->Adjacent.Insert (info);
	}
    }
  return false;
}

template <class K, class N, class E>
bool Graph<K, N, E>::InsertEdge2 (K i, K j, E& e)
{
  GraphNode<K, N, E> info1, info2, *i1 = info1;

  info1.Alias = i; 
  if (Nodes.Search (info1))
    {
      info2.Alias = j; 
      if (Nodes.Search (info2))
	{
	  GraphEdge<K, E> info;
	  info.to = info2.id;
	  info.To = info2.Alias;
	  info.data = e;
	  return info.Adjacent.Insert (info);
	}
    }
  return false;
}

template <class K, class N, class E>
bool Graph<K, N, E>::DeleteEdge2 (K i, K j)
{
  GraphNode<K, N, E> info1, info2, *i1 = &info1;

  info1.Alias = i;
  if (Nodes.Search (i1))
    {
      info2.Alias = j; 
      if (Nodes.Search (info2))
	{
	  GraphEdge<K, E> info;
	  info.to = info2.id;
	  return i1->Adjacent.Delete (info);
	}
    }
  return false;
}

template <class K, class N, class E>
bool Graph<K, N, E>::DeleteEdge2 (K i, K j, E& e)
{
  GraphNode<K, N, E> info1, info2, *i1 = &info1;

  info1.Alias = i;
  if (Nodes.Search (i1))
    {
      info2.Alias = j; 
      if (Nodes.Search (info2))
	{
	  GraphEdge<K, E> info;
	  info.to = info2.id;
	  if (i1->Adjacent.Delete (info))
	    {
	      e = info.data;
	      return true;
	    }
	}
    }
  return false;
}


//
// Search
//
template <class K, class N, class E>
GraphNode<K, N, E>* Graph<K, N, E>::Search (K i)
{
  GraphNode <K, N, E> info, *i1 = &info;

  info.Alias = i;
  if (Nodes.Search (i1))
    return i1;
  else
    return NULL;
}


//
// Traversals
//
template <class K, class N, class E>
bool Graph<K, N, E>::DFS (K start, bool (*Visit) (K&, int))
{
  for (BSTreeIter< GraphNode<K, N, E> > i (Nodes); 
       !i.Finished (); i.Step ())
    i.Get().Visited = false;
  return DFS (start, Visit, 0);
}

template <class K, class N, class E>
bool Graph<K, N, E>::DFS (K start, bool (*Visit) (K&, int), int d)
{
  GraphNode<K, N, E> *crt = NULL;

  crt = Search (start);
  if (crt->Visited)
    return true;
  else
    crt->Visited = true;
  Visit (crt->Alias, d); 
  for (BSTreeIter< GraphEdge<K, E> > i (crt->Adjacent); 
       !i.Finished (); i.Step ())
    {
      DFS (i.Get().To, Visit, d+1);
    }
  return true;
}


//
// Additional functions for save / restore from a file
//
template <class K, class N, class E>
bool Graph<K, N, E>::Save (const char* file) const
{
  ofstream out (file);
  if (out)
    {

      out.close ();
      return true;
    }
  return false;
}

template <class K, class N, class E>
bool Graph<K, N, E>::Read (const char*)
{

  return true;
}

template <class K, class N, class E>
ostream& operator << (ostream& out, Graph<K, N, E>& g)
{
  out << g.Nodes;
  return out;
}


//
// Operators for GraphNode manipulation inside the Binary Search Tree
//
template <class K, class T, class E>
bool operator < (const GraphNode<K, T, E>& t1, const GraphNode<K, T, E>& t2) 
{ return t1.Alias < t2.Alias; }

template <class K, class T, class E>
bool operator > (const GraphNode<K, T, E>& t1, const GraphNode<K, T, E>& t2) 
{ return t1.Alias > t2.Alias; }

template <class K, class T, class E>
bool operator <= (const GraphNode<K, T, E>& t1, const GraphNode<K, T, E>& t2) 
{ return t1.Alias <= t2.Alias; }

template <class K, class T, class E>
bool operator >= (const GraphNode<K, T, E>& t1, const GraphNode<K, T, E>& t2)
{ return t1.Alias >= t2.Alias; }

template <class K, class T, class E>
bool operator == (const GraphNode<K, T, E>& t1, const GraphNode<K, T, E>& t2)
{ return t1.Alias == t2.Alias; }

template <class K, class T, class E>
ostream& operator << (ostream& out, GraphNode<K, T, E>& t)
{ out << t.id << " > " << t.Alias << ": " << t.Adjacent;  return out; }


//
// Edge Manipulation
//
template <class K, class T>
bool operator < (const GraphEdge<K, T>& t1, const GraphEdge<K, T>& t2) 
{ return t1.to < t2.to; }

template <class K, class T>
bool operator > (const GraphEdge<K, T>& t1, const GraphEdge<K, T>& t2) 
{ return t1.to > t2.to; }

template <class K, class T>
bool operator <= (const GraphEdge<K, T>& t1, const GraphEdge<K, T>& t2) 
{ return t1.to <= t2.to; }

template <class K, class T>
bool operator >= (const GraphEdge<K, T>& t1, const GraphEdge<K, T>& t2)
{ return t1.to >= t2.to; }

template <class K, class T>
bool operator == (const GraphEdge<K, T>& t1, const GraphEdge<K, T>& t2)
{ return t1.to == t2.to; }

template <class K, class T>
ostream& operator << (ostream& out, GraphEdge<K, T>& t)
{ out << " " << t.to << " : " << t.To;  return out; }


#endif // __GRAPH