1 #ifndef _FORESTSZ_H 2 #define _FORESTSZ_H 3 4 #include <cassert> 5 #include <iostream> 6 #include "misc.h" 7 8 9 10 template <class L> 11 class ForestSZ { 12 protected: 13 unsigned int size_; 14 unsigned int *lml_; // postorder index of leftmost leaf descandant of the subtree rootet at T[i] 15 L *lb_; // labels of nodes in postorder 16 bool *keyroot_; // is node a keyroot 17 18 void calcKeyroots(); 19 20 public: 21 typedef unsigned int size_type; 22 typedef L label_type; 23 ForestSZ()24 ForestSZ() : size_(0), lml_(NULL), lb_(NULL),keyroot_(NULL) {}; 25 ForestSZ(unsigned int nrOfNodes); 26 ForestSZ(const ForestSZ<L> &f); 27 ~ForestSZ(); 28 size()29 inline size_type size() const { 30 return size_; 31 }; lml(unsigned long i)32 inline unsigned int lml(unsigned long i) const { 33 return lml_[i]; 34 }; label(unsigned long i)35 inline L label(unsigned long i) const { 36 return lb_[i]; 37 }; keyroot(unsigned long i)38 inline bool keyroot(unsigned long i) const { 39 return keyroot_[i]; 40 }; 41 numKeyroots()42 unsigned int numKeyroots() const { 43 unsigned int count=0; 44 for (unsigned int i=0; i<size_; i++) { 45 if (keyroot_[i]) 46 count++; 47 } 48 return count; 49 } 50 printParameters(const std::string & name)51 void printParameters(const std::string &name) const { 52 std::cout << name.c_str() << "# size: " << size() << std::endl; 53 std::cout << name.c_str() << "# keyroots: " << numKeyroots() << std::endl; 54 } 55 }; 56 57 #endif 58 59