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