# block tree structure

# blocks written to are leaves
# depth is log2 leaves

# when a flush is made, all blocks are written, and also enough nodes such that every leaf can be accessed within depth lookups.


# consider we have an existing tree
# with say m flushes, containing n leaves (or m leaves). we'll likely call it n.


# each flush shows which leaves it has

# additionally, with the final flush, each leaf has an existing depth.

# when we reflush, we need to provide a new index for any leaves that become too deep.

# which leaves are too deep?

# we could basically walk them all to find out. this would be a consistent first approach.

class Simple:
    class RangedData:
        def __init__(self, offset, data):
            self.start = offset
            self.data = data
            self.end = self.start + len(self.data)
    class Flush:
        # flush has a list of new leaves, and a list of indexes to old leaves with ranges
        def __init__(self, *writes, prev_flush=None):
            self.prev_flush = prev_flush
            self.data = writes

            # find extents
            start = min((write.start for write in self.data))
            end = max((write.end for write in self.data))
            
            if prev_flush is None:
                self.start = start
                self.end = end
                self.index = []
                return

            self.start = min(start, prev_flush.start)
            self.end = max(end, prev_flush.end)
            self.index = [(prev_flush.start, prev_flush.end, prev_flush)]

            # find leaf count and leaf depths
            offset = start
            while offset < end:
            
        #def lookup(self, offset
        def leaves(self, start = None, end = None):
            offset = self.start
            data_iter = iter(self.data)
            index_iter = iter(self.index)
            next_write = next(data_iter, None)
            next_index = next(index_iter, None)
            while offset < self.end:
                if next_write is not None:
                    assert offset <= next_write.start
                    if offset == next_write.start:
                        yield (0, next_write)
                        continue
                
            
    def __init__(self, latest = None):
        self.latest = latest
        self.pending = []
    def write(self, offset, data):
        self.pending.append((offset, data))
    def flush(self):
        self.latest = self.Flush(*self.pending, prev_flush=self.latest)
        self.pending = []