[ot][spam][crazy][crazy][spam]

[Karl Semich]

i realized random writes may be as simple as applying the same
algorithm to the left and right edges of each unwritten region. this
means implementing region bounds. i got as far as below before
overwhelming dyskinesia.

https://github.com/xloem/flat_tree

append_indices.py

# indexes a balanced tree of past indices
# every write, publish a .copy() paired with data, then pass the
locator to .append() to index it

class append_indices(list):

    def __init__(self, degree = 2, initial_indices = []):
        super().__init__(*initial_indices)
        self.degree = degree
        self.leaf_count, self.size = 0, 0
        for leaf_count, size, value in self:
            self.leaf_count += leaf_count
            self.size += size

    def append(self, added_size, last_publish):
        self.leaf_count += 1
        self.size += added_size

        new_leaf_count = self.leaf_count
        new_size = self.size

        for idx, (branch_leaf_count, branch_size, branch_id) in enumerate(self):
            if branch_leaf_count * self.degree <= new_leaf_count:
                break
            new_leaf_count -= branch_leaf_count
            new_size -= branch_size
        else:
            idx = len(self)

        self[idx:] = [(new_leaf_count, new_size, last_publish)]

mix_indices.py

class append_indices(list):
    def __init__(self, degree = 2, initial_indices = []):
        super().__init__(*initial_indices)
        self.degree = degree
        self.degree = degree
        self.leaf_count, self.size = 0, 0
        for leaf_count, size, value in self:
            self.leaf_count += leaf_count
            self.size += size
        self.splice_queue = []

    def _insert(self, last_publish, *ordered_splices):
        # a reasonable next step is to provide for truncation appends,
where a tail of the data is replaced with new data

        # currently only performs 1 append
        assert len(ordered_splices) == 1

        for spliced_out_start, spliced_out_stop, spliced_in_size in
ordered_splices:
            #assert spliced_out_start == self.size # truncation
appends are drafted but untested
            assert spliced_out_stop == self.size

            self.leaf_count += 1
            self.size += spliced_in_size

            new_leaf_count = self.leaf_count
            new_offset = 0

            for idx, (branch_leaf_count, branch_offset, branch_size,
branch_id) in enumerate(self):
                if branch_leaf_count * self.degree <= new_leaf_count:
                    break
                new_leaf_count -= branch_leaf_count
                new_offset += branch_size
            else:
                idx = len(self)

            self[idx:] = ((new_leaf_count, new_offset,
spliced_out_start + spliced_in_size - new_offset, last_publish),)

    def append(self, last_publish, added_size):
        self._insert(last_publish, (self.size, self.size, added_size))

    def snap(self, data):
        return (self.copy(), data)

test.py

from mix_indices import append_indices

index = append_indices(degree=3)
stored_indices = {}

import random
data = [random.randbytes(random.randint(1,8)) for x in range(24)]

for chunk in data:
    id = index.leaf_count
    stored_indices[id] = (index.copy(), chunk)
    index.append(id, len(chunk))

def iterate(index, start_offset, end_offset):
    subendoffset = 0
    for subleafcount, suboffset, subsize, subid in index:
        subindex, subdata = stored_indices[subid]
        subendoffset += subsize
        if subendoffset > start_offset:
            data = b''.join(iterate(subindex, start_offset, end_offset))
            yield data
            if subendoffset > end_offset:
                return
            yield subdata
            start_offset = subendoffset

data = b''.join(data)
print(data)
cmp = b''.join(iterate(index, 0, index.size))
print(cmp)

assert data == cmp

print(index)