class ConstrainedList (list): """Constrains the list class so it offers only the following primitive array API: - `lst[i]` for getting and setting a value at an *existing, positive* index `i` - `len(lst)` to obtain the number of slots - `lst.append(None)` to grow the list by *one slot at a time* - `del lst[len(lst)-1]` to delete the last slot in a list All other operations will result in an exception being raised. """ def __init__(self, *args): super().__init__(*args) def append(self, value): if value is not None: raise ValueError('Can only append None to constrained list!') super().append(value) def __getitem__(self, idx): if idx < 0 or idx >= len(self): raise ValueError('Can only use positive, valid indexes on constrained lists!') return super().__getitem__(idx)

def __setitem__(self, idx, value): if idx < 0 or idx >= len(self): raise ValueError('Can only use positive, valid indexes on constrained lists!') super().__setitem__(idx, value)

def __delitem__(self, idx): if idx != len(self)-1: raise ValueError('Can only delete last item in constrained list!') super().__delitem__(idx) def __getattribute__(self, name): if name in ('insert', 'pop', 'remove', 'min', 'max', 'index', 'count', 'clear', 'copy', 'extend'): raise AttributeError('Method "' + name + '" not supported on constrained list!') else: return super().__getattribute__(name) # __getattribute__ isn't called for special methods, so the following are needed

def __add__(self, value): raise AttributeError('Constrained lists do not support `+`!')

def __contains__(self, value): raise AttributeError('Constrained lists do not support `in`!') def __eq__(self, value): raise AttributeError('Constrained lists do not support `==`!') def __iter__(self): raise AttributeError('Constrained lists do not support iteration!') def __str__(self): raise AttributeError('Constrained lists do not support stringification!') def __repr__(self): raise AttributeError('Constrained lists do not support stringification!') # for testing only! (don't use this in your ArrayList implementation) def _as_list(self): return list(super().__iter__())

class ArrayList: def __init__(self): self.data = ConstrainedList() # don't change this line!

### subscript-based access ### def _normalize_idx(self, idx): nidx = idx if nidx < 0: nidx += len(self.data) if nidx < 0: nidx = 0 return nidx def __getitem__(self, idx): """Implements `x = self[idx]`""" assert(isinstance(idx, int)) nidx = self._normalize_idx(idx) if nidx >= len(self.data): raise IndexError return self.data[nidx]

def __setitem__(self, idx, value): """Implements `self[idx] = x`""" assert(isinstance(idx, int)) nidx = self._normalize_idx(idx) if nidx >= len(self.data): raise IndexError self.data[nidx] = value

def __delitem__(self, idx): """Implements `del self[idx]`""" assert(isinstance(idx, int)) nidx = self._normalize_idx(idx) if nidx >= len(self.data): raise IndexError for i in range(nidx+1, len(self.data)): self.data[i-1] = self.data[i] del self.data[len(self.data)-1]

### stringification ### def __str__(self): """Implements `str(self)`. Returns '[]' if the list is empty, else returns `str(x)` for all values `x` in this list, separated by commas and enclosed by square brackets. E.g., for a list containing values 1, 2 and 3, returns '[1, 2, 3]'.""" # YOUR CODE HERE raise NotImplementedError() def __repr__(self): """Supports REPL inspection. (Same behavior as `str`.)""" # YOUR CODE HERE raise NotImplementedError()

### single-element manipulation ### def append(self, value): """Appends value to the end of this list.""" # YOUR CODE HERE raise NotImplementedError() def insert(self, idx, value): """Inserts value at position idx, shifting the original elements down the list, as needed. Note that inserting a value at len(self) --- equivalent to appending the value --- is permitted. Raises IndexError if idx is invalid.""" # YOUR CODE HERE raise NotImplementedError() def pop(self, idx=-1): """Deletes and returns the element at idx (which is the last element, by default).""" # YOUR CODE HERE raise NotImplementedError() def remove(self, value): """Removes the first (closest to the front) instance of value from the list. Raises a ValueError if value is not found in the list.""" # YOUR CODE HERE raise NotImplementedError()

### predicates (T/F queries) ### def __eq__(self, other): """Returns True if this ArrayList contains the same elements (in order) as other. If other is not an ArrayList, returns False.""" # YOUR CODE HERE raise NotImplementedError()

def __contains__(self, value): """Implements `val in self`. Returns true if value is found in this list.""" # YOUR CODE HERE raise NotImplementedError()

### queries ### def __len__(self): """Implements `len(self)`""" # YOUR CODE HERE raise NotImplementedError() def min(self): """Returns the minimum value in this list.""" # YOUR CODE HERE raise NotImplementedError() def max(self): """Returns the maximum value in this list.""" # YOUR CODE HERE raise NotImplementedError() def index(self, value, i=0, j=None): """Returns the index of the first instance of value encountered in this list between index i (inclusive) and j (exclusive). If j is not specified, search through the end of the list for value. If value is not in the list, raise a ValueError.""" # YOUR CODE HERE raise NotImplementedError() def count(self, value): """Returns the number of times value appears in this list.""" # YOUR CODE HERE raise NotImplementedError()

### bulk operations ###

def __add__(self, other): """Implements `self + other_array_list`. Returns a new ArrayList instance that contains the values in this list followed by those of other.""" # YOUR CODE HERE raise NotImplementedError() def clear(self): self.data = ConstrainedList() # don't change this! def copy(self): """Returns a new ArrayList instance (with a separate data store), that contains the same values as this list.""" # YOUR CODE HERE raise NotImplementedError()

def extend(self, other): """Adds all elements, in order, from other --- an Iterable --- to this list.""" # YOUR CODE HERE raise NotImplementedError()

### iteration ### def __iter__(self): """Supports iteration (via `iter(self)`)""" # YOUR CODE HERE raise NotImplementedError()