##A414

def trend(f) : #f is a numerical vector
    r2 = 1.414213562370951 #square root of 2
    N = len(f)
    J = range(N//2)
    return[(f[2*j] + f[2*j+1]) / r2 for j in J]
    
def fluct(f) : #f is a numerical vector
    r2 = 1.414213562370951 #square root of 2
    N = len(f)
    J = range(N//2)
    return[(f[2*j] - f[2*j+1]) / r2 for j in J]
    
def haar(f,r=1) :
    if r==0 : return f
    if r==1 : return(trend(f) + fluct(f))
    N = len(f); m = N // 2**(r-1) #Divided as integer
    h =  haar(f,r-1); a = h[:m]
    return trend(a) + fluct(a) + h[m:] #concatenation
    
def energy(f) :
    return sum (t**2 for t in f)

##Tests
import numpy as np
import matplotlib.pyplot as plt
from math import *
pi = 3.141592653589793
x = np.arange(0,1,1/(2**9))
def func(x) : return (30*(x**2))*((1-x)**6)*np.sin(pi*5*x)

#From cdi-graphics:
def write(X,T,ha='center', va = 'center', fs='12', rot=0.0):
    return plt.text(X[0],X[1], T, horizontalalignment=ha,verticalalignment=va, fontsize=fs, rotation=rot)
def hline(a,b,h,lw=1,dash='k-'):
    x = np.arange(a,b+0.0001,b-a)
    return plt.plot(x,h+0*x,dash, lw=lw)
def vline(a,b,d,lw=1, dash='k-'):
    y = np.arange(a,b+0.0001,b-a)
    return plt.plot(d+0*y,y,dash, lw=lw)


import pylab as pl #Necessary for doing range with floats(frange)
plt.figure("30*(x^2)*((1-x)^6)*sin(5*pi*x)")

plt.subplot(2,1,1)
plt.plot(x,haar(func(x),2),'b-', lw=2)
plt.xlim(-0.01,1.)
for l in pl.frange(-0.7,0.5,0.1):
    hline(0,1.,l,0.2)
for l in pl.frange(0.,1.,0.1):
    vline(-0.7,0.5,l,0.2) 
write((0.5,0.7),'Second level Haar transformation')
write((1.0,0.),'0')
write((1.,0.5),'0.5')
write((1.,0.25),'0.25')
write((1.,-0.5),'-0.5')
write((1.,-0.25),'-0.25')
write((0.5,-0.7),'1/2')
write((0.25,-0.7),'1/4')
write((0.,-0.7),'0')
write((1.,-0.7),'1')
plt.plot([0],[0],'ko',[0],[0.25],'ko',[0],[0.5],'ko',[0],[-0.25],'ko',[0],[-0.5],'ko',[0.25],[0],'ko',[0.5],[0],'ko')
plt.plot((0.51,0.99),(-0.6,-0.6), 'k') # arrow line
plt.plot((0.51,0.51),(-0.6,-0.6), 'k', marker='<') # left arrowhead
plt.plot((0.99,0.99),(-0.6,-0.6), 'k', marker='>') # right arrowhead
plt.plot((0.26,0.49),(-0.6,-0.6), 'k')
plt.plot((0.26,0.26),(-0.6,-0.6), 'k', marker='<')
plt.plot((0.49,0.49),(-0.6,-0.6), 'k', marker='>')
plt.plot((0.01,0.24),(-0.6,-0.6), 'k')
plt.plot((0.01,0.01),(-0.6,-0.6), 'k', marker='<')
plt.plot((0.24,0.24),(-0.6,-0.6), 'k', marker='>') 
write((0.75,-0.55),'$d^1$',fs='15')
write((0.375,-0.55),'$d^2$',fs='15')
write((0.125,-0.7),'$a^2$',fs='15')
plt.axis('off')


plt.subplot(2,1,2)
plt.plot(x,haar(func(x),3),'b-', lw=2)
plt.xlim(-0.01,1.)
for l in pl.frange(-1.0,0.6,0.1):
    hline(0,1.,l,0.2)
for l in pl.frange(0.,1.,0.1):
    vline(-1.,0.6,l,0.2) 
write((0.5,0.8),'Third level Haar transformation')
write((1.0,0.),'0')
write((1.,0.6),'0.6')
write((1.,0.3),'0.3')
write((1.,-0.8),'-0.8')
write((1.,-0.4),'-0.4')
write((0.5,-1.),'1/2')
write((0.25,-1.),'1/4')
write((0.125,-1.),'1/8')
write((0.,-1.),'0')
write((1.,-1.),'1')
plt.plot([0],[0],'ko',[0],[0.3],'ko',[0],[0.6],'ko',[0],[-0.4],'ko',[0],[-0.8],'ko')
plt.plot([0.25],[0],'ko',[0.5],[0],'ko',[0.125],[0],'ko')
plt.plot((0.51,0.99),(-0.9,-0.9), 'k') # arrow line
plt.plot((0.51,0.51),(-0.9,-0.9), 'k', marker='<') # left arrowhead
plt.plot((0.99,0.99),(-0.9,-0.9), 'k', marker='>') # right arrowhead
plt.plot((0.26,0.49),(-0.9,-0.9), 'k')
plt.plot((0.26,0.26),(-0.9,-0.9), 'k', marker='<')
plt.plot((0.49,0.49),(-0.9,-0.9), 'k', marker='>')
plt.plot((0.13,0.24),(-0.9,-0.9), 'k')
plt.plot((0.13,0.13),(-0.9,-0.9), 'k', marker='<')
plt.plot((0.24,0.24),(-0.9,-0.9), 'k', marker='>')
plt.plot((0.01,0.11),(-0.9,-0.9), 'k')
plt.plot((0.01,0.01),(-0.9,-0.9), 'k', marker='<')
plt.plot((0.11,0.11),(-0.9,-0.9), 'k', marker='>') 
write((0.75,-0.84),'$d^1$',fs='15')
write((0.375,-0.84),'$d^2$',fs='15')
write((0.18,-0.84),'$d^3$',fs='15')
write((0.06,-1.03),'$a^3$',fs='15')
plt.axis('off')