Необходимо подобрать структуру данных для хранения данных z-index. Все индексы должны быть уникальными и для них должна быть определена операция сравнения. Операции со структурой: добавление индекса, который больше или меньше другого индекса, добавление индекса, большего максимального индекса, удаление индекса.
-
обычная трехмерная матрица подойдет?– perfect2 янв 2015 в 20:01
-
@perfect можно подробнее?– Im ieee3 янв 2015 в 12:14
-
@Im ieee просто z-index это обычно указатель глубины. например есть окно которое лежит поверх другого окна у него есть координаты в пространстве 1-я размерность матрицы указывает его расположение по горизонтали 2-я размерность указывает его положение по вертикали, а 3-я указывает на его положения в глубину (между другими окнами). так можно получить любой пиксел этого окна в любой момент времени– perfect4 янв 2015 в 9:38
1 ответ
Вам нужен лишь список z-индексов (тогда базируйтесь на std::set
), или z-index для группы объектов (тогда например std::map<double, VisualObject*>
)?
Смотрите. Если у вас есть std::set<double>
, то все операции выполняются просто.
- Уникальность — свойство
std::set
. - Сравнимость: элементы типа
double
сравниваются «из коробки». - Добавление индекса после данного:
- убеждаетесь, что элемент есть во множестве;
- получаете следующий (
upper_bound
); - подсчитываете среднее арифметическое этих элементов и вставляете во множество
- добавление элемента меньше минимального: получаете минимальный (
begin
, т. к. множество отсортировано), вставляете среднее арифметическое минимального иDOUBLE_MIN
. То же для максимального. - Удаление из коробки.
Единственный «скользкий» случай — если при вычислении среднего арифметического в пункте 3 оно окажется равным одному из чисел. Такое может быть, если вы вставляете очень много элементов. В этом случае придётся перенумеровать все индексы: подсчитать количество элементов, и в i
-ый по порядку элемент записать число i
.
-
Просто список z-индексов. На мой взгляд, выбор контейнера — дело второстепенное, основная сложность в том, как при добавлении нового индекса избежать изменения значений большого количества соседних индексов. Наверняка же есть структуры для равномерного или близкого к равномерному распределения целых чисел.– Im ieee3 янв 2015 в 12:13
-
@Im ieee, по крайней мере в Linux STL set реализован на rb-tree, поэтому добавление нового индекса стоит O(log N). Кстати, обход по итератору происходит по порядку возрастания значений элементов.– avp3 янв 2015 в 12:26
-
@avp Ну а для двусвязного списка вообще O(1). Дело в другом: допустим, индекс это просто целое число. Тогда при добавлении индекса, большего какого-то другого индекса, если следующие несколько чисел-индексов заняты, то их придётся увеличить. Очевидно, необходимо, чтобы подобное увеличение (или уменьшение) происходило как можно реже.– Im ieee3 янв 2015 в 12:39
-
@Im ieee, видимо, я не знаком с какой-то спецификой z-индексов (мне казалось, что требуется добавлять новые элементы в произвольные места структуры, сохраняя ее упорядоченность). А что Вам нужно на самом деле? (если можно, то объясните "на пальцах" (для дилетанта в этой области)).– avp3 янв 2015 в 12:45
-
@avp Так и есть, новые элементы в произвольные места структуры. Например, в плохой реализации, у нас есть двусвязный список индексов i1=1, i2=2, i3=3, i4=4. Нужно добавить индекс i больший i1 и меньший i2. Для этого нужно увеличить все индексы большие i1, то есть i2, i3 и i4, на 1, а i будет равно двум. Итоговый список индексов i1=1, i=2, i2=3, i3=4, i4=5.– Im ieee3 янв 2015 в 13:00