Re: [spam][crazy][fiction][random] Non-Canon MCBoss Spinoffs

https://github.com/karl3/rep

i _almost_ implemented dict. it works barebones but uses an
exponential growth ratio of 256.
i've almost reduced the exponential growth ratio to the smallest
needed power of 2, there's an arithmetic bug right now

i'll paste it

        if place != self._sentinel:
            collision = self._key(place)
            if collision != keyhash:
                assert idx ==
int.from_bytes(collision[:self._hashbytes], 'big') >> self._hashshift
#& self._hashmask
                spread = 0
                while True:
                    spread += 1
                    hashbits = self._hashbits + spread
                    expansion = 1 << spread
                    #hashmask = capacity - 1
                    hashbytes = (hashbits+7) >> 3
                    hashshift = (hashbytes << 3) - hashbits
                    idx = int.from_bytes(keyhash[:hashbytes], 'big')
>> hashshift #& hashmask
                    if idx != int.from_bytes(collision[:hashbytes],
'big') >> hashshift: #& hashmask:
                        break
                capacity = self._capacity * expansion
                assert 1 << hashbits == capacity
                expansionmask = spread - 1
                def content_generator():
                    for superidx, item in
enumerate(tqdm.tqdm(self.array, desc='growing hashtable',
leave=False)):
                        if item == self._sentinel:
                            yield from [self._sentinel] * expansion
                        else:
                            keyhash = self._key(item)
        if place != self._sentinel:
            collision = self._key(place)
            if collision != keyhash:
                assert idx ==
int.from_bytes(collision[:self._hashbytes], 'big') >> self._hashshift
#& self._hashmask
                spread = 0
                while True:
                    spread += 1
                    hashbits = self._hashbits + spread
                    expansion = 1 << spread
                    #hashmask = capacity - 1
                    hashbytes = (hashbits+7) >> 3
                    hashshift = (hashbytes << 3) - hashbits
                    idx = int.from_bytes(keyhash[:hashbytes], 'big')
>> hashshift #& hashmask
                    if idx != int.from_bytes(collision[:hashbytes],
'big') >> hashshift: #& hashmask:
                        break
                capacity = self._capacity * expansion
                assert 1 << hashbits == capacity
                expansionmask = spread - 1
                def content_generator():
                    for superidx, item in
enumerate(tqdm.tqdm(self.array, desc='growing hashtable',
leave=False)):
                        if item == self._sentinel:
                            yield from [self._sentinel] * expansion
                        else:
                            keyhash = self._key(item)
                            wholeidx =
int.from_bytes(keyhash[:hashbytes], 'big') #>> hashshift #& hashmask
                            assert superidx == wholeidx >> (hashbytes
* 8 - self._hashbits)
                            subidx = (wholeidx >> hashshift) & expansionmask
                            assert superidx * expansion + subidx ==
wholeidx >> hashshift
                            yield from [self._sentinel] * subidx
                            yield item
                            yield from [self._sentinel] * (expansion -
subidx - 1)
                self.array[:] =
IterableWithLength(content_generator(), self._capacity * expansion)
                        yield from [self._sentinel] * subidx
                            yield item
                            yield from [self._sentinel] * (expansion -
subidx - 1)
                self.array[:] =
IterableWithLength(content_generator(), self._capacity * expansion)

The arithmetic mistake is in this section:
                            wholeidx =
int.from_bytes(keyhash[:hashbytes], 'big') # misleading comment
removed
                            assert superidx == wholeidx >> (hashbytes
* 8 - self._hashbits)
                            subidx = (wholeidx >> hashshift) & expansionmask
                            assert superidx * expansion + subidx ==
wholeidx >> hashshift
The second assertion is raising. One of my bitwise arithmetics is wrong.

After reducing the exponential growth ratio I was going to implement
.update() for fast bulk updates of many items.

It's so useful to have basic data structures!