19 Multi-character CDM operations

This chapter specifies operational transformation for multi-character Create, Delete and Move (CDM) operations on text documents. Several sites may concurrently edit a set of documents, and a single operation may affect non-empty ranges within or across those documents. Transforming the operations received from other sites must make every site converge while preserving the users' intentions.

Half-open intervals allow a range to be processed as one unit until another operation introduces a boundary at which it must be split. Effects documents retain the additional state needed to identify characters through concurrent creates, deletes and moves, while working documents present the resulting visible text.

The subchapters first define effects documents, operations, coordinate systems and character identity. They then specify application, structural operations, elementary transformations, Dual IT, Transpose and information-preserving Merge. The algorithms are presented with their interval cases and dependency matrices, followed by C++ from the tested reference implementation.