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

packtree_base_int Class Reference

This is an integer version of the wavelet packet tree base class. More...

#include <packtree_base_int.h>

Inheritance diagram for packtree_base_int::

packtree_int List of all members.

Public Methods

void pr ()
 Print the wavelet packet tree data and wavelet transform result to standard out. More...

packnode<int>* getRoot ()
 get the root of the wavelet packet tree. More...

Protected Types

enum  printKind { BadPrintKind, printData, printCost, printBestBasis }

Protected Methods

void breadthFirstPrint (printKind kind)
 Print the wavelet packet tree, breadth first (this is also sometimes called a level traversal). More...

void newLevel (packnode< int > *top, bool freqCalc, bool reverse)
 Add a new level to the wavelet packet tree. More...

Protected Attributes

packnode<int>* root
 root of the wavelet packet tree. More...

 wavelet packet transform object. More...

Detailed Description

This is an integer version of the wavelet packet tree base class.

This class can be used for both compression and time/frequency analysis of an integer time series. However, this version was developed for lossless integer compression.

This class may be subclassed for classes that apply the wavelet best basis algorithm or for time/frequency wavelet packet trees.

Definition at line 55 of file packtree_base_int.h.

Member Enumeration Documentation

enum packtree_base_int::printKind [protected]

Enumeration values:

Definition at line 63 of file packtree_base_int.h.

00063                { BadPrintKind, 
00064                  printData, 
00065                  printCost, 
00066                  printBestBasis } printKind;

Member Function Documentation

void packtree_base_int::breadthFirstPrint ( printKind kind ) [protected]

Print the wavelet packet tree, breadth first (this is also sometimes called a level traversal).

The breadth first traversal uses a queue. The root of the tree is initially inserted into the queue. The function operates by deleting the node at teh front of the queue, printing the data associated with that node and adding the node's left and right children to the queue. Since a node's children are at the next lower level, and we add the left child before the right child, the function prints a tree level from left to right.

The above paragraph paraphrases Chapter 5, Level Order Traversal of Fundamentals of Data Structures in C by Horowitz, Sahni and Anderson-Freed, 1993.

Definition at line 129 of file packtree_base_int.cpp.

Referenced by pr(), packtree_int::prBestBasis(), and packtree_int::prCost().

00130 {
00131   queue<int> Q;
00133   Q.addQueue( root, 0 );
00134   while (! Q.queueEmpty() ) {
00135     packnode<int> *node = Q.queueStart()->node;
00136     size_t indent = Q.queueStart()->indent;
00137     Q.deleteStart();
00139     if (indent > 0) {
00140       // print 'indent' spaces
00141       printf("%*c", indent, ' ');
00142     }
00144     switch (kind) {
00145     case printData: node->pr();
00146       break;
00147     case printCost: node->prCost();
00148       break;
00149     case printBestBasis: node->prBestBasis();
00150       break;
00151     default:
00152       assert( false );
00153       break;
00154     } // switch
00156     packnode<int> *lhs = node->lhsChild();
00157     packnode<int> *rhs = node->rhsChild();
00159     if (lhs != 0) {
00160       Q.addQueue( lhs, indent + 2 );
00161     }
00162     if (rhs != 0) {
00163       Q.addQueue( rhs, indent + 2 );
00164     }
00165   }
00166 } // packtree_base_int::breadthFirstPrint

packnode< int > * packtree_base_int::getRoot ( ) [inline]

get the root of the wavelet packet tree.

Definition at line 75 of file packtree_base_int.h.

Referenced by packet_calc().

00075 { return root; }

void packtree_base_int::newLevel ( packnode< int > * top,
bool freqCalc,
bool reverse ) [protected]

Add a new level to the wavelet packet tree.

Wavelet packet trees are data structures that support a variety of applications.

If the reverse argument is true, the locations of the high pass and low pass filter results in the wavelet calculation will be reversed. This is used in building a wavelet packet tree for frequency analysis.

The top packnode object contains data from the previous level. If this is the first level in the tree, top will contain the input data set.

A packcontainer_int object is created with the top data. The packcontainer_int constructor will allocate new storage and copy the data into this storage. If the packcontainer_int object consists of N elements, then there will be N/2 elements on the left and N/2 or the right. The object allows the lhs and rhs data to be accessed as one array.

A wavelet transform step is calculated on the N element data set. This results in N/2 values from the wavelet scaling function (low pass function) and N/2 values from the wavelet function (high pass function). These values are used to create two new packnode objects which become children of top. Sub-trees for the new packnode objects are recursively calculated.

As the tree is constructed, the leaves of the tree are marked with a boolean flag in preparation for calculating the "best basis" representation for the data. See the algorithm outlined in section 8.2.2 of "Ripples in Mathematics" by Jensen and la Cour-Harbo

The wavelet packet tree form that is used for wavelet packet frequency analysis is described in section 9.3 (figure 9.14) ofg "Ripples in Mathematics".

Definition at line 47 of file packtree_base_int.cpp.

Referenced by packtree_int::packtree_int().

00050 {
00051   if (top != 0) {
00052     const size_t len = top->length();
00053     if (len > 1) {
00054       // Create a new wavelet packet container for use in
00055       // calculating the wavelet transform.  Note that the
00056       // container is only used locally.
00057       packcontainer_int container( top );
00059       if (reverse) {
00060         // Calculate the reverse foward wavelet transform step, 
00061         // where the high pass result is stored in the upper half
00062         // of the container and the low pass result is stored
00063         // in the lower half of the container.
00064         waveObj->forwardStepRev( container, len );
00065       }
00066       else {
00067         // Calculate the foward wavelet transform step, where
00068         // the high pass result is stored in the upper half
00069         // of the container and the low pass result is stored
00070         // in the lower half of the container.
00071         waveObj->forwardStep( container, len );
00072       }
00074       packnode<int> *lhs = new packnode<int>(container.lhsData(), 
00075                                                    len/2,
00076                                                    packnode<int>::LowPass );
00077       packnode<int> *rhs = new packnode<int>(container.rhsData(), 
00078                                                    len/2,
00079                                                    packnode<int>::HighPass );
00081       // set the "mark" in the top node to false and
00082       // mark the two children to true.
00083       top->mark( false );
00084       lhs->mark( true );
00085       rhs->mark( true );
00087       top->lhsChild( lhs );
00088       top->rhsChild( rhs );
00090       // The transform on the left hand side always uses
00091       // the standard order (e.g., low pass filter result
00092       // goes in the lower half, high pass goes in the
00093       // upper half of the container).
00094       newLevel( lhs, freqCalc, false );
00096       if (freqCalc) {
00097         // wavelet packet frequency analysis reverses the
00098         // storage locations for the filter results in the
00099         // right hand child
00100         newLevel( rhs, freqCalc, true );
00101       }
00102       else { // freq == false
00103         // use standard filter location
00104         newLevel( rhs, freqCalc, false );
00105       }
00106     }
00107   }
00108 } // newLevel

void packtree_base_int::pr ( )

Print the wavelet packet tree data and wavelet transform result to standard out.

Definition at line 175 of file packtree_base_int.cpp.

00176 {
00177   if (root != 0) {
00178     breadthFirstPrint(printData);
00179   }
00180 } // pr

Member Data Documentation

packnode< int > * packtree_base_int::root [protected]

root of the wavelet packet tree.

Definition at line 58 of file packtree_base_int.h.

liftbase< packcontainer_int, int > * packtree_base_int::waveObj [protected]

wavelet packet transform object.

Definition at line 61 of file packtree_base_int.h.

The documentation for this class was generated from the following files:
Generated at Sat Aug 10 13:23:39 2002 for Wavelet Packet Transform and Lossless Compression by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001