查看文章

Selective undo allows users to undo any operation in the history and is considered a key feature in collaborative applications. Operational transformation (OT) is a powerful tool for implementing selective undo because it can be used to rearrange operations in a history in arbitrary orders. Despite the significant progress over the past two decades, however, there is still a space for improvements. Most existing works take time quadratic or even exponential in the size of the operation history H to undo an operation. Although this might be acceptable for real-time collaboration, it would be suboptimal in mobile and asynchronous collaborative applications in which a long history may accumulate. In addition, it is important to prove an algorithm with regard to the correctness criteria it assumes. This paper proposes a novel OT-based algorithm that provides integrated do and selective undo. The algorithm achieves time …