Anton Stezhkin
20 уровень

Вариант решения задачи уровень 19 задание 16 (отслеживаем изменения)

Пост из группы Random
914491 участников

Предыстория:

Я очень долго решал эту задачу. В ней надо было сравнить 2 версии файла и найти изменения. Содержимое файлов я решил извлекать в виде массивов и сравнивать массивы. Потом долго тупил и ошибался и в конце концов нарисовал массивы на бумажке в клеточку. Вообще, перед этим я посмотрел другой вариант решения. Но он такой сложный, что я его не осилил :) К тому же там было 2 разных алгоритма на случай если старый файл длиннее и если новый файл длиннее. Мне это не понравилось.

Суть моего варианта решения:

Есть 2 одинаковых массива. По ходу текста я буду их называть "новый массив" и "старый массив". И в каждый из них могут быть вставлены новые элементы. Т.е. эталонным считается массив, соответствующий содержимому старого файла со всеми удалениями. Содержимое старого и нового файла рассматриваются как эталон со вставками. Мы проходим оба массива (содержимое старого и нового) в цикле. И если обнаруживаем вставку в одном из них - то пропускаем один шаг , чтобы одинаковые элементы сравниваемых массивов снова были рядом.

Алгоритм:

Переменные: i - индекс ячейки массива с содержимым СТАРОГО файла. nI - индекс ячейки массива с содержимым НОВОГО файла. Если элементы массивов отличаются - записываем их во временные переменные: oldMismatch - элемент из стагого массива newMismatch - элемент из нового массива При переборе элементов массива возможны слеюдущие случаи:
  1. переменные oldMismatch и newMismatch пусты. Элементы в двух массивах совпадают. Записываем Type.SAME в список. Идем дальше.

  2. переменные oldMismatch и newMismatch пусты. Элементы в двух массивах НЕ совпадают. Записываем значение из старого в oldMismatch, из нового - в newMismatch. Идем дальше.

  3. переменные oldMismatch и newMismatch НЕ пусты. Сравниваем их с текущими элементами массива.

    Делаем выводы. Записываем выводы в список (пременная lines). Пропускаем шаг цикла для одного из массивов.

    1. 3.1 oldMismatch равна текушему элементу НОВОГО массива. Это значит, что в файл добавили строку.

      Значение этой строки хранится в newMismatch. Так и запишем.

      lines.add(new LineItem(Type.ADDED, newMismatch));
      lines.add(new LineItem(Type.SAME, oldMismatch));

      Так как в массиве с содержимым нового файла есть дополнительный элемент, нужно сдвинуть новый массив на 1 элемент вперед относительно старого.

      Поэтому СТАРЫЙ массив пропускает 1 шаг цикла.

      i--;

    2. 3.2 newMismatch равна текущему элементу СТАРОГО массива. Это значит, что из файла была удалена строка. Записываем.

      lines.add(new LineItem(Type.REMOVED, oldMismatch));
       lines.add(new LineItem(Type.SAME, newMismatch));

      В СТАРОМ массиве есть допoлнительный элемент. Значит НОВЫЙ массив пропускает 1 шаг цикла.

      nI--;

  4. Обработка конца массива. И вот мы подошли к концу старого массива. Возможно несколько вариантов ситуации

    1. 4.1 - ArrayIndexOutOfBoundsException - новый массив короче старого. Записываем, что последняя строка файла была удалена.

    2. 4.2 - Остался последний элемент нового массива, не охваченный нашим вниманием. Записываем его как добавленный.

    3. 4.3 - Переменные oldMismatch и newMismatch не пусты. Записываем:

      lines.add(new LineItem(Type.ADDED, newMismatch));
      lines.add(new LineItem(Type.SAME, oldMismatch));
P.S. - не забываем обнулять переменные и следить за перемененной nI.