Haar Filter, Reversible Discrete Wavelet Transform

haar.py

import math
import sys

'''
python haar.py
python haar.py 1 5 3 1

'''

def wrap(value, ubound):
    return (value+ubound) % ubound

def encode(lst, ubound):
    deltas = []
    lst = list(lst)

    while len(lst) >= 2:
        avgs = []

        while lst:
            a, b = lst.pop(0), lst.pop(0)
            
            avg = (a+b)/2 if a<=b else (a+b+ubound)/2
            delta = wrap(b-a, ubound)
                
            avgs.append(avg)
            deltas.append(delta)
                
        lst = avgs
    return deltas, avg%ubound

def decode(deltas, avg, ubound):
    avgs = [avg]
    l = 1

    ceil = lambda v: int(math.ceil(v))

    while deltas:
        for i in range(l):
            delta, avg = deltas.pop(), avgs.pop()

            a = wrap(ceil(avg - delta/2.0), ubound)
            b = wrap(ceil(avg + delta/2.0), ubound)

            avgs[0:0] = [a, b]

        l*=2
    return avgs

def is_pow2(n):
    return (n & (n-1) == 0) and (n != 0)

if __name__ == "__main__":
    user_input = map(int, sys.argv[1:])
    
    if user_input:
        length = len(user_input)

        if not (is_pow2(length) and length >= 2):
            print "List length should be a power of 2, and larger than 2"
            sys.exit(1)

        samples = [user_input]
    else:
        samples = [
            [1,4],
            [6,1],
            [0,2,4,6,7,7,7,7],
            [1,2,3,4],
            [7,5,1,6,3,0,2,4],
            [3,2,3,7,5,5,1,1,0,2,5,1,2,0,1,2,0,2,1,0,0,2,1,2,0,2,1,0,0,2,1,2],
        ]

    for sample in samples:
        ubound = max(sample)+1
        length = len(sample)
        deltas, avg = encode(sample, ubound)

        print "Input:      %s, boundary = %s, length = %s" % (sample, ubound, length)
        print "Haar output:%s, average = %s" % (deltas, avg)
        print "Decoded:    %s" % decode(deltas, avg, ubound)
        print