Enhancing Rope data structure for collaborative text editing

Abstract

The Rope data structure is an alternative to strings and is developed specifically for handling large strings. It provides a faster solution for operations like concatenation. Thanks to this advantage, the Rope data structure is considered well-suited for use in text editors. The evolving needs of text editors have directed people towards platforms that allow collaborative text editing. With the widespread adoption of cloud systems, these platforms have become even more popular. As a result, people have started to prefer collaborative text editing over standard text editors. There is a limited number of studies in the literature regarding the data structures used in collaborative text editing platforms. This thesis aims to adapt the Rope data structure for use in collaborative text editing environments by developing effective and efficient implementations. Undoing operations, which are commonly used in text editors and have great importance for users, have various implementations. The faster implementations of these operations make the text editor preferred. While the implementations may not exhibit high efficiency in some operations, they significantly enhance the overall effectiveness of text editors. The data structures recommended for undoing operations are typically immutable, as they store version information, enabling rapid reverting to a previous version. Although the Rope data structure itself is immutable, there are certain operations where immutability requires further investigation, which is an aspect not extensively covered in the existing literature. This study implements the insert operation as immutable and measures its performance. As a result, while Rope becomes more effective, there is a slight decrease in efficiency for the insert operation. Another aspect that makes the Rope data structure suitable for collaborative text editing is the balanced tree structure it contains. This balanced tree structure accelerates operations like insert and search, which are crucial for text composition. Consequently, users can benefit from a text editor with higher performance. AVL trees and Red-Black trees are two well-researched and conventional examples of balanced trees. This study enhances Ropes with AVL and Red-Black tree. A crucial feature of collaborative text editing platforms is the ability of multiple users to make simultaneous changes to the document. Consequently, the underlying data structure must support concurrent transactions. This study demonstrates performance gains by making the Rope data structure suitable for concurrent operations. While making this, blocking and non-blocking concurrent algorithms were employed. In conclusion, this study firstly measures the efficiency of the Rope data structure compared to standard string operations in according to string lengths. The results indicate that Rope can be an alternative to strings for length above a certain threshold. The study also introduces an immutable insert operation to the Rope data structure for undoing operations and demonstrates the performance effect compared to a standard insert operation. Moreover, the study strengthens Rope by combining it with AVL trees and Red-Black trees, achieving faster insert and search operations. The integration of Red-Black and AVL trees with Rope is discussed in detail. Finally, the 'insert' and 'concatenation' operations, which are among the Rope operations, were turned into operations that can operate concurrently by using blocking and non-blocking algorithms, thus increasing performance.