Как правильно сделать циклический сдвиг в одномерном массиве?

#java #массивы

Я новичок в java и у меня возник данный вопрос. Опишу ситуацию: есть двумерный массив
типа int 9 на 9, и есть метод, который делает циклический сдвиг в одномерном массиве
на заданное количество элементов. 

Первое что я сделал это инициализировал первую строку двумерного массива числами
от 1 до 9.    

private static final int MAX = 9;
private static int[][] baseTable = new int[MAX][MAX];

for (int b = 0; b < 9; b++) {       

    baseTable[0][b] = b + 1;

}


После чего я, сделав сдвиг на один элемент, записал то что получится в 4-ю строчку
двумерного массива. 

baseTable[3] = CyclicShift.shiftLeft(baseTable[0], 1);


Но тут и возникла проблема: когда функция возвращает сдвинутый массив и записывает
его в 4-ю строчку почему-то сдвигается и нулевая строчка, и они, по сути, просто дублирую
друг друга. Как я понимаю, они просто ссылаются на одно и тоже место в памяти, и тут
возникает вопрос: почему нельзя таким образом проинициализировать строки в массиве?

Вот код метода shiftLeft:

public static int[] shiftLeft(int[] a, int iter) {
    if (a != null) {
        for (int m = 0; m < iter; m++) {
            int tmp = a[0];
            for (int i = 0; i < a.length - 1; i++) {
                a[i] = a[i + 1];
            }
            a[a.length - 1] = tmp;
        }
        return a;
    } else {
        return null;
    }
}


P.S. Проблема была решена сначала полным заполнением всего двумерного массива, а
затем сортировкой только тех строк, которых мне нужно, и запись в них же. Но интересует
именно механизм работы массива, и то, почему возникает такая ситуация.
    

Ответы

Ответ 1

Тут всё довольно просто. Дело в том, что вы переставляете элементы в том же самом
массиве, который и получаете в качестве источника.

Нужно определиться, что же все-таки должен делать ваш метод shiftLeft():


Переставлять элементы в том массиве, который получает
Или возвращать новый массив, являющийся перестановкой старого.


Сейчас он делает и то, и другое. А еще вместо того, чтобы сразу перемещать элементы
на N позиций, он делает N итераций — это не очень производительно.

Вот вариант, который создает новый массив и записывает в него значения со сдвигом,
используя созданный как раз для этих целей метод System.arraycopy(Object src, int srcPos,
Object dest, int destPos, int length)

Реализация:

public class ArrayShift {

    public static int[] shiftLeft(int[] a, int shift) {
        if (a != null) {
            int length = a.length;
            int[] b = new int[length];
            // шаг 1
            System.arraycopy(a, shift, b, 0, length - shift);
            // шаг 2
            System.arraycopy(a, 0, b, length - shift, shift);
            return b;
        } else {
            return null;
        }
    }
}


Вот как это работает.

Шаг 1:

array a:    0    1    2    3    4    5
                      ↓    ↓    ↓    ↓
array b:              _    _    _    _    _    _


Шаг 2:

array a:                        0    1    2    3    4    5
                                ↓    ↓
array b:    2    3    4    5    _    _


Несколько юнит-тестов:

import org.junit.Assert;
import org.junit.Test;

public class ArrayShiftTest {

    int[] source = {0, 1, 2, 3, 4, 5};

    @Test
    public void testValid() {
        int[] expected = {2, 3, 4, 5, 0, 1};
        Assert.assertArrayEquals(expected, ArrayShift.shiftLeft(source, 2));
    }

    public void testZero() {
        Assert.assertArrayEquals(source, ArrayShift.shiftLeft(source, 0));
    }

    /**
     * На отрицательных значениях метод сломается
     * */
    @Test(expected = IndexOutOfBoundsException.class)
    public void testNegative() {
        ArrayShift.shiftLeft(source, -1);
    }

    /**
     * На значениях выше длины массива — тоже
     * */
    @Test(expected = IndexOutOfBoundsException.class)
    public void testExceedLength() {
        ArrayShift.shiftLeft(source, 10);
    }
}


Если про юнит-тесты непонятно будет, спрашивайте.

Также подскажу вам три пункта, которые вы можете улучшить самостоятельно:


Сдвиг влево и вправо — одно и то же, можно задавать направление положительным и отрицательным
значением параметра и объединить shiftLeft и shiftRight
Если не объединять методы, то нужно что-то делать при отрицательных значениях
Необходимо подумать о значениях, превышающих длину массива


Ответ 2

Я совершенно не знаю Java, но попробую объяснить, как это мне представляется.:)

Думаю, что данное объявление 

private static int[][] baseTable = new int[MAX][MAX];


задает не двумерный массив, а массив массивов. Поэтому каждый элемент baseTable[i]
- это ссылка на одномерный массив.

Похоже функция CyclicShift.shiftLeft(baseTable[0], 1); действительно сдвигает циклически
элементы массивы baseTable[0]  и возвращает ссылку на этот же массив, то есть на baseTable[0]

Эту ссылку вы присваиваете ссылке baseTable[3]

baseTable[3] = CyclicShift.shiftLeft(baseTable[0], 1);


В результате две ссылки массива baseTable[] ссылаются на один и тот же целочисленный
массив.