// MultiCharCDMOp.cpp // // Author David Barrett-Lennard // (C)opyright Cedanet Pty Ltd 2007 #include "StdAfx.h" #include "Ceda/Core/cxUtils/PseudoRandom.h" #include "Ceda/Core/cxUtils/CedaAssert.h" #include "Ceda/Core/cxUtils/Tracer.h" #include "MidEffectsDoc.h" #include "MultiCharCDMOp.h" xchar GetCycledLowercaseChar(); using namespace ceda; /////////////////////////////////////////////////////////////////////////////////////////////////// // CDMCreateInterval CDMCreateInterval::CDMCreateInterval() : idoc(-1), iq(-1), prevI(NULL), nextI(NULL) { } bool CDMCreateInterval::operator==(const CDMCreateInterval& rhs) const { return opid == rhs.opid && str == rhs.str && idoc == rhs.idoc && iq == rhs.iq; } void CDMCreateInterval::AssertValid() const { cxAssert(size() > 0); cxAssert(idoc >= 0); cxAssert(iq >= 0); } void CDMCreateInterval::Write(xostream& os) const { os << opid << 'C' << '\'' << str << '\''; if (idoc) os << idoc << ':'; os << iq; } /////////////////////////////////////////////////////////////////////////////////////////////////// // CDMDeleteInterval CDMDeleteInterval::CDMDeleteInterval() : xdoc(-1), xq(-1), prevX(NULL), nextX(NULL) { } bool CDMDeleteInterval::operator==(const CDMDeleteInterval& rhs) const { return opid == rhs.opid && xdoc == rhs.xdoc && xq == rhs.xq && str == rhs.str; } void CDMDeleteInterval::AssertValid() const { cxAssert(size() > 0); cxAssert(xdoc >= 0); cxAssert(xq >= 0); } void CDMDeleteInterval::Write(xostream& os) const { os << opid << 'D' << '\'' << str << '\''; if (xdoc) os << xdoc << ':'; os << xq; } /////////////////////////////////////////////////////////////////////////////////////////////////// // CDMMoveInterval CDMMoveInterval::CDMMoveInterval() : e(-1), xdoc(-1), xq(-1), idoc(-1), iq(-1), prevX(NULL), nextX(NULL), prevI(NULL), nextI(NULL) { } bool CDMMoveInterval::operator==(const CDMMoveInterval& rhs) const { return opid == rhs.opid && e == rhs.e && xdoc == rhs.xdoc && xq == rhs.xq && idoc == rhs.idoc && iq == rhs.iq && str == rhs.str; } void CDMMoveInterval::AssertValid() const { cxAssert(size() > 0); cxAssert(e >= 0); cxAssert(xdoc >= 0); cxAssert(xq >= 0); cxAssert(idoc >= 0); cxAssert(iq >= 0); } void CDMMoveInterval::Write(xostream& os) const { os << opid << 'M' << '\'' << str << '\''; for (ssize_t i=0 ; i < e ; ++i) os << '*'; if (xdoc) os << xdoc << ':'; os << xq; os << "-->"; if (idoc) os << idoc << ':'; os << iq; } /////////////////////////////////////////////////////////////////////////////////////////////////// // SplitInterval() /* A CDMCreateInterval may only split so that the left and right parts are non-empty. The original interval becomes the left interval. The right interval is allocated from the heap and inserted into the linked list. Note that by tranferring identity of the interval to the left piece, splitting never causes the pointer to the first interval in the linked list to need to be updated. */ void SplitInterval(CDMCreateInterval* r1, ssize_t n1) { cxAssert(r1); cxAssert(n1 > 0); ssize_t n2 = r1->size() - n1; cxAssert(n2 > 0); CDMCreateInterval* r2 = new CDMCreateInterval; r2->opid = r1->opid; // Split the string r2->str.assign(r1->str.begin() + n1, r1->str.end()); cxAssert(r2->size() == n2); r1->str.erase(r1->str.begin() + n1, r1->str.end()); cxAssert(r1->size() == n1); r2->idoc = r1->idoc; r2->iq = r1->iq + n1; r2->prevI = r1; r2->nextI = r1->nextI; if (r1->nextI) { cxAssert(r1->nextI->prevI == r1); r1->nextI->prevI = r2; } r1->nextI = r2; } /* A CDMDeleteInterval may only split so that the left and right parts are non-empty. The original interval becomes the left interval. The right interval is allocated from the heap and inserted into the linked list. Note that by tranferring identity of the interval to the left piece, splitting never causes the pointer to the first interval in the linked list to need to be updated. Delete intervals can overlap (or alias). For example [-------) [----------------) [----) [-------) [----) [-------) [-------) [-------) | | split here --> need to split all the aliasing intervals. [--)[---) [----------------) [----) [--)[---) [--)[---) [--)[---) [--)[---) */ CDMDeleteInterval* SplitInterval(CDMDeleteInterval* r1, ssize_t n1, bool scanFirst = true) { cxAssert(r1); cxAssert(n1 > 0); //Tracer() << "Splitting r1 = " << *r1 << " n1 = " << n1 << '\n'; ssize_t n2 = r1->size() - n1; cxAssert(n2 > 0); // Walk backwards amongst the list of deletions so that r1 points at the first in the group of // aliasing deletions if (scanFirst) { CDMDeleteInterval* px; while( (px = r1->prevX) != NULL && px->xq == r1->xq) { cxAssert(px->str == r1->str); r1 = px; } } // Walk forwards through the aliasing intervals, splitting each interval into two pieces, left // and right. // The existing linked list of aliasing intervals become the left intervals. // Create the right linked list as we go. We don't tie them together until the end // // [--)[--f2--) // [--)[------) // [--)[--px2-) // [x1)[--x2--) // [--)[------) // [--)[------) CDMDeleteInterval* f2 = NULL; // Ptr to first right CDMDeleteInterval* x1 = r1; // Ptr to current left CDMDeleteInterval* x2 = NULL; // Ptr to current right CDMDeleteInterval* px2 = NULL; // Ptr to previous right #ifdef _DEBUG const xstring str = x1->str; #endif while(1) { cxAssert(x1); //Tracer() << "Splitting x1 = " << *x1 << '\n'; // Split x1 into [x1 x2] { x2 = new CDMDeleteInterval; // Record the first x2 if (!f2) f2 = x2; x2->opid = x1->opid; // Split the string x2->str.assign(x1->str.begin() + n1, x1->str.end()); cxAssert(x2->size() == n2); x1->str.erase(x1->str.begin() + n1, x1->str.end()); cxAssert(x1->size() == n1); x2->xdoc = x1->xdoc; x2->xq = x1->xq + n1; //Tracer() << " ---> x1 = " << *x1 << " x2 = " << *x2 << '\n'; // Connect up x2's into their own linked list if (px2) px2->nextX = x2; x2->prevX = px2; px2 = x2; } // Step to next interval in the alising group, if any CDMDeleteInterval* nx1 = x1->nextX; if (nx1 == NULL || nx1->xq != x1->xq) break; //Tracer() << " x1 = " << *x1 << " nx1 = " << *nx1 << '\n'; cxAssert(nx1->str == str); x1 = nx1; } cxAssert(x1); // last x1 cxAssert(f2); // first x2 cxAssert(x2); // last x2 f2->prevX = x1; x2->nextX = x1->nextX; if (x1->nextX) { cxAssert(x1->nextX->prevX == x1); x1->nextX->prevX = x2; } x1->nextX = f2; return f2; } /* A CDMMoveInterval 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 that by tranferring identity of the interval to the left piece, splitting never causes the pointer to the first interval in the extraction or insertion linked lists to need to be updated. [allowing for aliasing extractions] [-------) [----------------) [----) [-------) [----) [-------) [-------) [-------) | | split here --> need to split all the aliasing extractions. [--)[---) [----------------) [----) [--)[---) [--)[---) [--)[---) [--)[---) It must be remembered that the given interval may have been encountered while iterating through a linked list of insertions, and therefore may correspond to any one of the aliasing intervals in the set of extractions. */ CDMMoveInterval* SplitInterval(CDMMoveInterval* r1, ssize_t n1, bool scanFirst = true) { cxAssert(r1); cxAssert(n1 > 0); ssize_t n2 = r1->size() - n1; cxAssert(n2 > 0); /* todo. The walk backwards idea can be problematic. In a case of merging move operations it was found that when IT(x1,i2) is performed, the shift applied to previous extractions makes then appear to alias with subsequent extractions that we need to split. */ // Walk backwards amongst the list of extractions to find the first in the group of aliasing // extractions if (scanFirst) { CDMMoveInterval* px; while( (px = r1->prevX) != NULL && px->xq == r1->xq) { //Tracer() << "Stepping back from r1 = " << *r1 << " to px = " << *px << '\n'; cxAssert(px->str == r1->str); r1 = px; } } // Walk forwards, splitting each interval in the group of aliasing extractions. // Create two independent linked lists as we go. We don't tie them together until the end // // [--)[--f2--) // [--)[------) // [--)[--px2-) // [x1)[--x2--) // [--)[------) // [--)[------) CDMMoveInterval* f2 = NULL; CDMMoveInterval* x1 = r1; CDMMoveInterval* x2 = NULL; CDMMoveInterval* px2 = NULL; #ifdef _DEBUG const xstring str = x1->str; #endif while(1) { cxAssert(x1); // Split x1 into [x1 x2] { x2 = new CDMMoveInterval; // Record the first x2 if (!f2) f2 = x2; x2->opid = x1->opid; x2->e = x1->e; // Split the string x2->str.assign(x1->str.begin() + n1, x1->str.end()); cxAssert(x2->size() == n2); x1->str.erase(x1->str.begin() + n1, x1->str.end()); cxAssert(x1->size() == n1); x2->idoc = x1->idoc; x2->iq = x1->iq + n1; x2->prevI = x1; x2->nextI = x1->nextI; if (x1->nextI) { cxAssert(x1->nextI->prevI == x1); x1->nextI->prevI = x2; } x1->nextI = x2; x2->xdoc = x1->xdoc; x2->xq = x1->xq + n1; // Note that the x1's already form a linked list // Connect up x2's into their own linked list if (px2) px2->nextX = x2; x2->prevX = px2; px2 = x2; } // Step to next interval in the alising group, if any CDMMoveInterval* nx1 = x1->nextX; if (nx1 == NULL || nx1->xq != x1->xq) break; cxAssert(nx1->str == str); x1 = nx1; } cxAssert(x1); // last x1 cxAssert(f2); // first x2 cxAssert(x2); // last x2 f2->prevX = x1; x2->nextX = x1->nextX; if (x1->nextX) { cxAssert(x1->nextX->prevX == x1); x1->nextX->prevX = x2; } x1->nextX = f2; return f2; } /////////////////////////////////////////////////////////////////////////////////////////////////// // MultiCharCDMOp MultiCharCDMOp::MultiCharCDMOp() { } MultiCharCDMOp::~MultiCharCDMOp() { Clear(); } MultiCharCDMOp::MultiCharCDMOp(const MultiCharCDMOp& rhs) { operator=(rhs); } void MultiCharCDMOp::Clear() { m_opid.id = -1; m_opid.t = 0; for (MAP::iterator m = m_map.begin() ; m != m_map.end() ; ++m) { CDMDocIntervals& di = m->second; // Creations { CDMCreateInterval* r = di.c; while(r) { CDMCreateInterval* n = r->nextI; delete r; r = n; } } // Deletes { CDMDeleteInterval* r = di.d; while(r) { CDMDeleteInterval* n = r->nextX; delete r; r = n; } } // Moves { CDMMoveInterval* r = di.i; while(r) { CDMMoveInterval* n = r->nextI; delete r; r = n; } } } m_map.clear(); } MultiCharCDMOp& MultiCharCDMOp::operator=(const MultiCharCDMOp& rhs) { if (this != &rhs) { Clear(); m_opid = rhs.m_opid; // Map associated with isomorphism between original (rhs) and the copy (*this). // Maps from old CDMMoveInterval pointer to new CDMMoveInterval pointer typedef std::map PMAP; PMAP pMap; // Copy all the creations and deletions and connect them up in their double linked lists. // Copy all the moves and connect them up in their double linked list of insertions. for (MAP::const_iterator m2 = rhs.m_map.begin() ; m2 != rhs.m_map.end() ; ++m2) { const CDMDocIntervals& di2 = m2->second; CDMDocIntervals di1; // Copy linked list of creations { const CDMCreateInterval* r2 = di2.c; CDMCreateInterval* prevr1 = NULL; CDMCreateInterval* r1 = NULL; while(r2) { r1 = new CDMCreateInterval(*r2); r1->prevI = prevr1; r1->nextI = NULL; if (prevr1) prevr1->nextI = r1; else di1.c = r1; prevr1 = r1; r2 = r2->nextI; } } // Copy linked list of deletions { const CDMDeleteInterval* r2 = di2.d; CDMDeleteInterval* prevr1 = NULL; CDMDeleteInterval* r1 = NULL; while(r2) { r1 = new CDMDeleteInterval(*r2); r1->prevX = prevr1; r1->nextX = NULL; if (prevr1) prevr1->nextX = r1; else di1.d = r1; prevr1 = r1; r2 = r2->nextX; } } // Copy linked list of insertions { const CDMMoveInterval* r2 = di2.i; CDMMoveInterval* prevr1 = NULL; CDMMoveInterval* r1 = NULL; while(r2) { r1 = new CDMMoveInterval(*r2); pMap[r2] = r1; r1->prevI = prevr1; r1->nextI = NULL; // These will be filled in later using the map r1->prevX = NULL; r1->nextX = NULL; if (prevr1) prevr1->nextI = r1; else di1.i = r1; prevr1 = r1; r2 = r2->nextI; } } m_map[m2->first] = di1; } // Use map to fix all the prevX, nextX pointers and initialise each di1.x for (MAP::const_iterator m2 = rhs.m_map.begin() ; m2 != rhs.m_map.end() ; ++m2) { const CDMDocIntervals& di2 = m2->second; CDMDocIntervals& di1 = m_map[m2->first]; const CDMMoveInterval* r2 = di2.x; CDMMoveInterval* prevr1 = NULL; CDMMoveInterval* r1 = NULL; while(r2) { r1 = pMap[r2]; r1->prevX = prevr1; cxAssert(r1->nextX == NULL); if (prevr1) prevr1->nextX = r1; else di1.x = r1; prevr1 = r1; r2 = r2->nextX; } } AssertValid(); cxAssert(*this == rhs); } return *this; } void MultiCharCDMOp::AssertValid() const { ssize_t numMoveInsertions = 0; ssize_t numMoveExtractions = 0; for (MAP::const_iterator m = m_map.begin() ; m != m_map.end() ; ++m) { DocId doc = m->first; const CDMDocIntervals& di = m->second; // Creation positions must increase from left to right { const CDMCreateInterval* r = di.c; ssize_t q = 0; while(r) { r->AssertValid(); cxAssert(r->idoc == doc); cxAssert(q <= r->iq); q = r->iq + r->size(); r = r->nextI; } } // Delete positions must alias or else increase from left to right { const CDMDeleteInterval* p = NULL; const CDMDeleteInterval* n = di.d; ssize_t q = 0; while(n) { n->AssertValid(); cxAssert(n->xdoc == doc); if (p && p->xq == n->xq) { // Next interval is allowed to exactly alias the previous interval cxAssert(p->str == n->str); cxAssert(q = n->xq + n->size()); // Siteids must not decrease cxAssert(p->opid.id <= n->opid.id); } else { cxAssert(q <= n->xq); q = n->xq + n->size(); } p = n; n = n->nextX; } } // Move insertion positions must increase from left to right { const CDMMoveInterval* r = di.i; ssize_t q = 0; while(r) { r->AssertValid(); cxAssert(r->idoc == doc); ++numMoveInsertions; cxAssert(q <= r->iq); q = r->iq + r->size(); r = r->nextI; } } // Move extraction positions must alias or else increase from left to right { const CDMMoveInterval* p = NULL; const CDMMoveInterval* n = di.x; ssize_t q = 0; while(n) { n->AssertValid(); cxAssert(n->xdoc == doc); ++numMoveExtractions; if (p && p->xq == n->xq) { // Next interval is allowed to exactly alias the previous interval cxAssert(p->str == n->str); cxAssert(q = n->xq + n->size()); // e-coordinates must strictly increase cxAssert(p->e < n->e); } else { cxAssert(q <= n->xq); q = n->xq + n->size(); } p = n; n = n->nextX; } } } // For move operations, total number of extractions should match total number of insertions cxAssert(numMoveInsertions == numMoveExtractions); // todo: Each move extraction should be paired with a move insertion and vice versa } bool MultiCharCDMOp::operator==(const MultiCharCDMOp& rhs) const { if (m_opid != rhs.m_opid) return false; // Note that this test depends on removal of redundant entries in the map if (m_map.size() != rhs.m_map.size()) return false; { MAP::const_iterator m1 = m_map.begin(); MAP::const_iterator m2 = rhs.m_map.begin(); while(m1 != m_map.end()) { cxAssert(m2 != rhs.m_map.end()); if (m1->first != m2->first) return false; const CDMDocIntervals& di1 = m1->second; const CDMDocIntervals& di2 = m2->second; // Compare creations { const CDMCreateInterval* r1 = di1.c; const CDMCreateInterval* r2 = di2.c; while(r1) { if (!r2 || *r1 != *r2) return false; r1 = r1->nextI; r2 = r2->nextI; } if (r2) return false; } // Compare deletions { const CDMDeleteInterval* r1 = di1.d; const CDMDeleteInterval* r2 = di2.d; while(r1) { if (!r2 || *r1 != *r2) return false; r1 = r1->nextX; r2 = r2->nextX; } if (r2) return false; } // Compare move insertions { const CDMMoveInterval* r1 = di1.i; const CDMMoveInterval* r2 = di2.i; while(r1) { if (!r2 || *r1 != *r2) return false; r1 = r1->nextI; r2 = r2->nextI; } if (r2) return false; } // Compare move extractions { const CDMMoveInterval* r1 = di1.x; const CDMMoveInterval* r2 = di2.x; while(r1) { if (!r2 || *r1 != *r2) return false; r1 = r1->nextX; r2 = r2->nextX; } if (r2) return false; } ++m1; ++m2; } cxAssert(m2 == rhs.m_map.end()); } return true; } enum EIntervalType { IT_CREATE, IT_DELETE, IT_MOVE }; void MultiCharCDMOp::SetAtomicRandom(RandomInitSettings ris, const MidEffectsDocSet& ds, Opid opid) { cxAssert(opid.id >= 0); cxAssert(opid.t >= 0); m_opid = opid; /* 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. */ ssize_t numDocs = ds.size(); cxAlwaysAssert(numDocs > 0); EIntervalType type; if (ds.HasCharsThatExist()) { type = (EIntervalType) GetUniformDistInteger_ssize_t(0,3); } else { type = IT_CREATE; } if (type == IT_CREATE) { CDMCreateInterval* r = new CDMCreateInterval; r->opid = opid; // Choose random string to be created ssize_t n = GetUniformDistInteger_ssize_t(1,4); cxAssert(r->str.empty()); for (ssize_t i=0 ; i < n ; ++i) { r->str += GetCycledLowercaseChar(); } // Choose random destination position r->idoc = GetUniformDistInteger_ssize_t(0,numDocs); r->iq = GetUniformDistInteger_ssize_t(0,ds[r->idoc].sizeq() + 1); m_map[r->idoc].c = r; } else if (type == IT_DELETE) { CDMDeleteInterval* r = new CDMDeleteInterval; r->opid = opid; do { r->xdoc = GetUniformDistInteger_ssize_t(0,numDocs); r->xq = ds[r->xdoc].SelectRandomInterval(r->str); } while (r->str.empty()); m_map[r->xdoc].d = r; } else { cxAssert(type == IT_MOVE); CDMMoveInterval* r = new CDMMoveInterval; r->opid = opid; r->e = 0; // Choose random extraction interval do { r->xdoc = GetUniformDistInteger_ssize_t(0,numDocs); r->xq = ds[r->xdoc].SelectRandomInterval(r->str); } while (r->str.empty()); // Choose random destination location r->idoc = GetUniformDistInteger_ssize_t(0,numDocs); ssize_t nq = ds[r->idoc].sizeq(); if (r->xdoc == r->idoc) { if (GetUniformDistInteger_ssize_t(0,2)) { // Insert somewhere before the extraction string r->iq = GetUniformDistInteger_ssize_t(0,r->xq + 1); cxAssert(0 <= r->iq && r->iq <= r->xq); // Extraction is in post-insertion coords r->xq += r->size(); } else { // Insert somewhere after the extraction string r->iq = GetUniformDistInteger_ssize_t(r->xq + r->size(), nq + 1); } } else { r->iq = GetUniformDistInteger_ssize_t(0,nq + 1); } m_map[r->xdoc].x = r; m_map[r->idoc].i = r; } AssertValid(); } void MultiCharCDMOp::SetRandom(RandomInitSettings ris, const MidEffectsDocSet& ds, Opid opid) { cxAssert(opid.id >= 0); cxAssert(opid.t >= 0); m_opid = opid; cxAssert(0 <= ris.m_minAtomic); cxAssert(ris.m_minAtomic <= ris.m_maxAtomic); if (ris.m_minAtomic == 1 && ris.m_maxAtomic == 1) { SetAtomicRandom(ris,ds,opid); } else { // Build composite ops using the merge of atomic ops ssize_t n = GetUniformDistInteger_ssize_t(ris.m_minAtomic, ris.m_maxAtomic+1); MidEffectsDocSet dst = ds; Clear(); m_opid = opid; for (ssize_t i=0 ; i < n ; ++i) { MultiCharCDMOp O2; O2.SetAtomicRandom(ris,dst,opid); Merge(*this,O2); O2.Do(dst); } } } void MultiCharCDMOp::Write(xostream& os) const { os << '{'; bool first = true; for (MAP::const_iterator m = m_map.begin() ; m != m_map.end() ; ++m) { DocId doc = m->first; const CDMDocIntervals& di = m->second; /* if (doc) { os << doc << ':'; } */ // Creations { const CDMCreateInterval* r = di.c; while(r) { if (first) first = false; else os << ','; os << *r; r = r->nextI; } } // Deletions { const CDMDeleteInterval* r = di.d; while(r) { if (first) first = false; else os << ','; os << *r; r = r->nextX; } } // Insertions { const CDMMoveInterval* r = di.i; while(r) { if (first) first = false; else os << ','; os << *r; r = r->nextI; } } /* // Extractions { const CDMMoveInterval* r = di.x; while(r) { if (first) first = false; else os << ','; os << *r; r = r->nextX; } } */ } os << '}'; } void MultiCharCDMOp::Do(MidEffectsDocSet& ds) const { /* It would appear important for move extractions to be expressed in post-move-insertion coordinates. The difficulty is with transferring the deletion status for enabled move operations. This requires reading of the deletion flags in the extraction interval and transferring the flags values to the insertion interval. That's not easy unless extractions and insertions are expressed in the same coordinate system. It is important for all move insertions to have been applied in all documents before beginning the extractions. I.e. we clearly distinguish two phases at the level of the entire operation rather than on merely a single document at a time. */ for (MAP::const_iterator m = m_map.begin() ; m != m_map.end() ; ++m) { DocId doc = m->first; const CDMDocIntervals& di = m->second; // Do creations { const CDMCreateInterval* r = di.c; while(r) { cxAssert(r->idoc == doc); // Insert characters that have present = true, deleted = false ds[doc].Insert(r->iq,r->str,true); r = r->nextI; } } // Do deletions { const CDMDeleteInterval* r = di.d; while(r) { cxAssert(r->xdoc == doc); // Characters to be deleted must be marked as present cxAssert(ds[doc].IsPresent(r->xq, r->str)); // Set deleted = true on each character (if not already) ssize_t n = r->size(); for (ssize_t j=0 ; j < n ; ++j) { ssize_t q = r->xq + j; ds[doc].SetDeleted(q, true); } r = r->nextX; } } // Do move insertions { const CDMMoveInterval* r = di.i; while(r) { cxAssert(r->idoc == doc); ds[doc].Insert(r->iq,r->str,r->e == 0); r = r->nextI; } } } // Move extractions must be done in a separate phase! for (MAP::const_iterator m = m_map.begin() ; m != m_map.end() ; ++m) { DocId doc = m->first; const CDMDocIntervals& di = m->second; // Do move extractions { #ifdef _DEBUG const CDMMoveInterval* r1 = NULL; #endif const CDMMoveInterval* r2 = di.x; while(r2) { cxAssert(r2->xdoc == doc); #ifdef _DEBUG if (!r1 || r2->xq != r1->xq) { // Characters to be extracted must be marked as present, whether the move is // enabled or not. cxAssert(ds[doc].IsPresent(r2->xq, r2->str)); } #endif if (r2->e == 0) { ssize_t n = r2->size(); // Move is enabled, so mark characters as no longer present in the effects // document ds[doc].Remove(r2->xq,n); // Move the deleted status to the new location. This is straightforward // because move extractions are expressed in post insertion coordinates for (ssize_t j=0 ; j < n ; ++j) { ssize_t xq = r2->xq + j; ssize_t iq = r2->iq + j; if (ds[doc].IsDeleted(xq)) { ds[doc].SetDeleted(xq, false); ds[r2->idoc].SetDeleted(iq, true); } } } #ifdef _DEBUG r1 = r2; #endif r2 = r2->nextX; } } } } void MultiCharCDMOp::Undo(MidEffectsDocSet& ds) const { cxAlwaysAssert(0); // todo } // It is assumed that x1 points at the first interval, and x2 point at the last interval of a group // of aliasing extractions that need to be inserted into this operation. // It is assumed that xdoc and xq have already been initialised for each interval in the group // It is assumed there will be no intersection with any existing extractions at the new position void MultiCharCDMOp::InsertExtractions(CDMMoveInterval* x1, CDMMoveInterval* x2) { cxAssert(x1); cxAssert(x2); cxAssert(x1->prevX == NULL); cxAssert(x2->nextX == NULL); ssize_t xq = x1->xq; DocId xdoc = x1->xdoc; #ifdef _DEBUG // Validate group x1..x2. Must all be at the same position { const CDMMoveInterval* x = x1; while(1) { cxAssert(x->xdoc == xdoc); cxAssert(x->xq == xq); const CDMMoveInterval* nx = x->nextX; if (!nx) { cxAssert(x == x2); break; } x = nx; } } #endif MAP::iterator mx = m_map.find(xdoc); if (mx == m_map.end() || mx->second.x == NULL) { m_map[xdoc].x = x1; } else { // Scan for position where need to insert this extraction CDMMoveInterval* prevx = NULL; CDMMoveInterval* nextx = mx->second.x; while(nextx && nextx->xq < xq) { prevx = nextx; nextx = nextx->nextX; } // x1..x2 must not overlap with any existing extraction intervals cxAssert(prevx == NULL || prevx->xq + prevx->size() <= xq); cxAssert(nextx == NULL || xq + x1->size() <= nextx->xq); // Insert x1..x2 between prevx and nextx x1->prevX = prevx; x2->nextX = nextx; if (prevx) { cxAssert(prevx->nextX == nextx); prevx->nextX = x1; } else { cxAssert(m_map[xdoc].x == nextx); m_map[xdoc].x = x1; } if (nextx) { cxAssert(nextx->prevX == prevx); nextx->prevX = x2; } } } // Track the extraction position of the aliasing group of extractions headed by interval x1 to a // new location given by xdoc, xq. void MultiCharCDMOp::SetNewExtractionPosition(CDMMoveInterval* x1, DocId xdoc, ssize_t xq) { cxAssert(x1); cxAssert(xdoc >= 0); cxAssert(xq >= 0); ssize_t old_xq = x1->xq; DocId old_xdoc = x1->xdoc; // x1 must be the first aliasing extraction interval in the group cxAssert(x1->prevX == NULL || x1->prevX->xq < old_xq); // Scan the group headed by x1. Set new xdoc and xq for each interval in the group. // Set x2 to point at the last interval in the group CDMMoveInterval* x2 = x1; { while(1) { cxAssert(x2); cxAssert(x2->xdoc == old_xdoc); cxAssert(x2->xq == old_xq); // Set new xdoc and xq for each interval in the group x2->xdoc = xdoc; x2->xq = xq; CDMMoveInterval* nx = x2->nextX; if (!nx || nx->xq != old_xq) break; x2 = nx; } } cxAssert(x2); //Tracer() << "Tracking " << *x1 << " src to q = " << xq << '\n'; // Remove group x1..x2 from its current location { CDMMoveInterval* p = x1->prevX; CDMMoveInterval* n = x2->nextX; if (p) { // Interval is not at the front of the linked list, so simply remove it from the chain cxAssert(p->nextX == x1); p->nextX = n; if (n) { cxAssert(n->prevX == x2); n->prevX = p; } } else { // Interval is at the front of the linked list, so need to update the map cxAssert(m_map[old_xdoc].x == x1); if (n) { m_map[old_xdoc].x = n; cxAssert(n->prevX == x2); n->prevX = NULL; } else { // todo : Want map to be self cleaning - i.e. if all 4 pointers become NULL then remove // entry. m_map[old_xdoc].x = NULL; } } } x1->prevX = NULL; x2->nextX = NULL; InsertExtractions(x1,x2); //Tracer() << "Now x1 = " << *x1 << '\n'; //Tracer() << "THIS = " << *this << '\n'; AssertValid(); } // It is assumed that x1 points at the first interval, and x2 point at the last interval of a group // of aliasing extractions that need to be inserted into this operation. // It is assumed that xdoc and xq have already been initialised for each interval in the group // It is assumed there will be no intersection with any existing extractions at the new position void MultiCharCDMOp::InsertExtractions(CDMDeleteInterval* x1, CDMDeleteInterval* x2) { cxAssert(x1); cxAssert(x2); cxAssert(x1->prevX == NULL); cxAssert(x2->nextX == NULL); ssize_t xq = x1->xq; DocId xdoc = x1->xdoc; #ifdef _DEBUG // Validate group x1..x2. Must all be at the same position { const CDMDeleteInterval* x = x1; while(1) { cxAssert(x->xdoc == xdoc); cxAssert(x->xq == xq); const CDMDeleteInterval* nx = x->nextX; if (!nx) { cxAssert(x == x2); break; } x = nx; } } #endif MAP::iterator mx = m_map.find(xdoc); if (mx == m_map.end() || mx->second.d == NULL) { //Tracer() << "Setting new x1\n"; m_map[xdoc].d = x1; } else { // Scan for position where need to insert this extraction CDMDeleteInterval* prevx = NULL; CDMDeleteInterval* nextx = mx->second.d; while(nextx && nextx->xq < xq) { prevx = nextx; nextx = nextx->nextX; } // x1..x2 must not overlap with any existing extraction intervals cxAssert(prevx == NULL || prevx->xq + prevx->size() <= xq); cxAssert(nextx == NULL || xq + x1->size() <= nextx->xq); // Insert x1..x2 between prevx and nextx x1->prevX = prevx; x2->nextX = nextx; if (prevx) { cxAssert(prevx->nextX == nextx); prevx->nextX = x1; } else { cxAssert(m_map[xdoc].d == nextx); //Tracer() << "Setting new x1 ..2\n"; m_map[xdoc].d = x1; } if (nextx) { cxAssert(nextx->prevX == prevx); nextx->prevX = x2; } } } // Track the extraction position of the aliasing group of extractions headed by interval x1 to a // new location given by xdoc, xq. void MultiCharCDMOp::SetNewExtractionPosition(CDMDeleteInterval* x1, DocId xdoc, ssize_t xq) { cxAssert(x1); cxAssert(xdoc >= 0); cxAssert(xq >= 0); ssize_t old_xq = x1->xq; DocId old_xdoc = x1->xdoc; // x1 must be the first aliasing extraction interval in the group cxAssert(x1->prevX == NULL || x1->prevX->xq < old_xq); // Scan the group headed by x1. Set new xdoc and xq for each interval in the group. // Set x2 to point at the last interval in the group CDMDeleteInterval* x2 = x1; { while(1) { cxAssert(x2); cxAssert(x2->xdoc == old_xdoc); cxAssert(x2->xq == old_xq); // Set new xdoc and xq for each interval in the group x2->xdoc = xdoc; x2->xq = xq; CDMDeleteInterval* nx = x2->nextX; if (!nx || nx->xq != old_xq) break; x2 = nx; } } cxAssert(x2); //Tracer() << "Set new position of x1..x2 = " << *x1 << " .. " << *x2 << '\n'; //Tracer() << "Tracking " << *x1 << " src to q = " << xq << '\n'; // Remove group x1..x2 from its current location { CDMDeleteInterval* p = x1->prevX; CDMDeleteInterval* n = x2->nextX; //if (p) Tracer() << "p = " << *p << '\n'; //if (n) Tracer() << "n = " << *n << '\n'; if (p) { // Interval is not at the front of the linked list, so simply remove it from the chain cxAssert(p->nextX == x1); p->nextX = n; if (n) { cxAssert(n->prevX == x2); n->prevX = p; } } else { // Interval is at the front of the linked list, so need to update the map cxAssert(m_map[old_xdoc].d == x1); if (n) { m_map[old_xdoc].d = n; cxAssert(n->prevX == x2); n->prevX = NULL; } else { // todo : Want map to be self cleaning - i.e. if all 4 pointers become NULL then remove // entry. m_map[old_xdoc].d = NULL; } } } x1->prevX = NULL; x2->nextX = NULL; InsertExtractions(x1,x2); //Tracer() << "Now x1 = " << *x1 << '\n'; AssertValid(); } // DualIT_xx needs to postpone the tracking of interval extraction positions to the other operation's // insertion position. Otherwise this interferes with the iteration through the extraction intervals template struct SetNewExtractionPosCommand { SetNewExtractionPosCommand(T* x, DocId xdoc, ssize_t xq) : m_x(x), m_xdoc(xdoc), m_xq(xq) {} T* m_x; DocId m_xdoc; ssize_t m_xq; }; template void ApplyNewExtractionPosCommands(MultiCharCDMOp& O, const xvector >& N) { for (xvector >::const_iterator i=N.begin() ; i != N.end() ; ++i) { //Tracer() << "Tracking " << *i->m_x << " extraction to q = " << i->m_xq << '\n'; O.SetNewExtractionPosition(i->m_x, i->m_xdoc, i->m_xq); } } // Test whether it is possible to coalesce the delete intervals headed by r1,r2 // // [--r1--)[------r2------) // [------)[--------------) // [------)[--------------) // bool CanCoalesceDeleteIntervals(CDMDeleteInterval* r1, CDMDeleteInterval* r2) { cxAssert(r1); cxAssert(r2); ssize_t xq1 = r1->xq; ssize_t xq2 = r2->xq; // Ensure r1 is the head of its group cxAssert(!r1->prevX || r1->prevX->xq != xq1); // Ensure r2 is the head of its group cxAssert(!r2->prevX || r2->prevX->xq != xq2); #ifdef _DEBUG ssize_t xdoc = r1->xdoc; const xstring& str1 = r1->str; const xstring& str2 = r2->str; #endif if (r1->xq + r1->size() == r2->xq) { // Now check extractions. r1, r2 must head mergeable groups of aliasing intervals. while(1) { cxAssert(r1); cxAssert(r2); cxAssert(r1->xdoc == xdoc); cxAssert(r2->xdoc == xdoc); cxAssert(r1->str == str1); cxAssert(r2->str == str2); if (r1->opid != r2->opid) { return false; } CDMDeleteInterval* n1 = r1->nextX; CDMDeleteInterval* n2 = r2->nextX; bool f2 = (n2 && n2->xq == xq2); if (n1 && n1->xq == xq1) { if (!f2) return false; } else { return !f2; } r1 = n1; r2 = n2; } } return false; } // Coalesce the delete intervals headed by r1,r2 // // [--r1--)[------r2------) // [------)[--------------) // [------)[--------------) // CDMDeleteInterval* CoalesceDeleteIntervals(CDMDeleteInterval* r1, CDMDeleteInterval* r2) { cxAssert(r1); cxAssert(r2); CDMDeleteInterval* origr2 = r2; #ifdef _DEBUG ssize_t xq2 = r2->xq; #endif while(1) { cxAssert(r1); cxAssert(r2); cxAssert(r1->opid == r2->opid); r1->str += r2->str; CDMDeleteInterval* n2 = r2->nextX; delete r2; // Warning: n1 may point at the first r2 (which has been deleted). Therefore it is // important not to evaluate n1->xq to see whether we have reached the last r1 because // that may cause an access violation. Instead we compare n1 to origr2. CDMDeleteInterval* n1 = r1->nextX; cxAssert(n1); //Tracer() << "Coalesce : r1 --> " << *r1 << '\n'; if (n1 == origr2) { // Reached the end r1->nextX = n2; if (n2) { cxAssert(n2->xq != xq2); cxAssert(n2->prevX == r2); n2->prevX = r1; } return n2; } else { // Still going cxAssert(n2); cxAssert(n2->xq == xq2); r1 = n1; r2 = n2; } } } // Test whether it is possible to coalesce the move intervals headed by r1,r2 // // [--r1--)[------r2------) // [------)[--------------) // [------)[--------------) // bool CanCoalesceMoveIntervals(CDMMoveInterval* r1, CDMMoveInterval* r2) { cxAssert(r1); cxAssert(r2); DocId xdoc = r1->xdoc; if (xdoc == r2->xdoc && r1->xq + r1->size() == r2->xq) { ssize_t xq1 = r1->xq; ssize_t xq2 = r2->xq; // Now check extractions. r1, r2 must head mergeable groups of aliasing intervals. // Ensure r1 is the head of its group if (r1->prevX && r1->prevX->xq == xq1) return false; // Ensure r2 is the head of its group if (r2->prevX && r2->prevX->xq == xq2) return false; while(1) { cxAssert(r1); cxAssert(r2); if (r1->opid != r2->opid || r1->e != r2->e || r1->idoc != r2->idoc || r1->iq + r1->size() != r2->iq) { return false; } CDMMoveInterval* n1 = r1->nextX; CDMMoveInterval* n2 = r2->nextX; bool f2 = (n2 && n2->xq == xq2); if (n1 && n1->xq == xq1) { if (!f2) return false; } else { return !f2; } r1 = n1; r2 = n2; } } return false; } // Coalesce the move intervals headed by r1,r2 // // [--r1--)[------r2------) // [------)[--------------) // [------)[--------------) // void CoalesceMoveIntervals(CDMMoveInterval* r1, CDMMoveInterval* r2) { cxAssert(r1); cxAssert(r2); CDMMoveInterval* origr2 = r2; #ifdef _DEBUG ssize_t xq2 = r2->xq; #endif while(1) { cxAssert(r1); cxAssert(r2); r1->str += r2->str; CDMMoveInterval* n2 = r2->nextX; // Remove r2 from double linked list of insertions { cxAssert(r1->nextI == r2); cxAssert(r2->prevI == r1); CDMMoveInterval* r3 = r2->nextI; r1->nextI = r3; if (r3) { cxAssert(r3->prevI == r2); r3->prevI = r1; } } delete r2; // Warning: n1 may point at the first r2 (which has been deleted). Therefore it is // important not to evaluate n1->xq to see whether we have reached the last r1 because // that may cause an access violation. Instead we compare n1 to origr2. CDMMoveInterval* n1 = r1->nextX; cxAssert(n1); if (n1 == origr2) { // Reached the end r1->nextX = n2; if (n2) { cxAssert(n2->xq != xq2); cxAssert(n2->prevX == r2); n2->prevX = r1; } return; } else { // Still going cxAssert(n2); cxAssert(n2->xq == xq2); r1 = n1; r2 = n2; } } } void MultiCharCDMOp::CoalesceAdjacentIntervals() { MAP::iterator m = m_map.begin(); while (m != m_map.end()) { DocId doc = m->first; CDMDocIntervals& di = m->second; if (di.c || di.d || di.i || di.x) { // Coalesce adjacent creates { CDMCreateInterval* r1 = NULL; CDMCreateInterval* r2 = di.c; while(r2) { cxAssert(r2->idoc == doc); if (r1 != NULL && r1->opid == r2->opid && r1->iq + r1->size() == r2->iq) { cxAssert(r1->nextI == r2); cxAssert(r2->prevI == r1); r1->str += r2->str; CDMCreateInterval* r3 = r2->nextI; r1->nextI = r3; if (r3) { cxAssert(r3->prevI == r2); r3->prevI = r1; } delete r2; r2 = r3; } else { r1 = r2; r2 = r2->nextI; } } } // Coalesce adjacent deletes // This accounts for aliasing delete intervals { CDMDeleteInterval* r1 = NULL; CDMDeleteInterval* r2 = di.d; while(r2) { //Tracer() << "Coalesce : r2 = " << *r2 << '\n'; cxAssert(r2->xdoc == doc); if (r1 && CanCoalesceDeleteIntervals(r1,r2)) { r2 = CoalesceDeleteIntervals(r1,r2); // r1 += r2 } else { r1 = r2; // Step forwards to next group ssize_t xq = r2->xq; do { r2 = r2->nextX; } while(r2 && r2->xq == xq); } } } // Coalesce adjacent moves { CDMMoveInterval* r1 = NULL; CDMMoveInterval* r2 = di.i; while(r2) { cxAssert(r2->idoc == doc); if (r1 != NULL && r1->opid == r2->opid && r1->e == r2->e && r1->iq + r1->size() == r2->iq && r1->xdoc == r2->xdoc && r1->xq + r1->size() == r2->xq && CanCoalesceMoveIntervals(r1,r2)) { CoalesceMoveIntervals(r1,r2); r2 = r1->nextI; } else { r1 = r2; r2 = r2->nextI; } } } ++m; } else { // An STL map allows for removing an element and only invalidating those iterators that // point at the removed element m = m_map.erase(m); } } } /////////////////////////////////////////////////////////////////////////////////////////////////// void IT(MultiCharCDMOp& O1, const MultiCharCDMOp& O2) { MultiCharCDMOp copyO2 = O2; DualIT(O1, copyO2); } void ET(MultiCharCDMOp& O1, const MultiCharCDMOp& O2) { MultiCharCDMOp copyO2 = O2; Transpose(copyO2, O1); } /////////////////////////////////////////////////////////////////////////////////////////////////// // DualIT /* Definitions O1 --> O2 if O1 was already executed when O2 was generated O1 || O2 if neither O1 --> O2 or O2 --> O1 in-state(O) is the state on which operation O is executed out-state(O) is the state obtained after execution of operation O Let S = in-state(O), then S+O denotes out-state(O) O1,O2 are context equivalent, written as O1 <> O2 if in-state(O1) = in-state(O2) O1,O2 are context convergent, written as O1 >< O2 if out-state(O1) = out-state(O2) O1,O2 are context serialised, written as O1 >> O2 if out-state(O1) = in-state(O2) O1 ~ O2 if O1 <> O2 and O1 >< O2 Let O1 || O2. If O1 <> O2 then IT (O2,O1) = O2' satisfies O1 >> O2' If O2 >> O1 then IT2(O2,O1) = O2' satisfies O1 <> O2' If O1 >> O2 then ET (O2,O1) = O2' satisfies O1 <> O2' If O1 <> O2 then ET2(O2,O1) = O2' satisfies O2' >> O1 On the one diamond we can write 8 different functions as follows Precondition Post condition ------------------------------------------------------ / \ O2 <> O1 IT(O2,O1) = O2' O1 >> O2' O1 / \ O2' O1 <> O2 IT(O1,O2) = O1' O2 >> O1' / \ O2 >> O1' IT2(O2,O1') = O2' O1' >< O2' / \ O1 >> O2' IT2(O1,O2') = O1' O2' >< O1' \ / O2 >> O1' ET(O1',O2) = O1 O1 <> O2 \ / O1 >> O2' ET(O2',O1) = O2 O2 <> O1 O2 \ / O1' O1' >< O2' ET2(O2',O1') = O2 O2 >> O1' \ / O2' >< O1' ET2(O1',O2') = O1 O1 >> O2' */ /* In most of the algorithms below we iterate left to right through both sets of intervals. Sometimes we accumulate the number of characters inserted by one operation and this is applied as a shift to the intervals of the other operation. Sometimes the shifts need to be pre-applied - i.e. before positions ate compared. Sometimes intervals are indeed treated as intervals, and at other times they are treated as insertion positions. */ /* Let i1,i2 be insertions with i1 || i2 and i1 <> i2. This in place dual IT transforms i1 to i1' and i2 to i2' where i1' = IT(i1,i2) and i2' = IT(i2,i1) */ template void DualIT_ii(T1* i1, T2* i2) { ssize_t s1 = 0; // Accumulated characters inserted by i1 ssize_t s2 = 0; // Accumulated characters inserted by i2 while(i1 && i2) { // i1 || i2 => distinct sids cxAlwaysAssert(i1->opid.id != i2->opid.id); ssize_t d = (s1 + i2->iq) - (s2 + i1->iq); if (d < 0 || d == 0 && i2->opid.id < i1->opid.id) { // Process i2 i2->iq += s1; s2 += i2->size(); i2 = i2->nextI; } else { // Process i1 i1->iq += s2; s1 += i1->size(); i1 = i1->nextI; } } if (s1) { while (i2) { i2->iq += s1; i2 = i2->nextI; } } if (s2) { while (i1) { i1->iq += s2; i1 = i1->nextI; } } } /* Transforms i1 to i1' = IT2(i1,i2) where i1,i2 are mutually exclusive insertions satisfying i1 >> i2 We compare positions in the state obtained after execution of i2. For the purposes of comparison, positions of i2 don't require adjustment. However positions of i1 need to the shifted to the right by the accumulated shift from i2. */ template void IT2_ii(T1* i1, const T2* i2) { ssize_t s = 0; // Accumulated shift from i2 while(i1 && i2) { ssize_t d = i2->iq - (s + i1->iq); if (d <= 0) { // Process i2 s += i2->size(); i2 = i2->nextI; } else { if (d < i1->size()) { SplitInterval(i1,d); } // Process i1 i1->iq += s; i1 = i1->nextI; } } if (s) { while (i1) { i1->iq += s; i1 = i1->nextI; } } } /* Transforms x to x' = IT(x,i) where x are extractions and i are insertions satisfying x <> i. Note that in the input state x cannot reference characters in i implying that they are mutually exclusive. We make sense of what is happening in the document state obtained after performing the insertions. In this state all characters are present. Insertions are already in post insertion coordinates. Extractions need to be shifted right by the number of characters inserted on the left. Extraction intervals may need to be split - i.e. when there are insertions within the extraction interval */ template void IT_xi(T2* x, const T1* i) { //Tracer() << "IT xi\n"; ssize_t s = 0; // Accumulated shift from O1 while(i && x) { //Tracer() << " i = " << *i << '\n'; //Tracer() << " x = " << *x << '\n'; //Tracer() << " s = " << s << '\n'; ssize_t d = i->iq - (s + x->xq); //Tracer() << " d = " << d << '\n'; if (d <= 0) { // [2222222) // 1 s += i->size(); i = i->nextI; } else { if (d < x->size()) { // [222222) // 1 //Tracer() << " Splitting x = " << *x << " at n1 = " << d << '\n'; SplitInterval(x,d,false); } // [2222222) // 1 x->xq += s; x = x->nextX; } } if (s) { while (x) { x->xq += s; x = x->nextX; } } } /* Transforms i2 to i2' = ET2(i2,i1) where i1,i2 are mutually exclusive insertions satisfying i1 >< i2 Since i1 >< i2 and insertions use post insertion coordinates, i1 and i2 are represented in the same coordinate system (i.e. containing the union of all insertions). Therefore they can be directly compared. Intervals in i2 need to be shifted left by the number of insertions from i1. */ template void ET2_ii(T2* i2, const T1* i1) { ssize_t s = 0; // Accumulated shift from i1 while(i1 && i2) { if (i1->iq + i1->size() <= i2->iq) { // Next is [11111) s += i1->size(); i1 = i1->nextI; } else if (i2->iq + i2->size() <= i1->iq) { // Next is [22222) i2->iq -= s; i2 = i2->nextI; } else { // i1,i2 must be mutually exclusive cxAssert(0); } } if (s) { while (i2) { i2->iq -= s; i2 = i2->nextI; } } } /* Transforms x to x' = ET(x,i) where x are extractions and i are insertions satisfying i >> x and they are mutually exclusive. The latter means there are no characters inserted by i that are subsequently extracted by x. Since i >> x we can assume that x,i are expressed in the same post insertion coordinates. Therefore they can be directly compared. Intervals in x need to be shifted left by the number of insertions from i. */ template void ET_xi(T1* x, const T2* i) { ssize_t s = 0; // Accumulated shift from i while(i && x) { if (i->iq + i->size() <= x->xq) { // Next is [iiiii) s += i->size(); i = i->nextI; } else if (x->xq + x->size() <= i->iq) { // Next is [xxxxx) x->xq -= s; x = x->nextX; } else { // x,i must be mutually exclusive cxAssert(0); } } if (s) { while (x) { x->xq -= s; 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 operations is relevant: 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. */ template void Transposeii(T1* i1, T2* i2) { ssize_t s1 = 0; // Accumulated shift from i1 ssize_t s2 = 0; // Accumulated shift from i2 while(i1 && i2) { ssize_t d = i2->iq - (s2 + i1->iq); if (d <= 0) { // Process i2 i2->iq -= s1; s2 += i2->size(); i2 = i2->nextI; } else { if (d < i1->size()) SplitInterval(i1,d); // Process i1 i1->iq += s2; s1 += i1->size(); i1 = i1->nextI; } } if (s1) { while (i2) { i2->iq -= s1; i2 = i2->nextI; } } if (s2) { while (i1) { i1->iq += s2; i1 = i1->nextI; } } } template void Transposeii_slow(T1* i1, T2* i2) { IT2_ii(i1, i2); // i1 = IT(i1,i2) where i2 already includes i1 ET2_ii(i2, i1); // i2 = ET(i2,i1) where i1 already includes i2 } /* This algorithm handles the dual IT of extractions with extractions. The following part of the algorithm for IT is relevant: if (O1.xdoc == O2.xdoc && O1.xq == O2.xq) { if (O1.e == 0) { O2.xdoc = O1.idoc; O2.xq = O1.iq; } if (O2.e == 0) { O1.xdoc = O2.idoc; O1.xq = O2.iq; } 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 extractions have no effect on the effects document. */ void DualIT_xx( CDMMoveInterval* x1, CDMMoveInterval* x2, xvector >& N1, xvector >& N2) { while(x1 && x2) { if (x1->xq + x1->size() <= x2->xq) { // Next is [11111) x1 = x1->nextX; } else if (x2->xq + x2->size() <= x1->xq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (x1->xq < x2->xq) { // [1111111111111 // [2222222 x1 = SplitInterval(x1, x2->xq - x1->xq, false); cxAssert(x1); } else if (x2->xq < x1->xq) { // [2222222222222 // [1111111 x2 = SplitInterval(x2, x1->xq - x2->xq, false); cxAssert(x2); } cxAssert(x2->xq == x1->xq); if (x2->size() < x1->size()) { // [222222) // [111111111111) SplitInterval(x1, x2->size(), false); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, x1->size(), false); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); /* Due to extraction interval aliasing there could be multiple overlapping intervals from both O1 and O2. We process them all here. [--x1---) e=0 [-------) e=3 [--x2---) e=1 [-------) e=4 [-------) e=5 */ /* Tracking -------- Aliasing extractions are ordered by strictly increasing e-position. Note therefore that we can assume that we only have to look at the *first* interval to see whether there is an enabled move. If so then *all* move intervals in the other operation will need to track to the destination of that first move. Tracking needs to be delayed (i.e. performed asynchronously) because setting new extraction positions upsets the interation over the linked list of extractions, and the iteration over the maps. Note that destination positions of move/insert operations never track to new locations. We will always be interested in tracking all aliasing extractions in a group. Therefore we only need to issue a single asynchronous command to move the whole group of aliasing extractions. Consider for example that a group of extractions from O2 is tracked to the destination range [d,d+n) of a move performed by O1. Since O1 || O2 it must be the case that no source intervals in O2 overlap with [d,d+n). Therefore we can assume that tracking is relatively easy to perform - it is a simple matter of inserting the group of extractions at the proper position in O2.X, khowing that they won't overlap with any existing extractions in O2.X. */ if (x1->e == 0) N2.push_back(SetNewExtractionPosCommand(x2, x1->idoc, x1->iq)); if (x2->e == 0) N1.push_back(SetNewExtractionPosCommand(x1, x2->idoc, x2->iq)); /* Transform e-coordinates ----------------------- DualIT groups of aliasing extractions of move operations. [--x1---) e=0 [-------) e=3 [--x2---) e=1 [-------) e=4 [-------) e=5 The groups are headed by x1 and x2 respectively. All intervals in a group share the same extraction position xq. Each move interval has an e coordinate. Within a group it is assumed that moves are ordered according to increasing e-coordinate. e coordinate positions should never be repeated. This function transforms e-coordinates as though each interval represents a single character insertion into a hypothetical effects document whose only purpose is to select a unique winner amongst all competing move operations. Note that the e-cordinate is expressed in post-insertion coordinates. The algorithm is analgous to DualIT_ii(). In a single linear scan we process both sets of moves, applying shifts to e-coordinates. If e-coordinates match then we use siteids to break the tie. */ { ssize_t xq = x1->xq; ssize_t s1 = 0; // Accumulated e coordinate shift from O1 ssize_t s2 = 0; // Accumulated e coordinate shift from O2 while(1) { cxAssert(x1); cxAssert(x2); cxAssert(x1->xq == xq); cxAssert(x2->xq == xq); cxAssert(x1->str == x2->str); ssize_t d = (s1 + x2->e) - (s2 + x1->e); if (d < 0 || d == 0 && x2->opid.id < x1->opid.id) { // Process i2 x2->e += s1; ++s2; x2 = x2->nextX; if (!x2 || x2->xq != xq) { do { x1->e += s2; x1 = x1->nextX; } while(x1 && x1->xq == xq); break; } } else { // Process i1 x1->e += s2; ++s1; x1 = x1->nextX; if (!x1 || x1->xq != xq) { do { x2->e += s1; x2 = x2->nextX; } while(x2 && x2->xq == xq); break; } } } } } } } void IT_dx( CDMDeleteInterval* d, CDMMoveInterval* x, xvector >& N) { while(d && x) { if (d->xq + d->size() <= x->xq) { // Next is [ddddd) d = d->nextX; } else if (x->xq + x->size() <= d->xq) { // Next is [xxxxx) x = x->nextX; } else { // Intervals overlap if (d->xq < x->xq) { // [ddddddddddddd // [xxxxxxx d = SplitInterval(d, x->xq - d->xq, false); cxAssert(d); } else if (x->xq < d->xq) { // [xxxxxxxxxxxxx // [ddddddd x = SplitInterval(x, d->xq - x->xq, false); cxAssert(x); } cxAssert(x->xq == d->xq); if (x->size() < d->size()) { // [xxxxxx) // [dddddddddddd) //Tracer() << "Splitting d = " << *d << " with x size = " << x->size() << '\n'; SplitInterval(d, x->size(), false); //Tracer() << " --> d = " << *d << '\n'; //cxAssert(d->nextX); //Tracer() << " --> nd = " << *(d->nextX) << '\n'; } else if (d->size() < x->size()) { // [dddddd) // [xxxxxxxxxxxx) SplitInterval(x, d->size(), false); } // [dddddd) // [xxxxxx) cxAssert(d->size() == x->size()); /* There could be multiple overlapping intervals from both O1 and O2. We process them all here. [---d---) [-------) [---x---) e=0 [-------) e=4 [-------) e=5 Aliasing extractions are ordered by strictly increasing e-position. Note therefore that we can assume that we only have to look at the *first* interval x to see whether there is an enabled move. If so then *all* aliasing deletion intervals headed in d will need to track to the destination of that first move. Tracking needs to be delayed (i.e. performed asynchronously) because setting new extraction positions upsets the interation over the linked list of deletions, and the iteration over the maps. */ if (x->e == 0) N.push_back(SetNewExtractionPosCommand(d, x->idoc, x->iq)); // Skip past all these aliasing intervals { ssize_t xq = d->xq; do d = d->nextX; while(d && d->xq == xq); do x = x->nextX; while(x && x->xq == xq); } } } } /* The dualIT of O1,O2 leads to the following matrix +----+----+----+----+ X2 | cx | dx | ix | xx | +----+----+----+----+ I2 | ci | di | ii | xi | O2 +----+----+----+----+ D2 | cd | dd | id | xd | +----+----+----+----+ C2 | cc | dc | ic | xc | +----+----+----+----+ C1 D1 I1 X1 O1 Conceptually we start in the bottom left corner with a DualIT_cc() and finish in the top right corner with a DualIT_xx(). It is allowable to process the matrix for each document independently, on the provisor that the tracking of delete or extraction intervals is postponed until the end. Note that tracking only occurs in the squares dx,xd and xx and these don't feed into any other squares. */ void DualIT(MultiCharCDMOp& O1, MultiCharCDMOp& O2) { O1.AssertValid(); O2.AssertValid(); /* +----+----+----+----+ X2 | - | | | | +----+----+----+----+ I2 | + | | | | | O2 +----+----+----+----+ D2 | - | | - | | +----+----+----+----+ C2 | + | | | + | | | +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; DualIT_ii(di1.c, di2.c); IT_xi(di2.d, di1.c); IT_xi(di1.d, di2.c); DualIT_ii(di1.c, di2.i); DualIT_ii(di2.c, di1.i); IT_xi(di2.d, di1.i); IT_xi(di1.d, di2.i); IT_xi(di2.x, di1.c); IT_xi(di1.x, di2.c); } } { /* +----+----+----+----+ X2 | * | T | | | +----+----+----+----+ I2 | * | * | | | O2 +----+----+----+----+ D2 | * | * | * | T | +----+----+----+----+ C2 | * | * | * | * | +----+----+----+----+ C1 D1 I1 X1 O1 D1 needs to track M2. We want to do this when D1 and X2 are in the same coord system. This is post C1,C2,I2. At that moment we want to track to I2 when I2 is in post C1,C2,I2 */ xvector > ND1; xvector > ND2; for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; IT_dx(di1.d, di2.x, ND1); IT_dx(di2.d, di1.x, ND2); } } ApplyNewExtractionPosCommands(O1,ND1); ApplyNewExtractionPosCommands(O2,ND2); } /* +----+----+----+----+ X2 | * | * | - | | +----+----+----+----+ I2 | * | * | + | | | O2 +----+----+----+----+ D2 | * | * | * | * | +----+----+----+----+ C2 | * | * | * | * | +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; DualIT_ii(di1.i, di2.i); IT_xi(di2.x, di1.i); IT_xi(di1.x, di2.i); } } //Tracer() << "Before apply tracking : O1=" << O1 << " O2= " << O2 << '\n'; { /* +----+----+----+----+ X2 | * | * | * | T | +----+----+----+----+ I2 | * | * | * | * | O2 +----+----+----+----+ D2 | * | * | * | * | +----+----+----+----+ C2 | * | * | * | * | +----+----+----+----+ C1 D1 I1 X1 O1 X1 needs to track M2. We want to do this when X1 and X2 are in the same coord system. This is post C1,C2,I1,I2. At that moment we want to track to I2 when I2 is in post C1,C2,I1,I2 */ xvector > NM1; xvector > NM2; for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; DualIT_xx(di1.x, di2.x, NM1,NM2); } } ApplyNewExtractionPosCommands(O1,NM1); ApplyNewExtractionPosCommands(O2,NM2); } //Tracer() << "After apply tracking : O1=" << O1 << " O2= " << O2 << '\n'; O1.CoalesceAdjacentIntervals(); O2.CoalesceAdjacentIntervals(); O1.AssertValid(); O2.AssertValid(); } /////////////////////////////////////////////////////////////////////////////////////////////////// // Transpose /* Comments on bug fix related to call to Transpose_ee() Transpose_ee() is called for two different cases. We need to analyse them separately! Case 1 : TransposeConcurrent_xx_1 ------ if (x1 == x2) { if (x1.e < x2.e) --x2.e; else ++x1.e; if (x2.e == 0) async(x1 = i2); } This case is easy - Transpose_ee() can assume that all intervals have the same xq Case 2 : TransposeConcurrent_xx_2 ------ if (i1 == x2) { async: x2 = x1; if (i1.e < x2.e) --x2.e; else ++i1.e; if (x2.e == 0) async(x1 = i2); } O1 may have a number of intervals that alias the source interval. This is moved by O1 to different places. At most one can be enabled. O2.x2 will match that one. We want to transpose both groups, which means we must 1) follow i1 to its group of aliasing extractions 2) move to the head of the list. 3) Use independent xq1, xq2 for testing group membership. */ // At this point we are transposing conflicting moves. Each interval is regarded as an // insertion of a single character at its e coordinate. Therefore we now need to transpose // x1,x2 interval e-coordinates as though they are consecutively executed insertions. void Transpose_ee(CDMMoveInterval* x1, CDMMoveInterval* x2, CDMMoveInterval*& nx1, CDMMoveInterval*& nx2) { cxAssert(x1); cxAssert(x2); ssize_t s1 = 0; // Accumulated e coordinate shift from x1 ssize_t s2 = 0; // Accumulated e coordinate shift from x2 ssize_t xq1 = x1->xq; ssize_t xq2 = x2->xq; //Tracer() << "xq1 = " << xq1 << '\n'; //Tracer() << "xq2 = " << xq2 << '\n'; while(1) { //Tracer() << " x1 = " << x1 << "\n x2 = " << x2 << '\n'; if (x2->e <= s2 + x1->e) { // Process x2 x2->e -= s1; ++s2; x2 = x2->nextX; //Tracer() << " 1. x2 --> " << x2 << '\n'; if (!x2 || x2->xq != xq2) { do { x1->e += s2; x1 = x1->nextX; } while (x1 && x1->xq == xq1); break; } } else { // Process x1 x1->e += s2; ++s1; x1 = x1->nextX; if (!x1 || x1->xq != xq1) { do { x2->e -= s1; //Tracer() << " x2 = " << *x2 << '\n'; //Tracer() << "x2->xq = " << x2->xq << '\n'; x2 = x2->nextX; //Tracer() << " 2. x2 --> " << x2 << '\n'; } while (x2 && x2->xq == xq2); break; } } } nx1 = x1; nx2 = x2; } /* The transpose algorithm transforms [O1 O2] to [O2' O1']. This algorithm handles the transpose of extractions with extractions. The following part of the algorithm for IT/ET of single character move operations is relevant: if (x1 == x2) { if (x1.e < x2.e) --x2.e; else ++x1.e; if (x2.e == 0) async: x1 = i2; } 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_xx_1( CDMMoveInterval* x1, CDMMoveInterval* x2, xvector >& N1) { while(x1 && x2) { if (x1->xq + x1->size() <= x2->xq) { // Next is [11111) x1 = x1->nextX; } else if (x2->xq + x2->size() <= x1->xq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (x1->xq < x2->xq) { // [1111111111111 // [2222222 x1 = SplitInterval(x1, x2->xq - x1->xq, false); } else if (x2->xq < x1->xq) { // [2222222222222 // [1111111 x2 = SplitInterval(x2, x1->xq - x2->xq, false); } cxAssert(x2->xq == x1->xq); if (x2->size() < x1->size()) { // [222222) // [111111111111) SplitInterval(x1, x2->size(), false); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, x1->size(), false); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); //Tracer() << "\nSrc intervals x1=" << *x1 << " x2=" << *x2 << '\n'; // If x1->e == 0 then it would not be possible for x2 to alias x1 because x2 should have // tracked to the destination of x1 cxAlwaysAssert(x1->e > 0); CDMMoveInterval* nx1; CDMMoveInterval* nx2; Transpose_ee(x1,x2,nx1,nx2); // Note that we test whether x2 is enabled after ETing x2 e-coordinates backward past x1 if (x2->e == 0) { //Tracer() << "\nx2 enabled so x1 tracks to q = " << x2->iq << '\n'; N1.push_back(SetNewExtractionPosCommand(x1, x2->idoc, x2->iq)); } x1 = nx1; x2 = nx2; } } } /* cxAssert(i1.e == 0); x2 <-- x1; if (i1.e < x2.e) --x2->e; else ++i1->e; assert(x2.e >= 0); if (x2.e == 0) i1 <-- i2; */ void TransposeConcurrent_xx_2( CDMMoveInterval* i1, CDMMoveInterval* x2, xvector >& N1, xvector >& N2) { while(i1 && x2) { //Tracer() << "\nTesting i1=" << *i1 << " x2=" << *x2 << '\n'; if (i1->iq + i1->size() <= x2->xq) { // Next is [11111) i1 = i1->nextI; } else if (x2->xq + x2->size() <= i1->iq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (i1->iq < x2->xq) { // [1111111111111 // [2222222 SplitInterval(i1, x2->xq - i1->iq, true); i1 = i1->nextI; } else if (x2->xq < i1->iq) { // [2222222222222 // [1111111 x2 = SplitInterval(x2, i1->iq - x2->xq, false); } cxAssert(x2->xq == i1->iq); if (x2->size() < i1->size()) { // [222222) // [111111111111) SplitInterval(i1, x2->size(), true); } else if (i1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, i1->size(), false); } // [111111) // [222222) cxAssert(i1->size() == x2->size()); // TODO: Need to iterate through intervals from i1,x2 to process e coordinates // correctly //Tracer() << "\nTracking needed : i1=" << *i1 << " x2=" << *x2 << '\n'; //Tracer() << "nx2 = " << x2->nextX << '\n'; cxAssert(i1->e == 0); N2.push_back(SetNewExtractionPosCommand(x2, i1->xdoc, i1->xq)); CDMMoveInterval* nx2; { // Walk backwards from i1 in its group of aliasing extractions to the head of the // list CDMMoveInterval* x1 = i1; ssize_t xq = x1->xq; while(1) { CDMMoveInterval* p = x1->prevX; if (!p || p->xq != xq) break; x1 = p; } CDMMoveInterval* nx1; Transpose_ee(x1,x2,nx1,nx2); } cxAlwaysAssert(x2->e >= 0); if (x2->e == 0) { //Tracer() << "\nx2 enabled so i1 tracks to q = " << x2->iq << '\n'; N1.push_back(SetNewExtractionPosCommand(i1, x2->idoc, x2->iq)); } x2 = nx2; i1 = i1->nextI; //Tracer() << "next x2 = " << x2 << '\n'; //Tracer() << "next i1 = " << i1 << '\n'; } } } /* Implements the tracking rule : if (i1 == x2) x2 = x1, where x2 can be extractions or deletes todo: Track_ETxm used to be called Track_ETdm and assumed x2 were deleted. The same function can now be used to unchain move operations, needed for merging. Let [i x d] be given where [i x] represent moves. The deletes are in post move (i.e. post insertion) coordinates. With the intention of calculating ET(d,[i x]), this function determines where tracking is required. This involves testing for overlap between the deletion and insertion intervals (which are both expressed in the same post-insertion coordinates so they can be directly compared). Overlap implies that the move operation must be enabled (else the delete would instead overlap with the source of the move) The tracking rule can be summarised like this if (i == d) d = x The tracking commands to be applied to d are stored in N ready to be applied later. */ template void Track_ETxm(T* x2,CDMMoveInterval* i1,xvector >& N2) { //Tracer() << "\nTrack_ETxm\n"; while(i1 && x2) { //Tracer() << " i1 = " << *i1 << '\n'; //Tracer() << " x2 = " << *x2 << '\n'; if (i1->iq + i1->size() <= x2->xq) { // Next is [11111) i1 = i1->nextI; } else if (x2->xq + x2->size() <= i1->iq) { // Next is [22222) x2 = x2->nextX; } else { // Intervals overlap if (i1->iq < x2->xq) { // [1111111111111 // [2222222 SplitInterval(i1, x2->xq - i1->iq, true); i1 = i1->nextI; } else if (x2->xq < i1->iq) { // [2222222222222 // [1111111 //Tracer() << " Splitting x2 with n1 = " << i1->iq - x2->xq << '\n'; x2 = SplitInterval(x2, i1->iq - x2->xq, false); } //Tracer() << "... i1 = " << *i1 << '\n'; //Tracer() << "... x2 = " << *x2 << '\n'; cxAssert(x2->xq == i1->iq); if (x2->size() < i1->size()) { // [222222) // [111111111111) SplitInterval(i1, x2->size(), true); } else if (i1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, i1->size(), false); } // [111111) // [222222) cxAssert(i1->size() == x2->size()); cxAssert(i1->e == 0); N2.push_back(SetNewExtractionPosCommand(x2, i1->xdoc, i1->xq)); i1 = i1->nextI; // Skip past all aliasing delete intervals { ssize_t xq = x2->xq; do x2 = x2->nextX; while(x2 && x2->xq == xq); } } } } /* The transpose of O1,O2 leads to the following matrix +----+----+----+----+ | cx | dx | ix | xx | X2 +----+----+----+----+ | ci | di | ii | xi | I2 +----+----+----+----+ O2 | cd | dd | id | xd | D2 +----+----+----+----+ | cc | dc | ic | xc | C2 +----+----+----+----+ C1 D1 I1 X1 O1 Conceptually we start in the bottom right corner with a Transpose_xc() and finish in the top left corner with a Transpose_cx(). cxAlwaysAssert(O1.GetId() != O2.GetId()); ssize_t prev2dq = O2.iq; if (O2.idoc == O1.xdoc && O2.iq <= O1.xq) ++O1.xq; if (O1.idoc == O2.idoc) { if (O1.iq < O2.iq) --O2.iq; else ++O1.iq; } if (O1.xdoc == O2.xdoc && O1.xq == O2.xq || O1.idoc == O2.xdoc && O1.iq == O2.xq) { if (O1.e == 0) { O2.xdoc = O1.xdoc; O2.xq = O1.xq; } if (O1.e < O2.e) --O2.e; else ++O1.e; cxAlwaysAssert(O2.e >= 0); if (O2.e == 0) { O1.xdoc = O2.idoc; O1.xq = prev2dq; } } if (O1.idoc == O2.xdoc && O1.iq < O2.xq) --O2.xq; */ void Transpose(MultiCharCDMOp& O1, MultiCharCDMOp& O2) { cxAlwaysAssert(O1.GetId() != O2.GetId()); O1.AssertValid(); O2.AssertValid(); // Transpose [c1 d1 i1 x1] [c2 d2 i2 x2] { /* +----+----+----+----+ | | | | | X2 +----+----+----+----+ | | | | | I2 +----+----+----+----+ O2 | | | | | D2 +----+----+----+----+ | + | | | + | | | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; IT_xi(di1.x, di2.c); // x1 = IT(x1,c2) Transposeii(di1.i, di2.c); IT_xi(di1.d, di2.c); // d1 = IT(d1,c2) Transposeii(di1.c, di2.c); } } } { xvector > N2; /* +----+----+----+----+ | | | | | X2 +----+----+----+----+ | | | | | I2 +----+----+----+----+ O2 | | | | - | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; // d2 and i1 are expressed in the same coordinates (i.e. post c1,i1,c2). // Therefore it is meaningful to directly check for overlap. // Overlap implies that d2 is deleting characters moved by O1. Transpose requires // that d2 track to the extraction position of O1 Track_ETxm(di2.d, di1.i, N2); // async: if (i1 == d2) d2 = x1 } } ApplyNewExtractionPosCommands(O2,N2); // apply: if (i1 == d2) d2 = x1 } { /* +----+----+----+----+ | | | | | X2 +----+----+----+----+ | | | | | | | I2 +----+----+----+----+ O2 | - | | - | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; // Note this assumes that d2,i1 are mutually exclusive. That is indeed the case after // applying the previous tracking rule : if (i1 == d2) d2 = x1 ET_xi(di2.d, di1.i); // d2 = ET(d2,i1) // Note this assumes that d2,c1 are mutually exclusive which is the case because // O1 || O2. ET_xi(di2.d, di1.c); // d2 = ET(d2,c1) IT_xi(di1.x, di2.i); // x1 = IT(x1,i2) IT2_ii(di1.i, di2.i); // i1 = IT(i1,i2) where i2 already includes i1 } } } //Tracer() << "\n\nAfter IT i1,x1 past i2 : O1=" << O1 << "\n O2= " << O2 << '\n'; { /* +----+----+----+----+ | | | | + | X2 +----+----+----+----+ | | | * | * | I2 +----+----+----+----+ O2 | * | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ // i1,x1,i2,x2 are all in the context of c1,i1,c2,i2 xvector > N1; xvector > N2; for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; // Transpose as move operations that move the same w-characters. // In this state all intervals are in the context of both i1 and i2 so they can be // directly compared. // if (x1 == x2) // { // if (x1.e < x2.e) --x2.e; else ++x1.e; // if (x2.e == 0) async(x1 = i2); // } TransposeConcurrent_xx_1(di1.x,di2.x,N1); // if (i1 == x2) // { // async: x2 = x1; // if (i1.e < x2.e) --x2.e; else ++i1.e; // if (x2.e == 0) async(x1 = i2); // } TransposeConcurrent_xx_2(di1.i,di2.x,N1,N2); } } ApplyNewExtractionPosCommands(O1,N1); ApplyNewExtractionPosCommands(O2,N2); } //Tracer() << "\n\nAfter tracking : O1=" << O1 << "\n O2= " << O2 << '\n'; { /* +----+----+----+----+ | | | - | * | X2 +----+----+----+----+ | | | | - | * | I2 +----+----+----+----+ O2 | * | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; // ET both i2 and x2 backward past i1 { // Assumes x2,i1 are mutually exclusive. This is indeed the case after applying // the tracking rule - because x2=i1 causes x2 to track to x1. ET_xi(di2.x, di1.i); // x2 = ET(x2,i1) // Assumes i2,i1 are mutually exclusive ET2_ii(di2.i, di1.i); // i2 = ET(i2,i1) where i1 already includes i2 } // d1 must IT past [i2 x2]. // The tracking rule is : if (d1 == x2 and x2.e == 0) d1 = i2 IT_xi(di1.d, di2.i); // d1 = IT(d1,i2) } } } { /* +----+----+----+----+ | | | | * | * | X2 +----+----+----+----+ | | * | * | * | I2 +----+----+----+----+ O2 | * | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ xvector > ND1; for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; // d1 must IT past [i2 x2]. // The tracking rule is : if (d1 == x2 and x2.e == 0) d1 = i2 IT_dx(di1.d, di2.x, ND1); } } ApplyNewExtractionPosCommands(O1,ND1); } { /* +----+----+----+----+ | - | * | * | * | X2 +----+----+----+----+ | + | * | * | * | I2 +----+----+----+----+ O2 | * | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { MultiCharCDMOp::MAP::iterator m1 = O1.m_map.find(m2->first); if (m1 != O1.m_map.end()) { CDMDocIntervals& di1 = m1->second; CDMDocIntervals& di2 = m2->second; Transposeii(di1.c, di2.i); // Note this assumes that x2,c1 are mutually exclusive which is the case because // O1 || O2. ET_xi(di2.x, di1.c); // x2 = ET(x2,c1) } } } O1.CoalesceAdjacentIntervals(); O2.CoalesceAdjacentIntervals(); O1.AssertValid(); O2.AssertValid(); } /////////////////////////////////////////////////////////////////////////////////////////////////// // Merge /* Given insertions I1,I2 satisfying I1 >> I2 let I1 += I2, and clear I2 Example: I1 abcdefgh --> abc1111de111fg1111111h [ ) [ ) [ ) I2 --> abc1111d22e111fg11122221122211h [) [ ) [ ) Intervals from I1 may require splitting due to insertions by I2. I1 positions need to be shifted to the right to account for the accumulated shift from all the insertions by I2. I2 positions do not require shifting. */ template void Mergeii(T*& fi1, T*& fi2) { T* i1 = fi1; T* i2 = fi2; if (i1) { ssize_t s = 0; // Accumulated shift from I2 T* previ1 = NULL; while(i1 && i2) { ssize_t d = i2->iq - (s + i1->iq); if (d <= 0) { // [1111111) // ^ // [22222) T* nexti2 = i2->nextI; // Insert i2 immediately before i1 in I1 if (previ1) { cxAssert(previ1->nextI == i1); previ1->nextI = i2; } else { cxAssert(fi1 == i1); fi1 = i2; } i2->prevI = previ1; i2->nextI = i1; i1->prevI = i2; previ1 = i2; s += i2->size(); i2 = nexti2; } else { if (d < i1->size()) { // [111111) // ^ // [22222) SplitInterval(i1,d); } // [11111111) // ^ // [22222) i1->iq += s; previ1 = i1; i1 = i1->nextI; } } if (i2) { // Append intervals from i2 onwards onto end of I1 cxAssert(!i1); cxAssert(previ1); previ1->nextI = i2; i2->prevI = previ1; } else { // Apply shift to remaining intervals in I1 if (s) { while (i1) { i1->iq += s; i1 = i1->nextI; } } } } else { // Simply transfer all entries from I2 fi1 = i2; } fi2 = NULL; } /* Like Mergeii() except that assumes i1 has already been IT'd past i2. I.e. i1 >< i2 i1,i2 are already in post i1,i2 coordinates. Therefore no shifting is required */ template void Mergeii_noshift(T*& fi1, T*& fi2) { T* i1 = fi1; T* i2 = fi2; if (i1) { T* previ1 = NULL; while(i1 && i2) { //Tracer() << " Mergeii : i1 = " << *i1 << " i2 = " << *i2 << '\n'; ssize_t d = i2->iq - i1->iq; //Tracer() << " Mergeii : d = " << d << '\n'; if (d <= 0) { // [1111111) // ^ // [22222) T* nexti2 = i2->nextI; // Insert i2 immediately before i1 in I1 if (previ1) { cxAssert(previ1->nextI == i1); previ1->nextI = i2; } else { cxAssert(fi1 == i1); fi1 = i2; } i2->prevI = previ1; i2->nextI = i1; i1->prevI = i2; previ1 = i2; i2 = nexti2; } else { if (d < i1->size()) { // [111111) // ^ // [22222) SplitInterval(i1,d); } // [11111111) // ^ // [22222) previ1 = i1; i1 = i1->nextI; } } if (i2) { // Append intervals from i2 onwards onto end of I2 cxAssert(!i1); cxAssert(previ1); previ1->nextI = i2; i2->prevI = previ1; } } else { // Simply transfer all entries from I2 fi1 = i2; } fi2 = NULL; } // Insert j into the linked list just after i. If i = NULL then insert j at the front of the list template void InsertExtractionJustAfter(T*& first, T* i, T* j) { cxAssert(j); T* ni; if (i) { ni = i->nextX; i->nextX = j; } else { ni = first; first = j; } j->prevX = i; j->nextX = ni; if (ni) { cxAssert(ni->prevX == i); ni->prevX = j; } } /* Given [X1 X2] let X1 += X2, and clear X2 The extraction coordinate q-positions can be directly compared. Merging is straightforward except where the intervals overlap. Problem: Information preserving merging of extractions necesitates the aliasing of extractions. This is reminiscient of the repository where an interval can be associated with one insertion but any number of deletions. Proposal: In the linked list of extractions we allow for consecutive extraction intervals to have the same position and size to represent concurrent moves. Conceptually the extractions are performed in left to right order. only the last extraction may be enabled. */ void Mergedd(CDMDeleteInterval*& fx1, CDMDeleteInterval*& fx2) { CDMDeleteInterval* x1 = fx1; CDMDeleteInterval* x2 = fx2; CDMDeleteInterval* prevx1 = NULL; while(x1 && x2) { if (x1->xq + x1->size() <= x2->xq) { // Next is [11111) prevx1 = x1; x1 = x1->nextX; } else if (x2->xq + x2->size() <= x1->xq) { // Next is [22222) insert_next_x2: // Insert x2 between prevx1 and x1 CDMDeleteInterval* nextx2 = x2->nextX; InsertExtractionJustAfter(fx1, prevx1, x2); prevx1 = x2; x2 = nextx2; } else { // Intervals overlap if (x1->xq < x2->xq) { // [1111111111111 // [2222222 x1 = SplitInterval(x1, x2->xq - x1->xq, false); cxAssert(x1); prevx1 = x1->prevX; } else if (x2->xq < x1->xq) { // [2222222222222 // [1111111 SplitInterval(x2, x1->xq - x2->xq, false); cxAssert(x2->xq + x2->size() == x1->xq); goto insert_next_x2; } cxAssert(x2->xq == x1->xq); if (x2->size() < x1->size()) { // [222222) // [111111111111) SplitInterval(x1, x2->size(), false); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, x1->size(), false); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); // There may be multiple intervals here. The intervals from x2 must be inserted // in the manner of merge sort so that we maintain a total ordering by siteid. { ssize_t xq = x1->xq; // Merge in each x2 (that's at position xq) while(x2 && x2->xq == xq) { // In the manner of merge sort, step past all the x1 (that's at position xq) // with a smaller siteid while (x1 && x1->xq == xq && x1->opid.id < x2->opid.id) { prevx1 = x1; x1 = x1->nextX; } // Insert x2 between prevx1 and x1 CDMDeleteInterval* nextx2 = x2->nextX; InsertExtractionJustAfter(fx1, prevx1, x2); prevx1 = x2; x2 = nextx2; } // Step past remaining x1 that are at position xq while (x1 && x1->xq == xq) { prevx1 = x1; x1 = x1->nextX; } } } } if (x2) { cxAssert(!x1); // prevx1 points at the last interval in X1. Insert x2 onwards just after prevx1 if (prevx1) { cxAssert(prevx1->nextX == NULL); prevx1->nextX = x2; x2->prevX = prevx1; } else { cxAssert(fx1 == NULL); cxAssert(x2->prevX == NULL); fx1 = x2; } } fx2 = NULL; } void Mergexx(CDMMoveInterval*& fx1, CDMMoveInterval*& fx2) { CDMMoveInterval* x1 = fx1; CDMMoveInterval* x2 = fx2; CDMMoveInterval* prevx1 = NULL; while(x1 && x2) { if (x1->xq + x1->size() <= x2->xq) { // Next is [11111) prevx1 = x1; x1 = x1->nextX; } else if (x2->xq + x2->size() <= x1->xq) { // Next is [22222) insert_next_x2: // Insert x2 between prevx1 and x1 CDMMoveInterval* nextx2 = x2->nextX; InsertExtractionJustAfter(fx1, prevx1, x2); prevx1 = x2; x2 = nextx2; } else { // Intervals overlap { ssize_t d = x2->xq - x1->xq; if (d > 0) { // [1111111111111 // [2222222 x1 = SplitInterval(x1,d, false); cxAssert(x1); prevx1 = x1->prevX; } else if (d < 0) { // [2222222222222 // [1111111 SplitInterval(x2,-d, false); cxAssert(x2->xq + x2->size() == x1->xq); goto insert_next_x2; } } cxAssert(x2->xq == x1->xq); if (x2->size() < x1->size()) { // [222222) // [111111111111) SplitInterval(x1, x2->size(), false); } else if (x1->size() < x2->size()) { // [111111) // [222222222222) SplitInterval(x2, x1->size(), false); } // [111111) // [222222) cxAssert(x1->size() == x2->size()); // There may be multiple intervals here. The intervals from x2 must be inserted // in the manner of merge sort so that we maintain a total ordering by e. { ssize_t xq = x1->xq; ssize_t s = 0; // Accumulated e-shift from x2 while(1) { if (x2->e <= s + x1->e) { // [1) // ^ // [2) // // Insert x2 between prevx1 and x1 ++s; CDMMoveInterval* nextx2 = x2->nextX; InsertExtractionJustAfter(fx1, prevx1, x2); prevx1 = x2; x2 = nextx2; if (!x2 || x2->xq != xq) { // Apply shift to remaining intervals in X1 do { x1->e += s; prevx1 = x1; x1 = x1->nextX; } while (x1 && x1->xq == xq); break; } } else { // [1) // ^ // [2) x1->e += s; prevx1 = x1; x1 = x1->nextX; if (!x1 || x1->xq != xq) { // Insert remaining intervals from x2 cxAssert(prevx1); prevx1->nextX = x2; x2->prevX = prevx1; // Find lx2 = last x2 to be inserted CDMMoveInterval* lx2; do { lx2 = x2; x2 = x2->nextX; } while (x2 && x2->xq == xq); prevx1 = lx2; lx2->nextX = x1; if (x1) x1->prevX = lx2; break; } } } } } } if (x2) { cxAssert(!x1); // prevx1 points at the last interval in X1. Insert x2 onwards just after prevx1 if (prevx1) { cxAssert(prevx1->nextX == NULL); prevx1->nextX = x2; x2->prevX = prevx1; } else { cxAssert(fx1 == NULL); cxAssert(x2->prevX == NULL); fx1 = x2; } } fx2 = NULL; } /* O1 += O2, O2 = {} We use an in-place algorithm. We avoid unnecessary copying of data structures when O1 has many intervals. The merge of O1,O2 leads to the following matrix +----+ | xx | X2 +----+----+ | ii | xi | I2 +----+----+----+ O2 | dd | id | xd | D2 +----+----+----+----+ | cc | dc | ic | xc | C2 +----+----+----+----+ C1 D1 I1 X1 O1 Conceptually we start in the bottom right corner with a Transpose_xc() and finish along the diagonal where we can merge the creations, deletions, insertions and extractions. */ void Merge(MultiCharCDMOp& O1, MultiCharCDMOp& O2) { //Tracer() << "\nMerge entry\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); { /* +----+ | | X2 +----+----+ | | | I2 +----+----+----+ O2 | | | | D2 +----+----+----+----+ | |M | | | + | | | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { CDMDocIntervals& di2 = m2->second; if (di2.c) { CDMDocIntervals& di1 = O1.m_map[m2->first]; IT_xi(di1.x, di2.c); // x1 = IT(x1,c2) Transposeii(di1.i, di2.c); IT_xi(di1.d, di2.c); // d1 = IT(d1,c2) Mergeii(di1.c, di2.c); // assumes c1 >> c2 } } } //Tracer() << "\nAfter bottom row\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; { xvector > N2; /* +----+ | | X2 +----+----+ | | | I2 +----+----+----+ O2 | | | T | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { CDMDocIntervals& di2 = m2->second; if (di2.d) { CDMDocIntervals& di1 = O1.m_map[m2->first]; // d2 and i1 are expressed in the same coordinates (i.e. post c1,i1,c2). // Therefore it is meaningful to directly check for overlap. // Overlap implies that d2 is deleting characters moved by O1. Transpose requires // that d2 track to the extraction position of O1 Track_ETxm(di2.d, di1.i, N2); // async: if (i1 == d2) d2 = x1 } } ApplyNewExtractionPosCommands(O2,N2); } //Tracer() << "\nAfter track ET of deletes past moves\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; { /* +----+ | | X2 +----+----+ | | | | | I2 +----+----+----+ O2 | M | - | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 Notes ----- Merging moves needs some careful thought! Let O = [O1 O2] (i.e. merge) Then O.i, O.x will both be specified in post O.i coordinates. Now O.i is the combined effect of O1.i, O2.i. Therefore we see that merge involves ITing i1,x1 past i2 so that i1,x1,i2,x2 are all specified in the same (post i1+i2) coordinates. Now rather conveniently this coordinate system is precisely the one to be used to test for conflicting moves. For given [O1 O2] there are two cases where moves conflict 1. x2 = i1 2. x2 = x1 We must check both cases to find all examples of conflict. When there are conflicting moves we need to merge e-coords correctly. Now e-coords are associated with single char insertions, so merging e-coords will resemble the Mergeii() algorithm! However, before worying about merging we should think about the required tracking rule. Basically we need to unchain any chained moves. The rule is if (x2 == i1) x2 = x1; Consider that this rule is fully applied. Later when we perform Merge_xx() we can identify all conflicts by simply testing x2 = x1. In that case we invoke Merge_ee() (which is algorithmically like Mergeii()). */ for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { CDMDocIntervals& di2 = m2->second; CDMDocIntervals& di1 = O1.m_map[m2->first]; // Note this assumes that d2,i1 are mutually exclusive. That is indeed the case after // applying the tracking rule if (i1 == d2) d2 = x1 ET_xi(di2.d, di1.i); // d2 = ET(d2,i1) // This assumes that d1,d2 are in the same coord system. We get the union of all // deletes, which increases aliasing as required. Mergedd(di1.d, di2.d); IT_xi(di1.x, di2.i); // x1 = IT(x1,i2) IT2_ii(di1.i, di2.i); // i1 = IT(i1,i2) where i2 already includes i1 } } //Tracer() << "\nAfter IT x1,i1 past i2\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; { /* +----+ | T | X2 +----+----+ | * | * | I2 +----+----+----+ O2 | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ xvector > N2; for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { CDMDocIntervals& di2 = m2->second; if (di2.x) { CDMDocIntervals& di1 = O1.m_map[m2->first]; // Note that i1,x1,i2,x2 are now all in the context of both i1,i2 // Unchain chained moves // I.e. Track: if (x2 == i1) { x2 = x1; } Track_ETxm(di2.x,di1.i,N2); } } ApplyNewExtractionPosCommands(O2,N2); } //Tracer() << "\nAfter unchain chained moves\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; /* +----+ | M | X2 +----+----+ | M | * | I2 +----+----+----+ O2 | | * | * | D2 +----+----+----+----+ | * | * | * | * | C2 +----+----+----+----+ C1 D1 I1 X1 O1 */ // Merging of deletions or extractions must be delayed until after tracking of D2 or X2 // has been completed. for (MultiCharCDMOp::MAP::iterator m2 = O2.m_map.begin() ; m2 != O2.m_map.end() ; ++m2) { CDMDocIntervals& di2 = m2->second; CDMDocIntervals& di1 = O1.m_map[m2->first]; // This should assume that i1,i2 are in the same post i1,i2 coordinate system Mergeii_noshift(di1.i, di2.i); // assumes i1 >< i2 // This should assume that x1,x2 are in the same post i1,i2 coordinate system // This should do this: if (x2 == x1) { Merge_ee(); } Mergexx(di1.x, di2.x); } //Tracer() << "\nBefore clear O2 map\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; O2.m_map.clear(); //Tracer() << "\nBefore CoalesceAdjacentIntervals()\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; O1.CoalesceAdjacentIntervals(); //Tracer() << "\nBefore assert valid\n O1 = " << O1 << "\n O2 = " << O2 << '\n'; O1.AssertValid(); O2.AssertValid(); } void Merge(MultiCharCDMOp& O1, const MultiCharCDMOp& O2) { //Tracer() << "\nMerge with O1 = " << O1 << " O2 = " << O2 << '\n'; MultiCharCDMOp copyO2 = O2; Merge(O1, copyO2); //Tracer() << "\n---> O1 = " << O1 << " O2 = " << copyO2 << '\n'; }