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()
00131 {
00132 delete sibling_;
00133 delete child_;
00134
00135 }
00136
00138
00139 protected:
00140
00141 void setChild (SmiTreeNode<T> *c) {child_ = c;}
00142 void setSibling(SmiTreeNode<T> *s) {sibling_ = s;}
00143 SmiTreeNode<T> *getParentP() { return parent_; }
00144 SmiTreeNode<T> *getChildP() { return child_; }
00145 SmiTreeNode<T> *getSiblingP(){ return sibling_;}
00146
00147
00148 private:
00149 SmiTreeNode<T> *parent_;
00150 SmiTreeNode<T> *child_;
00151 SmiTreeNode<T> *sibling_;
00152 int scen_;
00153 int nchild_;
00154 int depth_;
00155 T ptr_;
00156 child_label_map child_labels_;
00157
00158 };
00159
00160
00166 void
00167 SmiTreeNodeUnitTest();
00168
00169
00170 template<class T>
00171 class SmiScenarioTree {
00172
00173 public:
00174
00175
00178
00179
00181 typename vector<T>::iterator treeBegin(){ return node_data.begin(); }
00183 typename vector<T>::iterator treeEnd(){ return node_data.end();}
00185 vector<T> &wholeTree(){ return node_data;}
00186
00190 typename vector<T>::iterator scenBegin(int s){
00191 getScenario(s);
00192 return scen_data.begin();
00193 }
00194
00195 typename vector<T>::iterator scenEnd(int s){
00196 getScenario(s);
00197 return scen_data.begin()+leaf_[s]->depth()+1;
00198 }
00199
00200
00201
00202
00203
00206
00208 SmiTreeNode<T> *getRoot() { return root_; }
00209
00211 SmiTreeNode<T> *getLeaf(int scn) { return leaf_[scn];}
00212
00214 SmiTreeNode<T> *find(unsigned int scenario, int stage)
00215 {
00216 assert (scenario < leaf_.size());
00217 SmiTreeNode<T> * n = leaf_[scenario];
00218 assert (stage < n->depth() + 1);
00219 while (stage < n->depth())
00220 n = n->getParent();
00221 return n;
00222 }
00223
00225 int getNumScenarios()
00226 {
00227 return (int) leaf_.size();
00228 }
00229
00230
00232 SmiTreeNode<T> *find(vector<int> &label)
00233 {
00234 assert(label.size()>0);
00235 SmiTreeNode<T> *n = root_,*next;
00236 unsigned int i=0;
00237 while ((i<label.size()) && (next=n->getChildByLabel(label[i])))
00238 {
00239 ++i;
00240 n=next;
00241 }
00242 return n;
00243 }
00244
00245
00247 vector<T> &getScenario(int scenario)
00248 {
00249 assert (scenario < (int) leaf_.size());
00250 SmiTreeNode<T> * n = leaf_[scenario];
00251
00252
00253
00254 int ns=n->depth()+1-scen_data.size();
00255 for (int j=0; j<ns;j++)
00256 scen_data.push_back(n->getDataPtr());
00257
00258 int i=n->depth()+1;
00259 while(i>0)
00260 {
00261 scen_data[--i] = n->getDataPtr();
00262 n = n->getParent();
00263 }
00264 return scen_data;
00265 }
00266
00267
00269
00270
00280 int addPathtoLeaf(int brscenario, int stage, vector<T> &pathdata, unsigned int start=0)
00281 {
00282 SmiTreeNode<T> *parent = NULL;
00283 int scenario=leaf_.size();
00284 if (scenario)
00285 parent = find(brscenario,stage);
00286
00287
00288 for (unsigned int i=start; i<pathdata.size(); ++i)
00289 {
00290 if (parent)
00291 {
00292 parent = parent->addChild(pathdata[i],scenario);
00293 }
00294 else
00295 {
00296 parent = root_ = new SmiTreeNode<T>(pathdata[0]);
00297 root_->setScenario(scenario);
00298 }
00299
00300 node_data.push_back(pathdata[i]);
00301 }
00302 if (pathdata.size())
00303 {
00304 leaf_.push_back(parent);
00305 }
00306 return leaf_.size()-1;
00307
00308 }
00309
00311 void setChildLabels(SmiTreeNode<T> *n, vector<int> labels)
00312 {
00313 int t = n->depth();
00314 while(n->hasChild())
00315 {
00316 n->setLastChildLabel(labels[++t]);
00317 n = n->getChild();
00318 }
00319 }
00320
00321
00328 int addPathtoLeaf(vector<int>labels, vector<T> &pathdata)
00329 {
00330 SmiTreeNode<T> *parent = NULL;
00331 int scenario=leaf_.size();
00332 if (scenario)
00333 parent = find(labels);
00334
00335 unsigned int i=0;
00336 if (parent) i=parent->depth()+1;
00337
00338 for (; i<pathdata.size(); ++i)
00339 {
00340 if (parent)
00341 {
00342 parent = parent->addChild(pathdata[i],scenario);
00343
00344 }
00345 else
00346 {
00347 parent = root_ = new SmiTreeNode<T>(pathdata[0]);
00348 root_->setScenario(scenario);
00349 }
00350
00351 node_data.push_back(pathdata[i]);
00352 }
00353 if (pathdata.size())
00354 {
00355 leaf_.push_back(parent);
00356 }
00357 return leaf_.size()-1;
00358
00359 }
00361
00364
00365 SmiScenarioTree<T>(): leaf_(0),root_(NULL) {}
00366
00368 virtual ~SmiScenarioTree<T>() {delete root_;}
00370
00371 private:
00372 vector<T> node_data;
00373 vector<T> scen_data;
00374 vector<SmiTreeNode<T> *> leaf_;
00375 SmiTreeNode<T> *root_;
00376 };
00377
00378
00384 void
00385 SmiScenarioTreeUnitTest();
00386
00387 #endif //SmiScenarioTree_H