pretend_dynamic_list.py

from math import floor, ceil, log
from typing import Tuple, List


class AppendOnlyList:
   """
   Seemed too boring to make something that copies all and reallocates each time it needs expanding.
   This is more like an array of pointers to arrays.
   """
    size = 0
    _arrays: List[Tuple[int,list]] = []

    def __init__(self):
        self._append_cursor = 0
        self._internal_size = 0
        self._start_size = 1
        self._extend()

    def append(self, item):
        if self.size == self._internal_size:
            self._extend()

        self._latest_array()[self._append_cursor] = item
        self._append_cursor += 1
        self.size += 1

    def __getitem__(self, index):
        if index < 0:
            index = self.size + index

        if index + 1 > self.size:
            raise IndexError("index out of range")

        ## Loop until reaching the right array

        # for included_size, arr in self._arrays:
        #     if index < included_size:
        #         local_index = -1 * (included_size - index)
        #         return arr[local_index]

        # Or mostly unnecessary and hard to understand O(1) approach which might even take longer in practice but was fun.
        arrays_index = ceil(log(index, 2))
        array = self._arrays[arrays_index][1]
        traversed_range = 2 ** arrays_index
        local_index = -1 * (traversed_range - index)

        return array[local_index]

    def __iter__(self):
        self._iter_arrays_iterator = iter(self._arrays)
        self._iter_array = None
        self._iter_local_i = 0
        self._iter_i = 0
        return self

    def __next__(self):
        if self._iter_i == self.size:
            raise StopIteration

        if not self._iter_array or self._iter_local_i >= len(self._iter_array):
            self._iter_local_i = 0
            self._iter_next_array()

        i = self._iter_local_i
        self._iter_local_i += 1
        self._iter_i += 1
        return self._iter_array[i]

    def __len__(self):
        return self.size

    def _iter_next_array(self):
        # This will raise StopIteration for me if the size is the same as internal size
        self._iter_upper_bound, self._iter_array = self._iter_arrays_iterator.__next__()

    def _latest_array(self):
        return self._arrays[-1][1]

    def _extend(self):
        array_size = self._internal_size or self._start_size
        array = list(None for _ in range(array_size)) # Pretend that's an array and this is an efficient way to allocate a memory block
        self._internal_size += array_size
        self._arrays.append((self._internal_size, array))
        self._append_cursor = 0


#  ============ Play with it =============

alist = AppendOnlyList()

for pos in range(ord("A"), ord("z")+1):
    alist.append(chr(pos))


print(alist[25]) # 26th letter => Z
print(alist[-1]) # last item => z
print(list(alist)) # Iterates through

print(alist[58]) # => will raise IndexError