Q1c

The class code has been repeated below. Edit the code below to implement your compact algorithm from part (c)(i) 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.

In [60]:

# *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(']')

 ### MY CODE bellow HERE ### ### MY CODE bellow HERE ### ### MY CODE bellow HERE ###

 ### MY CODE bellow HERE ### ### MY CODE bellow HERE ### ### MY CODE bellow HERE ### ### MY CODE bellow HERE ###

def compact(self) -> None:

 """Compacts the priority queue by reducing the priority of all tasks by the minimum priority."""

 min_priority = self.items[0]['priority']

 for item in self.items:

 if item['priority'] < min_priority:

 min_priority = item['priority']

 for item in self.items:

 item['priority'] -= min_priority

queue = LWPriorityQueue()

queue.insert(4, 'belt', 'AJ', 45)

queue.insert(9, 'belt', 'Stu', 45)

queue.insert(12, 'wallet', 'Alex', 60)

queue.insert(12, 'belt', 'Alex', 45)

print("Queue before compact:")

queue.print_queue()

queue.compact()

print("Queue after compact:")

queue.print_queue()

"""

Queue before compact:

[

 {'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}

]

Queue after compact:

[

 {'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}

 File "C:\Users\tomas\AppData\Local\Temp\ipykernel_13172\3156436936.py", line 110 ^ SyntaxError: EOF while scanning triple-quoted string literal