Сравнение списков - часть 3
Альтернативы удаления
и
дополняют общую операцию до соответствующих действий в каждой транзакции и могут приниматься в произвольном сочетании с двумя другими операциями.
Две конкурентные операции вставки и удаления элементов, пересекающиеся по индексам:
,
, где
, следует считать неконфликтными, поскольку операции удаления могут всегда быть корректно исполнены последовательно или вместе с соответствующими операциями вставки.
Для конфликтных операций вставки
и
, добавляющих неэквивалентные списки элементов
в одну и ту же позицию
i
исходного списка, пользователь должен принять решение относительно способа формирования консолидированного списка вставляемых элементов. Потенциально, любое размещение элементов альтернативных списков может считаться допустимым при выполнении следующих двух условий: оригинальный порядок элементов не изменяется и исключается дублирование эквивалентных элементов из разных версий списка в смежных позициях результирующего списка. Таким образом, возможные варианты консолидации представляются следующим образом:
Первые два условия гарантируют, что исходный порядок элементов при консолидации не будет нарушен. Третье условие, связанное с непосредственным предшествованием операций
в итоговой транзакции, обеспечивает исключение тождественных элементов при вставке в соседние позиции из разных списков. Возможный способ реализовать подобную стратегию заключается в применении упомянутых выше методов сравнения к консолидируемым последовательностям.
Пусть вспомогательные списки
,
представляют собой соответствующие последовательности вставки элементов
и
. Тогда их дельта представима в виде:
Способы консолидации элементов из альтернативных списков задаются на основе
следующими размещениями:
Размещения предполагают предшествование операций, определяемое естественным порядком позиций вставки и индексных интервалов в исходных операциях сформированной дельты. Тем самым, оперируя с альтернативными последовательностями вставки и выделяя отличия между ними, удается определить конструктивный способ разрешения данного рода конфликтов.
Рассмотрим следующий пример.
Начало Назад Вперед
