/home/coin/SVN-release/CoinAll-1.1.0/Smi/src/SmiScenarioTree.hpp

Go to the documentation of this file.

// Copyright (C) 2003, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef SmiScenarioTree_H
#define SmiScenarioTree_H

#if defined(_MSC_VER)
// Turn off compiler warning about long names
#  pragma warning(disable:4786)
#endif

#include <list>
#include <vector>
#include <map>
#include <iostream>
#include <assert.h>


using namespace std;

template <class T> 
class SmiTreeNode  {
   //friend void SmiTreeNodeUnitTest();
public:

        typedef map<int,SmiTreeNode<T>*> child_label_map;

        bool hasParent() { return (parent_!=NULL); }
        bool hasChild()  { return (child_!=NULL);  }
        bool hasSibling(){ return (sibling_!=NULL);}

        SmiTreeNode<T>  *getParent() { return parent_; }
        SmiTreeNode<T>  *getChild()  { return child_;  }
        SmiTreeNode<T>  *getSibling(){ return sibling_;}

        void setLastChildLabel(int label) { child_labels_.insert(make_pair(label,this->getChild()));}

        SmiTreeNode<T>  *getChildByLabel(int n){
                
                /*
                //AJK debug code
                child_label_map::iterator begpos = child_labels_.begin();
            child_label_map::iterator endpos = child_labels_.end();
                while(begpos!=endpos)
                {
                        printf(" found label %d \n",begpos->first);
                        ++begpos;
                }
                */
                typename child_label_map::iterator pos = child_labels_.find(n);
                if (pos!=child_labels_.end())
                        return pos->second;
                else
                        return NULL;
        }


        int depth() { return depth_; }
        int numChildren() { return nchild_; }
        int scenario() {return scen_; }
        void setScenario(int s) {scen_=s; }

        SmiTreeNode<T> * addChild(T cd, int scenario)
        {
                SmiTreeNode<T> *c = new SmiTreeNode(cd);
        
                c->parent_     = this;
                c->depth_      = depth_ + 1;
                c->sibling_    = child_;
                c->scen_       = scenario;
                nchild_++;
                child_ = c;
                return c;
        }

        vector<SmiTreeNode<T> *> *getChildren()
        {
                SmiTreeNode<T> *pnode = this;
                int i = this->numChildren();
                if (i==0){
                        return NULL;
                }
                vector<SmiTreeNode<T> *> *vec = new vector<SmiTreeNode<T> *>(i);
                (*vec)[--i] = pnode = pnode->getChild();
                while (i>0)
                        (*vec)[--i] = pnode = pnode->getSibling();
                return vec;
        }

        T getDataPtr() { return ptr_; }

//--------------------------------------------------------------------------

   SmiTreeNode<T>(){
        parent_=NULL;
        child_=NULL;
        sibling_= NULL;
        nchild_ = 0;
        depth_ = 0;
        scen_ = -1;
   }

   SmiTreeNode<T>(T p){
        parent_=NULL;
        child_=NULL;
        sibling_= NULL;
        nchild_ = 0;
        depth_ = 0;
        ptr_ = p;
        scen_ = -1;
   }

   
   ~SmiTreeNode()
   {
           delete sibling_;
           delete child_;
           //delete ptr_ ;
   }
 

protected:
        
        void setChild  (SmiTreeNode<T>  *c) {child_ = c;}
        void setSibling(SmiTreeNode<T>  *s) {sibling_ = s;}
        SmiTreeNode<T>  *getParentP() { return parent_; }
        SmiTreeNode<T>  *getChildP()  { return child_;  }
        SmiTreeNode<T>  *getSiblingP(){ return sibling_;}
        

private:
        SmiTreeNode<T>  *parent_;
        SmiTreeNode<T>  *child_;
        SmiTreeNode<T>  *sibling_;
        int scen_;
        int nchild_;
        int depth_;
        T ptr_;
        child_label_map child_labels_;

};

//#############################################################################
void
SmiTreeNodeUnitTest();


template<class T>
class SmiScenarioTree  {
   //friend void SmiScenarioTreeUnitTest();
public:

//---------------------------------------------------------------------------


        typename vector<T>::iterator treeBegin(){ return node_data.begin(); }
        typename vector<T>::iterator treeEnd(){ return node_data.end();}
        vector<T> &wholeTree(){ return node_data;}

        typename vector<T>::iterator scenBegin(int s){
                getScenario(s);
                return scen_data.begin();
        }

        typename vector<T>::iterator scenEnd(int s){
                getScenario(s);
                return scen_data.begin()+leaf_[s]->depth()+1;
        }




//---------------------------------------------------------------------------

        SmiTreeNode<T> *getRoot() { return root_; }

        SmiTreeNode<T> *getLeaf(int scn) { return leaf_[scn];}

        SmiTreeNode<T> *find(unsigned int scenario, int stage)
        {
                assert (scenario < leaf_.size());               
                SmiTreeNode<T> * n = leaf_[scenario];
                assert (stage < n->depth() + 1);
                while (stage < n->depth())
                        n = n->getParent();
                return n;
        }

        int getNumScenarios()
        {
                return (int) leaf_.size();
        }


        SmiTreeNode<T> *find(vector<int> &label)
        {
                assert(label.size()>0);
                SmiTreeNode<T> *n = root_,*next;
                unsigned int i=0;
                while ((i<label.size()) && (next=n->getChildByLabel(label[i])))
                {
                        ++i;
                        n=next;
                }
                return n;
        }


        vector<T> &getScenario(int scenario)
        {
                assert (scenario < (int) leaf_.size());
                SmiTreeNode<T> * n = leaf_[scenario];

//              if ( n->getDataPtr()==scen_data[n->depth()] ) return scen_data;

                int ns=n->depth()+1-scen_data.size();
                for (int j=0; j<ns;j++)
                        scen_data.push_back(n->getDataPtr());

                int i=n->depth()+1;
                while(i>0)
                {
                        scen_data[--i] = n->getDataPtr();
                        n = n->getParent();
                }
                return scen_data;
        }



//---------------------------------------------------------------------------
        int addPathtoLeaf(int brscenario, int stage, vector<T> &pathdata, unsigned int start=0)
        {
                SmiTreeNode<T> *parent = NULL;
                int scenario=leaf_.size();
                if (scenario)
                        parent = find(brscenario,stage);
                        

                for (unsigned int i=start; i<pathdata.size(); ++i)
                {       
                        if (parent)
                        {
                                parent = parent->addChild(pathdata[i],scenario);
                        }
                        else
                        {
                                parent = root_ = new SmiTreeNode<T>(pathdata[0]);
                                root_->setScenario(scenario);
                        }
                        // add data to full node_data array
                        node_data.push_back(pathdata[i]);
                }
                if (pathdata.size())
                {
                        leaf_.push_back(parent);                        
                }
                return leaf_.size()-1;
                
        }
  
        void setChildLabels(SmiTreeNode<T> *n, vector<int> labels)
        {
                int t = n->depth();
                while(n->hasChild())
                {
                        n->setLastChildLabel(labels[++t]);
                        n = n->getChild();
                }
        }


        int addPathtoLeaf(vector<int>labels, vector<T> &pathdata)
        {
                SmiTreeNode<T> *parent = NULL;
                int scenario=leaf_.size();
                if (scenario)
                        parent = find(labels);
                        
                unsigned int i=0;
                if (parent) i=parent->depth()+1;

                for (; i<pathdata.size(); ++i)
                {       
                        if (parent)
                        {
                                parent = parent->addChild(pathdata[i],scenario);
                                
                        }
                        else
                        {
                                parent = root_ = new SmiTreeNode<T>(pathdata[0]);
                                root_->setScenario(scenario);
                        }
                        // add data to full node_data array
                        node_data.push_back(pathdata[i]);
                }
                if (pathdata.size())
                {
                        leaf_.push_back(parent);                        
                }
                return leaf_.size()-1;
                
        }
//--------------------------------------------------------------------------

        SmiScenarioTree<T>(): leaf_(0),root_(NULL) {}

       virtual ~SmiScenarioTree<T>() {delete root_;}

private:
        vector<T> node_data;
        vector<T> scen_data;
        vector<SmiTreeNode<T> *> leaf_;
        SmiTreeNode<T> *root_;
};

//#############################################################################
void
SmiScenarioTreeUnitTest();

#endif //SmiScenarioTree_H

---