Класс SizeSequence

public class SizeSequence extends Object

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

Другой пример — многоколоночный компонент, такой как JTable, в котором размеры столбцов не равны. Объект SizeSequence может быть использован для хранения ширины и позиций X всех столбцов. Затем компонент может использовать объект SizeSequence для нахождения столбца, соответствующего определённой позиции. Компонент может обновлять объект 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, которые реализованы путём преобразования внутреннего массива в набор целочисленных размеров, копирования его в новый массив, а затем переформирования гибридного представления на месте.