A pt_PieceTable is the data structure used to represent the document. It presents an interface to access the document content as a sequence of (Unicode) characters. It includes an interface to access document structure and formatting information. It provides efficient editing operations, complete undo, and crash recovery.
The PieceTable consists of the following classs:
InitialBuffer -- This is a read-only character array consisting of the entire character content of the document and initially read from the disk. (All XML tags and other non-content items are omitted from this buffer.)
ChangeBuffer -- This is an append-only character array consisting of all character content inserted into the document during the editing session.
InitialAttrPropTable -- This is a read-only table of Attribute/Property structures extracted from the original document.
ChangeAttrPropTable -- This is an append-only table of Attribute/Property structures that are created during the editing session.
Piece -- This class represents a piece of the sequence of the document; that is, a contiguous sub-sequence having the same properties. Such as a span of text or an object (such as an in-line image). It contains a links to the previous and next Pieces in the document. Pieces are created in response to editing and formatting commands.
TextPiece -- This subclass represents a span of contiguous text in one of the buffers. All text within the span has the same (CSS) properties. A TextPiece is not necessarily the longest contiguous span; it is possible to have adjacent (both in order and in buffer position) TextPieces with the same properties. A TextPiece contains a buffer offset and length for the location an size of the text and a flag to indicate which buffer. A TextPiece contains (or contains a link to) the text formatting information. Note that the buffer offset only gives the location of the content of the span in one of the buffers, it does not specify the absolute position of the span in the document.
ObjectPiece -- This subclass represents an in-line object or image. It has no references to the buffers, but does provide a place-holder in the sequence.
PieceList -- This is doubly-linked list of Pieces. The are linked in document order. A forward traversal of this list will reveal the entire content of the document; in doing so, it may wildly jump around both of the buffers, but that is not an issue.
PX_ChangeRecord -- Each editing and formatting change is represented as a ChangeRecord. A ChangeRecord represents an atomic change that was made to one or more pieces. This includes offset/length changes to a TextPiece and changes to the PieceList.
Insert(position,bAfter,c) -- To insert one or more characters c into the document (either before or after) the absolute document position position, we do the following:
InsertSpan
. cr.span.m_documentOffset
contains the document position of the insertion. cr.span.m_span
marks the buffer position of the text that was inserted. cr.span.m_bAfter
remembers whether the insertion was before or after the document position. Delete(position,bAfter,length) -- To delete one or more characters from the document (either before or after) the absolute document position position, we do the following:
DeleteSpan
. cr.span.m_documentOffset
contains the document position of the deletion. cr.span.m_span
marks the buffer position of the text that was deleted. cr.span.m_bAfter
remembers whether the insertion was before or after the document position. ChangeFormatting()
Undo -- This can be implemented using the information in the ChangeVector. If the CurrentPosition in the ChangeVector is greater than zero, we have undo information. The information in the ChangeRecord prior to the CurrentPosition is used to undo the editing operation. After an undo the CurrentPosition is decremented.
If the ChangeRecord is of type InsertSpan
: we perform a delete operation using cr.span.m_documentOffset
, cr.span.m_span.m_length
and cr.span.m_bAfter
.
If the ChangeRecord is of type DeleteSpan
: we perform an insert operation using cr.span.m_documentOffset
, cr.span.m_span
, and cr.span.m_bAfter
.
ChangeFormatting
: InsertFormatting
: Redo -- This can be implemented using the information in the ChangeVector. If the CurrentPosition in the ChangeVector is less than the length of the ChangeVector, the redo has not been invalidated and may be applied. The information in the ChangeRecord at the CurrentPosition provides complete information to describe the editing operation to be redone. After a redo the CurrentPosition is advanced.
The content of the original file are never modified. Pieces in the PieceList describe the current document; the original content is referenced in a random access fashion. For systems with small memory or for very large documents, it may be worth demand loading blocks of the original content rather than loading it completly into the InitialBuffer.
Document content data (in the two buffers) are never moved once written. insert and delete operations change the Pieces in the PieceList, but do not move or change the contents of the two buffers.
TextPieces represent spans of text that are convenient for the structure of the document and a result of the sequence of editing operations. They are not optimized for layout or display.
const char *
into the buffers along with a length, which the caller could use in text drawing or measuring calls, but not c-style, zero-terminated strings. Mapping an absolute document position to a Piece involves a linear search of the PieceList to compute the absolute document position and find the correct Piece. The number of Pieces in a document is a function of the number of editing operations that have been performed in the session and of the complexity of the structure and formatting of the original document. A linear search might be painfully slow.
We provide a complete, but first-order undo with redo. That is, we do not put the undo-operation in the undo (like emacs).
TODO The before and after stuff on insert and delete is a bit of a hand-wave.
class PT_PieceTable { const UT_UCSChar * m_InitialBuffer; const UT_UCSChar * m_ChangeBuffer; pt_PieceList * m_pieceList; pt_AttrPropTable m_InitialAttrPropTable; pt_AttrPropTable m_ChangeAttrPropTable; ... };
class pt_Piece { enum PieceType { TextPiece, ObjectPiece, StructurePiece }; PieceType m_pieceType; <linked-list or tree pointers> ... };
class pt_Span { UT_Bool m_bInInitialBuffer; UT_uint32 m_offset; UT_uint32 m_length; };
class pt_TextPiece : public pt_Piece { pt_Span m_span; pt_AttrPropReference m_apr; ... };
class pt_ObjectPiece : public pt_Piece { ... };
class pt_StructurePiece : public pt_Piece { pt_AttrPropReference m_apr; ... };
class pt_PieceList { <container for linked-list or tree structure> ... };
class pt_AttrPropReference { UT_Bool m_bInInitialTable; UT_uint32 m_index; ... };
class pt_AttrProp { UT_HashTable * m_pAttributes; UT_HashTable * m_pProperties; ... };
class pt_AttrPropTable { UT_vector<pt_AttrProp *> m_Table; ... };
class pt_ChangeRecord { UT_Bool m_bMultiStepStart; UT_Bool m_bMultiStepEnd;
enum ChangeType { InsertSpan, DeleteSpan, ChangeFormatting, InsertFormatting, ... }; struct { UT_uint32 m_documentOffset; UT_Bool m_bAfter; pt_Span m_span; } span; struct { UT_uint32 m_documentOffset1; UT_uint32 m_documentOffset2; pt_AttrPropReference m_apr; } fmt; ... };
class pt_ChangeVector { UT_vector m_vecChangeRecords; UT_uint32 m_undoPosition; ... };