priority - an integer indicating the priority of the task

task - the details of the task itself

customer - the name of the customer; Jo records stock as the customer when the item is to be held in stock.

complete_time - the estimated time (in minutes) the task will take to complete.

In [20]:

# Note that this implementation differs from the queues in the book!

# DO NOT edit this code.

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

Q2(a) (8 marks)

To keep on top of how much there is to do, Jo wishes to know the number of tasks of each priority.

Write a problem definition for a function count priorities that will return a dictionary. The keys of the dictionary will be the priorities held within the queue; its values will be the frequency of occurrence of the priority in question.

For example, if Jo's queue currently looks like this:

priority	task	customer	complete_time
1	belt	stock	45
1	belt	stock	45
2	custom wallet	Erich	90
1	wallet	stock	60

then the dictionary returned would be: { 1:3, 2:1 }

Note: The dictionary has been printed across multiple lines here for clarity; the actual output would be {1:3, 2:1}.

Jo can interpret this as there are three tasks of priority 1 and one task of priority 2.

Function: count priorities Inputs: Preconditions: Output: Postconditions:

Q2(b)(8 marks)

The code below repeats the bump method from the above. bump will increase by one the priority for all items associated with a given customer.

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

Q1a

Add four different test cases to the table below to thoroughly test the method bump. The code below will generate a queue, which you should use for your answers. The case should match the given input. The list has been printed for reference.

leather_list = LWPriorityQueue()

leather_list.insert(1, 'belt', 'Steff', 45)

leather_list.insert(2, 'wallet', 'stock', 60)

leather_list.insert(2, 'wallet', 'Mo', 60)

leather_list.insert(2, 'wallet', 'stock', 60)

leather_list.insert(3, 'custom belt', 'Erich', 90)

print(leather_list.print_queue())

[ {'priority': 3, 'task': 'custom belt', 'customer': 'Erich', 'complete_time': 90} {'priority': 2, 'task': 'wallet', 'customer': 'stock', 'complete_time': 60} {'priority': 2, 'task': 'wallet', 'customer': 'Mo', 'complete_time': 60} {'priority': 2, 'task': 'wallet', 'customer': 'stock', 'complete_time': 60} {'priority': 1, 'task': 'belt', 'customer': 'Steff', 'complete_time': 45} ] None 

Case	customer

Q1b

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:

[ {'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:

[ {'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; see Section 6.4.1 for further guidance on outlining algorithms in English. Not using an English outline will lead to marks being deducted.

Write your answer here