Buttercola: In-place Stencil

Buttercola: In-place Stencil
Given a m*n matrix with integers, calculate the average value based on its 8 neighbors. Do it in-place. 

  public void computeAverageInplace(int[][] matrix) {

    if (matrix == null || matrix.length == 0) {

      return;

    }

     

    int m = matrix.length;

    int n = matrix[0].length;

     

    int[][] padMatrix = new int[m + 2][n + 2];

     

    for (int i = 0; i < m; i++) {

      for (int j = 0; j < n; j++) {

        padMatrix[i + 1][j + 1] = matrix[i][j];

      }

    }

     

    int t1 = 0;

    int t2 = 0;

     

    // step 1: compute the accumulation in row order

    for (int j = 1; j < n + 1; j++) {

      for (int i = 1; i < m + 1; i++) {     

        if (i == 1) {

          t1 = padMatrix[i][j];

          padMatrix[i][j] += padMatrix[i + 1][j];

        } else if (((i - 1) & 1) == 0) {

          if ((i - 1) % 4 == 0) {

            t1 = padMatrix[i][j];

            padMatrix[i][j] = padMatrix[i - 1][j] - t2 + padMatrix[i + 1][j];

          } else {

            t2 = padMatrix[i][j];

            padMatrix[i][j] = padMatrix[i - 1][j] - t1 + padMatrix[i + 1][j];

          }

        } else {

          if ((i - 1) % 4 == 1) {

            padMatrix[i][j] += t1 + padMatrix[i + 1][j];

          } else {

            padMatrix[i][j] += t2 + padMatrix[i + 1][j];

          }

        }

      }

    }

     

    // step 2: compute the accumatlion in col order

    for (int i = 1; i < m + 1; i++) {     

      for (int j = 1; j < n + 1; j++) {

        if (j == 1) {

          t1 = padMatrix[i][j];

          padMatrix[i][j] += padMatrix[i][j + 1];

        } else if (((j - 1) & 1) == 0) {

          if ((j - 1) % 4 == 0) {

            t1 = padMatrix[i][j];

            padMatrix[i][j] = padMatrix[i][j - 1] - t2 + padMatrix[i][j + 1];

          } else {

            t2 = padMatrix[i][j];

            padMatrix[i][j] = padMatrix[i][j - 1] - t1 + padMatrix[i][j + 1];

          }

        } else {

          if ((j - 1) % 4 == 1) {

            padMatrix[i][j] += t1 + padMatrix[i][j + 1];

          } else {

            padMatrix[i][j] += t2 + padMatrix[i][j + 1];

          }

        }

      }

    }

     

    // Copy the padMatrix back to matrix

    for (int i = 0; i < m; i++) {

      for (int j = 0; j < n; j++) {

        matrix[i][j] = padMatrix[i + 1][j + 1];

      }

    }

  }

   

  public int[][] computeAverageOutOfPlace(int[][] matrix) {

    int m = matrix.length;

    int n = matrix[0].length;

     

    int[][] padMatrix = new int[m + 2][n + 2];

     

    for (int i = 0; i < m; i++) {

      for (int j = 0; j < n; j++) {

        padMatrix[i + 1][j + 1] = matrix[i][j];

      }

    }

     

    int[][] result = new int[m][n];

     

    for (int i = 1; i < m + 1; i++) {

      for (int j = 1; j < n + 1; j++) {

        for (int p = i - 1; p <= i + 1; p++) {

          for (int q = j - 1; q <= j + 1; q++) {

            result[i - 1][j - 1] += padMatrix[p][q];

          }

        }

      }

    }

     

    return result;

  }

   

  public static void main(String[] args) {

    Solution sol = new Solution();

     

    int m = 17;

    int n = 20;

    int[][] matrix = new int[m][n];

    for (int i = 0; i < m; i++) {

      for (int j = 0; j < n; j++) {

        matrix[i][j] = (i * j) % 10;

      }

    }

     

    int[][] outOfPlace = sol.computeAverageOutOfPlace(matrix);

     

    System.out.println("Out of place result: ");

    for (int[] rows : outOfPlace) {

      for (int e : rows) {

        System.out.print(e + " ");

      }

       

      System.out.println("");

    }

     

    System.out.println("");

    System.out.println("In place result: ");

    sol.computeAverageInplace(matrix);

     

    for (int[] rows : matrix) {

      for (int e : rows) {

        System.out.print(e + " ");

      }

       

      System.out.println("");

    }

  }

Read full article from Buttercola: In-place Stencil