import array

class ArrayImpl3:
    def __init__(self, size):
        self.array = [None] * size
        self.i_end = -1

    def add_by_index(self, i_add, val):

        if self.i_end + 1 == len(self.array):
            self.expand_space()

        if i_add > self.i_end + 1 | i_add < 0:
            return

        # step01 : move all value one slot after
        for i in range(self.i_end, i_add - 1, -1):
            self.array[i + 1] = self.array[i]
            self.array[i] = None

        self.array[i_add] = val
        self.i_end += 1


    def add_by_value(self, val):
        self.add_by_index(self.i_end + 1, val)

    def expand_space(self):
        array_new = [None] * (len(self.array) * 2)

        for i in range(len(self.array)):
            array_new[i] = self.array[i]

        self.array = array_new

    def search_by_index(self, index):
        if index > self.i_end | index < 0:
            return None
        return self.array[index]

    def search_by_value(self, val):
        for i in range(self.i_end):
            if self.array[i] == val:
                return self.array[i]

        return None

    def remove_by_index(self, index):
        if index > self.i_end | index < 0:
            return
        self.array[index] = None

        for i in range(self.i_end, i_add - 1, -1):
            self.array[i + 1] = self.array[i]
            self.array[i] = None

        self.i_end -= 1

    def remove_by_value(self, val):
        # search
        for i in range(self.i_end):
            if self.array[i] == val:
                self.remove_by_index(i)

if __name__ == "__main__":
    # initialize
    myarray = ArrayImpl3(5)

    # add O(1)
    myarray.add_by_value(9)
    myarray.add_by_value(11)
    myarray.add_by_value(2)
    myarray.add_by_value(98)
    myarray.add_by_value(35)

    # add by value O(1) + expand O(n)
    myarray.add_by_value(44)

    # add by index O(n)
    i_add = 1
    myarray.add_by_index(i_add, 50)

    # search by value O(n)
    val001 = myarray.search_by_value(98)

    # search by index O(1)
    val002 = myarray.search_by_index(4)

    # remove by value O(n)
    myarray.remove_by_value(2)

    # remove by index O(n)
    i_remove = 3
    myarray.remove_by_index(i_remove)