psudocode for generic operation transform

gistfile1.py

# From "Real-Time Cooperative Editing Systems", Chengzheng Sun et al.
import copy


def generic_operation_transform(new_op, HB):
    """
    :param new_op: operation to be transformed
    :param HB: history buffer
    """
    # index of independent ops
    independent_ops = [idx for idx, item in enumerate(HB) if new_op.independent(item)]

    # if there are no independent ops, new_op shares the same context
    if len(independent_ops) is 0:
        return new_op

    # otherwise, find all ops that causally preceeds new_op
    k = independent_ops[0]
    preceding_ops = [idx for idx, item in enumerate(HB[k+1:]) if new_op.causally_precedes(item)]

    if len(preceding_ops) is 0:
        # if there are no preceeding ops, all the ops are independent
        # include all
        return LIT(HB[k, -1], new_op)
    else:
        # preceding ops should be excluded, and they also need to be
        # transformed to the new operation's execution context
        exclude_list = []
        for idx in preceding_ops:
            reverted = LET(HB[idx], HB[k:idx:-1])
            exclude_list.append(LIT(reverted, exclude_list))

        return LIT(LET(op_new, exclude_list[::-1]), HB[k:])


def LET(op, lst):
    return reduce(ET, lst, copy.deep_copy(op))

def LIT(op, list):
    return reduce(IT, lst, copy.deep_copy(op))

def IT(op1, op2):
    return op1.include(op2)

def EX(op1, op2):
    return op1.exclude(op2)


class BaseOperation(object):
    def __init__(self, site, sv):
        self.site = site
        self.sv = sv

    @property
    def site_state(self):
        return self.sv[self.site]

    def causally_precedes(self, op):
        return all(s1 <= s2 for s1, s2 in zip(self.sv, op.sv)) # and different op

    def independent(self, op):
        return not self.causally_precedes(op) and not op.causally_precedes(self)

    def include(self, op):
        raise NotImplementedError("i have a snake in my boots")

    def exclude(self, op):
        raise NotImplementedError("to infinity and beyond")