last stable version was at https://lists.cpunks.org/pipermail/cypherpunks/2022-July/102291.html # member variables draft. i think this is all the information that # was being replaced by leaf and index iteration. # - leaf count can be updated by summing children when graph is # changed. # - height is simply maximum child height + 1, can also update # when graph is changed # - parents is for adding dropped nodes to when branches are made # more shallow. it can be prefix-compared against to find a # shared ancestor when unifying neighboring entries. the only # other update I'm thinking of is when a new flush adds a shared # parent to every node. # it may be simpler or clearer to retain parent references, # and walk up them to the root to form parents lists when # they are needed; unsure class Data: def __init__(self, offset, data, end = None, height = 0, _parents = [], leaves = 1, parent = None): self.start = offset self.data = data if end is None: self.end = self.start + len(self.data) self.height = 0 self.parent = parent self._parents = _parents self.leaves = 1 class Flush: def __init__(self, parent = None): self.parent = parent if self.parent is not None: self.index = [self.parent] # this should expand self.parent if it's too deep, and shallow it if there is only one child # we don't want to expand the index past the max depth else: self.index = [] def write(self, offset, data): # 1. trim index to left and right of data # when trimming, can make the trimmed nodes shallower if parts are removed. removed parents can be added to .parents # if trimming makes a branch shallower at its leaves, it may become mergeable with its other neighbor # 2. remove items in between and replace with data # 3. merge data