The Sorted Map ADT
Store key-value pairs such that the keys can be compared (ordered). Supports the following operations.
The data: An ordered list should contain a list of items that can be ordered. It is assumed that the items cannot be duplicated.
Construction: initialize an empty sorted map. (Implement with __init__ ). Insertion: Inserts (key, value) pair into the sorted map. (Implement with
__setitem__ ).
Deletion: delete(key) deletes item with the given key from the sorted map. It is
assumed to be unique. If there is no such item, nothing needs to be done.
Membership testing: Check if an key is in the map. (Implement with __contains__ ).
Predecessor Search: Given a key k , return the value in the Sorted Map that has the largest key that is less than or equal to k . This provides inexact search if the exact key k does not appear. If there is no key in the map less than or equal to k , then it should
return None .
Iteration: Iterate through the keys in the list in order. (Implement with __iter__ ).
Index Access: Access the a value in the map given the key. (Implement with __getitem__ ). There should be an error ( KeyError ) if there is no item with the given
key.
Length: Return the length of the list. (implement with __len__ ).
An Abstract Class
This ADT is specified more completely in the SortedMap class provided in the skeleton. We would call this an abstract class because you can’t do anything with an instance. In fact, you would get an error just creating one. Every method just raises an error. This class
is meant to be extended by a subclass.
For example, a dictionary-based implementation is provided. It extends the SortedMap class and implements all of the methods by wrapping a dictionary object. This implementation is fast for many operations, but it is very slow (or at least slower than it could be), for predecessor search.
Implement the SortedMap ADT using a list.
Call your class ListSortedMap and put it in a file called listsortedmap.py . It must inherit from SortedMap . You should use binary search to make membership testing and predecessor search fast. You could also use binary search to find the correct index for insertion.
Implement the SortedMap ADT using a linked list.
Call your class LinkedListSortedMap and put it in a file called linkedlistsortedmap.py . It must inherit from SortedMap . This will save a little time for
insertion if the insertions are near the front of the list, however, you will not be able to do binary search. Overall, this will not be as efficient as the previous approaches, but if you want an extra challenge, look up skip lists to speed up insertion, membership testing, and predecessor search.
Write Tests!
Submit tests that exercise your code. Your code should get no warnings when running pep8.