/DSA2-Project-Implementing-PieceTable

1) Fully functioning text editor implementation of Piece Table using Linked List. 2) Splay tree implementation of Piece Table supporting Insertion in a text editor as of now.

Primary LanguageC

DSA2-Project-Implementing-PieceTable

Om Khare
112003066
DSA2 - Project
Division - 1

Includes :

  1. Fully functioning text editor implementation of Piece Table using Linked List.
  2. Splay tree implementation of Piece Table supporting Insertion in a text editor as of now.

Test Results

  1. Using Linked List:
    a. Insertion of 10000 characters in a 1,50,000 line text took 7.31 seconds:
  2. Using Splay tree:
    a. Insertion of 10000 characters in a 1,50,000 line text took < 1 second.

Graph of time required per insertion using Splay Tree

Graph

Analysis from graph

  • Spikes are observed in the graph
  • These sipkes are due to the splaying function of the splay tree.
  • Once we edit something, the edited piece of text is splayed to the root of the tree and hence the sudden drop in time required.
  • Although time required in some cases is more, the average time required is very less as compared to linked list implementation.

Conclusion

  • Splay tree method is efficient for normal file editing limiting the size of file to 1000 lines
  • Beyond that, the text editor should switch back to its linked list implemetation of piece table and auto save feature should be turned off.
  • A combination of splay tree and linked list will be the optimal solution.

References:

Build Your Own Text Editor
https://darrenburns.net/posts/piece-table/
https://www.cs.unm.edu/~crowley/papers/sds/node15.html
https://www.javatpoint.com/splay-tree