Question

Question 2 Consider the implementation we made in class for ArrayList, and its extensions you did in the lab. In this question, we will add two more methods to this class: the insert method and the pop method. For this question, please submit the modified ArrayList class. a) Implement the method insert (self, index, val) that inserts val before index (shifting the elements to make room for val). For example, your implementation should follow the behavior below: >>> arr_lst = ArrayList() >>> for i in range (1, 4+1): arr_lst.append(i) >>> arr lst.insert (2, 30) >>> arrlst [1, 2, 30, 3, 4] Notes: 1. Make sure to double the capacity of the array, if there is no room for an additional element. 2. Your function should raise an IndexError exception in any case the index (positive or negative) is out of range. b) Implement the method pop (self), that removes the last element from the list. The pop method should return the element removed from the list, and put None in its place in the array. If pop was called on an empty list, an IndexError exception should be raised. In order to maintain the linear memory usage of the list data structure, and its efficient amortized performance, we use the following shrinking strategy: When the number of elements in the list goes strictly below a quarter of the array's capacity, we shrink its capacity by half. For example, your implementation should follow the behavior below: >>> arr_lst = ArrayList() >>> for i in range (1, 5+1): arr_lst.append(i) >>> arr_lst.pop() 5 >>> arr_lst.pop() 4 >>> arr_lst.pop() 3 >>> arr_lst.pop() 2 >>> arr_lst [1] Note: After the executing the code above, the capacity of the array in ArrayList will be 4.
please be thorough with explanations. thank you

Answer 1

Working code implemented in Python and appropriate comments provided for better understanding.

Source Code for main.py:

import ctypes # provides low-level arrays
def make_array(n):
return (n * ctypes.py_object)()

class ArrayList:
def __init__(self):
self.data = make_array(1)
self.capacity = 1
self.n = 0

def __len__(self):
return self.n

def append(self, val):
if (self.n == self.capacity):
self.resize(2 * self.capacity)
self.data[self.n] = val
self.n += 1

def resize(self, new_size):
new_array = make_array(new_size)
for i in range(self.n):
new_array[i] = self.data[i]
self.data = new_array
self.capacity = new_size

def extend(self, iter_collection):
for elem in iter_collection:
self.append(elem)

def insert(self, index, val):
if (not (-self.n <= index <= self.n - 1)):
raise IndexError('invalid index')
if (self.n == self.capacity):
self.resize(2 * self.capacity)
self.append(1)
for i in range(-1, -(index+1),-1):
self[i] = self[i-1]
self[index] = val

def pop(self, index = -1):
if self.n == 0:
raise IndexError("empty list")
if abs(index) > self.n:
raise IndexError("out of bound")
if index < 0 and index != -1:
index += self.n
if index == -1:
temp = self.data[self.n-1]
self.data[self.n-1] = None
else:
temp = self.data[index]
self.data[index] = None
for i in range(index + 1, self.n):
self.data[i-1] = self.data[i]
self.n -= 1
if ((self.n) < (self.capacity//4)):
self.resize(self.capacity//2)
return temp

def __getitem__(self, ind):
if (not (-self.n <= ind <= self.n - 1)):
raise IndexError('invalid index')
if (ind < 0):
ind = self.n + ind
return self.data[ind]

def __setitem__(self, ind, val):
if (not (-self.n <= ind <= self.n - 1)):
raise IndexError('invalid index')
if (ind < 0):
ind = self.n + ind
self.data[ind] = val

def __repr__(self):
data_as_strings = [str(self.data[i]) for i in range(self.n)]
return '[' + ', '.join(data_as_strings) + ']'

def __add__(self, other):
res = ArrayList()
res.extend(self)
res.extend(other)
return res

def __iadd__(self, other):
self.extend(other)
return self

def __mul__(self, times):
res = ArrayList()
for i in range(times):
res.extend(self)
return res

def __rmul__(self, times):
return self * times

def main():
arr_lst = ArrayList()
for i in range(1, 5+1):
arr_lst.append(i)
print(arr_lst)
print(arr_lst.pop())   
print(arr_lst)
main()

Code Screenshots:

Sample Output Screenshots: