Please help, the code is python.
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__())
THIS IS THE ONLY PART OF THE CODE TO EDIT
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]'."""
def __repr__(self):
"""Supports REPL inspection. (Same behavior as `str`.)"""
### single-element manipulation ###
def append(self, value):
"""Appends value to the end of this list."""
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."""
def pop(self, idx=-1):
"""Deletes and returns the element at idx (which is the last element,
by default)."""
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."""
### 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."""
def __contains__(self, value):
"""Implements `val in self`. Returns true if value is found in this list."""
### queries ##
def __len__(self):
"""Implements `len(self)`"""
def min(self):
"""Returns the minimum value in this list."""
def max(self):
"""Returns the maximum value in this list."""
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."""
def count(self, value):
"""Returns the number of times value appears in this list."""
### 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."""
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."""
def extend(self, other):
"""Adds all elements, in order, from other --- an Iterable --- to this list."""
### iteration ###
def __iter__(self):
"""Supports iteration (via `iter(self)`)"""
EVERYTHING BELOW ARE TEST CASES THAT HAVE TO BE PASSED
Lab 04: Array-Backed Lists Overview For this assignment you will complete me implementation or the array-backed list data structure ArrayList started during class, so that is supports (teary) all the common and table sequence operations Implementation Details For the terayLists undertying data storage mechanism you will use the burn Python ist, constrained so that only the following operations (as would be supported by a primitive array) are available Ist[!] for getting and setting a value at an existing positive index len(1st) to obtain the number of slots Ist.append(none) to grow the list by one si a time del 1st[len(Ist)-1) to delete the last skin a list ConstrainedList To help keep us honest, we've defined an AP.constrained sub-class of the built-in list - Constrainedlist - an instance of which is assigned to the data route of each ArrayList. You should not change the definition of constrainedlist, and ensure that your ArrayList implementation never assigns a regular Python is to its data abute So long as you use constrainedlist in your implementation, you can be certain you're not performing any llegar operations 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 ArrayList And now for the task at hand. Weve partitioned the ArrayList methods you need to implement and the test cases that follow) into seven categories 1. Subscript-based access (completed in class) 2. Stringfication 3 Single-clement manipulation 4 Predictes (True False queries) 6. Buk operations 7. Therion Also, there are 23 memos -- a handful of which have already been implemented for you --- whose behavior are specified in their docstrings below Note that we let out API support for siete. Ist[start stop: step] x you can read about how. sices in the Pronos, but we just don't think its worth the extra busywork Hints/Advice We strongly advise that you start with the first category of functions and move down the sequentially, pausing after each to run the corresponding test cases. The only category that might be worth skipping to early on isleration --- 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 ist, 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 menos Read on In ): (6 points) test subscript-based access fron unittest import Testcase import randon tc - Testcase) Ist - ArrayListo) data - [1, 2, 3, 4) Ist data - Constraineduist(data) for 1 in range(len(data)) tc.assertEqual (Ist[i], data[1]) with c.assertRaises (IndexError): x - Ist[100) with tc. assertRaises (IndexError): Ist[100] - with tc. assertRaises (IndexError) del ist[100] Ist[1] - data 1) - 20 del catalo! del ist[ for! in range(len(data)) tc.assertEqual(Ist[i], data[1]) data - [randon.randint(1, 100) for in range(109) Ist.cata - ConstrainedList (data) for i in range(len(data) for 1 in rangelen (data)) tc. assertEqualists). data[1]) data - [randon.randint(1, 100) for - in range(100)] Ist data - ConstrainedList (data) for 1 in rangeln(data)) 1st[1] - data[i] - random.randint(101, 200) for 1 in range(50): to_del randon.randrange (len(data) del Ist[to_del) del data to del) for 1 in rangelen (data)): tc. assertEqualist[i], data[1]) for : in range(e. -Jen(data), -1): tc. assertEqual(Ist[:], data[1]) In): (4 points) test stringfication from unittest Import TestCase tc - Testcase() 1st - ArrayList() to assertis Instance(Ist.data, Constraineduist) tc.assertEqual('0'. str(st)) tc.assertEqual('0', repr(1st)) ist. data - Constrainedlist([1]) te assertEqual(3), str(st)) tc. assertEqual('11), reprist)) 1st.data - ConstrainedList([10, 20, 30, 40, 50)) tc.assertEqual('[10, 20, 30, 40, 50]', str(1st)) tc.assertEqual('[10, 20, 30, 40, 50]', repr(1st)) In ( ): (8 points) test single-element manipulation Read Only fron unittest import TestCase import random tc - Testcase) 1st - ArrayList() data- for in range(100): to_add - random.randrange (1000) data.append(to_add) 1st.append(to_add) tc. assertisInstance(Ist.data, constrained List) tc.assertEqual(data, Ist.data._as_list() for in range(100): to_ins - randon.randrange(1eee) ins_idx - randon.randrange(len(data)+1) data.insert(ins_idx, to_ins) 1st. Insert(ins_idx, to_ins) tc.assertEqual(data, Ist.data._as_list) for in range(100): pop_idx - randon.randrange(len(data)) In ): (10 points) test queries from unittest import Testcase tc - Test Case() ist. ArrayList() tc.assertEqual(, len(1st)) tc.assertEquale, ist.count(1) with tc. assertRaises (ValueError); IstIndex (1) import randon data - [randon.randrange(1000) for _ in range(109)] Ist.cata - Constrainedlist(data) tc.assertEqual (100, len(1st)) tc.assertEqual(ain (data), Ist.min()) to assertEquals(data), Istan) for x in data: tc.assertEqual (data. Index(x), ist. Index(x)) tc.assertEqual (data.count(x), Ist.count(x)) with tc.assertRaises (valueError): ist. Index (1000) Ist data - Constrainedist([1, 2, 1, 2, 1, 1, 1, 2, 1)) tc. assertEqual(1. Ist Index (2) tc. assertEqual (1, Ist. Index(2, 1)) tc. assertEqual (3, Ist.index(2, 2)) tc.assette ndex(2, 4)) tc.assertEqual(7. IstIndex(2.4, -1)) with te assertRaises (ValueError) 1st. Index (2, 4,-2) In 1: (6 points) test both operations from unittest import Testcase te - Testcase) In ): (6 points) test bulk operations from unittest import Testcase tc Testcase) 1st - ArrayList 1st2 - ArrayListo) 1st. Istilsta tc.assertisinstance(Ist), ArrayList) tc.assertEqual([], ist3.data._as_list) Import random data - [randon.randrange (1000) for - in range(58)] data2 - Crandon.randrange(1000) for in range(50)] Ista.data. Constrainedlist(data) 1st). Ist Ista tc. assertEqual (100, len(st) tc. assertEqualidata.data2, ist3.data._as_list()) Ist.clear() te assertEqual(). Ist.data._as_list()) Ist data - Constrainedist([randon.randrange(1008) for _in range(5)]) Ist2 - Ist.copy tc. assertist, 1st2) tc. assertist(st.data, Ist2.data) tc.assertEqual (Ist datas_list(), 1st2.data._as_list) Ist.clear() Ist extend(range(10) 1st.extend(range(10,0.-1)) Ist extend(data.copy) tc.assertEqual(70, lenist)) te assertEqual (list (range(10))Iist (range(10,0,-1)).data, Ist.data._as_list) In (): (2 points) test (teration from unittest import Test Case t - Testcase) Ist - Arratis) import random data. [random.randrange(1000) for in range(100)) Ist data - Constrainedlist(data) tc.assertEqual(data, [x for x in lst)) it- Iterist) 112 - Ster(s) for x in data: tc.assertEqual (next(it), x) tc.assertEqual next (t2), x) Lab 04: Array-Backed Lists Overview For this assignment you will complete me implementation or the array-backed list data structure ArrayList started during class, so that is supports (teary) all the common and table sequence operations Implementation Details For the terayLists undertying data storage mechanism you will use the burn Python ist, constrained so that only the following operations (as would be supported by a primitive array) are available Ist[!] for getting and setting a value at an existing positive index len(1st) to obtain the number of slots Ist.append(none) to grow the list by one si a time del 1st[len(Ist)-1) to delete the last skin a list ConstrainedList To help keep us honest, we've defined an AP.constrained sub-class of the built-in list - Constrainedlist - an instance of which is assigned to the data route of each ArrayList. You should not change the definition of constrainedlist, and ensure that your ArrayList implementation never assigns a regular Python is to its data abute So long as you use constrainedlist in your implementation, you can be certain you're not performing any llegar operations 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 ArrayList And now for the task at hand. Weve partitioned the ArrayList methods you need to implement and the test cases that follow) into seven categories 1. Subscript-based access (completed in class) 2. Stringfication 3 Single-clement manipulation 4 Predictes (True False queries) 6. Buk operations 7. Therion Also, there are 23 memos -- a handful of which have already been implemented for you --- whose behavior are specified in their docstrings below Note that we let out API support for siete. Ist[start stop: step] x you can read about how. sices in the Pronos, but we just don't think its worth the extra busywork Hints/Advice We strongly advise that you start with the first category of functions and move down the sequentially, pausing after each to run the corresponding test cases. The only category that might be worth skipping to early on isleration --- 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 ist, 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 menos Read on In ): (6 points) test subscript-based access fron unittest import Testcase import randon tc - Testcase) Ist - ArrayListo) data - [1, 2, 3, 4) Ist data - Constraineduist(data) for 1 in range(len(data)) tc.assertEqual (Ist[i], data[1]) with c.assertRaises (IndexError): x - Ist[100) with tc. assertRaises (IndexError): Ist[100] - with tc. assertRaises (IndexError) del ist[100] Ist[1] - data 1) - 20 del catalo! del ist[ for! in range(len(data)) tc.assertEqual(Ist[i], data[1]) data - [randon.randint(1, 100) for in range(109) Ist.cata - ConstrainedList (data) for i in range(len(data) for 1 in rangelen (data)) tc. assertEqualists). data[1]) data - [randon.randint(1, 100) for - in range(100)] Ist data - ConstrainedList (data) for 1 in rangeln(data)) 1st[1] - data[i] - random.randint(101, 200) for 1 in range(50): to_del randon.randrange (len(data) del Ist[to_del) del data to del) for 1 in rangelen (data)): tc. assertEqualist[i], data[1]) for : in range(e. -Jen(data), -1): tc. assertEqual(Ist[:], data[1]) In): (4 points) test stringfication from unittest Import TestCase tc - Testcase() 1st - ArrayList() to assertis Instance(Ist.data, Constraineduist) tc.assertEqual('0'. str(st)) tc.assertEqual('0', repr(1st)) ist. data - Constrainedlist([1]) te assertEqual(3), str(st)) tc. assertEqual('11), reprist)) 1st.data - ConstrainedList([10, 20, 30, 40, 50)) tc.assertEqual('[10, 20, 30, 40, 50]', str(1st)) tc.assertEqual('[10, 20, 30, 40, 50]', repr(1st)) In ( ): (8 points) test single-element manipulation Read Only fron unittest import TestCase import random tc - Testcase) 1st - ArrayList() data- for in range(100): to_add - random.randrange (1000) data.append(to_add) 1st.append(to_add) tc. assertisInstance(Ist.data, constrained List) tc.assertEqual(data, Ist.data._as_list() for in range(100): to_ins - randon.randrange(1eee) ins_idx - randon.randrange(len(data)+1) data.insert(ins_idx, to_ins) 1st. Insert(ins_idx, to_ins) tc.assertEqual(data, Ist.data._as_list) for in range(100): pop_idx - randon.randrange(len(data)) In ): (10 points) test queries from unittest import Testcase tc - Test Case() ist. ArrayList() tc.assertEqual(, len(1st)) tc.assertEquale, ist.count(1) with tc. assertRaises (ValueError); IstIndex (1) import randon data - [randon.randrange(1000) for _ in range(109)] Ist.cata - Constrainedlist(data) tc.assertEqual (100, len(1st)) tc.assertEqual(ain (data), Ist.min()) to assertEquals(data), Istan) for x in data: tc.assertEqual (data. Index(x), ist. Index(x)) tc.assertEqual (data.count(x), Ist.count(x)) with tc.assertRaises (valueError): ist. Index (1000) Ist data - Constrainedist([1, 2, 1, 2, 1, 1, 1, 2, 1)) tc. assertEqual(1. Ist Index (2) tc. assertEqual (1, Ist. Index(2, 1)) tc. assertEqual (3, Ist.index(2, 2)) tc.assette ndex(2, 4)) tc.assertEqual(7. IstIndex(2.4, -1)) with te assertRaises (ValueError) 1st. Index (2, 4,-2) In 1: (6 points) test both operations from unittest import Testcase te - Testcase) In ): (6 points) test bulk operations from unittest import Testcase tc Testcase) 1st - ArrayList 1st2 - ArrayListo) 1st. Istilsta tc.assertisinstance(Ist), ArrayList) tc.assertEqual([], ist3.data._as_list) Import random data - [randon.randrange (1000) for - in range(58)] data2 - Crandon.randrange(1000) for in range(50)] Ista.data. Constrainedlist(data) 1st). Ist Ista tc. assertEqual (100, len(st) tc. assertEqualidata.data2, ist3.data._as_list()) Ist.clear() te assertEqual(). Ist.data._as_list()) Ist data - Constrainedist([randon.randrange(1008) for _in range(5)]) Ist2 - Ist.copy tc. assertist, 1st2) tc. assertist(st.data, Ist2.data) tc.assertEqual (Ist datas_list(), 1st2.data._as_list) Ist.clear() Ist extend(range(10) 1st.extend(range(10,0.-1)) Ist extend(data.copy) tc.assertEqual(70, lenist)) te assertEqual (list (range(10))Iist (range(10,0,-1)).data, Ist.data._as_list) In (): (2 points) test (teration from unittest import Test Case t - Testcase) Ist - Arratis) import random data. [random.randrange(1000) for in range(100)) Ist data - Constrainedlist(data) tc.assertEqual(data, [x for x in lst)) it- Iterist) 112 - Ster(s) for x in data: tc.assertEqual (next(it), x) tc.assertEqual next (t2), x)
