A sorted bag behaves just like a regular bag but allows the user to visit its items in ascending order with the for loop. Therefore, the items added to this type of bag must have a natural ordering and recognize the comparison operators. Some examples of such items are strings and integers.
Define a new class named ArraySortedBag that supports this capability. Like ArrayBag, this new class is array based, but its in operation can now run in logarithmic time. To accomplish this, ArraySortedBag must place new items into its array in sorted order. The most efficient way to do this is to modify the add method to insert new items in their proper places. You also have to include a __contains__ method to implement the new, more efficient search.
Finally, you must change all references to ArrayBag to be ArraySortedBag.
The test file testbag.py has been included to test your implementation of ArraySortedBag
A version of the ArrayBag class has been copied into the file arraysortedbag.py as an optional starting point.
Here is the testbay.py below:
"""
File: testbag.py
A tester program for bag implementations.
"""
from arraybag import ArrayBag
from linkedbag import LinkedBag
from arraysortedbag import ArraySortedBag
from random import shuffle
def test(bagType):
"""Expects a bag type as an argument and runs some tests
on objects of that type."""
print("Testing", bagType)
lyst = list(range(1, 11))
shuffle(lyst)
print("The list of items added is:", lyst)
b = bagType(lyst)
print("Expect the bag's string, in ascending order:", b)
print("Add 5 more items to test increasing the array size:")
for i in range(11, 16):
b.add(i)
print("Expect the bag's string:", b)
test(ArraySortedBag)
#test(LinkedBag)
Out put:
sandbox $ python3 testbag.py
Testing
The list of items added is: [6, 13, 7, 9, 12, 14, 8, 11, 4, 5, 1, 10, 15, 2, 3]
Expect the bag's string, in ascending order: {6, 13, 7, 9, 12, 14, 8, 11, 4, 5, 1, 10, 15, 2, 3}
Add 5 more items to test increasing the array size:
Expect the bag's string: {6, 13, 7, 9, 12, 14, 8, 11, 4, 5, 1, 10, 15, 2, 3, 16, 17, 18, 19, 20}
Not sure what is wrong here.