68 Take RFactor of insertions/deletions on text field
A delta on a xvector
I,D are expressed in the same post insertion q-coordinates.
B represents a contiguous buffer of the elements to be inserted but not deleted by the delta. Each element takes up 'elementSize' bytes.
Precondition : B.size() == (I\D).Extent() * elementSize.
v is a given causally valid vector time. This function replaces I by RFactor(I,v). It also partitions B into Binside and Boutside according to whether an element in B (i.e. an element to be inserted but not deleted by the delta) was inserted by an operation identified by (s,t) inside X(v) or not.
I ← Rfactor(I,v)
Binside, Boutside ← B partitioned according to whether the insertion is inside X(v) or outside X(v).
void TakeRFactor(
const VectorTime& v,
VectorInsertions& I,
const VectorDeletions& D,
ssize_t elementSize,
const xvector<octet_t>& B,
xvector<octet_t>& Binside,
xvector<octet_t>& Boutside)
{
Binside.clear();
Boutside.clear();
// For processing the buffer B associated with insertions for I\D
const octet_t* p = B.data();
// Allow for measurement of extents of ([0,q) intersect D) for monotone increasing
// values of q.
MeasureExtentsOnVectorDeletions measureDExtents(MakeRangeFromBiDirectionalIterators(D));
// Iterate through the intervals of I. For each interval we determine whether it exists
// in X(v). This allows us to delete intervals inside X(v) as we go, in order to convert
// I into an RFactor.
VectorInsertions::Node* i = I.m_c.m_first;
while(i)
{
/*
Note that D may split interval i up into any number of parts
q1 q2
[------------------------------------) i (an interval of I)
[--) [---) [------------) D
[---) [-----) [-----------) i\D
For each i = [q1,q2) in I we can use measureDExtents to measure
e1 = D.extent(q1)
e2 = D.extent(q2)
Then e2-e1 represents the extent of (i intersect D).
That means the extent of i\D is
(q2-q1) - (e2-e1)
Let
n = ((q2-q1) - (e2-e1)) * elementSize
n represents the number of bytes in B associated with the insertion i.
*/
// Note that e1 must be calculated before e2, in order to follow the rule that
// measureDExtents.Extent(q) is called with monotone increasing values of q.
const ssize_t e1 = measureDExtents.Extent(i->m_q);
const ssize_t e2 = measureDExtents.Extent(i->m_q + i->m_n);
const ssize_t n = (i->m_n - (e2-e1)) * elementSize; // total extent of (i\D)
VectorInsertions::Node* next = i->m_next;
if (v.ExtentContains(i->m_opid))
{
// i inside X(v)
Binside.append(p, p+n);
// i is not part of the RFactor so erase i from I
I.m_c.Erase(i);
}
else
{
// i outside X(V)
Boutside.append(p, p+n);
}
p += n;
i = next;
}
cxAssert(p == B.data_end());
}Concept: FilteredListUpdater
A FilteredListUpdater is a concept with drop and keep methods which is used to define which elements in a linear list to drop and keep.
concept FilteredListUpdater
{
void drop(ssize_t n); // drop the next n elements of the linear list
void keep(ssize_t n); // keep the next n elements of the linear list
};A realisation of this concept on a reflected xvector is as follows:
class FilteredListUpdaterOnReflectedVector
{
public:
FilteredListUpdaterOnReflectedVector(ReflectedVector& rv) :
rv(rv)
{
keepPos = dropPos = rv.vf->data();
}
void drop(ssize_t n)
{
if (!isPOD)
{
DestructReflectedArrayVariable(rbcElement, n, dropPos);
}
dropPos += n * elementSize;
}
void keep(ssize_t n)
{
ssize_t numBytes = n * elementSize;
std::memmove(keepPos, dropPos, numBytes);
keepPos += numBytes;
dropPos += numBytes;
}
private:
ReflectedVector& rv;
octet_t* keepPos;
octet_t* dropPos;
};New idea
We want the function TakeRFactor to be moved from cxOperation to cxOT.
A non-leaky abstraction of a vector is needed, which doesn't have to deal with the vector element size.
Splitting B into Binside, Boutside is not required. Instead we just want to transform B to Boutside and delete the elements that we were moving into Binside.
Consider that we assume the vector B is represented by a variable of type VectorFieldUpdater. The RFactor of B is defined by the calls to keep/drop on its elements.
// Calculates the RFactor of the composite operation (I,D,B) with respect to vector time v
// and replaces I and B with their RFactor versions.
// For an optimisation D is not updated because it happen not to be required.
template<typename VectorInsertions, typename VectorDeletions, typename FilteredListUpdater, typename VectorTime>
void TakeRFactor(VectorInsertions& I, const VectorDeletions& D, FilteredListUpdater& B, const VectorTime& v)
{
// Allow for measurement of extents of ([0,q) intersect D) for monotone increasing
// values of q.
MeasureExtentsOnVectorDeletions measureDExtents(MakeRangeFromBiDirectionalIterators(D));
// Iterate through the intervals of I. For each interval we determine whether it exists
// in X(v). This allows us to delete intervals inside X(v) as we go, in order to convert
// I into an RFactor.
for (auto i = I.m_c.m_first ; i ; i = i->m_next)
{
/*
Note that D may split interval i up into any number of parts
q1 q2
[------------------------------------) i (an interval of I)
[--) [---) [------------) D
[---) [-----) [-----------) i\D
For each i = [q1,q2) in I we can use measureDExtents to measure
e1 = D.extent(q1)
e2 = D.extent(q2)
Then e2-e1 represents the extent of (i intersect D).
That means the extent of i\D is
n = (q2-q1) - (e2-e1)
n represents the number of elements in B associated with the insertion interval i.
*/
// Note that e1 must be calculated before e2, in order to follow the rule that
// measureDExtents.Extent(q) is called with monotone increasing values of q.
auto e1 = measureDExtents.Extent(i->m_q);
auto e2 = measureDExtents.Extent(i->m_q + i->m_n);
auto n = (i->m_n - (e2-e1)); // total extent of (i\D)
if (v.ExtentContains(i->m_opid))
{
// i inside X(v)
B.drop(n);
I.m_c.Erase(i); // i is not part of the RFactor
}
else
{
// i outside X(V)
B.keep(n);
}
}
}VectorRFactor.h in cxOT
Source: Ceda/cxOT/VectorRFactor.h