/* fundamential data structures for
 * finance++, trees and matrices 
 */

#ifdef GRAPHICS
#include "gd.h"
#include "gdfonts.h"
#endif

#define MAX(f1, f2)            ( (f1 >= f2) ? f1 : f2)

/* ************** Trees *****************/
struct MemorySaving
{
};

struct Complete
{
};

struct Empty
{
};

template <class DataStructureMethod, class UnderlyingCalculationMethod>
class Tree : protected DataStructureMethod, protected UnderlyingCalculationMethod
{
protected:
  TreeNode<double> *sRoot_;
};


template <class UnderlyingCalculationMethod>
class Tree<Complete, UnderlyingCalculationMethod> : UnderlyingCalculationMethod
{
private:
  int degree_;

// BEGIN treeConstr
  void Constr(int inQ) 
  { 
    degree_ = inQ; 
    
    sRoot_ = new TreeNode<double>;
    sRoot_->value = 0.0;
    sRoot_->childNum = 0;
    sRoot_->depth = 0;

    sBreadthFirstIter_ = NULL;
    sPostOrderIter_ = NULL;
  }
// END treeConstr

// BEGIN treeCompleteCalc
  void UpdateCalc(int N, int depth, TreeNode<double> *node, vector< vector<double> > M)
  {
    if(depth == N)
      return;

    node->children = vector<TreeNode<double> *>(degree_);
    
    for(int c = 0; c < degree_; c++)
      {
	node->children[c] = new TreeNode<double>();

	node->children[c]->value = underlyingChildValue(node->value, c, depth, M);
	node->children[c]->childNum = c;
	node->children[c]->depth = depth+1;
       
	UpdateCalc(N, depth+1, node->children[c], M);
      }
  }
// END treeCompleteCalc  

// BEGIN treeEmptyCalc
  void UpdateEmpty(int N, int depth, TreeNode<double> *node)
  {
    if(depth == N)
      return;

    node->value = 0.0;

    node->children = vector<TreeNode<double> *>(degree_);

    for(int c = 0; c < degree_; c++)
      {
	node->children[c] = new TreeNode<double>();
	node->children[c]->value = 0.0;
	node->children[c]->childNum = c;
	node->children[c]->depth = depth+1;
	
	UpdateEmpty(N, depth+1, node->children[c]);
      }
  }

// END treeEmptyCalc

#ifdef GRAPHICS

  gdImagePtr im_out;
  int width, height;
  int white, black;
  char buf[1024];

  void dumpNodes(TreeNode<double> *node, int depth, int offset)
  {
    int x = 75 * depth;
    int y = offset;

    if(degree_ == 2)
      x = 75 * (depth-1);
  
    sprintf(buf, "%.2f", node->value);
    gdImageString(im_out, gdFontSmall, x, y, (unsigned char *)buf, black);

    if(node->children.size() == 2)
      {
	dumpNodes(node->children[0], depth + 1, (int)(offset + (height / pow(2,depth+1))));
	dumpNodes(node->children[1], depth + 1, (int)(offset - (height / pow(2,depth+1))));

	gdImageLine(im_out, x, y+12, x+75, offset + (int)((height / pow(2, depth+1))), black);
	gdImageLine(im_out, x, y, x+75, offset - (int)((height / pow(2, depth+1))), black);
      }
    else if(node->children.size() == 3)
      {
	dumpNodes(node->children[0], depth + 1, (int)(offset + (height / pow(3,depth+1))));
	dumpNodes(node->children[1], depth + 1, (int)offset);
	dumpNodes(node->children[2], depth + 1, (int)(offset - (height / pow(3,depth+1))));

	gdImageLine(im_out, x, y+12, x+75, offset + (int)((height / pow(3, depth+1))), black);
	gdImageLine(im_out, x, y, x+75, offset, black);
	gdImageLine(im_out, x, y, x+75, offset - (int)((height / pow(3, depth+1))), black);
      }
  }
#endif

// BEGIN treeCompleteElements    
protected:
  TreeNode<double> *sRoot_;
  BreadthFirstIterator<double> *sBreadthFirstIter_;
  PostOrderIterator<double> *sPostOrderIter_;
// END treeCompleteElements  

public:
// BEGIN treeCompleteConstr
  Tree(int inQ, double S0, int N, vector<vector<double> >M, TFunctor *inVisitListener)
  { 
    Constr(inQ);
    sRoot_->value = S0;

    UpdateCalc(N, 0, sRoot_, M);
    
    sBreadthFirstIter_ = new BreadthFirstIterator<double>(sRoot_, degree_);
    sPostOrderIter_ = new PostOrderIterator<double>(sRoot_, degree_, inVisitListener);    
  }
// END treeCompleteConstr

// BEGIN treeEmptyConstr
  Tree(int inQ, int inN)
  {
    Constr(inQ);

    UpdateEmpty(inN, 0, sRoot_);

    sBreadthFirstIter_ = new BreadthFirstIterator<double>(sRoot_, degree_);
    sPostOrderIter_ = new PostOrderIterator<double>(sRoot_, degree_, NULL);    
  }
// END treeEmptyConstr

// BEGIN treeCompleteIterator
  BreadthFirstIterator<double> *GetBreadthFirstIterator(void)
  {
    return sBreadthFirstIter_;
  }
  
  PostOrderIterator<double> *GetPostOrderIterator(void)
  {
    return sPostOrderIter_;
  }
// END treeCompleteIterator

  TreeNode<double> *GetRoot(void)
  {
    return sRoot_;
  }

#ifdef GRAPHICS

  void dump(char *fname, int inWidth, int inHeight)
  {
    FILE *f_out;

    width = inWidth;
    height = inHeight;
  
    im_out = gdImageCreate(width, height);
  
    white = gdImageColorAllocate(im_out, 255, 255, 255);
    gdImageColorTransparent(im_out, white);
    black = gdImageColorAllocate(im_out, 0, 0, 0);

    if(degree_ == 2)
      dumpNodes(sRoot_, 1, height / 2);
    else if(degree_ == 3)
      dumpNodes(sRoot_, 0, height / 2);
    else
      printf("tree of degree %d not supported.\n", degree_);
  
    f_out = fopen(fname, "wb");
  
    gdImagePng(im_out, f_out);
    fclose(f_out);
    
    gdImageDestroy(im_out);
  }  

#endif


};

/************* End of Trees ******************/

/************* Jagged Matrices **************/

// BEGIN matrixNode
template <class T>
class MatrixNode
{
public:
  T value;
};
// END matrixNode

// generic matrix
template <class DataStructureMethod, class UnderlyingCalculationMethod>
class Matrix : DataStructureMethod, UnderlyingCalculationMethod
{

};

// complete matrix
template <class UnderlyingCalculationMethod>
class Matrix<Complete, UnderlyingCalculationMethod> : UnderlyingCalculationMethod
{
private:
  int degree_;

// BEGIN matrixImpl
protected:
  vector< vector< MatrixNode <double> *> > jag_;
// END matrixImpl

// BEGIN matrixConstr
public:
  void Constr(int inQ) 
  {
    degree_ = inQ;
    
    MatrixNode<double> *node = new MatrixNode<double>;
    vector<MatrixNode<double> *> column = vector<MatrixNode<double> *>(1);

    // add the root node first.
    node->value = 0.0;
    column[0] = node;
    jag_.push_back(column);
  }
// END matrixConstr

// BEGIN matrixEmptyConstr
  Matrix(int inQ, unsigned int inN)
  {
    Constr(inQ);
    
    MatrixNode<double> *node;
    vector<MatrixNode<double> *> column;

    unsigned int columnHeight;
    for(unsigned int columnNum = 1; columnNum < inN+1; columnNum++)
      {
	columnHeight = 1 + columnNum * (inQ-1);
	column = vector<MatrixNode<double> *>(columnHeight);

	for(unsigned int rowNum = 0; rowNum < columnHeight; rowNum++)
	  {
	    node = new MatrixNode<double>;

	    node->value = 0.0;
	    column[rowNum] = node;
	  }
	
	jag_.push_back(column);
      }
  }
// END matrixEmptyConstr

// BEGIN matrixCompleteConstr
  Matrix(int inQ, double S0, unsigned int inN, vector<vector<double> >M) 
  {
    MatrixNode<double> *node = new MatrixNode<double>;
    vector<MatrixNode<double> *> column = vector<MatrixNode<double> *>(1);
    
    Constr(inQ);

    // set the root node value.
    jag_[0][0]->value = S0;
    
    unsigned int columnHeight;
    // now add the remaining nodes
    for(unsigned int columnNum = 1; columnNum < inN+1; columnNum++)
      {
	columnHeight = 1 + columnNum * (inQ-1);
	column = vector<MatrixNode<double> *>(columnHeight);

	for(int rowNum = columnHeight - 1; rowNum >= 0; rowNum--)
	  {
	    node = new MatrixNode<double>;
	    unsigned int sRowNum = rowNum;

	    if(sRowNum == 0)
	      node->value = underlyingChildValue(jag_[columnNum-1][0]->value, 0, columnNum, M);
	    else if(sRowNum >= jag_[columnNum-1].size())
	      node->value = underlyingChildValue(jag_[columnNum-1][jag_[columnNum-1].size() - 1]->value,
						 sRowNum - jag_[columnNum-1].size() + 1, columnNum, M);
	    else
	      node->value = underlyingChildValue(jag_[columnNum-1][sRowNum - (sRowNum % inQ)]->value, 
						 sRowNum % inQ, columnNum, M);	      
	    
	    column[rowNum] = node;
	  }
	
	jag_.push_back(column);
      }
  }
// END matrixCompleteConstr

#ifdef GRAPHICS

  gdImagePtr im_out;
  int width, height;
  int white, black;
  char buf[1024];

  void dumpNode(double value, int depth, int offset)
  {
    int x = 75 * depth;
    int y = offset;

    if(degree_ == 2)
      x = 75 * depth;

    sprintf(buf, "%.2f", value);
    gdImageString(im_out, gdFontSmall, x, y, (unsigned char *)buf, black);
  }

  void dumpColumn(vector<MatrixNode<double> *> column, unsigned int depth, int offset)
  {
    for(unsigned int i = 0; i < column.size(); i++)
      {
	dumpNode(column[column.size() - 1 - i]->value, depth, (int)offset + (i * 75) );
	if(depth < jag_.size() - 1)
	  {
	    if(degree_ == 2)
	      {
		gdImageLine(im_out, 75 * (depth), offset + (i * 75),         // top line
			    75 * (depth+1), offset + (i*75) - 30, black);
		gdImageLine(im_out, 75 * (depth), offset + (i * 75) + 13,    // bottom line
			    75 * (depth+1), offset + (i*75)+13+30, black);
		
	      }
	    else if(degree_ == 3)
	      {
		gdImageLine(im_out, 75 * (depth)+10, offset + (i * 75),         // top line
			    75 * (depth+1), offset + (i*75) - 62, black);
		gdImageLine(im_out, 75 * (depth)+10, offset + (i * 75) + 13,    // horizontal line
			    75 * (depth+1), offset + (i*75)+13, black);
		gdImageLine(im_out, 75 * (depth)+10, offset + (i * 75) + 13,    // bottom line
			    75 * (depth+1), offset + (i*75)+13+62, black);
	      }
	  }
      }
  }

  void dump(char *fname, int inWidth, int inHeight)
  {
    FILE *f_out;

    width = inWidth;
    height = inHeight;
  
    im_out = gdImageCreate(width, height);
  
    white = gdImageColorAllocate(im_out, 255, 255, 255);
    gdImageColorTransparent(im_out, white);
    black = gdImageColorAllocate(im_out, 0, 0, 0);

    if(degree_ == 2)
      {
	for(unsigned int colNum = 0; colNum < jag_.size(); colNum++)
	  dumpColumn(jag_[colNum], colNum, (int)height / 2 - 37*colNum);
      }
    else if(degree_ == 3)
      for(unsigned int colNum = 0; colNum < jag_.size(); colNum++)
	dumpColumn(jag_[colNum], colNum, (int)height / 2 - 75*colNum);
    else
      printf("matrix of degree %d not supported.\n", degree_);
  
    f_out = fopen(fname, "wb");
  
    gdImagePng(im_out, f_out);
    fclose(f_out);
    
    gdImageDestroy(im_out);
  }  

#endif

  // BEGIN matrixAccess
  void Set(int col, int row, double inValue)
  {
    jag_[col][row]->value = inValue;
  }
  
  double Get(int col, int row)
  {
    return jag_[col][row]->value;
  }

  unsigned int Height(int col)
  {
    return jag_[col].size();
  }
  // END matrixAccess
};

// memory saving matrix
template <class UnderlyingCalculationMethod>
class Matrix<MemorySaving, UnderlyingCalculationMethod> : UnderlyingCalculationMethod
{
protected:

public:
  Matrix(int inQ, double S0, int N, vector<vector<double> >M) 
  {
  }

  void Set(int row, int col, double inValue);
  double Get(int row, int col);

};






















