69 Temporal Index values on insertion intervals
Consider a text field which supports insert and erase operations. Each insertion interval on the text field records a temporal index u. This is an integer which is part of the persistent state. In practise a 32 bit integer is probably adequate. This is only a minor increase in storage space, and doesn't complicate serialisation or splitting of intervals.
u is assigned at the time the insertion is originally generated and it never changes from the original value. It follows that for a given insertion interval all sites record the same value of u.
When an insertion interval splits, both parts inherit the same s,t and u values. One could say that s,t,u are global, immutable properties of occurrences of characters within a text field.
When an insertion is generated a site always assigns a value of u that is strictly larger than the u assigned to all other existing intervals in the field on that site at that point in time (whether locally or remotely generated).
It follows that the ordering by u respects the causal ordering on the intervals (i.e. the partial ordering of the precedes relation), meaning that for intervals i1,i2
i1 → i2 ⇒ i1.u < i2.u.
The converse is false.
Possible alternative
An alternative could be for insertion intervals to simultaneously take part in two double linked lists - ie for both a spatial ordering by q and a temporal ordering by u. However we reject this approach for the following reasons:
- this doesn't appear to be a very good fit for the merge algorithm because global u position order within a large O1 may take us for a long detour and we need to skip past many intervals until we reappear back inside the range of interest relevant to the merge algorithm. This could easily be much more expensive than a simple linear scan for minimum u if the range of interest is small.
- Serialisation of an operation is complicated
- It is less space efficient than simply storing a temporal index in each interval
- Splitting intervals is complicated