Класс 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, оба из которых реализованы путём преобразования внутреннего массива в набор целочисленных размеров, копирования его в новый массив и затем преобразования гибридного представления на месте.