Data Structure in Python

Array-Backed Lists

Implementation Details

For the ArrayList's underlying data storage mechanism you will use the built-in Python list, constrained so that only the following operations (as would be supported by a primitive array) are available:

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

ConstrainedList

To help keep us honest, we've defined an API-constrained sub-class of the built-in list -- ConstrainedList -- an instance of which is assigned to the dataattribute of each ArrayList. You should not change the definition of ConstrainedList, and ensure that your ArrayList implementation never assigns a regular Python list to its data attribute. So long as you use ConstrainedList in your implementation, you can be certain you're not performing any "illegal" operations (i.e., outside the constraints established above). If you invoke a disallowed operation, an appropriate exception will be raised.

Be sure to evaluate the following cell before testing your ArrayList implementation.

In [ ]:

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__()) 

ArrayList

And now for the task at hand. We've partitioned the ArrayList methods you need to implement (and the test cases that follow) into seven categories:

Subscript-based access (completed in class)

Stringification

Single-element manipulation

Predicates (True/False queries)

Queries

Bulk operations

Iteration

All told, there are 23 methods --- a handful of which have already been implemented for you --- whose behavior are specified in their docstrings below. Note that we left out API support for slices (e.g., lst[start:stop:step]); you can read about how to support slices in the Python docs, but we just don't think it's worth the extra busywork.

Hints / Advice

We strongly advise that you start with the first category of functions and move down the list sequentially, pausing after each to run the corresponding test cases. The only category that might be worth skipping to early on is Iteration --- which can help simplify several other methods. Keep in mind that while you're not permitted to make use of high level APIs in the underlying list, you can certainly make use of ArrayList methods you've already implemented.

For instance, your implementations of pop and remove can (and should) use the del operator on your own list to remove elements from the middle, and it probably makes sense to use extend in your __add__ and copy methods.

In [ ]:

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()