58 Merging coincident string insertions

todo: is anything below even useful?

Let O1,O2 be operations representing coincident insertions of q-contiguous intervals. WLOG assume the insertions are at q=0. Let's assume O1,O2 each already have monotone increasing siteids. We want an algorithm to dual IT these insertions, producing a result with monotone increasing effective siteids. We need a proof of correctness. Correct just means that under merging, all sites agree on the order of the coincident insertions. If the proof is hard we might first try implementing the proposed algorithm to at least check if it appears to be correct.

Representation

struct Interval
{
    Opid opid;          // identifies the op(s,t) that generated the operation
    int q;              // post-insertion q position
    int n;              // Number of characters to be inserted (the actual characters are stored elsewhere)
    int u;              // temporal index
};

struct InsertionIntervals
{
    forward_linked_list<Interval> intervals;
    int next_u;
};