#include <pf_Fragments.h>
Classes | |
| class | Iterator |
| class | Node |
Public Member Functions | |
| pf_Fragments () | |
| ~pf_Fragments () | |
| void | appendFrag (pf_Frag *pf) |
| void | insertFrag (pf_Frag *pfPlace, pf_Frag *pfNew) |
| void | insertFragBefore (pf_Frag *pfPlace, pf_Frag *pfNew) |
| void | unlinkFrag (pf_Frag *pf) |
| void | purgeFrags () |
| pf_Frag * | findFirstFragBeforePos (PT_DocPosition pos) const |
| pf_Frag * | getFirst () const |
| pf_Frag * | getLast () const |
| void | verifyDoc (void) const |
| Iterator | find (PT_DocPosition pos) const |
Private Member Functions | |
| Iterator | insertRoot (pf_Frag *new_piece) |
| Insert a new piece as the root of the tree. | |
| Iterator | insertLeft (pf_Frag *new_piece, Iterator it) |
| Insert a new piece to the left of a given node. | |
| Iterator | insertRight (pf_Frag *new_piece, Iterator it) |
| Insert a new piece to the right of a given node. | |
| void | erase (Iterator it) |
| Erase a piece from the tree. | |
| void | fixSize (Iterator it) |
| If the size of a tree's node changed, we should update the m_lengthLeft field of all its right parents. | |
| PT_DocPosition | documentPosition (const Iterator it) const |
| void | changeSize (int delta) |
| Iterator | begin () |
| Iterator | end () |
| size_t | size () const |
| PT_DocPosition | sizeDocument () const |
| void | _insertBST (Node *pn) |
| void | _insertFixup (Node *pn) |
| void | _eraseFixup (Node *pn) |
| void | _leftRotate (Node *x) |
| This method rotates a tree to the left. | |
| void | _rightRotate (Node *x) |
| This method rotates a tree to the left. | |
| PT_DocPosition | _calculateSize (Node *x) const |
| This method calculates the cumulated size of all the nodes that are in the subtree that has "x" as head. | |
| PT_DocPosition | _calculateLeftSize (pf_Frag *pf) const |
| This method calculates the cumulated size of all the nodes that are in the left subtree that has pf_Frag * pf as head. | |
| void | delete_and_purge_tree (Node *node) |
| will delete the tree AND delete the fragments | |
| void | delete_tree (Node *node) |
| same as above BUT keep the fragments (as we don't own them | |
| const Node * | _next (const Node *pn) const |
| const Node * | _prev (const Node *pn) const |
| const Node * | _first () const |
| const Node * | _last () const |
| Node * | _next (Node *pn) |
| Node * | _prev (Node *pn) |
| Node * | _first () |
| Node * | _last () |
Private Attributes | |
| Node * | m_pLeaf |
| Node * | m_pRoot |
| size_t | m_nSize |
| PT_DocPosition | m_nDocumentSize |
Friends | |
| class | pf_Frag |
| class | Iterator |
| pf_Fragments::pf_Fragments | ( | ) |
References m_pLeaf, m_pRoot, and xxx_UT_DEBUGMSG.
| pf_Fragments::~pf_Fragments | ( | ) |
References delete_tree(), m_pLeaf, and m_pRoot.
| PT_DocPosition pf_Fragments::_calculateLeftSize | ( | pf_Frag * | pf | ) | const [private] |
This method calculates the cumulated size of all the nodes that are in the left subtree that has pf_Frag * pf as head.
Hopefully we *NEVER* need to call this method since this number should be stored in the pf_Frag. In the past this number has been corrupted by some bugs, fixed now. This function is here in case we need to recover from a new bug in the PieceTable.
This operation is performed in O(log(n)), where n is the number of nodes in the subtree.
pf_Frag * is a pointer to Fragment for which we wish to calculate the size of the left side of it's location within the tree.
References _calculateSize(), pf_Frag::_getNode(), pf_Fragments::Node::left, m_pLeaf, and UT_ASSERT.
Referenced by verifyDoc().
| PT_DocPosition pf_Fragments::_calculateSize | ( | Node * | x | ) | const [private] |
This method calculates the cumulated size of all the nodes that are in the subtree that has "x" as head.
This operation is performed in O(log(n)), where n is the number of nodes in the subtree.
x is the head of the subtree
References pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Fragments::Node::item, m_pLeaf, pf_Fragments::Node::right, and UT_ASSERT.
Referenced by _calculateLeftSize(), and fixSize().
| void pf_Fragments::_eraseFixup | ( | Node * | pn | ) | [private] |
References _leftRotate(), _rightRotate(), pf_Fragments::Node::black, pf_Fragments::Node::color, pf_Fragments::Node::left, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::red, and pf_Fragments::Node::right.
Referenced by erase().
| const pf_Fragments::Node * pf_Fragments::_first | ( | ) | const [private] |
References pf_Fragments::Node::left, m_pLeaf, and m_pRoot.
| pf_Fragments::Node * pf_Fragments::_first | ( | ) | [private] |
References pf_Fragments::Node::left, m_pLeaf, and m_pRoot.
| void pf_Fragments::_insertBST | ( | Node * | pn | ) | [private] |
| void pf_Fragments::_insertFixup | ( | Node * | pn | ) | [private] |
References _leftRotate(), _rightRotate(), pf_Fragments::Node::color, fixSize(), pf_Fragments::Node::left, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::red, pf_Fragments::Node::right, and UT_ASSERT.
Referenced by insertLeft(), and insertRight().
| const pf_Fragments::Node * pf_Fragments::_last | ( | ) | const [private] |
References m_pLeaf, m_pRoot, and pf_Fragments::Node::right.
| pf_Fragments::Node * pf_Fragments::_last | ( | ) | [private] |
References m_pLeaf, m_pRoot, and pf_Fragments::Node::right.
| void pf_Fragments::_leftRotate | ( | Node * | x | ) | [private] |
This method rotates a tree to the left.
Let be 2 & 4 nodes of a tree. Let be 1, 3, 5 subtrees. This operation performs the rotation that appears in the this ASCII picture:
2 4 / \ / \ 1 4 => 2 5 / \ / \ 3 5 1 3
x is the head of the tree (node 2 in the picture).
References pf_Frag::accLeftTreeLength(), pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Fragments::Node::item, pf_Fragments::Node::left, m_pLeaf, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::right, and xxx_UT_DEBUGMSG.
Referenced by _eraseFixup(), and _insertFixup().
| pf_Fragments::Node * pf_Fragments::_next | ( | Node * | pn | ) | [private] |
References _next().
| const pf_Fragments::Node * pf_Fragments::_next | ( | const Node * | pn | ) | const [private] |
References pf_Fragments::Node::left, m_pLeaf, pf_Fragments::Node::parent, pf_Fragments::Node::right, and UT_ASSERT.
| const pf_Fragments::Node * pf_Fragments::_prev | ( | const Node * | pn | ) | const [private] |
References pf_Fragments::Node::left, m_pLeaf, pf_Fragments::Node::parent, pf_Fragments::Node::right, and UT_ASSERT.
Referenced by _prev().
| pf_Fragments::Node * pf_Fragments::_prev | ( | Node * | pn | ) | [private] |
References _prev().
| void pf_Fragments::_rightRotate | ( | Node * | x | ) | [private] |
This method rotates a tree to the left.
Let be 2 & 4 nodes of a tree. Let be 1, 3, 5 subtrees. This operation performs the rotation that appears in the this ASCII picture:
4 2 / \ / \ 2 5 => 1 4 / \ / \ 1 3 3 5
x is the head of the tree (node 4 in the picture).
References pf_Frag::accLeftTreeLength(), pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Fragments::Node::item, pf_Fragments::Node::left, m_pLeaf, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::right, and xxx_UT_DEBUGMSG.
Referenced by _eraseFixup(), and _insertFixup().
| void pf_Fragments::appendFrag | ( | pf_Frag * | pf | ) |
References find(), pf_Frag::getNext(), pf_Frag::getType(), insertRight(), insertRoot(), m_pLeaf, m_pRoot, sizeDocument(), UT_return_if_fail, pf_Fragments::Iterator::value(), and xxx_UT_DEBUGMSG.
Referenced by pt_PieceTable::appendFmtMark(), pt_PieceTable::appendObject(), pt_PieceTable::appendSpan(), pt_PieceTable::appendStrux(), pt_PieceTable::setPieceTableState(), and TFTEST_MAIN().
| Iterator pf_Fragments::begin | ( | ) | [inline, private] |
| void pf_Fragments::changeSize | ( | int | delta | ) | [private] |
References m_nDocumentSize, and UT_ASSERT.
Referenced by pf_Frag::lengthChanged().
| void pf_Fragments::delete_and_purge_tree | ( | Node * | node | ) | [private] |
will delete the tree AND delete the fragments
References pf_Fragments::Node::item, pf_Fragments::Node::left, m_pLeaf, and pf_Fragments::Node::right.
Referenced by purgeFrags().
| void pf_Fragments::delete_tree | ( | Node * | node | ) | [private] |
same as above BUT keep the fragments (as we don't own them
References pf_Fragments::Node::left, m_pLeaf, and pf_Fragments::Node::right.
Referenced by ~pf_Fragments().
| PT_DocPosition pf_Fragments::documentPosition | ( | const Iterator | it | ) | const [private] |
References pf_Frag::getLeftTreeLength(), pf_Fragments::Iterator::getNode(), pf_Fragments::Iterator::is_valid(), pf_Fragments::Node::item, m_pRoot, and UT_ASSERT.
Referenced by pf_Frag::getPos().
| Iterator pf_Fragments::end | ( | void | ) | [inline, private] |
Referenced by pf_Frag::getNextStrux().
| void pf_Fragments::erase | ( | Iterator | it | ) | [private] |
Erase a piece from the tree.
This operation has the exceptional guarantee "no throw".
| it | iterator to the node to erase. |
References _eraseFixup(), _next(), pf_Frag::_setNode(), pf_Fragments::Node::black, pf_Fragments::Node::color, fixSize(), pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Fragments::Iterator::getNode(), pf_Fragments::Iterator::is_valid(), pf_Fragments::Node::item, pf_Fragments::Node::left, m_nDocumentSize, m_nSize, m_pLeaf, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::right, pf_Frag::setLeftTreeLength(), UT_ASSERT, UT_DEBUGMSG, xxx_UT_DEBUGMSG, and pf_Frag::zero().
Referenced by unlinkFrag().
| pf_Fragments::Iterator pf_Fragments::find | ( | PT_DocPosition | pos | ) | const |
References pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Fragments::Node::item, Iterator, pf_Fragments::Node::left, m_pLeaf, m_pRoot, pf_Fragments::Node::right, sizeDocument(), UT_ASSERT, UT_SHOULD_NOT_HAPPEN, verifyDoc(), and xxx_UT_DEBUGMSG.
Referenced by appendFrag(), findFirstFragBeforePos(), getFirst(), and getLast().
| pf_Frag * pf_Fragments::findFirstFragBeforePos | ( | PT_DocPosition | pos | ) | const |
Search the rb-tree to find the first frag before pos.
| PT_DocPosition | we want to find for. |
References find(), sizeDocument(), and pf_Fragments::Iterator::value().
Referenced by PD_DocIterator::_findFrag(), pt_PieceTable::_getStruxFromPosition(), pt_PieceTable::_realChangeSpanFmt(), pt_PieceTable::changeLastStruxFmtNoUndo(), and pt_PieceTable::getFragFromPosition().
| void pf_Fragments::fixSize | ( | Iterator | it | ) | [private] |
If the size of a tree's node changed, we should update the m_lengthLeft field of all its right parents.
This function does that fix. You should pass an iterator to the node that changed its size. It assumes that the sizes of the tree are all right except for a change in the size of the node passed as argument.
| it | Iterator to the node that changed its size |
References _calculateSize(), pf_Frag::getLeftTreeLength(), pf_Fragments::Iterator::getNode(), pf_Fragments::Iterator::is_valid(), pf_Fragments::Node::item, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::right, and UT_ASSERT.
Referenced by _insertFixup(), erase(), and pf_Frag::lengthChanged().
| pf_Frag * pf_Fragments::getFirst | ( | void | ) | const |
References find(), m_pLeaf, m_pRoot, and pf_Fragments::Iterator::value().
Referenced by pt_PieceTable::_fixHdrFtrReferences(), pt_PieceTable::_makeFmtMark(), pt_PieceTable::_makeObject(), pt_PieceTable::_tellAndMaybeAddListener(), pt_PieceTable::appendFmt(), pt_PieceTable::appendLastStruxFmt(), pt_PieceTable::appendSpan(), pt_PieceTable::appendStruxFmt(), pt_PieceTable::calcDocsize(), pt_PieceTable::changeLastStruxFmtNoUndo(), pt_PieceTable::createAndSendDocPropCR(), PD_Document::findBookmark(), PD_Document::findFragOfType(), PD_Document::findHdrFtrStrux(), PD_Document::findPreviousStyleStrux(), pt_PieceTable::fixMissingXIDs(), PD_Document::getAllUsedStyles(), PD_Document::getLastSectionMutableSDH(), PD_Document::getLastSectionSDH(), PD_Document::getLastStruxOfType(), PD_Document::hasMath(), pt_PieceTable::insertFmtMarkBeforeFrag(), pt_PieceTable::insertObjectBeforeFrag(), pt_PieceTable::insertSpanBeforeFrag(), PD_Document::miniDump(), pt_PieceTable::purgeFmtMarks(), PD_XMLIDCreator::rebuildCache(), PD_Document::removeListener(), PD_Document::removeStyle(), PD_Document::repairDoc(), TFTEST_MAIN(), PD_Document::updateDocForStyleChange(), PD_Document::updateFields(), verifyDoc(), and PD_Document::verifySectionID().
| pf_Frag * pf_Fragments::getLast | ( | ) | const |
References find(), m_pLeaf, m_pRoot, sizeDocument(), and pf_Fragments::Iterator::value().
Referenced by pt_PieceTable::_deleteHdrFtrsFromSectionStruxIfPresent(), pt_PieceTable::_deleteHdrFtrStruxWithNotify(), pt_PieceTable::_findNextHyperlink(), IE_Imp_Text::_insertBlock(), IE_Imp_Text::_writeHeader(), pt_PieceTable::appendLastStruxFmt(), pt_PieceTable::appendSpan(), pt_PieceTable::appendStrux(), PD_Document::areDocumentContentsEqual(), pt_PieceTable::deleteSpan(), PD_Document::findForwardStyleStrux(), PD_Document::findHdrFtrStrux(), PD_Document::getAllUsedStyles(), pt_PieceTable::getBounds(), PD_Document::getCellSDHFromRowCol(), PD_Document::getEndCellStruxFromCellSDH(), PD_Document::getEndTableStruxFromTableSDH(), PD_Document::getLastFrag(), PD_Document::getLastSectionMutableSDH(), PD_Document::getLastSectionSDH(), PD_Document::getLastStruxOfType(), PD_Document::getRowsColsFromTableSDH(), PD_Document::removeStyle(), PD_Document::repairDoc(), TFTEST_MAIN(), PD_Document::updateDocForStyleChange(), PD_Document::updateFields(), verifyDoc(), and PD_Document::verifySectionID().
References pf_Frag::_getNode(), pf_Frag::getPos(), pf_Frag::getType(), insertRight(), UT_return_if_fail, and xxx_UT_DEBUGMSG.
Referenced by pt_PieceTable::_deleteSpan(), pt_PieceTable::_fmtChangeSpan(), pt_PieceTable::_insertFmtMark(), pt_PieceTable::_insertObject(), pt_PieceTable::_insertSpan(), pt_PieceTable::_insertStrux(), pt_PieceTable::insertStruxNoUpdateBefore(), and TFTEST_MAIN().
References pf_Frag::_getNode(), pf_Frag::getType(), insertLeft(), UT_return_if_fail, and xxx_UT_DEBUGMSG.
Referenced by pt_PieceTable::insertFmtMarkBeforeFrag(), pt_PieceTable::insertObjectBeforeFrag(), pt_PieceTable::insertSpanBeforeFrag(), pt_PieceTable::insertStruxBeforeFrag(), and TFTEST_MAIN().
| pf_Fragments::Iterator pf_Fragments::insertLeft | ( | pf_Frag * | new_piece, | |
| Iterator | it | |||
| ) | [private] |
Insert a new piece to the left of a given node.
This operation has the exceptional guarantee strong.
| new_piece | the piece to insert | |
| it | iterator to the reference node |
References _insertFixup(), pf_Frag::_setNode(), pf_Frag::getLength(), pf_Fragments::Iterator::getNode(), pf_Fragments::Iterator::is_valid(), Iterator, pf_Fragments::Node::left, m_nDocumentSize, m_nSize, m_pLeaf, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::red, pf_Fragments::Node::right, pf_Frag::setLeftTreeLength(), UT_ASSERT, and xxx_UT_DEBUGMSG.
Referenced by insertFragBefore().
| pf_Fragments::Iterator pf_Fragments::insertRight | ( | pf_Frag * | new_piece, | |
| Iterator | it | |||
| ) | [private] |
Insert a new piece to the right of a given node.
This operation has the exceptional guarantee strong.
| new_piece | the piece to insert | |
| it | iterator to the reference node |
References _insertFixup(), pf_Frag::_setNode(), pf_Frag::getLength(), pf_Fragments::Iterator::getNode(), pf_Fragments::Iterator::is_valid(), Iterator, pf_Fragments::Node::left, m_nDocumentSize, m_nSize, m_pLeaf, m_pRoot, pf_Fragments::Node::parent, pf_Fragments::Node::red, pf_Fragments::Node::right, pf_Frag::setLeftTreeLength(), UT_ASSERT, and xxx_UT_DEBUGMSG.
Referenced by appendFrag(), insertFrag(), and insertRoot().
| pf_Fragments::Iterator pf_Fragments::insertRoot | ( | pf_Frag * | new_piece | ) | [private] |
Insert a new piece as the root of the tree.
The tree should be empty before performing this operation.
| new_piece | the piece to become root |
References insertRight().
Referenced by appendFrag().
| void pf_Fragments::purgeFrags | ( | ) |
References delete_and_purge_tree(), m_pLeaf, and m_pRoot.
Referenced by pt_PieceTable::~pt_PieceTable().
| size_t pf_Fragments::size | ( | ) | const [inline, private] |
| PT_DocPosition pf_Fragments::sizeDocument | ( | ) | const [inline, private] |
Referenced by appendFrag(), find(), findFirstFragBeforePos(), and getLast().
| void pf_Fragments::unlinkFrag | ( | pf_Frag * | pf | ) |
| void pf_Fragments::verifyDoc | ( | void | ) | const |
References _calculateLeftSize(), getFirst(), getLast(), pf_Frag::getLeftTreeLength(), pf_Frag::getLength(), pf_Frag::getNext(), pf_Frag::getPos(), pf_Frag::getType(), pf_Frag::setLeftTreeLength(), UT_ASSERT, and UT_DEBUGMSG.
Referenced by find().
friend class Iterator [friend] |
Referenced by find(), insertLeft(), and insertRight().
friend class pf_Frag [friend] |
PT_DocPosition pf_Fragments::m_nDocumentSize [private] |
Referenced by changeSize(), erase(), insertLeft(), and insertRight().
size_t pf_Fragments::m_nSize [private] |
Referenced by erase(), insertLeft(), and insertRight().
Node* pf_Fragments::m_pLeaf [private] |
Node* pf_Fragments::m_pRoot [private] |
Referenced by _eraseFixup(), _first(), _insertFixup(), _last(), _leftRotate(), _rightRotate(), appendFrag(), documentPosition(), erase(), find(), fixSize(), getFirst(), getLast(), insertLeft(), insertRight(), pf_Fragments(), purgeFrags(), and ~pf_Fragments().
1.7.1