Класс SizeSequence

public class SizeSequence extends Object

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