#include "chain.h"
#include <assert.h>
#include <stdlib.h>

chain::chain(link *linkList, int linkNum) : sentinelCost(-1)
{
    this->linkList = new link[linkNum];
    for (int i = 0; i < linkNum; i++)
        this->linkList[i] = linkList[i];
    this->linkNum = linkNum;
}

chain::~chain() { 
    for (int i= 0; i < tableSize; i++) {
        delete []minCostTable[i];
    }
    delete []minCostTable;
    delete []linkList;
}


// table size may differ from linkNum for some types of chain
void chain::initTable(int tableSize)
{
    this->tableSize = tableSize;
    minCostTable = new partitionCost*[tableSize];
    for (int i= 0; i < tableSize; i++) {
        minCostTable[i] = new partitionCost[tableSize];
        for (int k= 0; k < tableSize; k++) {
            minCostTable[i][k].cost = sentinelCost;
        }
    }
}

double chain::minCost(int i, int k) {
    // indices are shifted by accessor methods

    // if it's already calculated, return it
    if (getMCTValue(i,k) > sentinelCost)
        return getMCTValue(i,k);

    // if k < i + 2, there's no cost
    if (k < i + 2) {
        setMCTValue(i, k, 0.0);
        setMCTSplit(i, k, i); // arbitrary split
    }
    else {
        double tmpMin; // candidate minimum
        for (int j= i + 1; j != k; j++) {
            tmpMin= minCost(i, j) + minCost(j, k) +
                componentWeight(i, j, k);
            if (j == i + 1 || tmpMin < getMCTValue(i,k)) {
                setMCTValue(i, k, tmpMin);
                setMCTSplit(i, k, j);
            }
        }
    }

    assert(getMCTValue(i, k) > sentinelCost);
    return getMCTValue(i, k);
}

/*****************************************************************
 * componentWeight: cost of one unit of the partition.
 * We put a trivial return value in the base class, since it is
 * meant to be overridden.
 ****************************************************************/
double chain::componentWeight(int i, int j, int k) {
    return 0.0;
}

/*****************************************************************
 * minPartition: list the components of this partition inOrder
 ****************************************************************/
componentNode *chain::minPartition(int i, int k) {
    componentNode *componentList= NULL, *leftList, *rightList;
  
    // make sure minCost has been calculated..
    // no need to use its return value
    minCost(i, k);

    if (k - i > 1) {
        int j = getMCTSplit(i, k);
        componentList= new componentNode;
        assert(componentList != NULL);
        componentList->value.i= i;
        componentList->value.j= j;
        componentList->value.k= k;
        componentList->tail= componentList; // tail so far...

        // get inOrder lists of right and left partitions
        rightList= chain::minPartition(j, k);
        leftList= chain::minPartition(i, j);

        componentList->next= rightList; // works if its NULL too
        if (rightList != NULL) {
            componentList->tail= rightList->tail;
        }

        if (leftList == NULL) {
            leftList= componentList; // lose empty leftList
        }
        else {
            leftList->tail->next= componentList;
        }

        leftList->tail= componentList->tail; // leftList can't be empty
        componentList= leftList;
    }

    return componentList;
}

double chain::partitionTally(componentNode *partitionList) {
    double sum= 0.0;
    componentNode *nextNode= partitionList;

    while (nextNode != NULL) {
        sum += componentWeight(nextNode->value.i, 
                               nextNode->value.j, 
                               nextNode->value.k);
        nextNode= nextNode->next;
    }
    return sum;
}

int chain::getMCTSplit(int i, int k)
{
    return minCostTable[i][k].j;
}

int chain::setMCTSplit(int i, int k, int j)
{
    return minCostTable[i][k].j = j;
}

double chain::getMCTValue(int i, int k)
{
    return minCostTable[i][k].cost;
}

double chain::setMCTValue(int i, int k, double d)
{
    return minCostTable[i][k].cost = d;
}