#----------------------------------------- Python Code for the Streaming Min-Max Filter -------------------------------------

#
# Streaming Min-Max Filter
#
# Implemented from the paper
# "Streaming Maximum and Minimum Filter using no more than three comparisons per
# element", Daniel Lemire (arXiv:cs/0610046v5)
#
#   Daniel Lemire, Streaming Maximum-Minimum Filter Using No More than
#   Three Comparisons per Element. Nordic Journal of Computing, 13 (4),
#   pages 328-339, 2006.
#
# Extensions to the cited algorithm:
# - check for empty deque's in while statements
# - centered output for odd size filters
# - same size result (appends at front end end of signal stream)
#
# Rein van den Boomgaard
#
from collections import deque
from numpy import *
from numpy.random import randn
from matplotlib.pylab import *

def streamingMinMax( a, w ):
    # w should be odd
    U = deque()
    L = deque()
    U.append(0)
    L.append(0)
    maxlist = 0*a
    minlist = 0*a

    for i in range (1,len(a)):
        if i-w/2>0:
            maxlist[i-w/2-1] = a[U[0]]
            minlist[i-w/2-1] = a[L[0]]
       
        if a[i]>a[i-1]:
            U.pop()
            while len(U)>0 and a[i]>a[U[-1]]: #U[-1] is the end of U
                U.pop()
        else:
            L.pop()
            while len(L)>0 and a[i]<a[L[-1]]:
                L.pop()
        U.append(i)
        L.append(i)
        if i==w+U[0]:
            U.popleft()
        elif i==w+L[0]:
            L.popleft()
           
    for i in range (len(a),len(a)+w/2+1):
        maxlist[i-w/2-1] = a[U[0]]
        minlist[i-w/2-1] = a[L[0]]
        U.append(i)
        L.append(i)
        if i==w+U[0]:
            U.popleft()
        elif i==w+L[0]:
            L.popleft()

    return (maxlist, minlist)




x = linspace(0, 2*3.14, 200)
a = sin(x)*cos(2*x) + .3*randn(len(x))
   
print a

W=11
mx, mn = streamingMinMax(a, W)
mxmx,mnmx = streamingMinMax(mx, W)
mxmn,mnmn = streamingMinMax(mn, W)


plot(x,a,'-b', x, mn, '-r', x, mx, '-r', x, mnmx, '-c', x, mxmn, '-c' )



show()