||This article provides insufficient context for those unfamiliar with the subject. Learn how and when to remove this template message) (May 2012) (|
A piece table is a data structure typically used to represent a series of edits on a (potentially) read-only text document. An initial reference (or 'span') to the whole of the original file is created, with subsequent inserts and deletes being created as combinations of one, two, or three references to sections of either the original document or of the spans associated with earlier inserts.
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.
J Strother Moore invented the piece table.
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. 
- Charles Crowley. "Data Structures for Text Sequences". Section "The piece table method".
- David Lu. "What's been wrought using the Piece Table?". (discussion)
- "AbiWord Development: Piece Table Background".
- James Brown. "Piece Chains: Design & Implementation of a Win32 Text Editor".
- Joaquin Cuenca Abela. "Improving the AbiWord's Piece Table".
- Niklaus Wirth, Jürg Gutknecht. "Project Oberon: The Design of an Operating System and Compiler". 2005. p. 90.
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|
|This computer science article is a stub. You can help Wikipedia by expanding it.|