142
правки
Изменения
→Получение полностью персистентных структур данных
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.
Когда есть запрос к какой-то версии , то нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную. Список ''List Order Maintenance'' позволяет делать это за <tex>O(1)</tex> с помощью операции <tex>order(p,q)</tex>.
В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
