Timsort (комментарии в коде)

package j.lab2; import javafx.util.Pair; import j.lab1.Stack; public class Timsort { private static final int MIN_GALLOP = 7; public static void sort(int[] array) { // Если длина массива < 64, сортируем его вставками. if (array.length < 64) { insertionSort(array, 0, array.length - 1); return; } // Вычисляем minrun. int r = 0; int n = array.length; while (n >= 64) { r |= n & 1; n >>= 1; } int minrun = n + r; // Создаём стек пар {<индекс начала>, <размер>} подмассива. Stack<Pair<Integer, Integer>> stack = new Stack<>(); // Пробегаемся по массиву, разбивая его на подмассивы и записывая эти подмассивы в стек. for (int i = 0, run; i < array.length; i += run) { // Ищем run. run = findRun(array, i); // Если run < minrun, достраиваем до minrun и сортируем подмассив вставками. if (run < minrun) { if (minrun <= array.length - i) { insertionSort(array, i, i + minrun - 1); run = minrun; } else { insertionSort(array, i, array.length - 1); run = array.length - i; } } // Записываем информацию о подмассиве в стек. stack.push(new Pair<>(i, run)); // Проверяем стек, и, если необходимо, объединяем подмассивы. if (stack.getSize() > 1) checkStack(stack, array); } // Если остались необъединённые подмассивы в стеке, объединяем их. while (stack.getSize() > 1) mergeStackEntries(stack, array); } private static void insertionSort(int[] array, int startIndex, int endIndex) { for (int i = startIndex; i <= endIndex; i++) { int value = array[i]; for (int j = i - 1; j >= startIndex && value < array[j]; j--) { array[j + 1] = array[j]; array[j] = value; } } } private static int findRun(int[] array, int start) { // Если индекс начала — конец массива, то это означает, что остался один элемент. if (start == array.length - 1) return 1; int current = start + 1; // Определяем отношение первых двух элементов и входим в цикл увеличения текущего // индекса, пока отношение остаётся таким же. if (array[start] <= array[current++]) while (current < array.length && array[current - 1] <= array[current]) current++; else { while (current < array.length && array[current - 1] > array[current]) current++; // В случае с обратным отношением упорядочиваем элементы // в обратном порядке, чтобы они шли по неубыванию. reverse(array, start, current - 1); } return current - start; } private static void checkStack(Stack<Pair<Integer, Integer>> stack, int[] array) { int x = stack.peek(1).getValue(); int y = stack.peek(2).getValue(); int z = (stack.getSize() >= 3) ? stack.peek(3).getValue() : Integer.MAX_VALUE; // Проверяем нарушение правил сохранения баланса. while (z <= y + x || y <= x) { // Начинаем слияние второго в стеке подмассива с меньшим соседним. if (x <= z) mergeStackEntries(stack, array); else { Pair<Integer, Integer> pop = stack.pop(); mergeStackEntries(stack, array); stack.push(pop); } if (stack.getSize() <= 1) return; x = stack.peek(1).getValue(); y = stack.peek(2).getValue(); z = (stack.getSize() >= 3) ? stack.peek(3).getValue() : Integer.MAX_VALUE; } } private static void mergeStackEntries(Stack<Pair<Integer, Integer>> stack, int[] array) { // Берём два верхних подмассива из стека. Pair<Integer, Integer> right = stack.pop(); Pair<Integer, Integer> left = stack.pop(); int rStart = right.getKey(); int lStart = left.getKey(); int rLength = right.getValue(); int lLength = left.getValue(); // Записываем их объединение в стек. stack.push(new Pair<>(lStart, lLength + rLength)); // Создаём временную копию левого подмассива. int[] lCopy = new int[lLength]; System.arraycopy(array, lStart, lCopy, 0, lLength); int lCount = 0, rCount = 0; // — счётчики копирования элементов из одного подмассива подряд. // Сортируем объединение подмассивов слиянием. // k — счётчик объединения подмассивов // i — счётчик временной копии левого подмассива // j — счётчик правого подмассива for (int k = lStart, i = 0, j = rStart; (i < lLength) && (k < rStart + rLength); k++) { // Сравниваем элементы левого и правого подмассивов // и копируем меньший из них в объединение подмассивов. if (lCopy[i] < array[j]) { array[k] = lCopy[i++]; // Отсчитываем число подряд идущих копирований из одного подмассива. // Если оно стало равным MIN_GALLOP, входим в «режим галопа». rCount = 0; if (++lCount == MIN_GALLOP) { lCount = 0; // До индекса, на котором закончился галоп, копируем часть подмассива в объединение. int gallopIndex = leftGallop(lCopy, i, lLength - 1, array[j]); System.arraycopy(lCopy, i, array, ++k, gallopIndex - i + 1); // Обновляем счётчики i и k. k += gallopIndex - i; i = gallopIndex + 1; } } else { array[k] = array[j++]; lCount = 0; if (++rCount == MIN_GALLOP) { rCount = 0; int gallopIndex = rightGallop(array, j, rStart + rLength - 1, lCopy[i]); System.arraycopy(array, j, array, ++k, gallopIndex - j + 1); k += gallopIndex - j; j = gallopIndex + 1; } } // Если правый подмассив закончился, копируем оставшиеся данные левого подмассива в объединение. if (j == rStart + rLength) { System.arraycopy(lCopy, i, array, k + 1, lLength - i); break; } } } private static int leftGallop(int[] array, int start, int end, int comparingValue) { int add = 1; int current = start; // Пока текущий элемент меньше элемента правого подмассива, // увеличиваем текущий индекс бинарным поиском. while (current <= end && array[current] < comparingValue) { add <<= 1; current += add; } // Корректируем текущий индекс, чтобы он не был за пределами подмассива, // и элемент по этому индексу был меньше элемента правого подмассива. if (current > end && array[end] < comparingValue) current = end; if (current > end || array[current] >= comparingValue) current -= add; return current; } private static int rightGallop(int[] array, int start, int end, int comparingValue) { int add = 1; int current = start; while (current <= end && array[current] <= comparingValue) { add <<= 1; current += add; } if (current > end && array[end] <= comparingValue) current = end; if (current > end || array[current] > comparingValue) current -= add; return current; } private static void reverse(int[] array, int startIndex, int endIndex) { int centerIndex = (startIndex + endIndex - 1) / 2; for (int i = startIndex; i <= centerIndex; i++) { int tmp = array[i]; array[i] = array[endIndex - i + startIndex]; array[endIndex - i + startIndex] = tmp; } } }

(Частично) персистентные списки

Я почитал про реализацию таких списков, но приведу свою реализацию, которую я придумал до этого (вы ведь этого хотели).

В классе персистентного списка имеется список изменений, в котором хранятся все изменения, сделанные над персистентным списком. Изменение — это абстрактный класс. В качестве классов, использующих реализацию класса изменения, выступают класс вставки элемента (Insert) и его удаления (Remove).

Первый метод этих классов — изменение списка. Данный метод позволяет выполнить изменение с входным списком. В классе Insert данный метод вставляет элемент по индексу; элемент и индекс задаются при инициализации объекта этого класса. В классе Remove метод change удаляет элемент в списке по индексу.

Второй метод — обновление в списке изменений элементов, следующих за указанным. В классе Insert этот метод инициализирует временной индекс и проверяет каждое последующее изменение. Временной индекс показывает, на каком индексе находится изменённый элемент в определённый момент времени. Если изменение происходит после этого элемента, то временной индекс остаётся таким же, но меняется индекс в происходящем изменении, если до — то мы смотрим характер происходящего изменения, и в соответствии с ним изменяем временной индекс. В классе Remove логика почти та же, но учитывается, что удалённый элемент нельзя повторно удалить, и поэтому если временной индекс совпадает индексом происходящего удаления, то мы удаляем это удаление из списка изменений — эта операция происходит единожды.

Частичная персистентность.

Чтобы прочитать персистентный список из прошлого, мы создаём новый список и выполняем над ним изменения из списка изменений до нужной версии, возвращаем полученный список.

Полная персистентность.

Перед добавлением изменения в список изменений, мы обновляем все последующие изменения в соответствии с правилами, определёнными выше.

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

Класс изменения

package j.lab2.change; import j.lab1.SinglyLinkedList; public abstract class Change<T> { int index; protected Change(int index) { this.index = index; } public abstract void change(SinglyLinkedList<T> list); public abstract void updateFollowingChanges(SinglyLinkedList<Change<T>> list, int initialVersion); }

Класс изменения-вставки

package j.lab2.change; import j.lab1.SinglyLinkedList; public class Insert<T> extends Change<T> { final T element; public Insert(T element, int index) { super(index); this.element = element; } @Override public void change(SinglyLinkedList<T> list) { list.insert(element, index); } @Override public void updateFollowingChanges(SinglyLinkedList<Change<T>> list, int initialVersion) { int temporalIndex = this.index; for (int i = initialVersion; i < list.getSize(); i++) { Change<T> change = list.get(i); if (change.index >= temporalIndex) change.index++; else if (change instanceof Insert) temporalIndex++; else if (change instanceof Remove) temporalIndex--; } } }

Класс изменения-удаления

package j.lab2.change; import j.lab1.SinglyLinkedList; public class Remove<T> extends Change<T> { public Remove(int index) { super(index); } @Override public void change(SinglyLinkedList<T> list) { list.removeAt(index); } @Override public void updateFollowingChanges(SinglyLinkedList<Change<T>> list, int initialVersion) { int temporalIndex = this.index; int removeChangeAt = -1; for (int i = initialVersion; i < list.getSize(); i++) { Change<T> change = list.get(i); if (change instanceof Insert) { if (change.index >= temporalIndex) change.index--; else temporalIndex++; } else if (change instanceof Remove) { if (change.index > temporalIndex) change.index--; else if (change.index < temporalIndex) temporalIndex--; else if (removeChangeAt < 0) removeChangeAt = i; } } if (removeChangeAt >= 0) list.removeAt(removeChangeAt); } }

Класс персистентного списка

package j.lab2; import j.lab1.SinglyLinkedList; import j.lab2.change.*; public class PersistentList<T> extends SinglyLinkedList<T> { SinglyLinkedList<Change<T>> changes = new SinglyLinkedList<>(); public SinglyLinkedList<T> persistentRead(int version) { SinglyLinkedList<T> result = new SinglyLinkedList<>(); for (int i = 0; i < version; i++) { changes.get(i).change(result); } return result; } public void persistentChange(int initialVersion, Change<T> change) { change.updateFollowingChanges(changes, initialVersion); changes.insert(change, initialVersion); } @Override public void prepend(T element) { super.prepend(element); changes.append(new Insert<>(element, 0)); } @Override public void append(T element) { super.append(element); changes.append(new Insert<>(element, getSize())); } @Override public void insert(T element, int index) { super.insert(element, index); changes.append(new Insert<>(element, index)); } @Override public T removeAt(int index) { T result = super.removeAt(index); changes.append(new Remove<>(index)); return result; } @Override public int remove(T object) { int result = super.remove(object); changes.append(new Remove<>(result)); return result; } }