Task: Need to implement four functions: Skeleton code: Week 5: Implementing a Ma

Question

Task:
Need to implement four functions:
Skeleton code:
Week 5: Implementing a Map Using a Sorted implement a map 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. in both programming languages, there is an empty main function in the Sorted List Map file The main function is not being tested and it is there as an option for you to use for your own testing/running 1, 14 Java The documented map interface is in Map. java and the class you need to implement is in SortedListHap. java 18 File: / Cor Python The documented map interface is in core.py and the class you need to implement is in sorted_list map.py 2 ELEC3SOS ExP32.pat 6-index.p class lype here to searc

Explanation / Answer

Entry Class

class Entry:

   def __init__(self, key, value):
       self._key = key
       self._value = value

   def get_key(self):
       return self._key

   def get_value(self):
       return self._value

   def set_key(self, key):
       self._key = key

   def set_value(self, value):
       self._value = value

   # Overloading the less than operator for sorting
   def __lt__(self, other):
       return self._key < other._key

Implemented functions

# Checks if an entry with key k exists in the map
def containsKey(self, k):
   # Search for key k in map using binary search
   # If not found, return False, else return True
   if self.binary_search(k) == -1 :
       return False
   return True

# Get the value corresponding to a key in the map
def get(self, k):
   # Get index of the entry using binary search
   ind = self.binary_search(k)

   # If key found, return the corresponding value, else return None object
   if ind != -1:
       return self._entries[ind].get_value()
   return None

# Inserts an entry with key k and value v
def put(self, k, v):
   # Search if the key already exists in the map
   ind = self.binary_search(k)

   # If found, just update the value
   if ind != -1:
       self._entries[ind].set_value(v)

   # If not found, create a new entry, append it to the map and sort it.
   else:
       newEntry = Entry(k, v)
       self._entries.append(newEntry)
       self._entries.sort()

# Remove an entry from the map
def remove(self, k):
   # Get index of the entry using binary search
   ind = self.binary_search(k)

   # If found, remov the entry and return the value
   if ind != -1:
       entry = self._entries[ind]
       self._entries.remove(entry)
       return entry.get_value()

   # If not found, return a None object
   return None

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.