Concurrent edits are created against the same document state but may be applied in a different order. Operational transformation adjusts a pending position so it still identifies the corresponding location after earlier inserts and deletes.
Design an EditPositionTransformer class:
EditPositionTransformer() creates a stateless transformer.int transform(int position, int[][] operations) returns the position after applying every concurrent operation in order.
Each operation is [type, p, length]:
- Type
0 inserts length characters at p. If p <= position, shift position right by length. - Type
1 deletes the half-open range [p, p + length). - If
p + length <= position, shift position left by length. - If
p >= position, leave position unchanged. - Otherwise, the deletion covers
position, so set position to p.
Apply each rule to the position produced by the preceding operation.
Example 1:
Input:
Output:
Explanation: The deletion covers [3,7), including position 5. The transformed position becomes the start of the deleted range.
Example 2:
Input:
Output:
Explanation: The insert shifts 10 to 12. The later deletion ends before 12, so it shifts the position left to 11.
Constraints
0 <= position <= 10^90 <= operations.length <= 10^5operations[i].length == 3operations[i][0] is 0 or 1.0 <= operations[i][1] <= 10^91 <= operations[i][2] <= 10^9- Every intermediate position and
p + length fit in a signed 32-bit integer. - At most
100 calls are made to transform.
Transform an Edit Positionhard