// MultiCharMoveOp.cpp // // Author David Barrett-Lennard // (C)opyright Cedanet Pty Ltd 2006 #include "StdAfx.h" #include "Ceda/Core/cxUtils/PseudoRandom.h" #include "Ceda/Core/cxUtils/CedaAssert.h" #include "Ceda/Core/cxUtils/Tracer.h" #include "EffectsDoc.h" #include "MultiCharMoveOp.h" using namespace ceda; /////////////////////////////////////////////////////////////////////////////////////////////////// // MoveInterval MoveInterval::MoveInterval() : id(-1), e(0), si(-1), sq(-1), di(-1), dq(-1), prevX(NULL), nextX(NULL), prevI(NULL), nextI(NULL) { } bool MoveInterval::operator==(const MoveInterval& rhs) const { return id == rhs.id && e == rhs.e && si == rhs.si && sq == rhs.sq && di == rhs.di && dq == rhs.dq && str == rhs.str; } void MoveInterval::Write(xostream& os) const { os << '<' << id << '\'' << str << '\''; for (ssize_t i=0 ; i < e ; ++i) { os << '*'; } if (si) { os << si << ':'; } os << sq << "-->"; if (di) { os << di << ':'; } os << dq << '>'; } /////////////////////////////////////////////////////////////////////////////////////////////////// // MultiCharMoveOp MultiCharMoveOp::MultiCharMoveOp() { } MultiCharMoveOp::~MultiCharMoveOp() { Clear(); } MultiCharMoveOp::MultiCharMoveOp(const MultiCharMoveOp& rhs) { operator=(rhs); } MultiCharMoveOp& MultiCharMoveOp::operator=(const MultiCharMoveOp& rhs) { if (this != &rhs) { Clear(); m_opid = rhs.m_opid; for (MAP::const_iterator m2 = rhs.I.begin() ; m2 != rhs.I.end() ; ++m2) { const MoveInterval* i2 = m2->second; MoveInterval* first = NULL; MoveInterval* prev = NULL; MoveInterval* i1 = NULL; while(i2) { i1 = new MoveInterval(*i2); i1->prevI = NULL; i1->nextI = NULL; i1->prevX = NULL; i1->nextX = NULL; if (prev) prev->nextI = i1; else first = i1; i1->prevI = prev; prev = i1; i2 = i2->nextI; } I[first->di] = first; } BuildExtractionMap(); AssertValid(); cxAssert(*this == rhs); } return *this; } void MultiCharMoveOp::InsertExtraction(MoveInterval* i) { cxAssert(i->prevX == NULL); cxAssert(i->nextX == NULL); MAP::iterator mx = X.find(i->si); if (mx == X.end()) { X[i->si] = i; } else { // Scan for position where need to insert this extraction MoveInterval* px = NULL; MoveInterval* nx = mx->second; while(nx && nx->sq < i->sq) { px = nx; nx = nx->nextX; } // Insert i between px and nx i->prevX = px; i->nextX = nx; if (px) { px->nextX = i; } else { X[i->si] = i; } if (nx) nx->prevX = i; } } // Assuming all the insertions, build the extraction map void MultiCharMoveOp::BuildExtractionMap() { X.clear(); for (MAP::iterator m = I.begin() ; m != I.end() ; ++m) // for each document { MoveInterval* i = m->second; while(i) { InsertExtraction(i); i = i->nextI; } } } void MultiCharMoveOp::AssertValid() const { // Insertion positions must increase from left to right ssize_t numInsertions = 0; { for (MAP::const_iterator m = I.begin() ; m != I.end() ; ++m) { DocId di = m->first; const MoveInterval* i = m->second; ssize_t dq = 0; while(i) { cxAssert(i->di == di); cxAssert(dq <= i->dq); cxAssert(i->str.size() > 0); dq = i->dq + i->str.size(); ++numInsertions; i = i->nextI; } } } // Extraction positions must increase from left to right ssize_t numExtractions = 0; { for (MAP::const_iterator m = X.begin() ; m != X.end() ; ++m) { DocId si = m->first; const MoveInterval* x = m->second; ssize_t sq = 0; while(x) { cxAssert(x->si == si); cxAssert(sq <= x->sq); cxAssert(x->str.size() > 0); sq = x->sq + x->str.size(); ++numExtractions; x = x->nextX; } } } // Total number of extractions should match total number of insertions cxAssert(numInsertions == numExtractions); // Each extraction should be paired with an insertion and vice versa } bool MultiCharMoveOp::operator==(const MultiCharMoveOp& rhs) const { if (m_opid != rhs.m_opid) return false; if (I.size() != rhs.I.size()) return false; if (X.size() != rhs.X.size()) return false; MAP::const_iterator m1 = I.begin(); MAP::const_iterator m2 = rhs.I.begin(); while(m1 != I.end()) { cxAssert(m2 != rhs.I.end()); const MoveInterval* i1 = m1->second; const MoveInterval* i2 = m2->second; while(i1) { if (i2 == NULL) { return false; } if (*i1 != *i2) return false; i1 = i1->nextI; i2 = i2->nextI; } if (i2) return false; ++m1; ++m2; } cxAssert(m2 == rhs.I.end()); return true; } void MultiCharMoveOp::SetRandom(RandomInitSettings ris, const OpDocSet& ds, Opid opid) { cxAssert(opid.id >= 0); cxAssert(opid.t >= 0); m_opid = opid; ssize_t numDocs = ds.size(); cxAlwaysAssert(numDocs > 0); /* Generating a random multi-char move operation is quite challenging! To keep it simple we merely generate a single interval move. It is assumed that merging will allow us later to generate more complex operations. */ MoveInterval* mi = new MoveInterval; mi->id = opid.id; mi->e = 0; do { mi->si = GetUniformDistInteger_ssize_t(0,numDocs); mi->sq = ds[mi->si].SelectRandomInterval(mi->str); } while (mi->str.empty()); // Generate random location for where to put it mi->di = GetUniformDistInteger_ssize_t(0,numDocs); ssize_t nq = ds[mi->di].sizeq(); if (mi->si == mi->di) { if (GetUniformDistInteger_ssize_t(0,2)) { // Insert somewhere before the extraction string mi->dq = GetUniformDistInteger_ssize_t(0,mi->sq + 1); cxAssert(0 <= mi->dq && mi->dq <= mi->sq); // Extraction is in post-insertion coords mi->sq += mi->str.size(); } else { // Insert somewhere after the extraction string mi->dq = GetUniformDistInteger_ssize_t(mi->sq + mi->str.size(), nq+1); } } else { mi->dq = GetUniformDistInteger_ssize_t(0,nq+1); } X[mi->si] = mi; I[mi->di] = mi; AssertValid(); } void MultiCharMoveOp::Clear() { m_opid.id = -1; m_opid.t = 0; // Delete all the intervals for (MAP::iterator m = I.begin() ; m != I.end() ; ++m) { MoveInterval* i = m->second; while(i) { MoveInterval* n = i->nextI; delete i; i = n; } } I.clear(); X.clear(); } void MultiCharMoveOp::Do(EffectsDocSet& ds) const { // Do all the insertions { for (MAP::const_iterator m = I.begin() ; m != I.end() ; ++m) // for each document { DocId di = m->first; const MoveInterval* i = m->second; while(i) { cxAssert(i->di == di); ds[di].Insert(i->dq,i->str,i->e == 0); i = i->nextI; } } } // Do all the extractions { for (MAP::const_iterator m = X.begin() ; m != X.end() ; ++m) // for each document { DocId si = m->first; const MoveInterval* i = m->second; while(i) { cxAssert(i->si == si); cxAlwaysAssert(ds[si].IsPresent(i->sq, i->str)); if (i->e == 0) { ds[si].Remove(i->sq, i->str.size()); } i = i->nextX; } } } } void MultiCharMoveOp::Undo(EffectsDocSet& ds) const { cxAlwaysAssert(0); // todo } void MultiCharMoveOp::Write(xostream& os) const { os << '['; bool first = true; for (MAP::const_iterator m = I.begin() ; m != I.end() ; ++m) { DocId di = m->first; const MoveInterval* i = m->second; while(i) { cxAssert(i->di == di); if (first) first = false; else os << ','; os << *i; i = i->nextI; } } os << ']'; { os << '{'; bool first = true; for (MAP::const_iterator m = X.begin() ; m != X.end() ; ++m) { DocId si = m->first; const MoveInterval* i = m->second; while(i) { cxAssert(i->si == si); if (first) first = false; else os << ','; os << *i; i = i->nextX; } } os << '}'; } } void MultiCharMoveOp::SetNewExtractionPosition(MoveInterval* i, DocId si, ssize_t sq) { cxAssert(i); cxAssert(si >= 0); cxAssert(sq >= 0); //Tracer() << "Tracking " << *i << " src to q = " << sq << '\n'; MoveInterval* prev = i->prevX; MoveInterval* next = i->nextX; // First remove interval from its current location if (prev) { // Interval is not at the front of the linked list, so simply remove it from the chain cxAssert(prev->nextX == i); prev->nextX = next; if (next) { cxAssert(next->prevX == i); next->prevX = prev; } } else { // Interval is at the front of the linked list, so need to update the map cxAssert(X[i->si] == i); if (next) { X[i->si] = next; cxAssert(next->prevX == i); next->prevX = NULL; } else { X.erase(i->si); } } i->si = si; i->sq = sq; i->prevX = NULL; i->nextX = NULL; InsertExtraction(i); //Tracer() << "Now i = " << *i << '\n'; AssertValid(); } /* A MoveInterval may only split so that the left and right parts are non-empty. The original interval becomes the left interval, both in the linked list of insertions and the linked list of extractions. The right interval is allocated from the heap and inserted into both linked lists. Note therefore that we don't upset the map entries in the operation - in the case where the interval is the first in the linked list, it will remain the first interval in the list. */ void MultiCharMoveOp::SplitInterval(MoveInterval* i, ssize_t n1) { cxAssert(n1 > 0); ssize_t n2 = i->size() - n1; cxAssert(n2 > 0); MoveInterval* next = new MoveInterval; next->id = i->id; next->e = i->e; next->si = i->si; next->sq = i->sq + n1; next->di = i->di; next->dq = i->dq + n1; next->str = xstring(i->str.begin() + n1, i->str.end()); cxAssert(next->size() == n2); i->str.erase(i->str.begin() + n1, i->str.end()); cxAssert(i->size() == n1); next->prevI = i; next->prevX = i; next->nextI = i->nextI; next->nextX = i->nextX; if (i->nextI) { cxAssert(i->nextI->prevI == i); i->nextI->prevI = next; } if (i->nextX) { cxAssert(i->nextX->prevX == i); i->nextX->prevX = next; } i->nextI = next; i->nextX = next; AssertValid(); } void MultiCharMoveOp::MergeAdjacentIntervals() { for (MAP::const_iterator m = I.begin() ; m != I.end() ; ++m) { DocId di = m->first; MoveInterval* i1 = NULL; MoveInterval* i2 = m->second; while(i2) { cxAssert(i2->di == di); if (i1 != NULL && i1->id == i2->id && i1->e == i2->e && i1->dq + i1->size() == i2->dq && i1->si == i2->si && i1->sq + i1->size() == i2->sq) { cxAssert(i1->nextI == i2); cxAssert(i1->nextX == i2); cxAssert(i2->prevI == i1); cxAssert(i2->prevX == i1); i1->str += i2->str; MoveInterval* i3 = i2->nextI; i1->nextI = i3; if (i3) { cxAssert(i3->prevI == i2); i3->prevI = i1; } MoveInterval* x3 = i2->nextX; i1->nextX = x3; if (x3) { cxAssert(x3->prevX == i2); x3->prevX = i1; } delete i2; i2 = i3; } else { i1 = i2; i2 = i2->nextI; } } } } /////////////////////////////////////////////////////////////////////////////////////////////////// void IT(MultiCharMoveOp& O1, const MultiCharMoveOp& O2) { MultiCharMoveOp copyO2 = O2; DualIT(O1, copyO2); } void ET(MultiCharMoveOp& O1, const MultiCharMoveOp& O2) { MultiCharMoveOp copyO2 = O2; Transpose(copyO2, O1); } /////////////////////////////////////////////////////////////////////////////////////////////////// // DualIT void DualIT_ii(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { for (MultiCharMoveOp::MAP::iterator m1 = O1.I.begin() ; m1 != O1.I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = O2.I.find(m1->first); if (m2 != O2.I.end()) { ssize_t s1 = 0; // Accumulated characters inserted by O1 ssize_t s2 = 0; // Accumulated characters inserted by O2 MoveInterval* i1 = m1->second; MoveInterval* i2 = m2->second; while(i1 && i2) { cxAlwaysAssert(i1->id != i2->id); ssize_t d = (s1 + i2->dq) - (s2 + i1->dq); if (d < 0 || d == 0 && i2->id < i1->id) { // Process i2 i2->dq += s1; s2 += i2->size(); i2 = i2->nextI; } else { // Process i1 i1->dq += s2; s1 += i1->size(); i1 = i1->nextI; } } if (s1 != 0) { while (i2) { i2->dq += s1; i2 = i2->nextI; } } if (s2 != 0) { while (i1) { i1->dq += s2; i1 = i1->nextI; } } } } } /* This algorithm handles the dual IT of insertions with deletions. The following part of the algorithm for IT of single character operations is relevant: O1 O2 IT(O1,O2) ---------------------------------------------------------------------------------------------- ins del if (O1.di == O2.si && O1.dq <= O2.sq) ++O2.sq; In the following example, let O1 insert '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. O2 O1' a222bc22222d22ef ---> a***bc*****d**ef ---> a111*11**b11c*****d**ef11 [ ) [ ) [) [ ) [) [) [) O1 O2' a222bc22222d22ef ---> a11121122b11c22222d22ef11 ---> a111*11**b11c*****d**ef11 [ ) [) [) [) [) [) [ ) [) Notes * We scan left to right through O1 and O2. At each step we consider the next extraction interval from O2 and the next insertion position from O1 * We make sense of what is happening in the document state obtained after performing O1. In this state all characters are present. Coords mentioned in O1 are already relative to this state. Coords in O2 need to be shifted right by the number of characters inserted on the left by O1. * Extraction intervals may need to be split - i.e. when there are insertions within the interval */ void DualIT_id(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { MultiCharMoveOp::MAP& I = O1.I; MultiCharMoveOp::MAP& X = O2.X; for (MultiCharMoveOp::MAP::iterator m1 = I.begin() ; m1 != I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = X.find(m1->first); if (m2 != X.end()) { ssize_t shift = 0; // Accumulated shift from I MoveInterval* i = m1->second; MoveInterval* x = m2->second; while(i && x) { ssize_t d = i->dq - (shift + x->sq); if (d <= 0) { // [2222222) // 1 shift += i->size(); i = i->nextI; } else { if (d < x->size()) { // [222222) // 1 O2.SplitInterval(x,d); } // [2222222) // 1 x->sq += shift; x = x->nextX; } } if (shift) { while (x) { x->sq += shift; x = x->nextX; } } } } } // DualIT_dd needs to postpone the tracking of interval source positions to the other operations // destination position. Otherwise this interferes with the iteration through the source intervals struct SetNewExtractionPosCommand { SetNewExtractionPosCommand(MoveInterval* i, DocId si, ssize_t sq) : m_i(i), m_si(si), m_sq(sq) {} MoveInterval* m_i; DocId m_si; ssize_t m_sq; }; void ApplyNewExtractionPosCommands(MultiCharMoveOp& O, const xvector& N) { for (xvector::const_iterator i=N.begin() ; i != N.end() ; ++i) { //Tracer() << "Tracking " << *i->m_i << " src to q = " << i->m_sq << '\n'; O.SetNewExtractionPosition(i->m_i, i->m_si, i->m_sq); } } /* This algorithm handles the dual IT of extractions with extractions. The following part of the algorithm for IT is relevant: if (O1.si == O2.si && O1.sq == O2.sq) { if (O1.e == 0) { O2.si = O1.di; O2.sq = O1.dq; } if (O2.e == 0) { O1.si = O2.di; O1.sq = O2.dq; } if (O2.e < O1.e || O2.e == O1.e && O2.GetId() < O1.GetId()) ++O1.e; else ++O2.e; } As we scan left to right, we treat the extractions as intervals. There are a number of cases for processing the next two intervals. Eg they can be disjoint, partially overlap, coincide or one interval can contain the other. Where intervals are both enabled and overlap then the overlapping part needs to be disabled. This may require splitting of the intervals. Note that when comparing q-positions we never apply shifts, because deletions have no effect on the effects document. */ void DualIT_dd(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { MultiCharMoveOp::MAP& X1 = O1.X; MultiCharMoveOp::MAP& X2 = O2.X; xvector N1; xvector N2; for (MultiCharMoveOp::MAP::iterator m1 = X1.begin() ; m1 != X1.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = X2.find(m1->first); if (m2 != X2.end()) { MoveInterval* x1 = m1->second; MoveInterval* x2 = m2->second; while(x1 && x2) { if (x1->sq + x1->size() <= x2->sq) { // Next is [11111) x1 = x1->nextX; } else if (x2->sq + x2->size() <= x1->sq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (x1->sq < x2->sq) { // [1111111111111 // [2222222 O1.SplitInterval(x1, x2->sq - x1->sq); x1 = x1->nextX; } else if (x2->sq < x1->sq) { // [2222222222222 // [1111111 O2.SplitInterval(x2, x1->sq - x2->sq); x2 = x2->nextX; } cxAssert(x2->sq == x1->sq); if (x2->size() < x1->size()) { // [222222) // [111111111111) O1.SplitInterval(x1, x2->size()); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) O2.SplitInterval(x2, x1->size()); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); if (x1->e == 0) { N2.push_back(SetNewExtractionPosCommand(x2, x1->di, x1->dq)); // The act of calling SetNewExtractionPosition() upsets our iteration // over the source intervals. // Worse still, it upsets the iteration over the X1 map. //O2.SetNewExtractionPosition(x2, x1->di, x1->dq); } if (x2->e == 0) { N1.push_back(SetNewExtractionPosCommand(x1, x2->di, x2->dq)); //O1.SetNewExtractionPosition(x1, x2->di, x2->dq); } if (x2->e < x1->e || x2->e == x1->e && x2->id < x1->id) ++x1->e; else ++x2->e; x1 = x1->nextX; x2 = x2->nextX; } } } } ApplyNewExtractionPosCommands(O1,N1); ApplyNewExtractionPosCommands(O2,N2); } void DualIT(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { O1.AssertValid(); O2.AssertValid(); DualIT_ii(O1,O2); DualIT_id(O1,O2); DualIT_id(O2,O1); DualIT_dd(O1,O2); O1.MergeAdjacentIntervals(); O2.MergeAdjacentIntervals(); O1.AssertValid(); O2.AssertValid(); } /////////////////////////////////////////////////////////////////////////////////////////////////// // Transpose /* The transpose algorithm transforms [O1 O2] to [O2' O1']. This algorithm handles the transpose of deletions with insertions. The following part of the algorithm for transpose of single character move operations is relevant: if (O2.di == O1.si && O2.dq <= O1.sq) ++O1.sq; In the following example, let O1 delete '1' characters, and O2 insert '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. O1 O2 a111bc1111de1111 ---> a***bc****de**** ---> a*2222**b222c****d222e**222** [ ) [ ) [ ) [ ) [ ) [ ) [ ) O2' O1' a111bc1111de1111 ---> a1222211b222c1111d222e1122211 ---> a*2222**b222c****d222e**222** [ ) [ ) [ ) [ ) [) [) [ ) [) [) We make comparisons in the state corresponding to after the execution of O2. In this state q-positions of O1 are shifted right to include the effect of O2. q-positions of O2 do not need to be shifted for the purposes of comparison of q-position. As we scan left to right we compare the next interval from O1 (shifted right) against the next insertion position from O2. If necessary the interval from O1 may need to be split. */ void TransposeConcurrent_di(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { MultiCharMoveOp::MAP& X = O1.X; MultiCharMoveOp::MAP& I = O2.I; for (MultiCharMoveOp::MAP::iterator m1 = X.begin() ; m1 != X.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = I.find(m1->first); if (m2 != I.end()) { ssize_t shift = 0; // Accumulated shift from I MoveInterval* x = m1->second; MoveInterval* i = m2->second; while(x && i) { ssize_t d = i->dq - (shift + x->sq); if (d <= 0) { // [11111) // 2 shift += i->size(); i = i->nextI; } else { if (d < x->size()) { // [111111) // 2 O1.SplitInterval(x,d); } // [111111) // 2 x->sq += shift; x = x->nextX; } } if (shift) { while (x) { x->sq += shift; x = x->nextX; } } } } } /* The transpose algorithm transforms [O1 O2] to [O2' O1']. This algorithm handles the transpose of insertions with insertions. The following part of the algorithm for IT/ET of single character move operations is relevant: if (O1.di == O2.di) { if (O1.dq < O2.dq) --O2.dq; else ++O1.dq; } In the following example, let O1 insert '1' characters, and O2 insert '2' characters. O1 O2 abcdef ---> a111bc1111d11111ef ---> a222111b2222c1111d111112222e2222f [ ) [ ) [ ) [ ) [ ) [ ) [ ) We compare q-positions in the state obtained after execution of O2. For the purposed of comparison q-positions of O2 don't require adjustment. However q-positions of O2 need to the shifted to the right. */ void TransposeConcurrent_ii_1(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { for (MultiCharMoveOp::MAP::iterator m1 = O1.I.begin() ; m1 != O1.I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = O2.I.find(m1->first); if (m2 != O2.I.end()) { ssize_t s2 = 0; // Accumulated shift from O2 MoveInterval* i1 = m1->second; MoveInterval* i2 = m2->second; while(i1 && i2) { cxAlwaysAssert(i1->id != i2->id); if (i2->dq <= s2 + i1->dq) { // Process i2 s2 += i2->size(); i2 = i2->nextI; } else { // Process i1 i1->dq += s2; i1 = i1->nextI; } } if (s2) { while (i1) { i1->dq += s2; i1 = i1->nextI; } } } } } void TransposeConcurrent_ii_2(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { for (MultiCharMoveOp::MAP::iterator m1 = O1.I.begin() ; m1 != O1.I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = O2.I.find(m1->first); if (m2 != O2.I.end()) { ssize_t s1 = 0; // Accumulated shift from O1 MoveInterval* i1 = m1->second; MoveInterval* i2 = m2->second; while(i1 && i2) { cxAlwaysAssert(i1->id != i2->id); if (i1->dq + i1->size() <= i2->dq) { // Next is [11111) s1 += i1->size(); i1 = i1->nextI; } else if (i2->dq + i2->size() <= i1->dq) { // Next is [22222) i2->dq -= s1; i2 = i2->nextI; } else { // O1 || O2 so intervals shouldn't overlap cxAssert(0); } } if (s1) { while (i2) { i2->dq -= s1; i2 = i2->nextI; } } } } } /* The transpose algorithm transforms [O1 O2] to [O2' O1']. This algorithm handles the transpose of deletions with deletions. The following part of the algorithm for IT/ET of single character move operations is relevant: if (O1.si == O2.si && O1.sq == O2.sq || O1.di == O2.si && O1.dq == O2.sq) { if (O1.e == 0) { O2.si = O1.si; O2.sq = O1.sq; } if (O1.e < O2.e) --O2.e; else ++O1.e; cxAlwaysAssert(O2.e >= 0); if (O2.e == 0) { O1.si = O2.di; O1.sq = prev2dq; } } In the following example, let O1 delete '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. O1 O2 ab11112221111cd ---> ab****222****cd ---> ab***********cd O2' O1' ab11112221111cd ---> ab1111***1111cd ---> ab***********cd O2 may delete characters that have already been deleted by O1. In that case O2 should be disabled. For the purpose of comparing q-positions there is no need to shift positions because these operations have no impact on the effects document. As we scan left to right we compare the next interval from O1 against the next interval from O2. There are a number of cases to consider. */ void TransposeConcurrent_dd(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { xvector N1; xvector N2; { MultiCharMoveOp::MAP& X1 = O1.X; MultiCharMoveOp::MAP& X2 = O2.X; for (MultiCharMoveOp::MAP::iterator m1 = X1.begin() ; m1 != X1.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = X2.find(m1->first); if (m2 != X2.end()) { MoveInterval* x1 = m1->second; MoveInterval* x2 = m2->second; while(x1 && x2) { if (x1->sq + x1->size() <= x2->sq) { // Next is [11111) x1 = x1->nextX; } else if (x2->sq + x2->size() <= x1->sq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (x1->sq < x2->sq) { // [1111111111111 // [2222222 O1.SplitInterval(x1, x2->sq - x1->sq); x1 = x1->nextX; } else if (x2->sq < x1->sq) { // [2222222222222 // [1111111 O2.SplitInterval(x2, x1->sq - x2->sq); x2 = x2->nextX; } cxAssert(x2->sq == x1->sq); if (x2->size() < x1->size()) { // [222222) // [111111111111) O1.SplitInterval(x1, x2->size()); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) O2.SplitInterval(x2, x1->size()); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); //Tracer() << "\nSrc intervals x1=" << *x1 << " x2=" << *x2 << '\n'; cxAssert(x1->e > 0); if (x1->e < x2->e) --x2->e; else ++x1->e; cxAlwaysAssert(x2->e >= 0); if (x2->e == 0) { //Tracer() << "\nx2 enabled so x1 tracks to q = " << x2->dq << '\n'; N1.push_back(SetNewExtractionPosCommand(x1, x2->di, x2->dq)); } x1 = x1->nextX; x2 = x2->nextX; } } } } } { MultiCharMoveOp::MAP& I = O1.I; MultiCharMoveOp::MAP& X = O2.X; for (MultiCharMoveOp::MAP::iterator m1 = I.begin() ; m1 != I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = X.find(m1->first); if (m2 != X.end()) { MoveInterval* i1 = m1->second; MoveInterval* x2 = m2->second; while(i1 && x2) { //Tracer() << "\nTesting i1=" << *i1 << " x2=" << *x2 << '\n'; if (i1->dq + i1->size() <= x2->sq) { // Next is [11111) i1 = i1->nextI; } else if (x2->sq + x2->size() <= i1->dq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (i1->dq < x2->sq) { // [1111111111111 // [2222222 O1.SplitInterval(i1, x2->sq - i1->dq); i1 = i1->nextI; } else if (x2->sq < i1->dq) { // [2222222222222 // [1111111 O2.SplitInterval(x2, i1->dq - x2->sq); x2 = x2->nextX; } cxAssert(x2->sq == i1->dq); if (x2->size() < i1->size()) { // [222222) // [111111111111) O1.SplitInterval(i1, x2->size()); } else if (i1->size() < x2->size()) { // [111111) // [222222222222) O2.SplitInterval(x2, i1->size()); } // [111111) // [222222) cxAssert(i1->size() == x2->size()); //Tracer() << "\nSrc intervals i1=" << *i1 << " x2=" << *x2 << '\n'; cxAssert(i1->e == 0); N2.push_back(SetNewExtractionPosCommand(x2, i1->si, i1->sq)); if (i1->e < x2->e) --x2->e; else ++i1->e; cxAlwaysAssert(x2->e >= 0); if (x2->e == 0) { //Tracer() << "\nx2 enabled so i1 tracks to q = " << x2->dq << '\n'; N1.push_back(SetNewExtractionPosCommand(i1, x2->di, x2->dq)); } i1 = i1->nextI; x2 = x2->nextX; } } } } } ApplyNewExtractionPosCommands(O1,N1); ApplyNewExtractionPosCommands(O2,N2); } /* The transpose algorithm transforms [O1 O2] to [O2' O1']. This algorithm handles the transpose of insertions with deletions. The following part of the algorithm for IT/ET of single character move operations is relevant: if (O1.di == O2.si && O1.dq < O2.sq) --O2.sq; In the following example, let O1 insert '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. O1 [ ) [ ) [ ) O2 a222b22222cd22222e --> a2221111b11122222cd11122222e --> a***1111b111*****cd111*****e [ ) [ ) [ ) O2' O1' a222b22222cd22222e --> a***b*****cd*****e --> a***1111b111*****cd111*****e [ ) [ ) [ ) [ ) [ ) [ ) Note that q-positions are compared in the state just after executing O1. In this state q-positions can be directly compared without applying shifts. It is assume that O1 || O2, so therefore intervals never overlap - which would mean that a character inserted by O1 was deleted by O2. Intervals in O2 need to be shifted left. */ void TransposeConcurrent_id(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { MultiCharMoveOp::MAP& I = O1.I; MultiCharMoveOp::MAP& X = O2.X; for (MultiCharMoveOp::MAP::iterator m1 = I.begin() ; m1 != I.end() ; ++m1) { MultiCharMoveOp::MAP::iterator m2 = X.find(m1->first); if (m2 != X.end()) { ssize_t shift = 0; // Accumulated shift from I MoveInterval* i1 = m1->second; MoveInterval* x2 = m2->second; while(i1 && x2) { if (i1->dq + i1->size() <= x2->sq) { // Next is [11111) shift += i1->size(); //Tracer() << "Accum shift = " << shift << " from i1 = " << *i1 << '\n'; i1 = i1->nextI; } else if (x2->sq + x2->size() <= i1->dq) { // Next is [22222) //Tracer() << "Applying shift=" << shift << " to x2=" << *x2 << '\n'; x2->sq -= shift; x2 = x2->nextX; } else { // Intervals overlap if (i1->dq < x2->sq) { // [1111111111111 // [2222222 O1.SplitInterval(i1, x2->sq - i1->dq); i1 = i1->nextI; } else if (x2->sq < i1->dq) { // [2222222222222 // [1111111 O2.SplitInterval(x2, i1->dq - x2->sq); x2 = x2->nextX; } cxAssert(x2->sq == i1->dq); if (x2->size() < i1->size()) { // [222222) // [111111111111) O1.SplitInterval(i1, x2->size()); } else if (i1->size() < x2->size()) { // [111111) // [222222222222) O2.SplitInterval(x2, i1->size()); } // [111111) // [222222) cxAssert(i1->size() == x2->size()); //Tracer() << "Intervals overlap : i = " << *i1 << " x = " << *x2 << '\n'; //Tracer() << " Applying shift=" << shift << " to x2=" << *x2 << '\n'; x2->sq -= shift; x2 = x2->nextX; //Tracer() << " Accum shift = " << shift << " from i1 = " << *i1 << '\n'; i1 = i1->nextI; } } if (shift) { while (x2) { //Tracer() << "Applying shift=" << shift << " to x2=" << *x2 << '\n'; x2->sq -= shift; x2 = x2->nextX; } } } } } /* cxAlwaysAssert(O1.GetId() != O2.GetId()); ssize_t prev2dq = O2.dq; if (O2.di == O1.si && O2.dq <= O1.sq) ++O1.sq; if (O1.di == O2.di) { if (O1.dq < O2.dq) --O2.dq; else ++O1.dq; } if (O1.si == O2.si && O1.sq == O2.sq || O1.di == O2.si && O1.dq == O2.sq) { if (O1.e == 0) { O2.si = O1.si; O2.sq = O1.sq; } if (O1.e < O2.e) --O2.e; else ++O1.e; cxAlwaysAssert(O2.e >= 0); if (O2.e == 0) { O1.si = O2.di; O1.sq = prev2dq; } } if (O1.di == O2.si && O1.dq < O2.sq) --O2.sq; */ void Transpose(MultiCharMoveOp& O1, MultiCharMoveOp& O2) { cxAlwaysAssert(O1.GetId() != O2.GetId()); O1.AssertValid(); O2.AssertValid(); TransposeConcurrent_di(O1,O2); //Tracer() << "After di O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); TransposeConcurrent_ii_1(O1,O2); //Tracer() << "After ii1 O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); TransposeConcurrent_dd(O1,O2); //Tracer() << "After dd O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); TransposeConcurrent_id(O1,O2); //Tracer() << "After id O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); TransposeConcurrent_ii_2(O1,O2); //Tracer() << "After ii2 O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); O1.MergeAdjacentIntervals(); O2.MergeAdjacentIntervals(); //Tracer() << "After merge O1 = " << O1 << " O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); } /////////////////////////////////////////////////////////////////////////////////////////////////// // Merge void Merge(MultiCharMoveOp& O1, const MultiCharMoveOp& O2) { cxAssert(0); }