"""

Please help me with this revised Python program.

SortedSetInheritance. A sorted set behaves just like a set, but allows the user to visit its items in ascending order with a for loop.

Define class ArraySortedSet, which inherits from class ArraySortedBag.

Class ArraySortedSet should have only two methods: __init__ and add.

Please use the starter code

Expected output:

The list of items added is: [2013, 61, 1973]

Expect 3: 3

Expect the set's string: {61, 1973, 2013}

Expect True: True

Expect False: False

Expect the items on separate lines:

61

1973

2013

Expect {}: {}

Expect {}: {}

Expect True: True

Expect False: False

Expect one of each item: {61, 1973, 2013}

Expect {}: {}

"""

## Starter code below:

###File: abstractbag.py

from arrays import Array from abstractbag import AbstractBag class ArrayBag(AbstractBag): """An array-based bag implementation.""" # Class variable DEFAULT_CAPACITY = 10 # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self.items = Array(ArrayBag.DEFAULT_CAPACITY) AbstractBag.__init__(self, sourceCollection) # Accessor methods def __iter__(self): """Supports iteration over a view of self.""" cursor = 0 while cursor < len(self): yield self.items[cursor] cursor += 1 # Mutator methods def clear(self): """Makes self become empty.""" self.size = 0 self.items = Array(ArrayBag.DEFAULT_CAPACITY) def add(self, item): """Adds item to self.""" # Check array memory here and increase it if necessary if len(self) == len(self.items): temp = Array(2 * len(self)) for i in range(len(self)): temp[i] = self.items[i] self.items = temp self.items[len(self)] = item self.size += 1 def remove(self, item): """Precondition: item is in self. Raises: KeyError if item in not in self. Postcondition: item is removed from self.""" # Check precondition and raise if necessary if not item in self: raise KeyError(str(item) + " not in bag") # Search for the index of the target item targetIndex = 0 for targetItem in self: if targetItem == item: break targetIndex += 1 # Shift items to the left of target up by one position for i in range(targetIndex, len(self) - 1): self.items[i] = self.items[i + 1] # Decrement logical size self.size -= 1 # Check array memory here and decrease it if necessary if len(self) < len(self.items) // 3 and \ 2 * len(self) >= ArrayBag.DEFAULT_CAPACITY: temp = Array(len(self.items) // 2) for i in range(len(self)): temp[i] = self.items[i] self.items = temp 

### File: abstractcollection.py

class AbstractCollection(object): """An abstract collection implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self.size = 0 if sourceCollection: for item in sourceCollection: self.add(item) # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self.size def __str__(self): """Returns the string representation of self.""" return "[" + ", ".join(map(str, self)) + "]" def __add__(self, other): """Returns a new bag containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result def __eq__(self, other): """Returns True if self equals other, or False otherwise.""" if self is other: return True if type(self) != type(other) or \ len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True def count(self, item): """Returns the number of instances of item in self.""" total = 0 for nextItem in self: if nextItem == item: total += 1 return total 

### File: arraybag.py

from arrays import Array from abstractbag import AbstractBag class ArrayBag(AbstractBag): """An array-based bag implementation.""" # Class variable DEFAULT_CAPACITY = 10 # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self.items = Array(ArrayBag.DEFAULT_CAPACITY) AbstractBag.__init__(self, sourceCollection) # Accessor methods def __iter__(self): """Supports iteration over a view of self.""" cursor = 0 while cursor < len(self): yield self.items[cursor] cursor += 1 # Mutator methods def clear(self): """Makes self become empty.""" self.size = 0 self.items = Array(ArrayBag.DEFAULT_CAPACITY) def add(self, item): """Adds item to self.""" # Check array memory here and increase it if necessary if len(self) == len(self.items): temp = Array(2 * len(self)) for i in range(len(self)): temp[i] = self.items[i] self.items = temp self.items[len(self)] = item self.size += 1 def remove(self, item): """Precondition: item is in self. Raises: KeyError if item in not in self. Postcondition: item is removed from self.""" # Check precondition and raise if necessary if not item in self: raise KeyError(str(item) + " not in bag") # Search for the index of the target item targetIndex = 0 for targetItem in self: if targetItem == item: break targetIndex += 1 # Shift items to the left of target up by one position for i in range(targetIndex, len(self) - 1): self.items[i] = self.items[i + 1] # Decrement logical size self.size -= 1 # Check array memory here and decrease it if necessary if len(self) < len(self.items) // 3 and \ 2 * len(self) >= ArrayBag.DEFAULT_CAPACITY: temp = Array(len(self.items) // 2) for i in range(len(self)): temp[i] = self.items[i] self.items = temp 

### File: arrays.py

""" File: arrays.py An Array is a restricted list whose clients can use only [], len, iter, and str. To instantiate, use  = array(, ) The fill value is None by default. """ class Array(object): """Represents an array.""" def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self.items = list() for count in range(capacity): self.items.append(fillValue) def __len__(self): """-> The capacity of the array.""" return len(self.items) def __str__(self): """-> The string representation of the array.""" return str(self.items) def __iter__(self): """Supports iteration over a view of an array.""" return iter(self.items) def __getitem__(self, index): """Subscript operator for access at index.""" return self.items[index] def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self.items[index] = newItem 

### File: arrayset.py

from arraybag import ArrayBag class ArraySet(ArrayBag): """An array-based set implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" ArrayBag.__init__(self, sourceCollection) # Mutator methods def add(self, item): """Adds item to self.""" if not item in self: ArrayBag.add(self, item) 

### File: arraysortedbag.py

# Adds __eq__ to ArraySortedBag, with O(n) running time. from arrays import Array from arraybag import ArrayBag class ArraySortedBag(ArrayBag): """An array-based sorted bag implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" ArrayBag.__init__(self, sourceCollection) # Accessor methods def __contains__(self, item): left = 0 right = len(self) - 1 while left <= right: midPoint = (left + right) // 2 if self.items[midPoint] == item: return True elif self.items[midPoint] > item: right = midPoint - 1 else: left = midPoint + 1 return False def __eq__(self, other): """Returns True if self equals other, or False otherwise.""" if self is other: return True if type(self) != type(other) or \ len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True # Mutator methods def add(self, item): """Adds item to self.""" # Check array memory here and increase it if necessary if len(self) == len(self.items): temp = Array(2 * len(self)) for i in range(len(self)): temp[i] = self.items[i] self.items = temp # Empty or last item, call ArrayBag.add if self.isEmpty() or item >= self.items[len(self) - 1]: ArrayBag.add(self, item) else: # Search for first item >= new item targetIndex = 0 while item > self.items[targetIndex]: targetIndex += 1 # Open a hole for new item for i in range(len(self), targetIndex, -1): self.items[i] = self.items[i - 1] # Insert item and update size self.items[targetIndex] = item self.size += 1 

### File: arraysortedset.py

from arraysortedbag import ArraySortedBag # define ArraySortedSet here 

### File: baginterface.py

class BagInterface(object): """Interface for all bag types.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" pass # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return True def __len__(self): """-Returns the number of items in self.""" return 0 def __str__(self): """Returns the string representation of self.""" return "" def __iter__(self): """Supports iteration over a view of self.""" return None def __add__(self, other): """Returns a new bag containing the contents of self and other.""" return None def __eq__(self, other): """Returns True if self equals other, or False otherwise.""" return False def count(self, item): """Returns the number of instances of item in self.""" return 0 # Mutator methods def clear(self): """Makes self become empty.""" pass def add(self, item): """Adds item to self.""" pass def remove(self, item): """Precondition: item is in self. Raises: KeyError if item in not in self. Postcondition: item is removed from self.""" pass 

### File: collectioninterface.py

class CollectionInterface(object): """Interface for all collection types.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" pass # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return True def __len__(self): """-Returns the number of items in self.""" return 0 def __str__(self): """Returns the string representation of self.""" return "" def __iter__(self): """Supports iteration over a view of self.""" return None def __add__(self, other): """Returns a new instance of the type of self containing the contents of self and other.""" return None def __eq__(self, other): """Returns True if self equals other, or False otherwise.""" return False # Mutator methods def clear(self): """Makes self become empty.""" pass def add(self, item): """Adds item to self.""" pass 

### File: testset.py

# A tester program for sorted sets. from arrayset import ArraySet from arraysortedset import ArraySortedSet def test(setType): """Expects a set type - as an argument and runs some tests on objects of that type.""" lyst = [2013, 61, 1973] print("The list of items added is:", lyst) s1 = setType(lyst) print("Expect 3:", len(s1)) print("Expect the set's string:", s1) print("Expect True:", 2013 in s1) print("Expect False:", 2012 in s1) print("Expect the items on separate lines:") for item in s1: print(item) s1.clear() print("Expect {}:", s1) s1.add(25) s1.remove(25) print("Expect {}:", s1) s1 = setType(lyst) s2 = setType(s1) print("Expect True:", s1 == s2) print("Expect False:", s1 is s2) print("Expect one of each item:", s1 + s2) for item in lyst: s1.remove(item) print("Expect {}:", s1) test(ArraySortedSet)