19.7 Elementary interval transformations
The major algorithms are ordered compositions of the following linear list scans. Advancing
i follows nextI; advancing x follows nextX.
Dual IT of concurrent insertion lists
DualITii(i1,i2) requires context-equivalent concurrent insertion lists.
template <class T1, class T2>
void DualIT_ii(T1* i1, T2* i2)
{
int s1 = 0;
int s2 = 0;
while (i1 && i2)
{
assert(i1->opid.id != i2->opid.id);
int d = (s1 + i2->iq) - (s2 + i1->iq);
if (d < 0 || (d == 0 && i2->opid.id < i1->opid.id))
{
i2->iq += s1;
s2 += i2->size();
i2 = i2->nextI;
}
else
{
i1->iq += s2;
s1 += i1->size();
i1 = i1->nextI;
}
}
while (i2) { i2->iq += s1; i2 = i2->nextI; }
while (i1) { i1->iq += s2; i1 = i1->nextI; }
}The site comparison orders coincident concurrent insertions.
IT2 of serialised insertion lists
IT2ii(i1,i2) requires mutually exclusive insertions with i1 >> i2.
template <class T1, class T2>
void IT2_ii(T1* i1, const T2* i2)
{
int s = 0;
while (i1 && i2)
{
int d = i2->iq - (s + i1->iq);
if (d <= 0)
{
s += i2->size();
i2 = i2->nextI;
}
else
{
if (d < i1->size()) SplitInterval(i1, d);
i1->iq += s;
i1 = i1->nextI;
}
}
while (i1) { i1->iq += s; i1 = i1->nextI; }
}The split case is:
[111111)
^
[22222) split i1 at the insertion point
IT of extraction past insertion
ITxi(x,i) requires context-equivalent, mutually exclusive lists.
template <class T1, class T2>
void IT_xi(T2* x, const T1* i)
{
int s = 0;
while (i && x)
{
int d = i->iq - (s + x->xq);
if (d <= 0)
{
s += i->size();
i = i->nextI;
}
else
{
if (d < x->size()) SplitInterval(x, d, false);
x->xq += s;
x = x->nextX;
}
}
while (x) { x->xq += s; x = x->nextX; }
} [iiiiiii) insertion is on the left: accumulate its length
x
[xxxxxxxx) insertion is inside: split the extraction
i
ET2 of convergent insertion lists
ET2ii(i2,i1) requires mutually exclusive insertions already expressed in their common
post-insertion coordinates.
template <class T1, class T2>
void ET2_ii(T2* i2, const T1* i1)
{
int s = 0;
while (i1 && i2)
{
if (i1->iq + i1->size() <= i2->iq)
{
s += i1->size();
i1 = i1->nextI;
}
else if (i2->iq + i2->size() <= i1->iq)
{
i2->iq -= s;
i2 = i2->nextI;
}
else
{
assert(0); // The insertion lists must be mutually exclusive.
}
}
while (i2) { i2->iq -= s; i2 = i2->nextI; }
}ET of extraction past insertion
ETxi(x,i) has the same scan as ET2ii, using xq for extraction
positions. Each insertion ending before x contributes to s; subtract
s when processing x. Any overlap violates the required mutual exclusion.
template <class T1, class T2>
void ET_xi(T1* x, const T2* i)
{
int s = 0;
while (i && x)
{
if (i->iq + i->size() <= x->xq)
{
s += i->size();
i = i->nextI;
}
else if (x->xq + x->size() <= i->iq)
{
x->xq -= s;
x = x->nextX;
}
else
{
assert(0); // The lists must be mutually exclusive.
}
}
while (x) { x->xq -= s; x = x->nextX; }
}Transpose of insertion lists
Transposeii(i1,i2) requires the context-serialised insertion sequence
[i1,i2]. It changes both lists in place to [i2',i1'], where
i2' >> i1', and applying either sequence has the same result. The equality case places
i2 before i1, as required when reversing their serial order.
template <class T1, class T2>
void Transposeii(T1* i1, T2* i2)
{
int s1 = 0;
int s2 = 0;
while (i1 && i2)
{
int d = i2->iq - (s2 + i1->iq);
if (d <= 0)
{
i2->iq -= s1;
s2 += i2->size();
i2 = i2->nextI;
}
else
{
if (d < i1->size()) SplitInterval(i1, d);
i1->iq += s2;
s1 += i1->size();
i1 = i1->nextI;
}
}
while (i2) { i2->iq -= s1; i2 = i2->nextI; }
while (i1) { i1->iq += s2; i1 = i1->nextI; }
}Deletes against move extractions
ITdx(d,x,N) scans extraction intervals without position shifts.
[ddddddddddddd) split d; continue with its right part
[xxxxxxx)
[xxxxxxxxxxxxx) split x; continue with its right part
[ddddddd)
[dddddddddddd) split d after common span
[xxxxxx)
[dddddd) split x after common span
[xxxxxxxxxxxx)
After splitting, both current spans are equal. If the head of the move alias group has
e=0, append a command to track the complete deletion alias group to the move's
(idoc,iq). Advance past both complete alias groups. Commands are applied after all
document scans.
void IT_dx(
DeleteInterval* d,
MoveInterval* x,
std::vector<SetNewExtractionPosCommand<DeleteInterval> >& N)
{
while (d && x)
{
if (d->xq + d->size() <= x->xq)
{
d = d->nextX;
}
else if (x->xq + x->size() <= d->xq)
{
x = x->nextX;
}
else
{
if (d->xq < x->xq)
d = SplitInterval(d, x->xq - d->xq, false);
else if (x->xq < d->xq)
x = SplitInterval(x, d->xq - x->xq, false);
assert(x->xq == d->xq);
if (x->size() < d->size())
SplitInterval(d, x->size(), false);
else if (d->size() < x->size())
SplitInterval(x, d->size(), false);
assert(d->size() == x->size());
if (x->e == 0)
N.push_back(SetNewExtractionPosCommand<DeleteInterval>(
d, x->idoc, x->iq));
int xq = d->xq;
do d = d->nextX; while (d && d->xq == xq);
do x = x->nextX; while (x && x->xq == xq);
}
}
}Wrappers
void IT(Operation& O1, const Operation& O2)
{
Operation copyO2 = O2;
DualIT(O1, copyO2);
}
void ET(Operation& O1, const Operation& O2)
{
Operation copyO2 = O2;
Transpose(copyO2, O1);
}Deep copying must recreate every move once and join that new object into both copied lists; copying the insertion and extraction lists independently would violate shared identity.