Как в treedoc вырабатывать posId для нового атома?

Question

[Artur Aralin]

Пробую сделать редактор совместного редактирования текста на основе crdt, но никак не пойму как вырабатывается ключ позиции.

Есть где почитать про то как реализовать всттавку в treedoc? (не научная статья, а именно реализация).

Answer 1

[TheRonCronix]

Ну, вот здесь бинарное дерево предлагают: https://hal.inria.fr/inria-00445975/document. Псевдокод там есть.
Или как вариант (не прдуманный) числа с бесконечной точностью:
например 1 < 2 < 3 < 4 ...
далее хотим между 1 и 2 что-то вставить, получаем: 1 < 11 < 12 < 13 < ... < 2
11 < 111 < 112 < ... < 12
...
В компе вариант будет двоичный.

Comments

[Artur Aralin]

т.е. получается, что posId у всех элементов поддерева должен быть обновлен?

[Artur Aralin]

TheRonCronix