51 Effective siteids
Consider that the first interval in temporal order in O1 is an interval with siteid s1, and the second is an interval with siteid s2 and appearing on the left of the first.
O1: s2 s1
If s2 < s1 then this breaks up O1 neatly into three regions. Otherwise if s1 < s2 then we actually have a no man's land between them.
O1: s2 s1
<s1 NONE >s1
We can emulate the selection process by setting the effective siteid of all intervals in this range to s1.
Alternatively consider that s2 is to the right of s1. Then we have
O1: s1 s2
If s1 < s2 then this breaks up O1 neatly into three regions. Otherwise if s2 < s1 then we again have a no man's land between them. Again, we can emulate the selection process by setting the effective siteid of all intervals in this range to s1.
Now consider s1,s2,s3. There are lots of cases to consider! The intervals can appear in 6 different orders by q position and 6 different orders by siteid, giving 36 combinations! It is not clear whether all these are possible.
Calculation of effective siteids
Let O be q-contiguous. We want to calculate the effective siteid and effective temporal index of its intervals. It is claimed we can do this with essentially a simple left to right linear scan.
[TODO: That's not quite true - there are possibly some right to left scans involved as well - maybe enough to make it O(n2) in pathological cases].
Let the intervals be ordered by q-position and each interval records its generating siteid s and temporal index u.
The following algorithm in C++ assumes there are n given q-contiguous intervals ordered by q-position and for each i in [0,n), s[i] is the siteid and u[i] is the temporal index of the ith interval. The function calculates the effective siteid es[i], and the effective temporal index eu[i] for each i. We assume n > 0.
void CalculateEffectiveSiteids(const int s[],const int u[],int n, int es[], int eu[])
{
es[0] = s[0];
eu[0] = u[0];
for (int i=1 ; i < n ; ++i)
{
if (es[i-1] <= s[i])
{
es[i] = s[i];
eu[i] = u[i];
}
else
{
assert(eu[i-1] != u[i]);
if (eu[i-1] < u[i])
{
// i-1 dominates i, so i inherits es,eu from i-1
es[i] = es[i-1];
eu[i] = eu[i-1];
}
else
{
// i dominates i-1, so we must scan right to left as far as
// needed to assign the s,u of i to the es,eu of itself and the
// preceding intervals
int j = i;
do
{
es[j] = s[i];
eu[j] = u[i];
--j;
if (es[j] > s[i])
{
if (eu[j] < u[i])
{
// j dominates i, so we need to assign the es,eu
// of j to all the intervals in [j+1,i].
for (int k=j+1 ; k <= i ; ++k)
{
es[k] = es[j];
eu[k] = eu[j];
}
break;
}
}
else
{
break;
}
} while (j > 0);
}
}
}
}
Example
For the given list, we conceptually break it up into maximal q-contiguous pieces. E.g. in the following there are 3 maximal q-contiguous pieces.
1 2 3
[------------)[---)[-----) [--------)[---)[--------------------) [---)
<--------- q contiguous ---------->
For each maximal q-contiguous piece calculate the effective siteids using a left to right scan.
[Technically that's not quite true - there are possibly some right to left scans involved as well - maybe enough to make it O(n^2) in pathological cases]
For q-contiguous intervals it is required that the effective siteids increase left to right. In the following example it must be the case that es1 < es2 < es3.
[------------)[---)[-----)
s1 s2 s3
es1 es2 es3
If the s1,s2,s3 on the intervals satisfy s1 < s2 < s3 (i.e. the siteids are increasing left to right), then this is the easy case. Result will be es1=s1, es2=s2, es3=s3.
Here is a more complex example. Let the following list of (s,u) values be for a maximal q-contiguous section:
s 2 4 6 8 2 5 5 3
u 6 0 7 4 6 5 3 2
Consider that we iterate through the intervals from O in order of q-position. While the siteid monotone increases we simply assign es and eu from s,u
es 2 4 6 8
eu 6 0 7 4
Now we want to add the interval with s=2, u=6. We can no longer simply assign es,eu from s,u because it will break the requirement that effective siteids monotone increase from left to right. There are two possibilities, depending on the comparison of u coord to the eu of the last interval in the list we are building. In this case the new interval has a larger (i.e. losing) u coord so it inherits the es=8,eu=4 from the tail of the list:
es 2 4 6 8 8
eu 6 0 7 4 4
Now we want to add s=5, u=5. Again we have a lower siteid than at the tail of the list we are building, so we must compare u values. Again we inherit es=8, eu=4:
es 2 4 6 8 8 8
eu 6 0 7 4 4 4
Now we want to add the interval with s=5,u=3. This time the entry to be added dominates the tail of the list because it has a lower u coord. This dominating s,u is propagated, starting from the tail of the list using a right to left scan until the requirement that siteids monotone increase is established once again:
es 2 4 5 5 5 5 5
eu 6 0 3 3 3 3 3
Finally we want to add the interval with s=3, u=2. Again this dominates intervals in the tail so we propagate es=3,eu=2 from right to left. Eventually we reach the interval with es=4,eu=0. This dominates all the intervals that come after it, so we have to scan left to right again applying es=4, eu=0. The end result is:
es 2 4 4 4 4 4 4 4
eu 6 0 0 0 0 0 0 0
It is conceivable that any risk of O(n2) behavior can be eliminated by using a representation that partitions this list into sub-lists and we avoid the need to explicitly iterate through a sub-list when applying a different (es,eu).
Properties
Then ordering based on the effective siteids is equivalent to the order that arises from transforming a list against a list where each list is in temporal order.
Let each interval be described by s and q. Let size = 1. A list L in temporal order is characterised by L[u].s and L[u].q. We assume L[0].q = 0. In spatial order we have M[q].s and M[q].u
How to map from L to M: Note that s(u) is maintained in both representations.
Putting it another way: Let s[u] provide s as a function of u = 0,1,2,.... Let Q[u] provide q as function of u, and u[q] provide u as a function of q = 0,1,2,...
E.g.
u 0 1 2 3 4 5 6
s[u] 4 5 8 5 2 2 6
Q[u] 0 1 1 2 2 0 2
q 0 1 2 3 4 5 6
s[q] 2 4 6 8 2 5 5
u[q] 5 0 6 2 4 3 1
-
Calculate u[q] from Q[u]
We insert u=0 then u=1 then u=2 and so on at the position given by Q[u]
u[q] 0 0 1 0 2 1 0 2 3 1 0 2 4 3 1 5 0 2 4 3 1 5 0 6 2 4 3 1 -
Calculate Q[u] from u[q]
We extract u=0 as an L factor resulting in q that equals the number of elements to its left that have already been extracted (which must be 0). Then we extract u=1, and so on.
u[q] q 5 *0 6 2 4 3 1 0 5 *0 6 2 4 3 *1 1 5 *0 6 *2 4 3 *1 1 5 *0 6 *2 4 *3 *1 2 5 *0 6 *2 *4 *3 *1 2 *5 *0 6 *2 *4 *3 *1 0 *5 *0 *6 *2 *4 *3 *1 2
For any given adjacent pair q,q+1, if s[q] > s[q+1] then let either q inherit from q+1 or vice versa, the winner being chosen according to smaller u.
Then: the final result is independent of the order in which effective s,u are applied.
Def: Let [] denote the empty list.
Def: Let L1,L2 be lists. Then L1+L2 denotes the concatenation of L1,L2. + is associative but doesn't commute.
Def: let L be a list. Then n*L denotes n additions of L+L+...+L
i.e. 0*L = []
1*L = L
2*L = L+L
3*L = L+L+L
etc
Notes
For any given operation we can formalise the concept of breaking it up into as few q-contiguous pieces as possible. ie each q-contiguous piece is maximal because there are no adjacent pieces to which it can be merged to form a larger q-contiguous range.
For each maximal q-contiguous piece we can calculate the effective siteids as shown above. As a result we end up with a very simple dual IT algorithm!
Note that for an operation O with vin(O) = v∅, it will always be the case that (for a given text field) O is q-contiguous. In particular the entire HB is always q-contiguous. Gaps only appear when we take an RFactor of O with respect to some causally valid vector time. The calculated effective siteids of the intervals depend on the locations of the gaps. This shows that there is no point calculating effective siteids for the entire HB because they won't generally be applicable to an RFactor relevant to dual IT.
Maintaining effective siteids in a transient suffix
The only remaining ingredient is to determine how to update the effective siteids under merging. More specifically given two q-coincident, q-contiguous operations, what are the effective siteids of the merged result? Well of course there is nothing to do because the merge results in a single q-contiguous result that is ordered by effective siteid, and working in the manner of merge sort.
It would seem that local operations are the culprit as far as upsetting the ordering by siteid in q-contiguous sections. So we need to investigate what happens to effective siteids when we insert an interval. Note that this will always have the largest u coord.
The rule is very simple:
When an insertion operation is generated, we consider the characters to the left and to the right of the insertion position. We refer to these as the neighbors. If the local site's siteid falls between the siteids of the neighbors there is nothing to do. However if it is smaller than both neighbors then it inherits s,u from the neighbor with smallest s. If it is larger than both then it inherits the s,u from the neighbor with largest s.
PROBLEM: This doesn't account for the fact that factorisation is often required on a transient suffix, and factorisation affects the effective siteids.
EffectiveSiteIds.h in cxOT
Source: Ceda/cxOT/EffectiveSiteIds.h