Instead of using two lists to store the key/value entries in the map, we can use a single list. The individual keys and corresponding values can both be saved in a storage object that is then added to the list. A sample instance illustrating the data organization required for this approach is shown in Figure 2.9.1.
Figure 2.9.1: The Map ADT implemented using a single list.
Storage Class
As we indicated earlier in Chapter 1, we want to avoid the use of tuples when storing structured data since it is better practice to use classes with named fields. The MapEntry storage class will be used to store the individual key/value pairs:
class MapEntry :
def __init__(self, key, value) :
self.key = key
self.value = value
Note this storage class is intended to be private since it is only intended for use by the Map class that provides the single list implementation of the Map ADT.
Constructor and Length Operations
The implementation of the constructor only involves the creation and storage of an empty list to hold the map entries:
class Map :
def __init__(self) :
self._entryList = list()
As with the Set class implemented earlier in the chapter, the length operation can simply return the length of the list containing the storage objects:
def __len__(self) :
return len(self._entryList)
Adding Entries
Many of the methods require a search to determine if the map contains a given key. In this implementation, the standard in operator cannot be used since the list contains MapEntry objects and not simply key entries. Instead, we have to search the list ourselves and examine the key field of each MapEntry object. Likewise, we routinely have to locate within the list the position containing a specific key/value entry. Since these operations will be needed in several methods, we can create a helper method that combines the two searches and use it where needed.
def _findPosition(self, key) :
for i in range(len(self)) :
if self._entryList[i].key == key :
return i
return -1
The _findPosition helper method searches the list for the given key. If the key is found, the index of its location is returned; otherwise, the function returns -1 to indicate the key is not contained in the map.
When used by the other methods, the value returned by the helper method can be evaluated to determine both the existence of the key and the location of the corresponding entry if the key is in the map. Given the helper method, we can now implement the add operation:
def add(self, key, value) :
ndx = self._findPosition(key)
if ndx >= 0 :
self._entryList[ndx].value = value
return False
else :
entry = MapEntry(key, value)
self._entryList.append(entry)
return True
By combining the two searches into a single operation, we eliminate the need to first determine if the map contains the key and then having to search again for its location.
Source Listing
The implementation of the Map ADT using a single list to store the entries is provided in the listing below. The implementation of the remove, clear, and valueOf methods are left as an exercise. The implementation of the map iterator is also left as an exercise. As with the search operation, we can not simply iterate over the elements of the list contained in the _entryList instance variable since the elements contain storage objects comprised of both a key and value.
Program Listing
# Implementation of Map ADT using a single list. class Map : # Creates an empty map instance. def __init__(self) : self._entryList = list() # Returns the number of entries in the map. def __len__(self) : return len(self._entryList) # Determines if the map contains the given key. def __contains__(self, key) : ndx = self._findPosition(key) return ndx is not None # Adds a new entry to the map if the key does exist. Otherwise, the # new value replaces the current value associated with the key. def add(self, key, value) : ndx = self._findPosition(key) if ndx >= 0 : # if the key was found self._entryList[ndx].value = value return False else : # otherwise add a new entry entry = MapEntry(key, value) self._entryList.append(entry) return True # --- The remaining methods go here. --- # Returns an iterator for traversing the keys in the map. def __iter__(self) : return MapIterator(self._entryList) # Helper method used to find the index position of a key. If the # key is not found, None is returned. def _findPosition(self, key) : # Iterate through each entry in the list. for i in range(len(self)) : # Is the key stored in the ith entry? if self._entryList[i].key == key : return i # When not found, return None. return -1 # Private storage class for holding the key/value pairs. class MapEntry : def __init__(self, key, value) : self.key = key self.value = value
|
