Task 1 [9 marks]

Implement a complete version of an Array-Based List. Use 50 as the maximum number of elements. To create arrays use the method build_array from referential_array.py as discussed in the Lectures. Your List should include implementations for the following 10 functions:

__str__(self): Returns a string representation of the list. Structure the string so that there is one item per line. Called by str(self)

__len__(self): Returns the length of the list. Called by len(self)

__contains__(self, item): Returns True if item is in the list, False otherwise. Called by item in self

__getitem__(self, index): Returns the item at index in the list, if index is non-negative. If it is negative, it will return the last item if index is 1, the second-to last if index is 2, and so on up to minus the length of the list, which returns the first item. The function raises an IndexError if index is out of the range from -len(self) to len(self). Called by self[index]

__setitem__(self, index, item): Sets the value at index in the list to be item. The index can be negative, behaving as described above. Raises an IndexError if index is out of the range from -len(self) to len(self). Called by self[index] = item

__eq__(self, other): Returns True if this list is equivalent to other. Called by self == other

append(self, item): Adds item to the end of the list. Remember the underlying array is and should remain of fixed size. The operation should raise an Exception if the list is full.

insert(self, index, item): Inserts item into self before position index. The index can be negative, behaving as described above. Raises an IndexError if index is out of the range from -len(self) to len(self).

remove(self, item): Deletes the first instance of item from the list. Raises a ValueError if item does not exist in self

delete(self, index): Deletes the item at index from the list, moving all items after it towards the start of the list. The index can be negative, behaving as described above. Raises an IndexError if index is out of the range from -len(self) to len(self).

sort(self, reverse): Sorts the items in the list in ascending order if reverse is False or descending order if is reverse is True. Pick your favourite sorting algorithm from those covered in the Lectures.

Make your class iterable.

Task 2 [2 marks]

Modify your list implementation so that the size of the underlying array is dynamic. The base size of the array is 20 and should never be less than 20. However, if the list becomes full, it is resized to be 2 times larger than the current size. Likewise, the underlying size should decrease by half if the underlying array is larger than the base size but the content occupies less than 1/8 of the available space. When resizing the list, retain the contents of the list. That is, when it is initially filled, it will be resized to 20 items, then 40, while retaining the contents initially in it. The same happens when the size of the array shrinks.

Task 3 [2 marks]

Re-do task 1, now with a Linked Structure instead of an array.

Task 5 [6 marks]

Write a text editor as a Python program that allows a user to perform the 6 commands shown below using a menu. It is advisable that the Editor itself is a class with an attribute containing an list of lines. The list should be the type you have implemented on Task 2.

insert num: which inserts a line of text (given by the user) in the list before position num, and raises an exception if no num is given

read filename: which opens the file, filename, reads all the lines in from the file, put each line as a separate item into a list, and then closes the file.

write filename: which creates or opens a file, filename, writes every item in the list into the file, and then closes the file.

print num1 num2: which prints the lines between positions num1 and num2, if num1

delete num: which deletes the line of text in the list at position num, and deletes all the lines if no num is given.

search word: which takes a word and prints the line numbers in which the target word appears. Search should be case insensitive. Search should work as expected in a standard text editor, for example ignoring punctuation. 3 This function must be accessible through the menu via commands search and count.

quit: which quits the program.

Tasks 1, 2, 3 and 5 used as a reference. Need help with Task 6. Thank you :)

Task 6 14 marks] Re-implement your editor using a Linked List instead of an Array-based list. If done properly, switching your text-editor to a Linked List implementation should take no more than changing a single line. To ensure this, make sure that the List ADT is implemented with the same functions and function signatures in both implementations (Tasks 1, 2,3). Write a page of text, using what you know of theory to analyse how the performance of your text editor would change when switching implementations