Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

packtree.cpp

Go to the documentation of this file.
00001 
00033 
00034 #include <assert.h>
00035 #include <stdio.h>
00036 
00037 #include "packcontainer.h"
00038 #include "packtree.h"
00039 
00040 
00059 packtree::packtree( const double *vec, 
00060                     const size_t N, 
00061                     liftbase<packcontainer, double> *w )
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
00076 
00077 
00078 
00098 void packtree::cleanTree(packnode<double> *top, bool removeMark )
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
00117 
00118 
00119 
00124 void packtree::prCost()
00125 {
00126   if (root != 0) {
00127     breadthFirstPrint(printCost);
00128   }
00129 }
00130 
00131 
00136 void packtree::prBestBasis()
00137 {
00138   if (root != 0) {
00139     cleanTree( root, false );
00140     breadthFirstPrint(printBestBasis);
00141   }
00142 } // prBestBasis
00143 
00144 
00153 double packtree::bestBasisWalk( packnode<double> *top )
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
00191 
00192 
00197 void packtree::bestBasis()
00198 {
00199   bestBasisWalk( root );
00200 } // bestBasis
00201 
00202 
00218 void packtree::checkBestBasis( packnode<double> *top )
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
00235 
00236 
00237 
00250 bool packtree::bestBasisOK()
00251 {
00252   foundOriginalData = false;
00253   foundBestBasisVal = false;
00254   checkBestBasis( root );
00255 
00256   bool rslt = (foundBestBasisVal && (!foundOriginalData));
00257 
00258   return rslt;
00259 } // bestBasicOK
00260 
00261 
00271 void packtree::buildBestBasisList( packnode<double> *top, 
00272                                    packdata_list<double> &list )
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
00284 
00285 
00286 
00291 packdata_list<double> packtree::getBestBasisList()
00292 {
00293   packdata_list<double> list;
00294 
00295   buildBestBasisList( root, list );
00296   return list;
00297 } // getBestBasisList

Generated at Sat Aug 10 13:23:34 2002 for Wavelet Packet Transform and Lossless Compression by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001