62 Sending a delta on a vector field

At the base vector time the field already contains real characters intersperced with tombstones. 

   ..........*********...........................******......***********........****

Nevertheless as far as the working set is concerned we can ignore these tombstones. No information about them is recorded by the working set.

Since the base vector time we have

  1. additional insertions of real characters
  2. additional insertions of tombstones
  3. conversion of existing characters to tombstones.

This is recorded using

  1. list of insertion intervals (s,t,q,n) since base vector time
  2. list of deletion intervals (s,t,q,n) since base vector time

Delta is sent as:

  1. list of insertion intervals
  2. list of deletion intervals. This may delete characters that existed before the base vector time, and also delete characters inserted since the base vector time.
  3. a single string of the inserted characters.

However we would rather not send tombstone characters (we haven't even recorded them!). Is that possible?

In theory the receiver can determine the intersection of 1) and 2) (which are both expressed in the same post insertion q coords), and therefore determine the sections of the string that contain tombstones.

So we use this approach...

To gather the delta we iterate through the insertion intervals 

    [----)   [---------------)         [----)    [------------)    [---)

A subset of these need to be sent (according to which (s,t) are outside X(rhv)). E.g. 

             [---------------)                   [------------)    [---)

For each of thsse we want to send exactly those bytes that are currently present in the field

We can show the intervals from the recorded deletions as well: 

             [---------------)                   [------------)    [---)          I = insertions outside X(rhv)

        [-------)  [---)          [---) [--)        [--)   [-----------------)    D = deletions

Note that I and D are both recorded in the same post-insertion coordinates.

We want to gather the characters in I\D. From D, we can record p as we go so we know what parts need to be copied from the xvector field.

Dealing with arbitrary xvector<T>

It is assumed q coordinates are in T not bytes. We need to know the size of T so we can adjust pointers in the xvector correctly.

VectorGetDelta.h

Source: Ceda/cxOT/VectorGetDelta.h