last stable version was at
https://lists.cpunks.org/pipermail/cypherpunks/2022-July/102291.html
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
