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 }
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
00108
00109 if (top->mark()) {
00110 removeMark = true;
00111 }
00112 }
00113 cleanTree( top->lhsChild(), removeMark );
00114 cleanTree( top->rhsChild(), removeMark );
00115 }
00116 }
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 }
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) {
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 {
00178 top->cost( v2 );
00179 }
00180 cost = top->cost();
00181 }
00182 else {
00183
00184
00185 assert( false );
00186 }
00187 }
00188
00189 return cost;
00190 }
00191
00192
00197 void packtree::bestBasis()
00198 {
00199 bestBasisWalk( root );
00200 }
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 }
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 }
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 }
00284
00285
00286
00291 packdata_list<double> packtree::getBestBasisList()
00292 {
00293 packdata_list<double> list;
00294
00295 buildBestBasisList( root, list );
00296 return list;
00297 }