class Chunk:
    def __init__(self, start, end, data, height, parent, leaf_count):
        self.start = start
        self.end = end
        self.data = data
        self.height = height
        self.parent = parent
        self.leaf_count = 1
    def list_parents(self, root=None):
        parents = []
        while self is not None:
            parents.append(self)
            self = self.parent
        if root is not None and parents[-1] is not root:
            parents.append(root)
        parents.reverse()
        return parents
    def shared_parents(self, *others, root=None):
        parents = self.list_parents()
        for other in others:
            parents = [
                    parent for parent, compare
                    in zip(parents, other.list_parents())
                    if parent.data is other.data
            ]
        if root is not None and parents[0] is not root:
            parents.insert(0, root)
        return parents
    def trimmed(self, start, end, parent):
        if start < self.end and end > self.start:
            # the trim overlaps
            result = []
            if start > self.start:
                result.append(self.end_trimmed(start, parent))
            if end < self.end:
                result.append(self.start_trimmed(end, parent))
            return result
        else:
            return [self]

class Data(Chunk):
    def __init__(self, start, data, parent = None):
        super().__init__(start, start + len(data), data, 0, parent, 1)
    def end_trimmed(self, new_end, parent):
        trimmed = Data(self.start, self.data[:new_end - self.start], parent)
        assert trimmed.end == new_end
        return trimmed
    def start_trimmed(self, new_start, parent):
        trimmed = Data(new_start, self.data[new_start - self.start:], parent)
        assert trimmed.end == self.end
        return trimmed
    #def merged(*datas):
#

class FlushIndex(Chunk):
    def __init__(self, prev_flush = None):
        data = []
        if prev_flush is not None:
            leaf_count = prev_flush.leaf_count
            max_depth = leaf_count.bit_length()
            #copy in index of parent, referencing parent where depth is not too deep
            #for idx, entry in enumerate(prev_flush.data):
            #    if entry.height < 
#
#            - expand where too deep
#            - shallow where only 1 child
            height = prev_flush.height + 1
            data = [prev_flush]
            super().__init__(parent.start, parent.end, data, height, None, parent.leaf_count)
        else:
            super().__init__(None, None, [], 0, None, 0)

    def write(self, offset, data):
        for idx, entry in enumerate(self.data):
            if entry.start > 
            

        trim index to left and right of new data. update leaf count.
            link trimmed nodes shallower if parts are removed
            if a branch is made shallower by losing leaves, it may become mergeable with its neighbors
        remove items that data overwrites and insert data where it goes
        merge adjacent data items
        update leaf count if write does not merge

# parent means the data leaves are underneath
# so we are parent to the old flush, not other way around