In this assignment, we will create two variants of the classes from Assignment 2; SortedArrayBufferNoDups and SortedArrayBufferWithDups. As the name implies, the first class is a sorted array and does not allow the insertion of duplicate values, while the second one does. The SortedArrayBufferNoDups class should look like the ArrayBufferNoDups class in Assignment 2. Only the insert operation has to change. Insert has to insert in order. Here there is only one remove function which is stableRemove that has to be slightly altered so that you dont have to go until the end of the array to find the integer. You can stop when you have reached a value greater than the value being passed in. For example if your array contains integers [1,3,5,7,9] and you are asked to remove integer 4, you can stop once you reach 5 as you know 4 cannot be found now.

The SortedArrayBufferWithDups class should also look like the class in ArrayBufferWithDups class in previous section. This time, change the insert function that allows duplicates but needed to be inserted in order, and implement one remove function which is stableRemove as for the NoDups case. Now implement the findAll and stableRemoveAll. The findAll function should return an int with the number of elements that have the same value as the target value, while the stableRemoveAll function should remove all copies of the target value. Have the stableRemoveAll function return an int with the number of values that were actually removed. Here stableRemoveAll becomes easier as you know the number of occurrences and now if you find the locationOf the first one you can stop looking and remove starting from that index to the number of occurrences. So for example if you have an integer array [1,3,5,5,5,7,9] and you are asked to remove 5, location of first 5 is 2 and number of occurrences for 5 is 3. So you need to remove from index 2 to 4(3 occurrences). For this assignment, like assignment 2 have the constructor take an integer argument for the size.

from gettext import find class BufferArray: def __init__(self): self._numberofelements = 0 self._buffer_size = 20 # None is used to define a null data type or no value at all. self._intArray = [None] * self._buffer_size def insert(self, value): if self._numberofelements == self._buffer_size - 1: return False self._intArray[self._numberofelements] = value self._numberofelements += 1 return True # def display(self): print(",".join(map(str, self._intArray[:self._numberofelements]))) # def locationOf(self, value): if value in self._intArray: print(self._intArray.index(value)) else: print(-1) # def find(self, value): if value in self._intArray: return True else: print(False) # def fastRemove(self, value): if value in self._intArray: index = self._intArray.index(value) self._intArray[index], self._intArray[self._numberofelements - 1] = self._intArray[ self._numberofelements - 1], \ self._intArray[index] self._numberofelements -= 1 return True else: return False # def stableRemove(self, value): if value in self._intArray: index = self._intArray.index(value) self._intArray = self._intArray[:index] + self._intArray[index + 1:] self._numberofelements -= 1 return True else: return False # children classes class ArrayBufferNoDups(BufferArray): def __init__(self): super().__init__() self.value = None self._numberofelements = 0 self._buffer_size = 20 # None is used to define a null data type or no value at all. self._intArray = [None] * self._buffer_size def insert(self, value): if self._numberofelements == self._buffer_size - 1: return False elif find(self.value): return False else: self._intArray[self._numberofelements] = value self._numberofelements += 1 return True class ArrayBufferWithDups(BufferArray): def __init__(self): super().__init__() self._numberofelements = 0 self._buffer_size = 20 # None is used to define a null data type or no value at all. self._intArray = [None] * self._buffer_size def findAll(self, value): if value in self._intArray: return self._intArray.count(value) else: return -1 # remove all elements of same value def fastRemoveAll(self, value): value_amount = self.findAll(value) if value_amount != -1: for val in range(value_amount): self.fastRemove(value) else: return False # remove all elements of same value def stableRemoveAll(self, value): value_amount = self.findAll(value) if value_amount != -1: for val in range(value_amount): self.stableRemove(value) else: return False class SortedArrayNoDups(ArrayBufferNoDups): def __init__(self): super().__init__() self._numberofelements = 0 self._buffer_size = 20 # None is used to define a null data type or no value at all. self._intArray = [None] * self._buffer_size def insert(self, value): # sorted_arraynodups = sorted(self._intArray) if self._numberofelements == self._buffer_size - 1: return False elif find(self.value): return False else: self._intArray[self._numberofelements] = value self._numberofelements += 1 return True # b_array = BufferArray() # b_array.insert(7) # b_array.insert(8) # b_array.insert(9) # b_array.insert(10) # b_array.insert(11) # b_array.insert(12) # b_array.insert(13) # b_array.insert(14) # b_array.insert(15) # b_array.display() # b_array.stableRemove(8) # b_array.display() # b_array.find(8) # b_array.locationOf(22) # b_array.locationOf(15) # # a_nodups = ArrayBufferNoDups() # a_nodups.insert(11) # a_nodups.insert(12) # a_nodups.insert(13) # a_nodups.insert(14) # a_nodups.insert(15) # a_nodups.insert(16) # a_nodups.insert(17) # a_nodups.insert(18) # a_nodups.insert(19) # a_nodups.insert(20) # a_nodups.insert(21) # a_nodups.insert(22) # a_nodups.insert(23) # a_nodups.insert(24) # a_nodups.insert(25) # a_nodups.insert(26) # a_nodups.insert(27) # a_nodups.insert(28) # a_nodups.insert(29) # a_nodups.insert(30) # a_nodups.insert(14) # a_nodups.display() # a_nodups.stableRemove(14) # a_nodups.display() # a_nodups.find(15) # a_nodups.locationOf(28) # a_withdups = ArrayBufferWithDups() # array_size = int(input("Enter the size of the array: ")) # for val in range(array_size): # temp = int(input("enter value of {} element: ".format(val))) # a_withdups.insert(temp) # # key = int(input("enter value to be removed: ")) # a_withdups.display() # a_withdups.findAll(11) # a_withdups.fastRemoveAll(2) # a_withdups.display() # a_withdups.stableRemoveAll(11) # a_withdups.display() sa_nodups = SortedArrayNoDups() sa_nodups.insert(1) sa_nodups.insert(5) sa_nodups.insert(9) sa_nodups.insert(2) sa_nodups.insert(4) sa_nodups.insert(4) sa_nodups.display()