In computing, a piece table is a data structure typically used to represent a text document while it is edited in a text editor. Initially a reference (or 'span') to the whole of the original file is created, which represents the as yet unchanged file. Subsequent inserts and deletes replace a span by combinations of one, two, or three references to sections of either the original document or to a buffer holding inserted text.[1]
Typically the text of the original document is held in one immutable block, and the text of each subsequent insert is stored in new immutable blocks. Because even deleted text is still included in the piece table, this makes multi-level or unlimited undo easier to implement with a piece table than with alternative data structures such as a gap buffer.
This data structure was invented by J Strother Moore.[2]
For this description, we use buffer as the immutable block to hold the contents.
A piece table consists of three columns:
In addition to the table, two buffers are used to handle edits:
Definition: Index(i): return the character at position iTo retrieve the i-th character, the appropriate entry in a piece table is read.
Given the following buffers and piece table:
| Buffer | Content | |
|---|---|---|
| Original file | ipsum sit amet | |
| Add file | Lorem deletedtext dolor |
| Add | 0 | 6 | |
| Original | 0 | 5 | |
| Add | 17 | 6 | |
| Original | 5 | 9 |
To access the i-th character, the appropriate entry in the piece table is looked up.
For instance, to get the value of Index(15), the 3rd entry of piece table is retrieved. This is because the 3rd entry describes the characters from index 11 to 16 (the first entry describes characters in index 0 to 5, the next one is 6 to 10). The piece table entry instructs the program to look for the characters in the "add file" buffer, starting at index 17 in that buffer. The relative index in that entry is 15-11 = 4, which is added to the start position of the entry in the buffer to obtain index of the letter: 4+17 = 21. The value of Index(15) is the 21st character of the "add file" buffer, which is the character "o".
For the buffers and piece table given above, the following text is shown: Lorem ipsum dolor sit amet
Inserting characters to the text consists of:
Single character deletion can be one of two possible conditions:
Several text editors use an in-RAM piece table internally, including Bravo, Abiword,[3] [4] [5] Atom[6] and Visual Studio Code.[7]
The "fast save" feature in some versions of Microsoft Word uses a piece table for the on-disk file format.
The on-disk representation of text files in the Oberon System uses a piece chain technique that allows pieces of one document to point to text stored in some other document, similar to transclusion.[8]