#include <packtree_base_int.h>
Inheritance diagram for packtree_base_int::
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... | |
| liftbase<packcontainer_int, int>* | waveObj |
| wavelet packet transform object. More... | |
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.
|
|
Definition at line 63 of file packtree_base_int.h. 00063 { BadPrintKind,
00064 printData,
00065 printCost,
00066 printBestBasis } printKind;
|
|
|
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;
00132
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();
00138
00139 if (indent > 0) {
00140 // print 'indent' spaces
00141 printf("%*c", indent, ' ');
00142 }
00143
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
00155
00156 packnode<int> *lhs = node->lhsChild();
00157 packnode<int> *rhs = node->rhsChild();
00158
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
|
|
|
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; }
|
|
|
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 );
00058
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 }
00073
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 );
00080
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 );
00086
00087 top->lhsChild( lhs );
00088 top->rhsChild( rhs );
00089
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 );
00095
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
|
|
|
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
|
|
|
root of the wavelet packet tree.
Definition at line 58 of file packtree_base_int.h. |
|
|
wavelet packet transform object.
Definition at line 61 of file packtree_base_int.h. |
1.2.8.1 written by Dimitri van Heesch,
© 1997-2001