#include <math.h>

int haar(double * X, int n, int l, int skip = 1)
{
    static double isqrt2 = 1.0 / (sqrt(2.0));
    int ret = 0;
    if(l > 0)
    {
        if(n%2 == 0)
        {
            double * d = new double[n/2];
            double * s = new double[n/2];
            for(int i = 0; i < n/2; i++)
            {
                s[i] = X[2*i*skip] + X[(2*i+1)*skip];
                d[i] = X[2*i*skip] - X[(2*i+1)*skip];
            }

            if(haar(s,n/2,l-1) == 0)
            {
                for(int i = 0; i < n/2; i++)
                {
                    X[i*skip] = s[i]*isqrt2;
                    X[(n/2 + i)*skip] = d[i]*isqrt2;
                }
            }
            else
            {
                ret = -1;
            }
            
            delete d;
            delete s;
        }
        else
        {
            ret = -1;
        }
    }
    return ret;
}


int ihaar(double * X, int n, int l, int skip = 1)
{
    static double s2 = sqrt(2.0) / 2.0;
    int ret = 0;
    if(l > 0)
    {
        if(n%2 == 0)
        {
            double * d = new double[n/2];
            double * s = new double[n/2];

            for(int i = 0; i < n/2; i++)
            {
                s[i] = X[i*skip];
            }

            if(ihaar(s,n/2,l-1) == 0)
            {
                for(int i = 0; i < n/2; i++)
                {
                    d[i] = X[(i+n/2)*skip];
                }
                
                for(int i = 0; i < n/2; i++)
                {
                    X[2*i*skip] = (s[i] + d[i])*s2;
                    X[(2*i+1)*skip] = (s[i] - d[i])*s2;
                }
            }
            else
            {
                ret = -1;
            }
            
            delete d;
            delete s;
        }
        else
        {
            ret = -1;
        }
    }
    return ret;
}

int haar2(double * X, int n, int m, int l)
{
    int ret = 0;

    for(int row = 0; (row < n) && (ret == 0); row++)
    {
        ret = haar(X+row*m, m, l);
    }

    for(int col = 0; (col < m) && (ret == 0); col++)
    {
        ret = haar(X+col, n, l, m);
    }
    
    return ret;
}

int ihaar2(double * X, int n, int m, int l)
{
    int ret = 0;

    for(int col = 0; (col < m) && (ret == 0); col++)
    {
        ret = ihaar(X+col, n, l, m);
    }

    for(int row = 0; (row < n) && (ret == 0); row++)
    {
        ret = ihaar(X+row*m, m, l);
    }
    
    return ret;
}