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 ilen(lst) to obtain the number of slotslst.append(None) to grow the list by one slot at a timedel lst[len(lst)-1] to delete the last slot in a listConstrainedList¶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 data attribute 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.
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:
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.
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.
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()
# test subscript-based access
from unittest import TestCase
import random
tc = TestCase()
lst = ArrayList()
data = [1, 2, 3, 4]
lst.data = ConstrainedList(data)
for i in range(len(data)):
tc.assertEqual(lst[i], data[i])
with tc.assertRaises(IndexError):
x = lst[100]
with tc.assertRaises(IndexError):
lst[100] = 0
with tc.assertRaises(IndexError):
del lst[100]
lst[1] = data[1] = 20
del data[0]
del lst[0]
for i in range(len(data)):
tc.assertEqual(lst[i], data[i])
data = [random.randint(1, 100) for _ in range(100)]
lst.data = ConstrainedList(data)
for i in range(len(data)):
lst[i] = data[i] = random.randint(101, 200)
for i in range(50):
to_del = random.randrange(len(data))
del lst[to_del]
del data[to_del]
for i in range(len(data)):
tc.assertEqual(lst[i], data[i])
for i in range(0, -len(data), -1):
tc.assertEqual(lst[i], data[i])
# test stringification
from unittest import TestCase
tc = TestCase()
lst = ArrayList()
tc.assertIsInstance(lst.data, ConstrainedList)
tc.assertEqual('[]', str(lst))
tc.assertEqual('[]', repr(lst))
lst.data = ConstrainedList([1])
tc.assertEqual('[1]', str(lst))
tc.assertEqual('[1]', repr(lst))
lst.data = ConstrainedList([10, 20, 30, 40, 50])
tc.assertEqual('[10, 20, 30, 40, 50]', str(lst))
tc.assertEqual('[10, 20, 30, 40, 50]', repr(lst))
# test single-element manipulation
from unittest import TestCase
import random
tc = TestCase()
lst = ArrayList()
data = []
for _ in range(100):
to_add = random.randrange(1000)
data.append(to_add)
lst.append(to_add)
tc.assertIsInstance(lst.data, ConstrainedList)
tc.assertEqual(data, lst.data._as_list())
for _ in range(100):
to_ins = random.randrange(1000)
ins_idx = random.randrange(len(data)+1)
data.insert(ins_idx, to_ins)
lst.insert(ins_idx, to_ins)
tc.assertEqual(data, lst.data._as_list())
for _ in range(100):
pop_idx = random.randrange(len(data))
tc.assertEqual(data.pop(pop_idx), lst.pop(pop_idx))
tc.assertEqual(data, lst.data._as_list())
for _ in range(25):
to_rem = data[random.randrange(len(data))]
data.remove(to_rem)
lst.remove(to_rem)
tc.assertEqual(data, lst.data._as_list())
with tc.assertRaises(ValueError):
lst.remove(9999)
# test predicates
from unittest import TestCase
tc = TestCase()
lst = ArrayList()
lst2 = ArrayList()
lst.data = ConstrainedList([])
lst2.data = ConstrainedList([1, 2, 3])
tc.assertNotEqual(lst, lst2)
lst.data = ConstrainedList([1, 2, 3])
tc.assertEqual(lst, lst2)
lst.data = ConstrainedList([])
tc.assertFalse(1 in lst)
tc.assertFalse(None in lst)
lst.data = ConstrainedList(range(100))
tc.assertFalse(100 in lst)
tc.assertTrue(50 in lst)
# test queries
from unittest import TestCase
tc = TestCase()
lst = ArrayList()
tc.assertEqual(0, len(lst))
tc.assertEqual(0, lst.count(1))
with tc.assertRaises(ValueError):
lst.index(1)
import random
data = [random.randrange(1000) for _ in range(100)]
lst.data = ConstrainedList(data)
tc.assertEqual(100, len(lst))
tc.assertEqual(min(data), min(lst))
tc.assertEqual(max(data), max(lst))
for x in data:
tc.assertEqual(data.index(x), lst.index(x))
tc.assertEqual(data.count(x), lst.count(x))
with tc.assertRaises(ValueError):
lst.index(1000)
lst.data = ConstrainedList([1, 2, 1, 2, 1, 1, 1, 2, 1])
tc.assertEqual(1, lst.index(2))
tc.assertEqual(1, lst.index(2, 1))
tc.assertEqual(3, lst.index(2, 2))
tc.assertEqual(7, lst.index(2, 4))
tc.assertEqual(7, lst.index(2, 4, -1))
with tc.assertRaises(ValueError):
lst.index(2, 4, -2)
# test bulk operations
from unittest import TestCase
tc = TestCase()
lst = ArrayList()
lst2 = ArrayList()
lst3 = lst+lst2
tc.assertIsInstance(lst3, ArrayList)
tc.assertEqual([], lst3.data._as_list())
import random
data = [random.randrange(1000) for _ in range(50)]
data2 = [random.randrange(1000) for _ in range(50)]
lst.data = ConstrainedList(data)
lst2.data = ConstrainedList(data2)
lst3 = lst + lst2
tc.assertEqual(100, len(lst3))
tc.assertEqual(data + data2, lst3.data._as_list())
lst.clear()
tc.assertEqual([], lst.data._as_list())
lst.data = ConstrainedList([random.randrange(1000) for _ in range(50)])
lst2 = lst.copy()
tc.assertIsNot(lst, lst2)
tc.assertIsNot(lst.data, lst2.data)
tc.assertEqual(lst.data._as_list(), lst2.data._as_list())
lst.clear()
lst.extend(range(10))
lst.extend(range(10,0,-1))
lst.extend(data.copy())
tc.assertEqual(70, len(lst))
tc.assertEqual(list(range(10))+list(range(10,0,-1))+data, lst.data._as_list())
# test iteration
from unittest import TestCase
tc = TestCase()
lst = ArrayList()
import random
data = [random.randrange(1000) for _ in range(100)]
lst.data = ConstrainedList(data)
tc.assertEqual(data, [x for x in lst])
it1 = iter(lst)
it2 = iter(lst)
for x in data:
tc.assertEqual(next(it1), x)
tc.assertEqual(next(it2), x)