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

packtree_int.cpp

Go to the documentation of this file.
00001 
00033 #include <assert.h>
00034 #include <stdio.h>
00035 
00036 #include "packcontainer_int.h"
00037 #include "packtree_int.h"
00038 
00039 
00058 packtree_int::packtree_int( const int *vec, 
00059                             const size_t N, 
00060                             liftbase<packcontainer_int, int> *w )
00061 {
00062   waveObj = w;
00063 
00064   block_pool mem_pool;
00065   int *vecCopy = (int *)mem_pool.pool_alloc( N * sizeof( int ) );
00066 
00067   for (int i = 0; i < N; i++) {
00068     vecCopy[i] = vec[i];
00069   }
00070 
00071   root = new packnode<int>( vecCopy, N, packnode<int>::OriginalData );
00072   root->mark( true );
00073   newLevel( root, false, false ); 
00074 } // packtree_int
00075 
00076 
00077 
00097 void packtree_int::cleanTree(packnode<int> *top, bool removeMark )
00098 {
00099   if (top != 0) {
00100     if (removeMark) {
00101       if (top->mark()) {
00102         top->mark( false );
00103       }
00104     }
00105     else {
00106       // if a mark is found, then set all the "marks" below that
00107       // point to false (e.g., remove the marks).
00108       if (top->mark()) {
00109         removeMark = true;
00110       }
00111     }
00112     cleanTree( top->lhsChild(), removeMark );
00113     cleanTree( top->rhsChild(), removeMark );
00114   }
00115 } // cleanTree
00116 
00117 
00118 
00123 void packtree_int::prCost()
00124 {
00125   if (root != 0) {
00126     breadthFirstPrint(printCost);
00127   }
00128 }
00129 
00130 
00135 void packtree_int::prBestBasis()
00136 {
00137   if (root != 0) {
00138     cleanTree( root, false );
00139     breadthFirstPrint(printBestBasis);
00140   }
00141 } // prBestBasis
00142 
00143 
00152 int packtree_int::bestBasisWalk( packnode<int> *top )
00153 {
00154   int cost = 0;
00155 
00156   if (top != 0) {
00157     packnode<int> *lhs = top->lhsChild();
00158     packnode<int> *rhs = top->rhsChild();
00159 
00160     if (lhs == 0 && rhs == 0) { // we've reached a leaf
00161       cost = top->cost();
00162     }
00163     else if (lhs != 0 && rhs != 0) {
00164 
00165       int lhsCost = bestBasisWalk( lhs );
00166       int rhsCost = bestBasisWalk( rhs );
00167 
00168       int v1 = top->cost();
00169       int v2 = lhsCost + rhsCost;
00170 
00171       if (v1 <= v2) {
00172         top->mark( true );
00173         lhs->mark( false );
00174         rhs->mark( false );
00175       }
00176       else { // v1 > v2
00177         top->cost( v2 );
00178       }
00179       cost = top->cost();
00180     }
00181     else {
00182       // The tree does not seem to be a full binary tree
00183       // Something has gone badly wrong.
00184       assert( false );
00185     }
00186   }
00187 
00188   return cost;
00189 } // bestBasicWalk
00190 
00191 
00196 void packtree_int::bestBasis()
00197 {
00198   bestBasisWalk( root );
00199 } // bestBasis
00200 
00201 
00217 void packtree_int::checkBestBasis( packnode<int> *top )
00218 {
00219   if (top != 0) {
00220     if (top->mark()) {
00221       foundBestBasisVal = true;
00222       if (top->getKind() == packdata<int>::OriginalData) {
00223         foundOriginalData = true;
00224       }
00225     }
00226     if (!foundOriginalData) {
00227       checkBestBasis( top->lhsChild() );
00228     }
00229     if (!foundOriginalData) {
00230       checkBestBasis( top->rhsChild() );
00231     }
00232   }
00233 }  // checkBestBasis
00234 
00235 
00236 
00249 bool packtree_int::bestBasisOK()
00250 {
00251   foundOriginalData = false;
00252   foundBestBasisVal = false;
00253   checkBestBasis( root );
00254 
00255   bool rslt = (foundBestBasisVal && (!foundOriginalData));
00256 
00257   return rslt;
00258 } // bestBasicOK
00259 
00260 
00270 void packtree_int::buildBestBasisList( packnode<int> *top, 
00271                                        packdata_list<int> &list )
00272 {
00273   if (top != 0) {
00274     if (top->mark()) {
00275       list.add( top );
00276     }
00277     else {
00278       buildBestBasisList( top->lhsChild(), list );
00279       buildBestBasisList( top->rhsChild(), list );
00280     }
00281   }
00282 } // buildBestBasisList
00283 
00284 
00285 
00290 packdata_list<int> packtree_int::getBestBasisList()
00291 {
00292   packdata_list<int> list;
00293 
00294   buildBestBasisList( root, list );
00295   return list;
00296 } // 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