/*
 * a chain is a list of links, which can be partitioned in various
 * ways.  Each partition has an associated cost which we can try
 * to compute
 *
 */

/*
 * a link is the unit for building chains and partitions.  It has
 * two associated double values, x and y, which may work as
 * coordinates for a vertex (vertexChain), dimensions of a matrix
 * (matrix chain), or a key and its frequency (bst chain).
 *
 */

struct link {
    double x, y;
};


/*
 * component: three integers specify a basic unit of a partition
 *
 */

struct component {
    int i, j, k;
};

/*
 * componentNode: single element of a linked list of components
 *
 */

struct componentNode {
    component value;
    componentNode *next;
    componentNode *tail;
};

/*
 * a partition has an associated cost, plus it can be specified
 * by its range (i...k) and its j (top level division).
 * The range is implicit, so it needs data members cost and
 * j.
 *
 */

struct partitionCost {
    double cost; // cost of this partition
    int j; // index of where to split this partition
};

const double doubleFudge= 0.000001; // for comparing doubles

class chain {
  public:

    /*
     * create a chain given a list of links, linkList, and the
     * size of this list, linkNum.
     *
     */

    chain(link *linkList, int linkNum);

    virtual ~chain();

    /*
     * minPartition: return a minimal partition of the range i..k
     * as a list of components.
     *
     */

    componentNode *minPartition(int i, int k);

    /*
     * partitionTally: return the sum of the costs of the components
     * of partitionList.
     *
     */

    double partitionTally(componentNode *partitionList);

 protected:

    /*
     * componentWeight is the portion of the cost of a partition that
     * belongs to a single component, determined by the range
     * i..k and the choice of j.  This corresponds to w(i,j,k) in
     * the handout.
     *
     */

    virtual double componentWeight(int i, int j, int k);

    /*
     * minCost calculates the cost of a minimal partition of the
     * portion of this chain in the range i..k.  It updates
     * minCostTable to hold this minimal cost, plus the index
     * j that specifies a partition that achieves the minimal
     * cost.  This corresponds to c[i][k] in the handout.
     *
     */

    double minCost(int i, int k);

    // keep track of cost of minimum partitions
    link *linkList; // list of the links in this chain
    const double sentinelCost; // out-of-range sentinel for costs
    int linkNum; // number of links in this chain
    partitionCost **minCostTable;

    /*
     * accessor methods for the minCostTable, since the indexes
     * may be shifted for some types of chains.
     *
     */

    virtual int getMCTSplit(int i, int k);
    virtual int setMCTSplit(int i, int k, int j);
    virtual double getMCTValue(int i, int k);
    virtual double setMCTValue(int i, int k, double d);
    
    /* table size is specific to derived classes */
    void initTable(int tableSize);
    int tableSize; /* we'll need to keep track */
};


/*
 * a chain of vertices is a polygon.  If it's a convex polygon
 * (something we don't check) then it can be triangulated, and
 * a minimal triangulation found, so long as there is a component
 * cost function defined for each triangle.
 *
 */

class vertexChain: public chain {

  public:

    // constructor calls base constructor
    vertexChain(link *linkList, int linkNum);

    /*
     * override the componentWeight(int i, int j, int k) function
     *
     */

    double componentWeight(int i, int j, int k);

    /*
     * minPartition: return the partition for a chain with linkNum
     * links.
     *
     */

    componentNode *minPartition(int linkNum);

};


/*
 * matrixChain.h: public interface for matrix chains.
 *
 */

class matrixChain : public chain {
 
  public:

    /*
     * constructor calls base constructor from chain
     *
     */

    matrixChain(link *linkList, int linkNum);

    /*
     * override the componentWeight(int i, int j, int k) function
     *
     */

    double componentWeight(int i, int j, int k);

    /*
     * minPartition: return the partition for a matrix chain with
     * linkNum links.
     *
     */

    componentNode *minPartition(int linkNum);

};

/*
 * bstChain.h
 * public interface for BST chains
 *
 */

class bstChain: public chain {

  public:

    // constructor calls base constructor
    bstChain(link *linkList, int linkNum);


    /*
     * override the componentWeight(int i, int j, int k) function.
     *
     */

    double componentWeight (int i, int j, int k);


    /*
     * minPartition: return the partition of a BST chain with linkNum
     * links.
     *
     */

    componentNode *minPartition(int linkNum);

 protected:
    /*
     * accessor methods for the minCostTable, since the indexes
     * may be shifted for some types of chains.
     *
     */

    int getMCTSplit(int i, int k);
    int setMCTSplit(int i, int k, int j);
    double getMCTValue(int i, int k);
    double setMCTValue(int i, int k, double d);

};