00001
00002
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
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
00061
00062
00063
00064
00065
00066
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
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
00191
00192
00193
00194
00195 template<class T>
00196 class SmiScenarioTree {
00197
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
00294
00295
00296
00297
00298
00299
00300
00301 int i = n->depth() + 1;
00302 scen_data.resize(i,n->getDataPtr());
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
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