OR-Set Merge

An Observed-Remove Set (OR-Set) tracks adds and removes using unique tags. A remove only deletes the specific add tags it has observed.

To merge two OR-Sets, take the union of their Adds and Removes. An element is present if it has at least one add tag not present in Removes.

Return the merged OR-Set and the sorted list of elements present.

Types

type Tag struct {
    Replica string
    Counter int
}

type TaggedElem struct {
    Element string
    Tag     Tag
}

type ORSet struct {
    Adds    []TaggedElem
    Removes []TaggedElem
}

Function signature

func MergeORSet(a, b ORSet) (ORSet, []string)

Example

a.Adds    = [("x", r1#1), ("y", r1#2)]
a.Removes = []

b.Adds    = [("x", r2#1)]
b.Removes = [("x", r1#1)]

merged elements = ["x", "y"]  // r2#1 remains for x

Constraints

• 0 <= len(Adds), len(Removes) <= 100000
• Tags are unique within each list

Notes

• The returned element list must be sorted ascending.
• The merged OR-Set should not contain duplicate tags.