Часто бывают случаи, когда нам нужно задать порядок на множестве объектов, у которых нет имманентного им приоритета. Например, список покупок - у абстрактного молока нет какой-то характеристики, по которой мы можем судить, что оно менее приоритетнее хлеба. В таком случае объекты наделяются приоритетом снаружи, то есть, он условный. Обычно, программисты назначают тривиальный целочисленный приоритет: молоко - 1, хлеб - 2 и так далее.

Не стоит путать приоритет (вес) объекта с его идентификатором, который может быть инкрементальным целочисленным или, например, случайным UUID.

Проблема в том, что подобные множества объектов имеют свойство приобретать новые элементы и это может доставить неудобства. Представим, что эти объекты где-то хранятся: в хешмапе (и по какой-то нелепой случайности, поле приоритета используется в вычислении хеша) или, самое неприятное, в базе данных. В какой-то момент обязательно появляется колбаса, которая чуть менее приоритетнее хлеба, но приоритетнее молока.

Ситуация стандартная, поведение тоже стандартное - переназначаем новые приоритеты: молоко-1, колбаса - 2, хлеб - 3. Такое переназначение может быть достаточно трудоёмким.

Часто встречаются предусмотрительные программисты, которые ожидая новых элементов, назначают приоритеты с запасом: молоко - 1, колбаса- 5, хлеб - 10. Это решение не очень элегантное и запаса может не всегда хватить.

Другое стандартное поведение - ввести рациональные приоритеты: молоко - 1, колбаса - 1.5, хлеб - 2. Плюс такого подхода в том, что между двумя любыми элементами можно вставить сколько угодно новых. Минусы тоже есть - если заранее не подумать о рациональных приоритетах, то придётся менять тип данных столбца в базе данных. Ещё один плохой момент - нецелое число представляется в компьютере с округлением, что может привести к неточным расчётам.

Кстати, почему между любыми двумя рациональными числами можно вставить ещё одно число? Потому что, дробная часть числа сравнивается не в числовом порядке (101>11), а в лексикографическом (0.101<0.11). Таким образом, если перейти от чисел к строкам, которые сравниваются лексикографически, то можно избавиться от проблем с возможным округлением.

Слово А меньше слова В в лексикографическом смысле, если либо А целиком является префиксом В, либо первый слева неравный символ у А меньше, чем у В.

Вторая часть определения даёт нам возможность сделать так, что между любыми двумя нашими словами можно вставить третье. Для этого, последний символ любого слова должен быть таким, чтобы в алфавите присутствовали символы и больше, и меньше его. Рассмотрим небольшой алфавит из трех элементов: =, < и >. В таком алфавите = как раз сгодится на роль последнего символа любого слова.

Представим, что у нас есть три объекта. Дадим им приоритеты:

1
2
3
молоко:   а=
хлеб:     b=
говядина: с=

Здесь, первая буква добавлена и для наглядности, и для практического удобства - например, это три разные категории товаров: мясное, мучное, молочное. Теперь начинаем добавлять новые объекты: менее приоритетная, чем хлеб булка - b<= (уменьшили последний символ, он получился крайний в алфавите, следовательно добавили равно, чтобы не нарушать правило составления слов). Далее, пирожок между булкой и хлебом: берём хлеб, вычисляем приоритет меньший, получаем b<=, но такой уже присвоен булке, тогда вычисляем приоритет больше нее - b<>=. То есть алгоритм следующий: нужно вычислить приоритет больше, чем исходный - увеличиваем последний символ и добавляем средний символ алфавита, если увеличеный был крайним. Если полученный приоритет уже существует, то вычисляем приоритет меньший этого и так далее. Алгоритм для вычисления приоритета меньшего исходного аналогичен. Получаем такую картину:

1
2
3
4
5
молоко:   а=
булка:    b<=
пирожок:  b<>=
хлеб:     b=
говядина: с=

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

На языке Raku такую генерацию можно написать следующим образом:

1
2
3
4
5
6
7
8
9
10
11
12
sub next($w is copy, Set $set, :$prev) {
  my @subst = '<=', '>=';  # массив замен
  my $i = $prev ?? 0 !! 1; # тернарный оператор: истин ли $prev
  $w ~~ s/.$/{ @subst[$i++]   }/;
  $w ~~ s/.$/{ @subst[$i % 2] }/ while $set{$w};
  $w # возвращаемое значение
}

my $set = SetHash.new: 'a=';
say next('a=', $set) eq 'a>='; # Output: True
$set.set('a>=');
say next('a>=', $set, :prev) eq 'a><='; # Output: True;

Объявляется функция next с тремя аргументами: изначальным словом $w, сетом уже имеющихся слов $set типа Set и параметром-ключём $prev, который используется чтобы генерировать не следующее слово, а предыдущее (см. строку 12). Самые интересные строки это 4 и 5. Тут используется оператор s/// - оператор замены. Берется изначальная $w, в ней ищется подстрока, которая удовлетворяет регулярному выражению между первыми косыми чертами (.$ - один символ перед концом текста) и заменяется за строку, между вторыми косыми чертами (вместо строки мы используем вычислимый блок, в котором берем нужную замену из массива). Стоит заменить, что оператор меняет исходную строку $w, вместо возвращения новой. Это позволяет использовать переменную $w в условии цикла в строке 5 (проверка, присутствует ли уже новое слово). Строки с 9 по 12 иллюстрируют использование функции.