Сортировка иерархических структур

[Brainenjii]

Какие существуют приемы этого дела?
Поясню - я никогда не заморачивался с сортировкой узлов дерева - как были созданы, так их и вывожу. Но вот недавно вежливо попросили в форме приказа, чтобы можно было задавать пользовательскую сортировку. Как это сделать оптимально в плане трудозатрат и производительности (в таком порядке ^_^)?

[MageSlayer]

Пользовательская сортировка?
Это сортировка по полям в базе что ли?
Ну дык и используйте сортировку с помощью базы данных.

[Brainenjii]

Хм... Вот есть дерево

Код: Выделить всё

Элемент 1
|--Элемент 1.1
|  |-Элемент 1.1.1
|  |-Элемент 1.1.2
|  |-Элемент 1.1.3
|--Элемент 1.2
Элемент 2
|--Элемент 2.1
|  |-Элемент 2.1.1
|  |-Элемент 2.1.2
|  |-Элемент 2.1.3
|--Элемент 2.2
|  |-Элемент 2.2.1
|  |-Элемент 2.2.2
|  |-Элемент 2.2.3


Захотел пользователь и перенёс элемент 2.2.3 над 2.2.1, а 1.1.3 над 1.1.2. При этом весь остальной порядок остался точно таким же,как и раньше. Вот как бы это организовать

Код: Выделить всё

Элемент 1
|--Элемент 1.1
|  |-Элемент 1.1.1
|  |-Элемент 1.1.3
|  |-Элемент 1.1.2
|--Элемент 1.2
Элемент 2
|--Элемент 2.1
|  |-Элемент 2.1.1
|  |-Элемент 2.1.2
|  |-Элемент 2.1.3
|--Элемент 2.2
|  |-Элемент 2.2.3
|  |-Элемент 2.2.1
|  |-Элемент 2.2.2


[MageSlayer]

Ну добавьте поле в таблицу order_num : integer и делайте сортировку по нему.
Ну, а ,например, в базе - хранимую процедуру для обновления этого поля при перемещении пользователем элементов в дереве.

Если нужно будет сортировать по имени, в запросе явно добавьте сортировку по полю имени и т.д.

[Brainenjii]

Эм... Дерево может быть очень большим... Менять все индексы для всех элементов ради одного переставления (пусть даже на самой вершине дерева) - это как-то... Плюс, после переноса надо оповестить об этом всех, кто пользуется этим деревом... Пересылать всё дерево - это тоже как-то ^_^
Пока у меня есть мысль - хранить для каждого элемента дерева 3 ссылки - родитель (очевидно), предыдущий элемент в своей ветке и следующей элемент в своей ветке. Так для "Элемент 1.1.1" предыдущий будет nil, а следующий - 1.1.2. После переноса мне потребуется только изменить 3 элемента - 1.1.1 (сделать следующим 1.1.3), 1.1.2 (заменить предыдущий на 1.1.3, а следующий на nil), и 1.1.3(предыдущий - 1.1.1, а следующий 1.1.2). Так максимум для одного перемещения мне потребуется изменить только 4 элемента. Как мне кажется, решение достаточно очевидно... Но с такой структурой будет сложнее строить дерево. Нет ли готовых оптимальных алгоритмов для решения этой задачи. Или нет ли других решений для этой задачи? ^_^

[Padre_Mortius]

Brainenjii, может стоит хранить этот порядок в конфиге клиента?

[Brainenjii]

нет, порядок должен быть един для всех. Меняется он довольно редко. Но возможность должна быть ^_^ И несмотря на редкость, вариант с изменением значения какого-то флага для всех элементов дерева мне все-равно представляется сомнительным...

[Padre_Mortius]

тогда думаю, что стоит определиться с необходимостью выполнения сортировки или же применения пользовательского порядка. Если для всех должно быть все одинаково, то однозначно добавлять поле в таблицу, если каждому клиенту, то хранить в конфиге

[Brainenjii]

должно быть всё одинаково. Причем, как именно одинаково для каждого дерева должна быть возможность указать отдельно. Т.е. есть деревья, отсортированные по времени ввода узлов, по алфавиту, т.е. с автоматической сортировкой. Здесь ничего сложного, отсортировать можно и на клиенте. Но потребовалась и пользовательская сортировка, например, по важности. И во все отчеты, во все хранилища данные должны выводится именно в заданном администратором дерева порядке. Так что без введения поля в таблицу не обойтись. Но и одним полем обойтись будет сложновато, как мне кажется. Возможно я ошибаюсь.
Я выше описал вариант, как сохранить сортировку, добавив 2 поля (предыдущий, следующий), уменьшим число задействованных узлов при перемещении для худшего случая до 7 (если меняется и родитель) и 4 - если перемещение в рамках ветки. Есть ли более оптимальные варианты?

[MageSlayer]

Эм... Дерево может быть очень большим... Менять все индексы для всех элементов ради одного переставления (пусть даже на самой вершине дерева) - это как-то... Плюс, после переноса надо оповестить об этом всех, кто пользуется этим деревом... Пересылать всё дерево - это тоже как-то ^_^

Зачем менять индексы для всех элементов?
Индексы будут меняться только для подуровня куда перемещается элемент и то, только после того, куда идет вставка.

Оповестить всех?
Какое это имеет отношение к сортировке?
Если перемещение элементов уже есть и вам по какой-то причине нужно что-там оповещать, то это уже должно было реализовано.

Пересылать все дерево тоже никому не надо.
Уже сто раз перетерли - используйте VirtualTreeView с "ленивым" заполнением/обновлением дерева и все будет нормально.

[Brainenjii]

Ага, т.е. для каждого подуровня ведется свой индекс. Тогда теряется выигрыш по количеству задействованных узлов когда в ветке больше 4 элементов. Не сказал - у меня все построено так, что для изменения объектов создаются копии этих объектов, которые затем (после всех изменений) возвращаются в общий список, и идет оповещение всех потоков о проведении этих изменений. Потому число задействованных элементов для меня критично.
Древовидные списки у меня и так "виртуальные", но деревья у меня используются не для вывода пользователю (исключение администратор дерева), а для расчетов и формирования отчетности. Пересылать дерево (вернее изменения) приходится для того, чтобы все экземпляры программы работали с одними и теми же деревьями.

[AlexVinS]

нет, порядок должен быть един для всех. Меняется он довольно редко. Но возможность должна быть ^_^ И несмотря на редкость, вариант с изменением значения какого-то флага для всех элементов дерева мне все-равно представляется сомнительным...

Вам придется выбирать или быстрая сортировка и вообще чтение дерева (дополнительное поле для сортировки или даже множественная модель как в http://www.codenet.ru/db/other/trees/) или быстрое изменение дерева (вариант с двусвязным списоком "соседей"). Сделать быстрым и то и другое еще никому не удалавалось да и невозможно скорее всего.

[MageSlayer]

Не сказал - у меня все построено так, что для изменения объектов создаются копии этих объектов, которые затем (после всех изменений) возвращаются в общий список, и идет оповещение всех потоков о проведении этих изменений. Потому число задействованных элементов для меня критично.

А-а-а. Теперь понятно.
Вы пытаетесь натянуть модификацию метаданных (связей) на свою архитектуру, которая рассчитана на модификацию только данных.
Ну, значит остается только пожелать вам успехов

[Brainenjii]

Спасибо за пожелания! ^_^
А вообще - как можно переделать архитектуру, чтобы учесть и модификацию метаданных? Потому как вопрос реляций крайне волнует ^_^ {пункты номер 2 и 1, соответственно}

[MageSlayer]

А вообще - как можно переделать архитектуру, чтобы учесть и модификацию метаданных?

Ну во-первых, нужно разделить таблицы данных и метаданных.
То есть изменения метаданных не должны приводить к созданию новых версий данных.

Дальше есть два варианта:
1. Идеологически более правильный - переработать архитектуру чтобы учитывались обновления метаданных.
2. Более простой. Прикрутить механизм работы с метаданными сбоку . То есть как отдельный механизм со своими правилами.