- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# /home/coin/svn-release/Smi-0.93.1/Smi/src/SmiScenarioTree.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2003, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    00003 #ifndef SmiScenarioTree_H
    00004 #define SmiScenarioTree_H
    00005
    00012 #include <vector>
    00013 #include <map>
    00014 #include <iostream>
    00015 #include <cassert>
    00016
    00017 #include "CoinPragma.hpp"
    00018
    00026 template<class T>
    00027 class SmiTreeNode {
    00028         //friend void SmiTreeNodeUnitTest();
    00029 public:
    00030
    00031         typedef std::map<int, SmiTreeNode<T>*> child_label_map;
    00032
    00033         bool hasParent() {
    00034                 return (parent_ != NULL);
    00035         }
    00036         bool hasChild() {
    00037                 return (child_ != NULL);
    00038         }
    00039         bool hasSibling() {
    00040                 return (sibling_ != NULL);
    00041         }
    00042
    00043         SmiTreeNode<T> *getParent() {
    00044                 return parent_;
    00045         }
    00046         SmiTreeNode<T> *getChild() {
    00047                 return child_;
    00048         }
    00049         SmiTreeNode<T> *getSibling() {
    00050                 return sibling_;
    00051         }
    00052
    00053         void setLastChildLabel(int label) {
    00054                 child_labels_.insert(std::make_pair(label, this->getChild()));
    00055         }
    00056
    00057         SmiTreeNode<T> *getChildByLabel(int n) {
    00058
    00059                 /*
    00060                  //AJK debug code
    00061                  child_label_map::iterator begpos = child_labels_.begin();
    00062                  child_label_map::iterator endpos = child_labels_.end();
    00063                  while(begpos!=endpos)
    00064                  {
    00065                  printf(" found label %d \n",begpos->first);
    00066                  ++begpos;
    00067                  }
    00068                  */
    00069                 typename child_label_map::iterator pos = child_labels_.find(n);
    00070                 if (pos != child_labels_.end())
    00071                         return pos->second;
    00072                 else
    00073                         return NULL;
    00074         }
    00075
    00076         int depth() {
    00077                 return depth_;
    00078         }
    00079         int numChildren() {
    00080                 return nchild_;
    00081         }
    00082         int scenario() {
    00083                 return scen_;
    00084         }
    00085         void setScenario(int s) {
    00086                 scen_ = s;
    00087         }
    00088
    00089         // Returns new child node with cd, linked in the tree
    00090         SmiTreeNode<T> * addChild(T cd, int scenario) {
    00091                 SmiTreeNode<T> *c = new SmiTreeNode(cd);
    00092
    00093                 c->parent_ = this;
    00094                 c->depth_ = depth_ + 1;
    00095                 c->sibling_ = child_;
    00096                 c->scen_ = scenario;
    00097                 nchild_++;
    00098                 child_ = c;
    00099                 return c;
    00100         }
    00101
    00102         std::vector<SmiTreeNode<T> *> *getChildren() {
    00103                 SmiTreeNode<T> *pnode = this;
    00104                 int i = this->numChildren();
    00105                 if (i == 0) {
    00106                         return NULL;
    00107                 }
    00108                 std::vector<SmiTreeNode<T> *> *vec = new std::vector<SmiTreeNode<T> *> (i);
    00109                 (*vec)[--i] = pnode = pnode->getChild();
    00110                 while (i > 0)
    00111                         (*vec)[--i] = pnode = pnode->getSibling();
    00112                 return vec;
    00113         }
    00114
    00115         T getDataPtr() {
    00116                 return ptr_;
    00117         }
    00118
    00119         //--------------------------------------------------------------------------
    00122
    00123         SmiTreeNode<T> () {
    00124                 parent_ = NULL;
    00125                 child_ = NULL;
    00126                 sibling_ = NULL;
    00127                 nchild_ = 0;
    00128                 depth_ = 0;
    00129                 scen_ = -1;
    00130         }
    00131
    00133         SmiTreeNode<T> (T p) {
    00134                 parent_ = NULL;
    00135                 child_ = NULL;
    00136                 sibling_ = NULL;
    00137                 nchild_ = 0;
    00138                 depth_ = 0;
    00139                 ptr_ = p;
    00140                 scen_ = -1;
    00141         }
    00142
    00144
    00145         ~SmiTreeNode<T>() {
    00146                 delete sibling_;
    00147                 delete child_;
    00148         }
    00149
    00151
    00152 protected:
    00153
    00154         void setChild(SmiTreeNode<T> *c) {
    00155                 child_ = c;
    00156         }
    00157         void setSibling(SmiTreeNode<T> *s) {
    00158                 sibling_ = s;
    00159         }
    00160         SmiTreeNode<T> *getParentP() {
    00161                 return parent_;
    00162         }
    00163         SmiTreeNode<T> *getChildP() {
    00164                 return child_;
    00165         }
    00166         SmiTreeNode<T> *getSiblingP() {
    00167                 return sibling_;
    00168         }
    00169
    00170 private:
    00171         SmiTreeNode<T> *parent_;
    00172         SmiTreeNode<T> *child_;
    00173         SmiTreeNode<T> *sibling_;
    00174         int scen_;
    00175         int nchild_;
    00176         int depth_;
    00177         T ptr_;
    00178         child_label_map child_labels_;
    00179
    00180 };
    00181
    00182 //#############################################################################
    00188 void SmiTreeNodeUnitTest();
    00189
    00190 /*TODO: split this class into two classes
    00191  *      1) SmiScenarioTree
    00192  *  2) SmiLabelledTree
    00193  */
    00194
    00195 template<class T>
    00196 class SmiScenarioTree {
    00197         //friend void SmiScenarioTreeUnitTest();
    00198 public:
    00199
    00200         //---------------------------------------------------------------------------
    00203
    00204
    00206         typename std::vector<T>::iterator treeBegin() {
    00207                 return node_data.begin();
    00208         }
    00210         typename std::vector<T>::iterator treeEnd() {
    00211                 return node_data.end();
    00212         }
    00214         std::vector<T> &wholeTree() {
    00215                 return node_data;
    00216         }
    00217
    00221         typename std::vector<T>::iterator scenBegin(int s) {
    00222                 getScenario(s);
    00223                 return scen_data.begin();
    00224         }
    00225
    00226         typename std::vector<T>::iterator scenEnd(int s) {
    00227                 getScenario(s);
    00228                 return scen_data.begin() + leaf_[s]->depth() + 1;
    00229         }
    00230
    00231         //---------------------------------------------------------------------------
    00234
    00236         SmiTreeNode<T> *getRoot() {
    00237                 return root_;
    00238         }
    00239
    00241         SmiTreeNode<T> *getLeaf(int scn) {
    00242                 return leaf_[scn];
    00243         }
    00244
    00246         SmiTreeNode<T> *find(unsigned int scenario, int stage) {
    00247                 assert (scenario < leaf_.size());
    00248                 SmiTreeNode<T> * n = leaf_[scenario];
    00249                 assert (stage < n->depth() + 1);
    00250                 while (stage < n->depth())
    00251                         n = n->getParent();
    00252                 return n;
    00253         }
    00254
    00256         int getNumScenarios() {
    00257                 return (int) leaf_.size();
    00258         }
    00259
    00261         SmiTreeNode<T> *find(std::vector<int> &label) {
    00262
    00263                 assert(label.size()>0);
    00264                 SmiTreeNode<T> *n = root_, *next;
    00265                 unsigned int i = 0;
    00266                 while ((i < label.size()) && (next = n->getChildByLabel(label[i]))) {
    00267                         ++i;
    00268                         n = next;
    00269                 }
    00270                 return n;
    00271         }
    00272
    00274         SmiTreeNode<T> *find(int *label, unsigned int sz) {
    00275
    00276                 assert(sz>0);
    00277                 SmiTreeNode<T> *n = root_, *next;
    00278                 if (!n)
    00279                         return n;
    00280                 unsigned int i = 0;
    00281                 while ((i < sz) && (next = n->getChildByLabel(label[i]))) {
    00282                         ++i;
    00283                         n = next;
    00284                 }
    00285                 return n;
    00286         }
    00287
    00289         std::vector<T> &getScenario(int scenario) {
    00290                 assert (scenario < (int) leaf_.size());
    00291                 SmiTreeNode<T> * n = leaf_[scenario];
    00292
    00293                 //if ( n->getDataPtr()==scen_data[n->depth()] ) return scen_data;
    00294                 //Christian: Why is this necessary? Reason: Number of Stages places should be readily available in the vector, if this is not already the case, do it..
    00295                 //int ns = n->depth() + 1 - scen_data.size();
    00296                 //for (int j = 0; j < ns; j++)
    00297                 //      scen_data.push_back(n->getDataPtr());
    00298
    00299                 //Christian: TODO: Why not change this so, that it looks better? i.e. i-- and i= n->depth(); and i >= 0?
    00300                 //Christian: TODO: Think about changing container from vector to deque or list..
    00301                 int i = n->depth() + 1;
    00302                 scen_data.resize(i,n->getDataPtr()); //Maybe a call to capacity should do it too.. ?! TODO
    00303                 while (i > 0) {
    00304                         scen_data[--i] = n->getDataPtr();
    00305                         n = n->getParent();
    00306                 }
    00307                 return scen_data;
    00308         }
    00309
    00311
    00312         //---------------------------------------------------------------------------
    00322         int addPathtoLeaf(int brscenario, int stage, std::vector<T> &pathdata,
    00323                         unsigned int start = 0) {
    00324                 SmiTreeNode<T> *parent = NULL;
    00325                 int scenario = static_cast<int>(leaf_.size());
    00326                 if (scenario)
    00327                         parent = find(brscenario, stage);
    00328
    00329                 parent = addNodesToTree(parent, scenario, pathdata, start);
    00330
    00331                 if (pathdata.size()) {
    00332                         leaf_.push_back(parent);
    00333                 }
    00334                 return static_cast<int>(leaf_.size()) - 1;
    00335
    00336         }
    00337
    00339         void setChildLabels(SmiTreeNode<T> *n, std::vector<int> labels) {
    00340                 int t = n->depth();
    00341                 while (n->hasChild()) {
    00342                         n->setLastChildLabel(labels[++t]);
    00343                         n = n->getChild();
    00344                 }
    00345         }
    00346
    00353         int addPathtoLeaf(std::vector<int> &labels, std::vector<T> &pathdata) {
    00354                 SmiTreeNode<T> *parent = NULL;
    00355                 int scenario = static_cast<int>(leaf_.size());
    00356                 if (scenario)
    00357                         parent = find(labels);
    00358
    00359                 unsigned int i = 0;
    00360                 if (parent)
    00361                         i = parent->depth() + 1;
    00362
    00363                 parent = addNodesToTree(parent, scenario, pathdata, i);
    00364
    00365                 if (pathdata.size()) {
    00366                         leaf_.push_back(parent);
    00367                 }
    00368                 return static_cast<int>(leaf_.size()) - 1;
    00369
    00370         }
    00371
    00372         SmiTreeNode<T> * addNodesToTree(SmiTreeNode<T> *parent, int scenario,
    00373                         std::vector<T> &pathdata, int start) {
    00374
    00375                 for (unsigned int i = start; i < pathdata.size(); ++i) {
    00376                         if (parent) {
    00377                                 parent = parent->addChild(*&pathdata[i], scenario);
    00378                         } else {
    00379                                 parent = root_ = new SmiTreeNode<T> (*&pathdata[0]);
    00380                                 root_->setScenario(scenario);
    00381                         }
    00382                         // add data to full node_data array
    00383                         node_data.push_back(*&pathdata[i]);
    00384                 }
    00385
    00386                 return parent;
    00387         }
    00389         //--------------------------------------------------------------------------
    00392
    00393         SmiScenarioTree<T> () :
    00394                 leaf_(0), root_(NULL) {
    00395         }
    00396
    00398         virtual ~SmiScenarioTree<T> () {
    00399                 delete root_;
    00400         }
    00402
    00403 private:
    00404         std::vector<T> node_data;
    00405         std::vector<T> scen_data;
    00406         std::vector<SmiTreeNode<T> *> leaf_;
    00407         SmiTreeNode<T> *root_;
    00408 };
    00409
    00410 //#############################################################################
    00416 void SmiScenarioTreeUnitTest();
    00417
    00418 #endif //SmiScenarioTree_H