Piece table

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. 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.

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. 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. The piece table's ordering of rows implicitly describes the ordering of characters to use from the available buffers. I.e., the first row of the piece table (e.g., ) describes the first sequence of characters in the PTD (e.g., PTD indices 0–5). The second row of the piece table (e.g., ) describes the sequence of characters from a possibly different buffer that will immediately follow the characters chosen from the first sequence (e.g., PTD indices 6–10). This continues to the end of the PTD. In the above example, the piece table indicates that the PTD will have 6 + 5 + 6 + 9 = 26 characters. To get the (character) value Index(15) , we first find the entry (row) in the piece table that corresponds to the PTD index 15. The first entry describes characters in PTD indices 0 to 5, the second entry PTD indices 6 to 10, and the 3rd entry PTD indices 11–16. Since the 3rd entry of the piece table corresponds to PTD index 15 (11 ≤ 15 ≤ 16), the 3rd entry is retrieved. The piece table's 3rd 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 PTD_SoughtIndex − PTD_StartIndexOfEntry = 15 − 11 = 4, which is added to the start position of the entry in the buffer to obtain the 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". In general and in the above example, Buffer_IdxOfSoughtChar = PTD_SoughtIndex − PTD_StartIdxOfEntry + Buffer_StartIdxOfEntry 21 = 15 − 11 + 17 SoughtChar = Entry_NameOfBuffer[Buffer_IdxOfSoughtChar] 'o' = AddFileBuf[21] --------------------------- So, 'o' = Index(15) For the buffers and piece table given above, the following PTD is shown: "Lorem " (from piece table entry 1) +"ipsum" (from piece table entry 2) +" dolor" (from piece table entry 3) +" sit amet" (from piece table entry 4) -------------------------- Lorem ipsum dolor sit amet

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376710916 under CC BY-SA 4.0; modifications have been made.