Класс SizeSequence

public class SizeSequence extends Object

Объект SizeSequence эффективно поддерживает упорядоченный список размеров и соответствующих позиций. Одним из случаев, в которых может быть уместен SizeSequence, является компонент, отображающий несколько строк неодинакового размера. В этом случае один объект SizeSequence можно использовать для отслеживания высоты и Y-позиций всех строк.

Другим примером может служить многоколоночный компонент, такой как JTable, в котором размеры столбцов неодинаковы. JTable может использовать один объект SizeSequence для хранения ширины и X-позиций всех столбцов. Затем JTable может использовать объект SizeSequence, чтобы найти столбец, соответствующий заданной позиции. JTable может обновлять объект SizeSequence при изменении размера одного или нескольких столбцов.

На следующем рисунке показана связь между данными о размерах и позициях для многоколоночного компонента.

На рисунке первый индекс (0) соответствует первому столбцу, второй индекс (1) — второму столбцу и так далее. Позиция первого столбца начинается с 0, а столбец занимает size₀ пикселей, где size₀ — значение, возвращаемое getSize(0). Таким образом, первый столбец заканчивается на позиции size₀ - 1. Затем второй столбец начинается с позиции size₀ и занимает size₁ (getSize(1)) пикселей.

Обратите внимание, что объект SizeSequence просто представляет интервалы вдоль оси. В наших примерах интервалы обозначают высоту или ширину в пикселях. Однако столь же подходящей может быть любая другая единица измерения (например, время в днях).

Примечания по реализации

Обычно при хранении размеров и позиций элементов выбирают хранение либо размеров, либо самих позиций. Во время отрисовки необходимы две распространённые операции: getIndex(position) и setSize(index, size). При любом выбранном внутреннем формате одна из этих операций становится затратной, когда количество элементов велико. Если хранятся размеры, поиск индекса элемента, содержащего заданную позицию, требует времени, линейно зависящего от числа элементов. Если же хранятся позиции, изменение размера элемента с заданным индексом требует обновления позиций затронутых элементов, что также является линейным вычислением.

Подобно описанным выше подходам, этот класс внутренне хранит массив из N целых чисел, но использует гибридное кодирование, занимающее промежуточное положение между подходами на основе размеров и на основе позиций. В результате получается структура данных, для хранения которой требуется тот же объём памяти, но большинство операций можно выполнять за время Log(N), а не O(N), где N — число элементов в списке.

Две операции, время выполнения которых по-прежнему линейно зависит от числа элементов, — это методы insertEntries и removeEntries. Оба метода преобразуют внутренний массив в набор целочисленных размеров, копируют его в новый массив, а затем заново формируют гибридное представление на месте.