Jo has a tendency to not maintain the priorities very well, adding new customers as high priorities
Question:
Jo has a tendency to not maintain the priorities very well, adding new customers as high priorities to get them out of the way faster; this often leads to lots of priorities with an excessively large range. These priorities need to be 'compacted', so if Jo has a queue that looks like this:
```Python
[
{'priority':4, 'task':'belt', 'customer':'AJ', 'complete_time':45},
{'priority':9, 'task':'belt', 'customer':'Stu', 'complete_time':45},
{'priority':12, 'task':'wallet', 'customer':'Alex', 'complete_time':60},
{'priority':12, 'task':'belt', 'customer':'Alex', 'complete_time':45},
]
```
then a `compact` method would refactor the queue to look like this:
```Python
[
{'priority':0, 'task':'belt', 'customer':'AJ', 'complete_time':45},
{'priority':1, 'task':'belt', 'customer':'Stu', 'complete_time':45},
{'priority':2, 'task':'wallet', 'customer':'Alex', 'complete_time':60},
{'priority':2, 'task':'belt', 'customer':'Alex', 'complete_time':45},
]
```
***Outline in English an algorithm to carry out the requirements of `compact`. An outline in English should *not* be program code or pseudo-code 1 for further guidance on outlining algorithms in English. Not using an English outline will lead to negative reviews****
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
The class code has been repeated below. Edit the code below to implement your compact algorithm from the previous question as a method. For this question you may use any standard Python methods that belong to the dict or list objects if you wish, although it is not required to deviate from those included in the book.
#PYTHON
# *Write your code solution here*
# Note that this implementation differs from the queues in the book!
class LWPriorityQueue:
"""A dynamic array implementation of a max-priority queue.
Items with the same priority are retrieved in FIFO order.
Items are stored as dictionaries.
"""
def __init__(self):
"""Create a new empty queue."""
self.items = [] # in ascending order
def length(self) -> int:
"""Return the number of items in the queue."""
return len(self.items)
def find_max(self) -> int:
"""Return index of the oldest item with the highest priority."""
if self.length() == 0:
return -1
max_priority = 0
oldest_item = 0
for index in range(self.length()):
if self.items[index]['priority'] >= max_priority:
max_priority = self.items[index]['priority']
oldest_item = index
return oldest_item
def remove_max(self) -> None:
"""Remove the oldest item with the highest priority."""
if self.length() > 0:
item_to_remove = self.find_max()
self.items.pop(item_to_remove)
def get_max(self) -> dict:
"""Returns the dictionary of the oldest item with the highest priority,
or an empty dictionary."""
index = self.find_max()
if index == -1:
return {}
else:
return self.items[index]
def bump(self, customer: str) -> None:
"""Increases by one the priority of all items
attributed to the specified customer."""
for index in range(self.length()):
if self.items[index]['customer'] == customer:
self.items[index]['priority'] += 1
def insert(self, priority: int, task: str, customer: str, complete_time: int) -> None:
"""Add item with the given priority to the queue."""
item = {
'priority': priority,
'task': task,
'customer': customer,
'complete_time': complete_time
}
self.items.insert(0, item)
def print_queue(self) -> None:
""" Prints the current state of the priority queue """
print('[')
for item in self.items:
print(' ', item)
print(']')
### ADD YOUR CODE HERE ###
Expert Answer:
