Rotating a matrix in Java

Question

Introduction

This program is about rotating a matrix. For example, let the matrix be

abcde
fghij
klmno
pqrst

Now, after rotating two steps clockwise we will obtain

kfabc
pmlgd
qnihe
rstoj

The way I dealt with rotations is the following: I maintain \$\min(\lfloor m / 2 \rfloor, \lfloor n / 2 \rfloor)\$ "rotation lists" where \$m\$ is the number of rows and \$n\$ is the number of columns in the matrix. Each rotation list is a circular, doubly-linked list in which each node knows the \$x\$- and \$y\$-coordinates of the matrix position it represents. This makes rotation easier to implement in the sense that instead of a "hard-coded" rotation we perform a simple rotation in a list, which is done simply via moving the contents in the matrix according to the rotation list.

Implementation

RotableMatrix.java

package net.coderodde.fun;

import java.util.Scanner;

/**
 * This class implements a rotable matrix.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 28, 2018)
 * @param <I> the matrix cell type.
 */
public class RotableMatrix<I> {

    /**
     * Implements the linked list structure that makes it easy to rotate a
     * matrix.
     */
    private static final class Node {

        private final int x;
        private final int y;
        private Node previous;
        private Node next;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    /**
     * The minimum number of rows or columns in a matrix.
     */
    private static final int MINIMUM_ROWS_COLUMNS = 1;

    /**
     * The data stored in the matrix.
     */
    private final I[] data;

    /**
     * The number of rows in the matrix.
     */
    private final int rows;

    /**
     * The number of columns in the matrix.
     */
    private final int columns;

    /**
     * The array of rotation lists.
     */
    private final Node[] rotationLists;

    /**
     * The length of each corresponding rotation list. In other words, the 
     * length of {@code rotationLists[index]} is 
     * {@code rotationListsLength[index]}.
     */
    private final int[] rotationListsLength;

    /**
     * Used for buffering some elements in the rotation lists.
     */
    private final I[] rotationBuffer;

    /**
     * Constructs an empty rotable matrix with {@code rows} rows and 
     * {@code columns} columns.
     * 
     * @param rows    the number of rows.
     * @param columns the number of columns. 
     */
    public RotableMatrix(int rows, int columns) {
        this.rows = checkRows(rows);
        this.columns = checkColumns(columns);
        this.data = (I[]) new Object[rows * columns];
        int numberOfRotationListsColumnwise = columns / 2;
        int numberOfRotationListsRowwise = rows / 2;
        int numberOfRotationLists = Math.min(numberOfRotationListsColumnwise,
                                             numberOfRotationListsRowwise);
        this.rotationLists = new Node[numberOfRotationLists];
        this.rotationListsLength = new int[numberOfRotationLists];
        this.rotationBuffer = (I[]) new Object[columns + rows - 1];
        populateRotationLists(numberOfRotationLists);
    }

    /**
     * Returns the number of columns in this matrix.
     * 
     * @return the number of columns.
     */
    public int getNumberOfColumns() {
        return columns;
    }

    /**
     * Returns the number of rows in this matrix.
     * 
     * @return the number of rows.
     */
    public int getNumberOfRows() {
        return rows;
    }

    /**
     * Reads a matrix cell.
     * 
     * @param x the {@code x}-coordinate of the target cell.
     * @param y the {@code y}-coordinate of the target cell.
     * @return the contents of the target cell.
     */
    public I get(int x, int y) {
        checkX(x);
        checkY(y);
        return data[y * columns + x];
    }

    /**
     * Writes a matrix cell.
     * 
     * @param x the {@code x}-coordinate of the target cell.
     * @param y the {@code y}-coordinate of the target cell.
     * @param value the value to set to the target cell.
     */
    public void set(int x, int y, I value) {
        checkX(x);
        checkY(y);
        data[y * columns + x] = value;
    }

    /**
     * Rotates the matrix. Positive value of {@code count} rotates clockwise, 
     * the negative counter-clockwise.
     * 
     * @param count the number of positions to rotate.
     * @return this matrix.
     */
    public RotableMatrix<I> rotate(int count) {
        for (int offset = 0; offset < rotationLists.length; offset++) {
            rotateAtOffset(offset, count);
        }

        return this;
    }

    /**
     * A simple dump of the matrix data to a string.
     * 
     * @return a simple textual representation of the matrix contents.
     */
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        String rowSeparator = "";

        for (int y = 0; y < rows; y++) {
            stringBuilder.append(rowSeparator);
            rowSeparator = "\n";

            for (int x = 0; x < columns; x++) {
                stringBuilder.append(get(x, y).toString());
            }
        }

        return stringBuilder.toString();
    }

    /**
     * Rotates the {@code offset}th rotation list by {@code count} positions.
     * 
     * @param offset the offset of the rotation list.
     * @param count  the number of positions to rotate. The negative values 
     *               rotate counter-clockwise, and the positive values rotate
     *               clockwise.
     */
    private void rotateAtOffset(int offset, int count) {
        int currentRotationListLength = rotationListsLength[offset];
        count %= currentRotationListLength;

        if (count == 0) {
            // Nothing to do.
            return;
        }

        if (count < 0) {
            // Rotate counter-clockwise:
            count = -count;
            int count2 = currentRotationListLength - count;

            if (count < count2) {
                rotateAtOffsetCounterClockwise(offset, count);
            } else {
                rotateAtOffsetClockwise(offset, count2);
            }
        } else {
            // Here, we have count > 0 so rotate clockwise:
            int count2 = currentRotationListLength - count;

            if (count < count2) {
                rotateAtOffsetClockwise(offset, count);
            } else {
                rotateAtOffsetCounterClockwise(offset, count2);
            }
        }
    }

    /**
     * Implements the clockwise rotation.
     * 
     * @param offset the rotation list index.
     * @param count  the number of steps to rotate.
     */
    private void rotateAtOffsetClockwise(int offset, int count) {
        Node sourceNode = rotationLists[offset];
        Node targetNode = sourceNode;

        for (int i = 0; i < count; i++) {
            rotationBuffer[i] = get(sourceNode.x, sourceNode.y);
            sourceNode = sourceNode.previous;
        }

        for (int i = 0; i < rotationListsLength[offset] - count; i++) {
            set(targetNode.x, targetNode.y, get(sourceNode.x, sourceNode.y));
            targetNode = targetNode.previous;
            sourceNode = sourceNode.previous;
        }

        for (int i = 0; i < count; i++) {
            set(targetNode.x, targetNode.y, rotationBuffer[i]);
            targetNode = targetNode.previous;
        }

        emptyBuffer(count);
    }

    /**
     * Implements the counter-clockwise rotation.
     * 
     * @param offset the rotation list index.
     * @param count  the number of steps to rotate.
     */
    private void rotateAtOffsetCounterClockwise(int offset, int count) {
        Node sourceNode = rotationLists[offset];
        Node targetNode = sourceNode;

        for (int i = 0; i < count; i++) {
            rotationBuffer[i] = get(sourceNode.x, sourceNode.y);
            sourceNode = sourceNode.next;
        }

        for (int i = 0; i < rotationListsLength[offset] - count; i++) {
            set(targetNode.x, targetNode.y, get(sourceNode.x, sourceNode.y));
            targetNode = targetNode.next;
            sourceNode = sourceNode.next;
        }

        for (int i = 0; i < count; i++) {
            set(targetNode.x, targetNode.y, rotationBuffer[i]);
            targetNode = targetNode.next;
        }

        emptyBuffer(count);
    }

    /**
     * Sets to {@code null} first {@code count} positions in the rotation
     * buffer. We do this so the garbage collector can reclaim some space.
     * 
     * @param count the number of first array components in the rotation buffer
     *              to set to {@code null}.
     */
    private void emptyBuffer(int count) {
        for (int i = 0; i < count; i++) {
            rotationBuffer[i] = null;
        }
    }

    /**
     * Populates the rotation lists.
     * 
     * @param numberOfRotationLists the number of rotation lists in this matrix.
     */
    private void populateRotationLists(int numberOfRotationLists) {
        for (int rotationList = 0; 
                rotationList < numberOfRotationLists; 
                rotationList++) {
            populateSingleRotationLists(rotationList);
        }
    }

    /**
     * Creates a single rotation list at given offset.
     * 
     * @param offset the offset of the list. The value of zero deals with the
     *               outermost rotation list. The value of one deals with the
     *               second outermost rotation list, and so on.
     */
    private void populateSingleRotationLists(int offset) {
        Node previousNode = null;

        for (int x = offset; x < columns - offset; ++x) {
            Node node = new Node(x, offset);

            if (previousNode == null) {
                rotationLists[offset] = node;
            } else {
                previousNode.next = node;
                node.previous = previousNode;
            }

            previousNode = node;
        }

        for (int y = offset + 1; y < rows - offset - 1; ++y) {
            Node node = new Node(columns - offset - 1, y);
            previousNode.next = node;
            node.previous = previousNode;
            previousNode = node;
        }

        for (int x = columns - offset - 1; x >= offset; x--) {
            Node node = new Node(x, rows - offset - 1);
            previousNode.next = node;
            node.previous = previousNode;
            previousNode = node;
        }

        for (int y = rows - offset - 2; y > offset; y--) {
            Node node = new Node(offset, y);
            previousNode.next = node;
            node.previous = previousNode;
            previousNode = node;
        }

        previousNode.next = rotationLists[offset];
        rotationLists[offset].previous = previousNode;
        rotationListsLength[offset] = 
                2 * (columns - 2 * offset) +
                2 * (rows - 2 * (offset + 1));
    }

    /**
     * Checks that the number of rows is not too small.
     * 
     * @param rows the number of rows to check.
     * @return the input number of rows on success.
     * @throws IllegalArgumentException if the number of rows is too small.
     */
    private int checkRows(int rows) {
        return checkImpl(rows, "Too litte rows (" + rows + ").");
    }

    /**
     * Checks that the number of columns is not too small.
     * 
     * @param columns the number of columns to check.
     * @return the input number of columns on success.
     * @throws IllegalArgumentException if the number of columns is too small.
     */
    private int checkColumns(int columns) {
        return checkImpl(columns, "Too little columns (" + columns + ").");
    }

    /**
     * Implements the check of matrix dimensions.
     * 
     * @param items            the number of columns or rows.
     * @param exceptionMessage the exception message upon failure.
     * @return                 the input number.
     * @throws IllegalArgumentException if some parameter is too small.
     */
    private int checkImpl(int items, String exceptionMessage) {
        if (items < MINIMUM_ROWS_COLUMNS) {
            throw new IllegalArgumentException(exceptionMessage);
        }

        return items;
    }

    /**
     * Checks that the given {@code x}-coordinate is within bounds.
     * 
     * @param x the {@code x}-coordinate to check.
     */
    private void checkX(int x) {
        if (x < 0) {
            throw new IndexOutOfBoundsException("x(" + x + ") < 0");
        }

        if (x >= columns) {
            throw new IndexOutOfBoundsException(
                    "x(" + x + ") >= columns(" + columns + ")");
        }
    }

    /**
     * Checks that the given {@code y}-coordinate is within bounds.
     * 
     * @param y the {@code y}-coordinate to check.
     */
    private void checkY(int y) {
        if (y < 0) {
            throw new IndexOutOfBoundsException("y(" + y + ") < 0");
        }

        if (y >= rows) {
            throw new IndexOutOfBoundsException(
                    "y(" + y + ") >= columns(" + rows + ")");
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        RotableMatrix<Character> matrix = getRandomCharMatrix(4, 5);
        System.out.println(matrix);

        while (scanner.hasNextInt()) {
            int count = scanner.nextInt();
            System.out.println();
            System.out.println(matrix.rotate(count));
        }

        System.out.println(matrix);
    }    

    private static RotableMatrix<Character> getRandomCharMatrix(int rows, 
                                                                int columns) {
        RotableMatrix<Character> matrix = new RotableMatrix<>(rows, columns);
        char c = 'A';

        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < columns; x++) {
                matrix.set(x, y, c++);
            }
        }

        return matrix;
    }
}

Critique request

I would like to hear anything that comes to mind.

Answer 1

I like that approach to separate the matrix configuration from the actual rotation logic.

But we could go one step further and let the nodes know theit neighbors so that you can trigger the "head node" of each "shell" and the nodes would do the rotation themselves by tranfering their actual content to the neigbour:

class Node<I>{
  public enum RotationDirection{ CLOCK_WISE, COUNTER_CLOCK_WISE };
  private final Map<RotationDirection, Node> neighbors = new HashMap<>();
  private I content;
  private boolean isRotationStart = false;

  Node(I initialContent){
    content = initialContent;
  }

  public setNeighbor(RotationDirection direction, Node neighbor){
        neighbors.put(direction, neighbor);
  }

  public void rotate(RotationDirection direction){
     isRotationStart = true; // avoid endless loop
     neighbors.getOrDefault(direction, this).rotate(direction, content);
  }

  private  void rotate(RotationDirection direction, I content){
    oldContent = this.content;
    this.content = content;
    if(!isRotationStart )
        neighbors.get(direction).rotate(direction, oldContent);
  }
}

Usage:

class MatrixRotator<I>{
    private final Node<String>[][] matrix 
    private final List<Node<I>> shellHeadNodes = new ArrList<>();
    MatrixRotator(I[][] initialData){
      int m = initialData.legth;
      int n = initialData[0].length;
      Node<I>[][] matrix = new Node<>[m][n];        
      for(int i = 0; i<m; i++)
        for(int j =0 j<n; j++)
           matrix[i][j] = new Node(getInitialContentFor(i,j));
      buildShellsRecursively(Math.min(m,n));
    }

    private void buildShellsRecursively(int level){
      if(level < 1 ) return;
      shellHeadNodes.add(matrix[level][level]);
      for (int i = level+1, i< matrix.length-level, i ++) {
        // set neighors in rows
        matrix[i-1][level].setNeigbour(CLOCK_WISE, matrix[i][level]);
        matrix[i][level].setNeigbour(COUNTER_CLOCK_WISE, matrix[i-1][level]);
        matrix[i-1][matrix[0].length-level].setNeigbour(COUNTER_CLOCK_WISE, matrix[i][level]);
        matrix[i][matrix[0].length-level].setNeigbour(CLOCK_WISE, matrix[i-1][level]);
      }

      for (int i = level+1, i< matrix[0].length-level, i ++) {
        // set neighors in columns
        matrix[level][i-1].setNeigbour(CLOCK_WISE, matrix[level][i]);
        matrix[level][i].setNeigbour(COUNTER_CLOCK_WISE, matrix[level][i-1]);
        matrix[matrix.length-level][i-1].setNeigbour(COUNTER_CLOCK_WISE, matrix[level][i]);
        matrix[matrix.length-level][i].setNeigbour(CLOCK_WISE, matrix[level][i-1]);
      }

    }

   public void rotateBy(int steps, RotationDirection direction){
      for(int i =0; i < steps; i++)
        for(Node<I> shellHed : shellHeadNodes)
            shellHead.rotate(direction);      
   }
}

disclaimer:
The code is only to show the intent and is untested. Also the duplication in the two for loops should be removed.

---

I am afraid that it is not as efficient as mine since you rotate only one position at a time

This is a learning project right? So how big can your input data get? Do you really expect noticeable differences in execution time?

Never refuse a solution because of performance considerations unless you have proven by measurement that there actually is a performance problem and this particular code really causes it and the alternative really solves it.

Beside this...
There is an easy way to adopt the "Jump" in my approach:

in class Node

  public void rotate(RotationDirection direction, int steps){
     isRotationStart = true; // avoid endless loop
     List<I> contentFifo = new ArrayList(Arrays.asList(new I[steps]));
     neighbors.getOrDefault(direction, this).rotate(direction, contentFifo);
  }

  private  void rotate(RotationDirection direction, int steps,  List<I> contentFifo){
    if(0<contentFifo.size()) {
      if(!isRotationStart || steps == contentFifo.size())
         contentFifo.add(this.content);
      this.content = contentFifo.remove(0);
      neighbors.get(direction).rotate(direction, steps, oldContent);
    }
  }

in class MatrixRotator

   public void rotateBy(int steps, RotationDirection direction){
        for(Node<I> shellHed : shellHeadNodes)
            // clever calculation of node count in current shell to avoid "overturns" ...
            shellHead.rotate(direction, steps % shellNodeCount);      
   }

---

BTW: here is the "clever" way to count the nodes of a "shell":

Node.class

public int countNodes(){
   Set<Node<I>> shellNodes = new HashSet();
   shellNodes.add(this);
   neighbors.getOrDefault(RotationDirection.CLOCK_WISE, this).addTo(shellNodes);
}

private void addTo(Set<Node<I>> shellNodes){
  if(!shellNodes.contains(this)){
    shellNodes.add(this);        
    neighbors.get(RotationDirection.CLOCK_WISE).addTo(shellNodes); 
  }
}

MatrixRotator.class

//private final List<Node<I>> shellHeadNodes = new ArrList<>();
private final Map<Node<I>,Integer> shellNodeCounts = new HashMap<>();

private void buildShellsRecursively(int level){
  if(level < 1 ) return;
  // shellHeadNodes.add(matrix[level][level]); // move down
  for  // no change
  //...
  shellNodeCounts.put(matrix[level][level],matrix[level][level].countNodes());
}

public void rotateBy(int steps, RotationDirection direction){
    for(Node<I> shellHead : shellNodeCounts.keySet()){
        int shellNodeCount = shellNodeCounts.get(shellHead);
        shellHead.rotate(direction, steps % shellNodeCount);      
    }
}