Implement a map in PYTHON using a sorted list of entries. You should keep the en
ID: 3708331 • Letter: I
Question
Implement a map in PYTHON using a sorted list of entries. You should keep the entry list sorted by key at all times, and make use of the binary search routine included in the scaffold to speed up key lookups.
The binary search function is : def binary_search(self, key):
min = 0
max = len(self._entries)
while min < max:
mid = int((max + min)/2)
mid_key = self._entries[mid].get_key()
if mid_key == key:
return mid
elif mid_key < key:
min = mid + 1
else:
max = mid
# not found
return -1
the functions we need to implement using this are:
containsKey(k)
: Returns true if there exists an entry with key k in the map, false otherwise.
get(k)
: If the map contains an entry with key k and value v, returns v. Otherwise
returns null.
put(k, v)
: Inserts an item with with key k and value v; if there is already an item with
key k, then replaces its value with v.
remove(k)
: If the map contains an entry with key k and value v, removes said entry and
returns v. Otherwise returns null.
You can't use the built-in Python functions
Explanation / Answer
class item:
def __init__(self, key, val):
self.key = key
self.val = val
def get_key(self):
return self.key
def get_value(self,key):
return self.val
def set_value(self,val):
self.val = val
class Map:
def __init__(self, l):
self._entries = l
def binary_search(self,key):
min = 0
max = len(self._entries)
while min < max:
mid = int(max + min)/2
mid_key = self._entries[mid].get_key()
if mid_key == key:
return mid
elif mid_key < key:
min = mid + 1
else:
max = mid
return -1
def containsKey(self,k):
index = binary_search(self,key)
if index == -1:
return False
else
return True
def put(self,key, val):
i1 = item(key,val)
index = binary_search(self,key)
if index == -1:
for i in range(len(self._entries)):
if self._entries[i].get_key() >key):
index = i
break
if index != -1:
self._entries.append(i1)
else:
self._entries.insert(index,i1)
else:
self._entries[index].set_value(val)
def get(self,k):
index = binary_search(self,key)
if index == -1:
return None
else:
return self._entries[index].get_value()
def remove(self,k):
index = binary_search(self,key)
if index == -1:
return None
else:
return del self._entries[index]
class map contains the binary search function as given in the question.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.