Класс 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 — число элементов в списке.

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