00001
00002
00003 #ifndef SmiScenarioTree_H
00004 #define SmiScenarioTree_H
00005
00006 #if defined(_MSC_VER)
00007
00008 # pragma warning(disable:4786)
00009 #endif
00010
00016 #include <list>
00017 #include <vector>
00018 #include <map>
00019 #include <iostream>
00020 #include <assert.h>
00021
00022
00023 using namespace std;
00024
00033 template <class T>
00034 class SmiTreeNode {
00035
00036 public:
00037
00038 typedef map<int,SmiTreeNode<T>*> child_label_map;
00039
00040 bool hasParent() { return (parent_!=NULL); }
00041 bool hasChild() { return (child_!=NULL); }
00042 bool hasSibling(){ return (sibling_!=NULL);}
00043
00044 SmiTreeNode<T> *getParent() { return parent_; }
00045 SmiTreeNode<T> *getChild() { return child_; }
00046 SmiTreeNode<T> *getSibling(){ return sibling_;}
00047
00048 void setLastChildLabel(int label) { child_labels_.insert(make_pair(label,this->getChild()));}
00049
00050 SmiTreeNode<T> *getChildByLabel(int n){
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 typename child_label_map::iterator pos = child_labels_.find(n);
00063 if (pos!=child_labels_.end())
00064 return pos->second;
00065 else
00066 return NULL;
00067 }
00068
00069
00070 int depth() { return depth_; }
00071 int numChildren() { return nchild_; }
00072 int scenario() {return scen_; }
00073 void setScenario(int s) {scen_=s; }
00074
00075 SmiTreeNode<T> * addChild(T cd, int scenario)
00076 {
00077 SmiTreeNode<T> *c = new SmiTreeNode(cd);
00078
00079 c->parent_ = this;
00080 c->depth_ = depth_ + 1;
00081 c->sibling_ = child_;
00082 c->scen_ = scenario;
00083 nchild_++;
00084 child_ = c;
00085 return c;
00086 }
00087
00088 vector<SmiTreeNode<T> *> *getChildren()
00089 {
00090 SmiTreeNode<T> *pnode = this;
00091 int i = this->numChildren();
00092 if (i==0){
00093 return NULL;
00094 }
00095 vector<SmiTreeNode<T> *> *vec = new vector<SmiTreeNode<T> *>(i);
00096 (*vec)[--i] = pnode = pnode->getChild();
00097 while (i>0)
00098 (*vec)[--i] = pnode = pnode->getSibling();
00099 return vec;
00100 }
00101
00102 T getDataPtr() { return ptr_; }
00103
00104
00107
00108 SmiTreeNode<T>(){
00109 parent_=NULL;
00110 child_=NULL;
00111 sibling_= NULL;
00112 nchild_ = 0;
00113 depth_ = 0;
00114 scen_ = -1;
00115 }
00116
00118 SmiTreeNode<T>(T p){
00119 parent_=NULL;
00120 child_=NULL;
00121 sibling_= NULL;
00122 nchild_ = 0;
00123 depth_ = 0;
00124 ptr_ = p;
00125 scen_ = -1;
00126 }
00127
00129
00130 ~SmiTreeNode<T>()
00131 {
00132 delete sibling_;
00133 delete child_;
00134 }
00135
00137
00138 protected:
00139
00140 void setChild (SmiTreeNode<T> *c) {child_ = c;}
00141 void setSibling(SmiTreeNode<T> *s) {sibling_ = s;}
00142 SmiTreeNode<T> *getParentP() { return parent_; }
00143 SmiTreeNode<T> *getChildP() { return child_; }
00144 SmiTreeNode<T> *getSiblingP(){ return sibling_;}
00145
00146
00147 private:
00148 SmiTreeNode<T> *parent_;
00149 SmiTreeNode<T> *child_;
00150 SmiTreeNode<T> *sibling_;
00151 int scen_;
00152 int nchild_;
00153 int depth_;
00154 T ptr_;
00155 child_label_map child_labels_;
00156
00157 };
00158
00159
00165 void
00166 SmiTreeNodeUnitTest();
00167
00168
00169 template<class T>
00170 class SmiScenarioTree {
00171
00172 public:
00173
00174
00177
00178
00180 typename vector<T>::iterator treeBegin(){ return node_data.begin(); }
00182 typename vector<T>::iterator treeEnd(){ return node_data.end();}
00184 vector<T> &wholeTree(){ return node_data;}
00185
00189 typename vector<T>::iterator scenBegin(int s){
00190 getScenario(s);
00191 return scen_data.begin();
00192 }
00193
00194 typename vector<T>::iterator scenEnd(int s){
00195 getScenario(s);
00196 return scen_data.begin()+leaf_[s]->depth()+1;
00197 }
00198
00199
00200
00201
00202
00205
00207 SmiTreeNode<T> *getRoot() { return root_; }
00208
00210 SmiTreeNode<T> *getLeaf(int scn) { return leaf_[scn];}
00211
00213 SmiTreeNode<T> *find(unsigned int scenario, int stage)
00214 {
00215 assert (scenario < leaf_.size());
00216 SmiTreeNode<T> * n = leaf_[scenario];
00217 assert (stage < n->depth() + 1);
00218 while (stage < n->depth())
00219 n = n->getParent();
00220 return n;
00221 }
00222
00224 int getNumScenarios()
00225 {
00226 return (int) leaf_.size();
00227 }
00228
00229
00231 SmiTreeNode<T> *find(vector<int> &label)
00232 {
00233 assert(label.size()>0);
00234 SmiTreeNode<T> *n = root_,*next;
00235 unsigned int i=0;
00236 while ((i<label.size()) && (next=n->getChildByLabel(label[i])))
00237 {
00238 ++i;
00239 n=next;
00240 }
00241 return n;
00242 }
00243
00244
00246 vector<T> &getScenario(int scenario)
00247 {
00248 assert (scenario < (int) leaf_.size());
00249 SmiTreeNode<T> * n = leaf_[scenario];
00250
00251
00252
00253 int ns=n->depth()+1-scen_data.size();
00254 for (int j=0; j<ns;j++)
00255 scen_data.push_back(n->getDataPtr());
00256
00257 int i=n->depth()+1;
00258 while(i>0)
00259 {
00260 scen_data[--i] = n->getDataPtr();
00261 n = n->getParent();
00262 }
00263 return scen_data;
00264 }
00265
00266
00268
00269
00279 int addPathtoLeaf(int brscenario, int stage, vector<T> &pathdata, unsigned int start=0)
00280 {
00281 SmiTreeNode<T> *parent = NULL;
00282 int scenario=leaf_.size();
00283 if (scenario)
00284 parent = find(brscenario,stage);
00285
00286
00287 for (unsigned int i=start; i<pathdata.size(); ++i)
00288 {
00289 if (parent)
00290 {
00291 parent = parent->addChild(pathdata[i],scenario);
00292 }
00293 else
00294 {
00295 parent = root_ = new SmiTreeNode<T>(pathdata[0]);
00296 root_->setScenario(scenario);
00297 }
00298
00299 node_data.push_back(pathdata[i]);
00300 }
00301 if (pathdata.size())
00302 {
00303 leaf_.push_back(parent);
00304 }
00305 return leaf_.size()-1;
00306
00307 }
00308
00310 void setChildLabels(SmiTreeNode<T> *n, vector<int> labels)
00311 {
00312 int t = n->depth();
00313 while(n->hasChild())
00314 {
00315 n->setLastChildLabel(labels[++t]);
00316 n = n->getChild();
00317 }
00318 }
00319
00320
00327 int addPathtoLeaf(vector<int>labels, vector<T> &pathdata)
00328 {
00329 SmiTreeNode<T> *parent = NULL;
00330 int scenario=leaf_.size();
00331 if (scenario)
00332 parent = find(labels);
00333
00334 unsigned int i=0;
00335 if (parent) i=parent->depth()+1;
00336
00337 for (; i<pathdata.size(); ++i)
00338 {
00339 if (parent)
00340 {
00341 parent = parent->addChild(pathdata[i],scenario);
00342
00343 }
00344 else
00345 {
00346 parent = root_ = new SmiTreeNode<T>(pathdata[0]);
00347 root_->setScenario(scenario);
00348 }
00349
00350 node_data.push_back(pathdata[i]);
00351 }
00352 if (pathdata.size())
00353 {
00354 leaf_.push_back(parent);
00355 }
00356 return leaf_.size()-1;
00357
00358 }
00360
00363
00364 SmiScenarioTree<T>(): leaf_(0),root_(NULL) {}
00365
00367 virtual ~SmiScenarioTree<T>() {delete root_;}
00369
00370 private:
00371 vector<T> node_data;
00372 vector<T> scen_data;
00373 vector<SmiTreeNode<T> *> leaf_;
00374 SmiTreeNode<T> *root_;
00375 };
00376
00377
00383 void
00384 SmiScenarioTreeUnitTest();
00385
00386 #endif //SmiScenarioTree_H