//So Matt and Sven have written a little library that allows
//C++ to do multiple dispatch.

//This function defines the disp class, which allows users
//to create dispatcher objects which can be used to achieve
//2 dimensionally polymorphic behavior.

//This version of the dispatcher requires users to specify the
//inheritance graph themselves, which is a pain.  However,
//as far as we can tell, short of hacking g++, there is no
//other way to implement multiple dispatch for an arbitrary
//set of classes.

//Some simple dynamic programing tequines are currently being
//used to try to speed up the dispatcher.

//Here is nice webpage explaining things in more detail:
//http://www.cs.swarthmore.edu/~bulnes/PL/lab1/index.html

#ifndef MULTI_DISP_H
#define MULTI_DISP_H

#include "igraph.hpp" //our inheritance graph class
#include <map>
#include <typeinfo>

template<class B1, class B2, class R>
class disp {

protected:

  //We wrap pointers to the registered functions in 
  //function objects. This is the best way that we
  //have found to store functions of different types
  //in a uniform type datastructure (in this case, 
  //the structure is a hash table, though earlier
  //implentations used a matrix).

  //The abstract function function object.
  typedef R (*base_func)(B1*,B2*);
  struct afun {
    virtual ~afun() {};
    virtual R operator()(B1*,B2*) = 0;
  }; 

  //The type specific non-abstract function object.
  template<class A1, class A2> 
  struct fun : public afun {
    typedef R (*my_fun)(A1 *, A2 *);
    my_fun f;
    fun(my_fun f) : f(f) {}
    virtual R operator()(B1 * b1, B2 * b2) { 
    return f(dynamic_cast<A1 *>(b1),dynamic_cast<A2 *>(b2)); 
    }
  };
  

  /////////////////////////////////////////////////
  //Two trival datatypes that our hashtables will need:
  class int2 {
    int a,b;
  public:
    int2(int a,int b) : a(a), b(b) {}
    int &operator[](int i) { return i ? b : a; }
    int operator[](int i) const { return i ? b : a; }
  };

  struct int2comp {
    bool operator()(const int2 a, const int2 b) {
    return a[0]<b[0] || (a[0]==b[0] && a[1]<b[1]);
    }
  };
  
  //////////////////////////////////////////
  //The first hash table, mem_hash, is used to
  //memoize calls to the dispatcher (speed is good).
  //The second hash, fun_hash, is used to assosiate
  //functions with the position of their argument types
  //in the relavent inheritance graphs.

  typedef map<string,afun *> Mem_Hash;
  typedef map<int2,afun *, int2comp> Fun_Hash;
  Mem_Hash mem_hash;
  Fun_Hash fun_hash;

  igraph<B1> g1;
  igraph<B2> g2;

  void build_leaf_list()
  {
    g1.build_leaf_list();
    g2.build_leaf_list();
    mem_hash.clear();
  }

  afun* get_fun(int i, int j) {
    return fun_hash[int2(i,j)];
  }

public:

  //functions that allow you to add vertices and edges to
  //the inheritance graph coresponding with the first argument.
  template<class T>
  int vertex_add_1() {
    int n = g1.template vertex_add<T> ();
    build_leaf_list();
    return n;
  }
  void edge_add_1(int p, int c) {
    g1.edge_add(p,c);
    build_leaf_list();
  }

  //add vertices and edges to the graph for the the second argument.
  template<class T>
  int vertex_add_2() {
    int n = g2.template vertex_add<T> ();
    build_leaf_list();
    return n;
  }
  void edge_add_2(int p, int c) {
    g2.edge_add(p,c);
    build_leaf_list();
  }

  //dispatch (aka, the reason we wrote this library)
  //call this function to effect a virtual function call with
  //2 polymorphic dimensions.
  R dispatch(B1 * b1, B2 * b2) {
   
    //dynamic programing in action!
    string mem_hash_key=string(typeid(*b1).name()) + typeid(*b2).name();
    Mem_Hash::iterator h=mem_hash.find(mem_hash_key);
    if(h != mem_hash.end()) { 
      //cout << " (hash_hit) " << mem_hash_key << " "; 
      afun * fun=h->second;
      return(*fun)(b1,b2);
    }

    //we don't have a memoized version of this call,
    //so calculate the proper function by navigating the
    //inheritance graph.
    vector<int> p1 = g1.chain_of_preferences(b1);
    vector<int> p2 = g2.chain_of_preferences(b2);
    int i,j;
    for(i =0; i < p1.size(); i++)
      for(j = 0; j < p2.size(); j++)
	if(get_fun(p1[i],p2[j]))
	  {
	    afun * fun = get_fun(p1[i],p2[j]);
	    //cout << " (hash insert) ";
	    mem_hash[mem_hash_key]=fun;
	    return (*fun)(b1,b2);
	  }

    //so we have to use the parents
    {
      afun * fun = get_fun(0,0);
      mem_hash[mem_hash_key]=fun;
      //cout << " (hash insert) ";
      return (*fun)(b1,b2);
    }
  }

  //Register a function with the dispatcher. You need to pass
  //in the integer graph vertex ids that you got from the vertex_add
  //command.
  template<class A1, class A2>
  void add(int a1,int a2, R (*f)(A1*,A2*)) {
    fun_hash[int2(a1,a2)] = new fun<A1,A2>(f);
    mem_hash.clear();
  }
  
  //The constructor requires a base function connecting the two
  //toplevels of the inheritance graphs.  It also gives you integer vertex
  //ids for the graph base vertices (effectively returned in b1 and b2).
  disp(int *b1,int *b2,base_func f) {
    fun_hash[int2(0,0)] = new fun<B1,B2>(f);
    if(b1)
      *b1=0;
    if(b2)
      *b2=0;
    build_leaf_list();
  }
  
  ~disp() {
    for(Fun_Hash::iterator h=fun_hash.begin();h!=fun_hash.end();h++)
      delete h->second;
  }

};

#endif