Tree sort

Материал из Eludia.

Описание

Иерархическая сортировка заданного списка:

• каждый элемент-предок предшествует своему поддереву;
• порядок элементов с общим предком остаётся без изменения.

Записи и предки идентифицируются по полям:

id

уникальный номер записи;

parent

уникальный номер предка.

К каждой записи в процессе вычислений приписываются следующие поля:

ord_local

порядок данной записи среди множества записей с общим предком;

ord

порядок записи сводящий алфавитное упорядочение к иерархическому (конкатенация ord_local для корня, прародителя,... родителя и текущей записи);

level

уровень текущей записи в дереве.

Имена всех указанных полей переопределяются одноимёнными опциями.

Значения ord числовые, дополненные нулями слева таким образом, чтобы все ord в одной выборке имели одинаковую длину. Соответственно, арифметический порядок для них совпадает с алфавитным (лидирующий нуль НЕ является признаком восьмеричной системы счисления). Для каждой записи $i выполняется равенство

length ($i -> {ord}) == ($i -> {level} + 1) * length ($i -> {local})

Синопсис (Perl 5)

my $rubrics = tree_sort (
 sql_select_all ('SELECT id, parent, label FROM rubrics WHERE fake = 0 ORDER BY label')
);

my $rubrics = tree_sort (
 sql_select_all ('SELECT id, parent, label FROM rubrics WHERE fake = 0 ORDER BY label'),
 {
  id        => 'id',
  parent    => 'parent',
  ord_local => '__ord_local',
  ord       => '__ord',
  level     => '__level',
 },
); ## тот же результат, но другие имена дополнительных полей