/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package windowopt;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;

/**
 *
 * @author Serafino
 */
public class Main {


    public static void printMatrix(int [][] A){
        for (int i = 0; i < A.length; i++)
        {
            for (int j = 0; j < A[0].length; j++)
            {
                System.out.print(A[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static void simpleWindowing(int [][] mat, int rad){
        int cols = mat[0].length;
        int rows = mat.length;
        int i, j;
        int h = 0;
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; j++)
            {
                h = 0;
                
                for (int ry =- rad; ry <= rad; ry++)
                {
                    int y = i + ry;

                    if (y >= 0 && y < rows)
                    {
                        for (int rx =- rad; rx <= rad; rx++)
                        {
                            int x = j + rx;

                            if (x >= 0 && x < cols)
                            {
                                
                                h += mat[y][x];
                            }
                        }

                    }
                }
            }
        }
    }

    public static void opt1Windowing(int [][] mat, int rad){
        int i, j = 0, h, y, col;
        int cols = mat[0].length;
        int rows = mat.length;

        ArrayDeque<Integer> q = null;

        for (i = 0; i < rows; ++i)
        {

            q = new ArrayDeque<Integer>();
            h = 0;

            for (int rx = 0; rx <= rad; rx++)
            {
                if (rx < cols)
                {

                    int mem = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            mem += mat[y][rx];

                        }
                    }
                    q.addLast(mem);
                    h += mem;
                }
            }
            j = 0;

            for (j = 1; j < cols; j++)
            {

                col = j + rad;
                if (j - rad > 0)
                {
                    h -= q.peekFirst();
                    q.pop();
                }
                if (j + rad < cols)
                {
                    int mem = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            mem += mat[y][col];
                        }
                    }
                    q.addLast(mem);
                    h += mem;
                }
            }
        }
    }

    public static void opt2Windowing(int [][] mat, int rad){
        int cols = mat[0].length;
        int rows = mat.length;

        int i = 0;
        int j = 0;
        int h = 0;
        int hh = 0;
        ArrayList<int []> M = new ArrayList<int []>();
        for (int ry = 0; ry <= rad; ry++)
        {
            if (ry < rows)
            {
                int [] q = new int [rad + 1];
                M.add(q);
                for (int rx = 0; rx <= rad; rx++)
                {
                    if (rx < cols)
                    {
                        int val = mat[ry][rx];
                        q[rx] = val;
                        h += val;
                    }
                }
            }
        }
        int firstSize = M.get(0).length;
        int mSize = M.size();
        ArrayList<Integer> C = new ArrayList<Integer>(2*rad + 1);
        ArrayList<Integer> Q = null;
        ArrayList<Integer> R = new ArrayList<Integer>(rows);

        for (int k = 0; k < firstSize; k++)
        {
            C.add(k, 0);
        }
        for (int k = 0; k < mSize; k++)
        {
            R.add(k, 0);
        }

        ListIterator<int []> mit;
        ListIterator<Integer> rit;
        ListIterator<Integer> cit;

        for (mit = M.listIterator(), rit = R.listIterator(); mit.hasNext();)
        {
            
            Integer r = rit.next();
            int rsum = 0, u;
            int [] prow = mit.next();
            for (cit = C.listIterator(), u = 0;
                cit.hasNext(); u++)
            {
                Integer c = cit.next();
                int p = prow[u];
                rsum += p;
                cit.set(c + p);
                
            }
            rit.set(r + rsum);
        }

        for (i = 0; i < rows; ++i)
        {
            j = 0;
            if (i - rad > 0)
            {

                int [] prow = M.get(0);
                int u, p;
                for(cit = C.listIterator(), u = 0;
                   cit.hasNext(); ++u)
                {
                    Integer c = cit.next();
                    p = prow[u];
                    cit.set(c - p);
                }
                M.remove(0);
                h -= R.get(0);
                R.remove(0);
            }
            int row = i + rad;
            if (row < rows && i > 0)
            {
                int [] newQ = new int [rad + 1];
                M.add(newQ);
                int rx;
                int tot = 0;
                for (rx = 0; rx <= rad; rx++)
                {
                    if (rx < cols)
                    {
                        int val = mat[row][rx];
                        newQ[rx] = val;
                        C.set(rx, C.get(rx) + val);
                        tot += val;
                    }
                }
                R.add(tot);
                h += tot;
            }
            hh = h;
            Q = new ArrayList<Integer>(cols);
            Q.addAll(C);
            for (j = 1; j < cols; j++)
            {
                int col = j + rad;
                if (j - rad > 0)
                {
                    hh -= Q.get(0);
                    Q.remove(0);
                }
                if (j + rad < cols)
                {

                    int val = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        int y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            val += mat[y][col];
                        }
                    }
                    hh += val;
                    Q.add(val);

                }
            }
        }
    }

    public static void opt3Windowing(int [][] mat, int rad, int [] Q, int [] R){
        int cols = mat[0].length;
        int rows = mat.length;

        int i = 0;
        int j = 0;
        int k = 0;
        int h = 0;
        int hh = 0;
        int frad = rad + 1;
        ArrayDeque<int []> M = new ArrayDeque<int []>();

        for (int ry = 0; ry <= rad; ry++)
        {
            if (ry < rows)
            {
                int [] q = new int [rad + 1];
                M.add(q);
                for (int rx = 0; rx <= rad; rx++)
                {
                    if (rx < cols)
                    {
                        int val = mat[ry][rx];
                        q[rx] = val;
                        h += val;
                    }
                }
            }
        }
        int mSize = M.size();
        int [] C = new int[rad + 1];
        int rFirst = 0;
        int rLast = rad + 1;
        Iterator<int []> mit;
        for (mit = M.iterator(), k = rFirst; mit.hasNext(); ++k)
        {
            int rsum = 0, u;
            int [] prow = mit.next();
            for (u = 0; u < rad + 1; u++)
            {
                int p = prow[u];
                rsum += p;
                C[u] += p;
            }
            R[k] += rsum;
        }

        int [] newQ = null;
        int [] lastQ = null;
        for (i = 0; i < rows; ++i)
        {
            j = 0;
            if (i - rad > 0)
            {
                int [] prow = M.getFirst();
                int u, p;
                for(u = 0; u < frad; ++u)
                {
                    C[u] -= prow[u];
                }
                lastQ = M.pop();
                h -= R[rFirst];
                rFirst++;
            }
            int row = i + rad;
            if (row < rows && i > 0)
            {
                if (row < 2 * rad + 1)
                 newQ = new int [rad + 1];
                else
                 newQ = lastQ;
                M.addLast(newQ);
                int rx;
                int tot = 0;
                for (rx = 0; rx <= rad; rx++)
                {
                    if (rx < cols)
                    {
                        int val = mat[row][rx];
                        newQ[rx] = val;
                        C[rx] += val;
                        tot += val;
                    }
                }
                R[rLast] = tot;
                rLast++;
                h += tot;
            }
            //System.out.println("i " + i + " j " + j + "h " + h);
            hh = h;
            System.arraycopy(C, 0, Q, 0, rad + 1);
            int qFirst = 0;
            int qLast = rad + 1;

            for (j = 1; j < cols; j++)
            {
                int col = j + rad;
                if (j - rad > 0)
                {
                    hh -= Q[qFirst];
                    qFirst++;
                }
                if (col < cols)
                {
                    int val = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        int y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            val += mat[y][col];
                        }
                    }
                    hh += val;
                    Q[qLast] = val;
                    qLast++;
                }
                //System.out.println("i " + i + " j " + j + "h " + hh);
            }
        }

    }

    public static void opt4Windowing(int [][] mat, int rad, int [] q){
        int i, j = 0, h, y, col;
        int cols = mat[0].length;
        int rows = mat.length;
        //int[] q = new int [cols];

        for (i = 0; i < rows; ++i)
        {
            h = 0;
            int qFirst = 0;
            int qLast = 0;
            for (int rx = 0; rx <= rad; rx++)
            {
                if (rx < cols)
                {
                    int mem = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            mem += mat[y][rx];
                        }
                    }
                    q[qLast] = mem;
                    qLast++;
                    h += mem;
                }
            }
            j = 0;
            //System.out.println("i " + i + " j " + j + "h " + h);

            qFirst = 0;
            qLast = rad + 1;
            for (j = 1; j < cols; j++)
            {
                col = j + rad;
                if (j - rad > 0)
                {
                    h -= q[qFirst];
                    qFirst++;
                }
                if (j + rad < cols)
                {
                    int mem = 0;
                    for (int ry =- rad; ry <= rad; ry++)
                    {
                        y = i + ry;

                        if (y >= 0 && y < rows)
                        {
                            mem += mat[y][col];

                        }
                    }
                    q[qLast] = mem;
                    qLast++;
                    h += mem;

                }
                //System.out.println("i " + i + " j " + j + "h " + h);
            }
        }

    }

    public static void opt5Windowing(int [] mat, int rad, int w, int h, int [] sum){

        
        int s = 0;
        for ( int x = 0; x < w; ++x )
        {
                s += mat[x];
                sum[ x ] = s;
        }
        for ( int y = 1; y < h; ++y )
        {
                int yw = y * w;
                sum[yw] = sum[yw - w] + mat[yw];
                for ( int x = 1; x < w; ++x )
                {
                        int ywx = yw + x;
                        sum[ywx] = sum[ywx - w] + sum[ywx - 1] + mat[ywx] - sum[ywx - w - 1];
                }
        }

//        for (int k = 0; k < sum.length; k++)
//        {
//            System.out.println(sum[k]);
//        }

        h--;
        w--;
        int yMin, yMax, xMin, xMax, y1w, y2w;
        int s1, s2, s3, s4, tot;
        for ( int y = 0; y <= h; ++y )
        {
                yMin = Math.max(-1, y - rad - 1);
                yMax = Math.min(h, y + rad);
                y1w = yMin * (w + 1);
                y2w = yMax * (w + 1);
                for (int x = 0; x <= w; ++x)
                {
                        xMin = Math.max(-1, x - rad - 1);
                        xMax = Math.min(w, x + rad);
                        if (y1w < 0 && xMin < 0)
                        {
                            s1 = 0;
                            s2 = 0;
                            s3 = 0;
          
                        }
                        else if (y1w < 0)
                        {
                            s1 = 0;
                            s2 = 0;
                            s3 = sum[y2w + xMin];

                        }
                        else if (xMin < 0)
                        {
                            s1 = 0;
                            s3 = 0;
                            s2 = sum[y1w + xMax];
                        }
                        else
                        {
                            s1 = sum[y1w + xMin];
                            s2 = sum[y1w + xMax];
                            s3 = sum[y2w + xMin];
                        }

                        s4 = sum[y2w + xMax];
                        tot = s1 + s4 - s2 - s3;

//                        System.out.print(s1 + "+" + s4 + "-" +
//                                        s2 + "-" + s3 + "=");
//                        System.out.println( tot);
                }
        }
    }

    public static void main(String[] args) {

        int rows = 400;
        int cols = 400;
        int rad = 2;
//        int [][] mat = {{8,10,4,9,1,3,5,9,4,10} ,
//                        {1,6,3,3,8,4,8,10,1,3} ,
//                        {4,10,10,8,1,4,10,9,7,6} ,
//                        {8,7,3,8,1,4,10,10,10,2} ,
//                        {8,3,4,7,6,6,9,2,5,8} ,
//                        {2,4,9,5,9,1,5,7,1,4} ,
//                        {3,7,10,5,2,4,8,9,9,4} ,
//                        {9,2,6,4,6,5,4,7,6,10} ,
//                        {6,5,10,2,8,6,6,5,2,9} ,
//                        {9,4,6,3,3,7,7,8,9,5}};
//
//        int [] unimat = {8,10,4,9,1,3,5,9,4,10 ,
//                        1,6,3,3,8,4,8,10,1,3 ,
//                        4,10,10,8,1,4,10,9,7,6 ,
//                        8,7,3,8,1,4,10,10,10,2 ,
//                        8,3,4,7,6,6,9,2,5,8 ,
//                        2,4,9,5,9,1,5,7,1,4 ,
//                        3,7,10,5,2,4,8,9,9,4 ,
//                        9,2,6,4,6,5,4,7,6,10 ,
//                        6,5,10,2,8,6,6,5,2,9 ,
//                        9,4,6,3,3,7,7,8,9,5};

        int [][] mat = new int [rows][cols];
        int [] unimat = new int [rows * cols];
        int seed = 48;
        int i, j;
        Random r = new Random(seed);
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; j++)
            {
                int rnd = 1 + r.nextInt() % 10;
                mat[i][j] = rnd;
                unimat[i * cols + j] = rnd;
            }
        }



        long start, end, result;
        int [] Q = new int[cols];
        System.out.println("ArrayDeque of int[] + int[]");
        int [] R = new int[rows];
        start = end = result = 0;
        start = System.currentTimeMillis();
        opt3Windowing(mat, rad, Q, R);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);

        System.out.println("column ArrayList + row ArrayList cached");
        start = end = result = 0;
        start = System.currentTimeMillis();
        opt2Windowing(mat, rad);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);

        System.out.println("simple");
        start = end = result = 0;
        start = System.currentTimeMillis();
        simpleWindowing(mat, rad);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);

        System.out.println("column ArrayDeque cached");
        start = end = result = 0;
        start = System.currentTimeMillis();
        opt1Windowing(mat, rad);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);

        System.out.println("column array cached");
        start = end = result = 0;
        int [] q = new int [cols];
        start = System.currentTimeMillis();
        opt4Windowing(mat, rad, q);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);


        System.out.println("integral");
        int [] sum = new int[cols * rows];
        start = end = result = 0;
        start = System.currentTimeMillis();
        opt5Windowing(unimat, rad, cols, rows, sum);
        end = System.currentTimeMillis();
        result = end - start;
        System.out.println(result);

    }

}