Question
priority - an integer indicating the priority of the task task - the details of the task itself customer - the name of the customer;
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started