Piece Table
Created on 2023-05-09T23:00:56-05:00
Citation: "Data Structures for Text Sequences" by Charles Crowley.
- Piece Chains which mentions the citation.
- Abiword's use of red-black tables to make piece tables faster
A piece table is two things: a buffer where data exists, and a "span" object which points to a slice of that buffer and provides metadata.
Piece tables allow undo-redo support and multiple versions within a file--also why some very old versions of Word leaked old revisions of documents. Buffers are permanently appended to in a file and referenced by pieces. Changes involve swapping out the "pieces." So insertion between two sentences is to insert text in some available buffer space and slice the original pieces around the new insertion. Browsing versions of a document are then a matter of following the piece connections for that version of a document.
The "piece chain" modification creates a doubly linked list of pieces.
Abiword uses a tree system to position pieces so the piece nearest to a given character position can be retrieved very quickly.