#include "DecisionTree.h"using namespace DT;DecisionTree::~DecisionTree() {    if (headVertex == NULL) {        delete headVertex;    } else {        delete currLeaf;    }}double DecisionTree::getProb(double state, double* allStates) const{    const Leaf* l = getLeaf(allStates);#ifdef DEBUG    if (l == NULL) {        cout << "ERROR: could not find leaf for states!\n";        // HACK        cout << "us = " << var << " (" << allStates[var] << ")\n";        return 0;    }    // DEBUG    if (l->getProb(state) == 0.0) {        cout << "ERROR: leaf returned less than zero in DT::getProb!\n";    }#endif    return l->getProb(state);}double DecisionTree::getLogProb(double state, double* allStates) const{    const Leaf* l = getLeaf(allStates);#ifdef DEBUG    if (l == NULL) {        cout << "ERROR: could not find leaf for states!\n";        // HACK        cout << "us = " << var << " (" << allStates[var] << ")\n";        return 0;    }    // DEBUG    if (l->getLogProb(state) == 0.0) {        cout << "ERROR: leaf returned zero in DT::getLogProb!\n";    }#endif    return l->getLogProb(state);}double DecisionTree::sample(double* allStates) const{    const Leaf* l = getLeaf(allStates);#ifdef DEBUG    if (l == NULL) {        cout << "ERROR: could not find leaf for states!\n";        // HACK        cout << "us = " << var << " (" << allStates[var] << ")\n";        return 0;    }#endif    return l->sample();}list<double> DecisionTree::getSplits(int var) const{    list<double> ret;    if (headVertex != NULL) {        headVertex->getSplits(var, ret);    }    return ret;}const Leaf* DecisionTree::getLeaf(double* allStates) const{    if (headVertex == NULL) {        if (currLeaf == NULL) {            cout << "ERROR: no leaf found in getLeaf()!\n";            return NULL;        } else {            return currLeaf;        }    }#if 0    return headVertex->getLeaf(allStates);#else    const Vertex* currVertex = headVertex;    while (currVertex) {        list<Branch*>::const_iterator c = currVertex->children.begin();        //for (c = currVertex->children.begin(); c != currVertex->children.end(); c++)        if (!(*c)->inRange(allStates[currVertex->split])) {            c++;        }        if ((*c)->childLeaf) {            return (*c)->childLeaf;        } else {            currVertex = (*c)->childVertex;        }    }    cout << "ERROR: no leaf found!\n";    return NULL;#endif}void DecisionTree::beginVertex(int splitVar){    // DEBUG    //cout << "Starting vertex!\n";    currVertex = new Vertex(splitVar, currBranch);    if (headVertex == NULL) {        // If there's no root vertex, set it as such        headVertex = currVertex;    } else {        // Otherwise, add it as the child of a branch        currBranch->setVertex(currVertex);    }}void DecisionTree::endVertex(){    // DEBUG    //cout << "Ending vertex!\n";    if (currVertex != headVertex) {        currVertex = currBranch->getParent();    }}void DecisionTree::beginBranch() {    // DEBUG    //cout << "Adding branch!\n";    currBranch = new Branch(currVertex);    currVertex->addChild(currBranch);}void DecisionTree::endBranch() {    // DEBUG    //cout << "Ending branch!\n";    // Move up in the tree    currBranch = currVertex->getParent();}void DecisionTree::endValues(list<Range> values) {    currBranch->setValues(values);}void DecisionTree::beginMultinomial() {    currLeaf = currMultinomial = new Multinomial(maxVal);    leafList.push_back(currLeaf);    if (currBranch != NULL) {        currBranch->setLeaf(currLeaf);    }}void DecisionTree::endProbs(double* probs) {    currMultinomial->setProbs(probs);}void DecisionTree::endBinGaussian() {    currLeaf = new BinGaussian(currMean, currSD, currProbMissing);    leafList.push_back(currLeaf);    if (currBranch != NULL) {        currBranch->setLeaf(currLeaf);    }}namespace DT {Vertex::~Vertex(){    list<Branch*>::iterator c;    for (c = children.begin(); c != children.end(); c++) {        delete (*c);    }}void Vertex::getSplits(int var, list<double>& splits){    // Search for splits in each branch    for (list<Branch*>::iterator i = children.begin();             i != children.end(); i++) {        (*i)->getSplits(var, splits);    }}Leaf* Vertex::getLeaf(double* allStates){    Leaf* ret = NULL;    for (list<Branch*>::iterator i = children.begin();             i != children.end() && ret == NULL; i++) {        ret = (*i)->getLeaf(allStates);    }    if (ret == NULL) {        cout << "ERROR: no leaf found, split = " << split             << " (" << allStates[split] << ")" << endl;    }    return ret;}Branch::~Branch(){     // Delete children in destructor (but not parent!)    delete childVertex;    delete childLeaf; }bool Branch::inRange(double val){    for (list<Range>::iterator i = values.begin();             i != values.end(); i++) {        if (i->inRange(val)) {            return true;        }    }    return false;}void Branch::getSplits(int var, list<double>& splits){    // Add values from this branch, if we're splitting on the right var    if (parent->getSplitVar() == var) {        Range r = *(values.begin());        if (!r.missing && r.minV > -HUGE) {            splits.push_back(r.minV);        }    }    if (childVertex != NULL) {        childVertex->getSplits(var, splits);    }}Leaf* Branch::getLeaf(double* allVals) {    if (!inRange(allVals[parent->getSplitVar()])) {        return NULL;    } else if (childLeaf != NULL) {        return childLeaf;    } else if (childVertex != NULL) {        return childVertex->getLeaf(allVals);    } else {        cout << "ERROR: missing leaf or branch in DecisionTree!\n";        return NULL;    }}};