#ifndef I_GRAPH_H
#define I_GRAPH_H

#include <iostream>
#include <vector>
#include <typeinfo>
#include <string>

using namespace std;

//igraph:
//In order to decide how to route any given function call, we
//need to have a graph representing the inheritance heirarchy.

template<class base>
class igraph {

  //anode: "abstract node"
  //We keep track of type in our graph by creating a new
  //templated instance of the node class for type.
  //So to handle our nodes, we use pointers
  //to the abstract class "anode". 
  
  //The templated argument specifies the type of the root of
  //the graph.
  struct anode {
    virtual int num_parents() = 0;
    virtual int num_children() = 0;
    virtual int parent(int i) = 0;
    virtual int child(int i) = 0;
    virtual void add_parent(int i) =0;
    virtual void add_child(int i) =0;
    virtual void remove_parent(int i) =0;
    virtual void remove_child(int i) =0;
    virtual bool isa(base *b) = 0;
    virtual base* me() = 0;
    virtual string class_name() =0;
    virtual ~anode() {}
  };
  
  //node:
  //node is templated with a class A, where A must somehow be a 
  //desendant of class base.  
  //That isa function is what we use to navigate the graph
  //when we are trying to figure out how to dispatch a 
  //given pair of arguments.
  
  template<class A>
  class node : public anode {
    vector<int> parents;
    vector<int> children;
  public:
    virtual int num_parents() { return parents.size(); }
    virtual int num_children(){ return children.size(); }
    virtual int parent(int i) { return parents[i]; }
    virtual int child(int i)  { return children[i]; } 
    virtual void add_parent(int i) { parents.push_back(i); }
    virtual void add_child(int i) { children.push_back(i); }
    virtual bool isa(base *b) { return dynamic_cast<A *>(b); }
    virtual string class_name() { return typeid(A).name(); }
    virtual base* me() { return new A; }
    
    virtual void remove_parent(int j) { 
      bool found = false;
      for(int i = 0; i < parents.size() - 1; i++) {
	if(parents[i] == j) found = true;
	if(found) parents[i] = parents[i+1];
      }
      parents.pop_back();
    }

    virtual void remove_child(int j) { 
      bool found = false;
      for(int i = 0; i < children.size() - 1; i++) {
	if(children[i] == j) found = true;
	if(found) children[i] = children[i+1];
      }
      children.pop_back();
    }
  }; 
  
  vector<int> leaves;

 public:  
  //only public because the graph interferance code needs to touch this..
  vector< anode* > data; 
  
  int leaf(int i) const { return leaves[i]; }
  int num_leaves() const{ return leaves.size(); }

  anode* operator[](int i) const { return data[i]; }

  igraph() 
    {
      data.push_back(new node<base>());
    }
  
  ~igraph()
    {
    for(int i = 0; i < data.size(); i++)
      delete data[i];
    }

  template<class A>
    int vertex_add()
    {
      int i = data.size();
      data.push_back(new node<A>());
      return i;
    }
  
  void edge_add(int p, int c)
    {
      data[c]->add_parent(p);
      data[p]->add_child(c);
    }

  void edge_remove(int p, int c)
    {
      data[c]->remove_parent(p);
      data[p]->remove_child(c);
    }
  
  void build_leaf_list()
    {
      leaves.clear();
      for(int i = 0; i < data.size(); i++)
	if(data[i]->num_children() == 0)
	  leaves.push_back(i);
    }

  
  //The chain of preferences function is the core feature of
  //the inheritance graph.  You pass in a base*, probably one of
  //the arguments that you are trying to figure out how to dispatch, 
  //and this function returns a vector of ints indicating what
  //vertices of the graph (object types), the base* can be cast to.
  //The vector is sorted in order of preference, where preference is
  //defined according to the depth first search detailed on the webpage.
  //(http://www.cs.swarthmore.edu/~bulnes/PL/lab1/index.html)
  vector<int> chain_of_preferences(base *b)
    {
      vector<int> opt;
      vector<int> prefs;
      
      int i,j;
      for(int i=0; i < leaves.size(); i++)
	opt.push_back(leaves[i]);
      
      for(j = 0; j < opt.size(); j++) {
	if(data[opt[j]]->isa(b))
	  prefs.push_back(opt[j]);
	
	for(int i=0; i < data[opt[j]]->num_parents(); i++)
	  opt.push_back(data[opt[j]]->parent(i));
      }
      return prefs;
    }

  //used for debugging, prints out sudo c++ class definitions
  //explaining the inheritance structure represented by the graph.
  friend ostream& operator<<(ostream &out, const igraph &g) {
    vector<string> class_defs;
    for(int i=0;i<g.data.size();i++) {
      out << "class " << g.data[i]->class_name() 
	  << " : " << endl;
      for(int j=0;j<g.data[i]->num_parents();j++) 
	out << "\tpublic " << g.data[g.data[i]->parent(j)]->class_name() << endl;
      out << endl;
    }
    return out;
  }
};


#endif