#include <packtree.h>
Inheritance diagram for packtree::
Public Methods  
packtree (const double *vec, const size_t n, liftbase< packcontainer, double > *w)  
Construct a wavelet packet tree from a vector of double values. More...  
~packtree ()  
destructor does nothing. More...  
void  prCost () 
Print the wavelet packet tree cost values in breadth first order. More...  
void  prBestBasis () 
Print the wavelet packet tree, showing the nodes that have been selected by the "best basis" algorithm. More...  
void  bestBasis () 
Calculate the wavelet packet "best basis". More...  
bool  bestBasisOK () 
Return true is be best basis has been calculated properly, return false if the best basis has not been calculated or it was not calculated properly. More...  
packdata_list<double>  getBestBasisList () 
Return a list consisting of the best basis packdata values. More...  
Private Methods  
packtree (const packtree &rhs)  
disallow the copy constructor. More...  
packtree ()  
disallow the default constructor. More...  
double  bestBasisWalk (packnode< double > *root) 
Walk the wavelet packet tree and apply the "best basis" algorithm described in Chapter 8 of Ripples in Mathematics. More...  
void  buildBestBasisList (packnode< double > *root, packdata_list< double > &list) 
Traverse the tree from the top down and add the best basis nodes to the best basis list. More...  
void  checkBestBasis (packnode< double > *root) 
Recursively traverse the wavelet packet tree and check that the best basis result is correct. More...  
void  cleanTree (packnode< double > *root, bool removeMark) 
The best basis algorithm selects the nodes nearest the tree root for the best basis set. More...  
Private Attributes  
bool  foundOriginalData 
Found original data marked as part of the best basis. More...  
bool  foundBestBasisVal 
found a best basis value in the wavelet packet tree. More... 
The constructor is passed a vector of doubles, the length of the vector (which must be a power of two) and a pointer to a wavelet lifting scheme class that will be used in calculating the wavelet transform step. If the vector passed to the constructor contains N double vaues, the result of the constructor will be a wavelet packet tree with log_{2}(N) levels.
Definition at line 57 of file packtree.h.

disallow the copy constructor.
Definition at line 70 of file packtree.h. 00070 {}; 

disallow the default constructor.
Definition at line 72 of file packtree.h. 00072 {}; 

Construct a wavelet packet tree from a vector of double values. The size of the vector, which must be a power of two, is passed in N. A wavelet Lifting Scheme object is passed in w. This object is used to calculate the wavelet transform step which is applied at each level (where level > 0) of the wavelet packet tree. The first level (level 0) of the wavelet packet tree contains the original data set.
Definition at line 59 of file packtree.cpp. 00062 { 00063 waveObj = w; 00064 00065 block_pool mem_pool; 00066 double *vecCopy = (double *)mem_pool.pool_alloc( N * sizeof( double ) ); 00067 00068 for (int i = 0; i < N; i++) { 00069 vecCopy[i] = vec[i]; 00070 } 00071 00072 root = new packnode<double>( vecCopy, N, packnode<double>::OriginalData ); 00073 root>mark( true ); 00074 newLevel( root, false, false ); 00075 } // packtree 

destructor does nothing.
Definition at line 90 of file packtree.h. 00090 {} 

Calculate the wavelet packet "best basis".
Definition at line 197 of file packtree.cpp. Referenced by main().
00198 { 00199 bestBasisWalk( root ); 00200 } // bestBasis 

Return true is be best basis has been calculated properly, return false if the best basis has not been calculated or it was not calculated properly. The best basis is calculated in reference to a particular cost function. A particular cost function will not always result in a data set which differs from the original data set. If this is the case, the "best basis" result will include the original data. Definition at line 250 of file packtree.cpp. Referenced by main().
00251 { 00252 foundOriginalData = false; 00253 foundBestBasisVal = false; 00254 checkBestBasis( root ); 00255 00256 bool rslt = (foundBestBasisVal && (!foundOriginalData)); 00257 00258 return rslt; 00259 } // bestBasicOK 

Walk the wavelet packet tree and apply the "best basis" algorithm described in Chapter 8 of Ripples in Mathematics. Nodes that are "marked" become part of the best basis, which is a minimal representation of the data in terms of the cost function. Definition at line 153 of file packtree.cpp. Referenced by bestBasis().
00154 { 00155 double cost = 0.0; 00156 00157 if (top != 0) { 00158 packnode<double> *lhs = top>lhsChild(); 00159 packnode<double> *rhs = top>rhsChild(); 00160 00161 if (lhs == 0 && rhs == 0) { // we've reached a leaf 00162 cost = top>cost(); 00163 } 00164 else if (lhs != 0 && rhs != 0) { 00165 00166 double lhsCost = bestBasisWalk( lhs ); 00167 double rhsCost = bestBasisWalk( rhs ); 00168 00169 double v1 = top>cost(); 00170 double v2 = lhsCost + rhsCost; 00171 00172 if (v1 <= v2) { 00173 top>mark( true ); 00174 lhs>mark( false ); 00175 rhs>mark( false ); 00176 } 00177 else { // v1 > v2 00178 top>cost( v2 ); 00179 } 00180 cost = top>cost(); 00181 } 00182 else { 00183 // The tree does not seem to be a full binary tree 00184 // Something has gone badly wrong. 00185 assert( false ); 00186 } 00187 } 00188 00189 return cost; 00190 } // bestBasicWalk 

Traverse the tree from the top down and add the best basis nodes to the best basis list. Note that the list object is simply a package for a scalar value, the pointer to the head of the list. So it can be passed by value without incurring a cost greater than passing a pointer (e.g., pass by reference). Definition at line 271 of file packtree.cpp. Referenced by getBestBasisList().
00273 { 00274 if (top != 0) { 00275 if (top>mark()) { 00276 list.add( top ); 00277 } 00278 else { 00279 buildBestBasisList( top>lhsChild(), list ); 00280 buildBestBasisList( top>rhsChild(), list ); 00281 } 00282 } 00283 } // buildBestBasisList 

Recursively traverse the wavelet packet tree and check that the best basis result is correct. That is, that the best basis has been calculated and that it does not include the orignal data set. The best basis includes the original data set with the packnode ofr the original data set is marked. This algorithm makes use of two class global variables. There may be a purely recursive, way to do this without these global class variables, but these variables make the algorithm much easier. The variables are initialized by the calling function bestBasisOK(). Definition at line 218 of file packtree.cpp. Referenced by bestBasisOK().
00219 { 00220 if (top != 0) { 00221 if (top>mark()) { 00222 foundBestBasisVal = true; 00223 if (top>getKind() == packdata<double>::OriginalData) { 00224 foundOriginalData = true; 00225 } 00226 } 00227 if (!foundOriginalData) { 00228 checkBestBasis( top>lhsChild() ); 00229 } 00230 if (!foundOriginalData) { 00231 checkBestBasis( top>rhsChild() ); 00232 } 00233 } 00234 } // checkBestBasis 

The best basis algorithm selects the nodes nearest the tree root for the best basis set. These nodes are "marked" true with a boolean flag. The best basis algorithm outlined in Ripples in Mathematics sets any marks in nodes that are below a marked node in the tree (nodes which are in a subtree of a marked node) to false. However, this is unnecessary when the best basis set is collected, since the algorithm uses top down tree traversal and stops at marked node. A problem does arise when the entire tree is printed to show the nodes that are marked as part of the best basis set. In this case the result may appear wrong, since child nodes of a best basis node are marked. This function does a top down traversal setting the "marks" on these child nodes to false. Definition at line 98 of file packtree.cpp. Referenced by prBestBasis().
00099 { 00100 if (top != 0) { 00101 if (removeMark) { 00102 if (top>mark()) { 00103 top>mark( false ); 00104 } 00105 } 00106 else { 00107 // if a mark is found, then set all the "marks" below that 00108 // point to false (e.g., remove the marks). 00109 if (top>mark()) { 00110 removeMark = true; 00111 } 00112 } 00113 cleanTree( top>lhsChild(), removeMark ); 00114 cleanTree( top>rhsChild(), removeMark ); 00115 } 00116 } // cleanTree 

Return a list consisting of the best basis packdata values.
Definition at line 291 of file packtree.cpp. Referenced by main().
00292 { 00293 packdata_list<double> list; 00294 00295 buildBestBasisList( root, list ); 00296 return list; 00297 } // getBestBasisList 

Print the wavelet packet tree, showing the nodes that have been selected by the "best basis" algorithm.
Definition at line 136 of file packtree.cpp. Referenced by main().
00137 { 00138 if (root != 0) { 00139 cleanTree( root, false ); 00140 breadthFirstPrint(printBestBasis); 00141 } 00142 } // prBestBasis 

Print the wavelet packet tree cost values in breadth first order.
Definition at line 124 of file packtree.cpp. Referenced by main().
00125 { 00126 if (root != 0) { 00127 breadthFirstPrint(printCost); 00128 } 00129 } 

found a best basis value in the wavelet packet tree.
Definition at line 66 of file packtree.h. 

Found original data marked as part of the best basis. This means that the best basis function failed (or that the original data is the most compact representation relative to the cost function used). Definition at line 64 of file packtree.h. 