00001
00002 #ifndef _LIFTBASE_H_
00003 #define _LIFTBASE_H_
00004
00030
00031 #include <assert.h>
00032
00154 template <class T, class T_elem >
00155 class liftbase {
00156
00157 protected:
00158
00159 typedef enum {
00161 forward = 1,
00163 inverse = 2
00164 } transDirection;
00165
00166
00173 void split( T& vec, int N )
00174 {
00175
00176 int start = 1;
00177 int end = N - 1;
00178
00179 while (start < end) {
00180 for (int i = start; i < end; i = i + 2) {
00181 T_elem tmp = vec[i];
00182 vec[i] = vec[i+1];
00183 vec[i+1] = tmp;
00184 }
00185 start = start + 1;
00186 end = end - 1;
00187 }
00188 }
00189
00198 void merge( T& vec, int N )
00199 {
00200 int half = N >> 1;
00201 int start = half-1;
00202 int end = half;
00203
00204 while (start > 0) {
00205 for (int i = start; i < end; i = i + 2) {
00206 T_elem tmp = vec[i];
00207 vec[i] = vec[i+1];
00208 vec[i+1] = tmp;
00209 }
00210 start = start - 1;
00211 end = end + 1;
00212 }
00213 }
00214
00215
00224 virtual void predict( T& vec, int N, transDirection direction ) = 0;
00225
00238 virtual void predictRev( T& vec, int N, transDirection direction ) {};
00239
00240
00249 virtual void update( T& vec, int N, transDirection direction ) = 0;
00250
00251
00255 virtual void updateRev( T& vec, int N, transDirection direction ) {}
00256
00257 public:
00258
00262 virtual void forwardStep( T& vec, const int n )
00263 {
00264 split( vec, n );
00265 predict( vec, n, forward );
00266 update( vec, n, forward );
00267 }
00268
00278 virtual void forwardStepRev( T& vec, const int N )
00279 {
00280 assert(false);
00281 }
00282
00297 virtual void forwardTrans( T& vec, const int N )
00298 {
00299
00300 for (int n = N; n > 1; n = n >> 1) {
00301 forwardStep( vec, n );
00302 }
00303 }
00304
00305
00309 virtual void inverseStep( T& vec, const int n )
00310 {
00311 update( vec, n, inverse );
00312 predict( vec, n, inverse );
00313 merge( vec, n );
00314 }
00315
00324 virtual void inverseStepRev( T& vec, const int n )
00325 {
00326 assert( false );
00327 }
00328
00329
00339 virtual void inverseTrans( T& vec, const int N )
00340 {
00341
00342 for (int n = 2; n <= N; n = n << 1) {
00343 inverseStep( vec, n );
00344 }
00345 }
00346
00347
00348 };
00349
00350 #endif