Assignment 2¶
Due Friday, March 31 at 5pm.
High-low priority task queue¶
Using an array implementation, write an efficient
Queue
data structure that performs the following operations in (amortized) constant time.push(a)
Adds integer
a
to end of queue.peek()
Returns the integer at the front of the queue. Throws an exception if the queue is empty.
pop()
Removes and returns the integer at the front of the queue. Throws an exception if the queue is empty.
Consider a priority system where there are two queues: one with high priority and one with low priority. Using your defined
Queue
implementation, write an efficientHighLowQueue
data structure that performs the following operations in (amortized) constant time.push_low(a)
Adds integer
a
to the end of the low priority queue.push_high(a)
Adds integer
a
to the end of the high priority queue.peek()
Returns the integer at the front of the high priority queue if non-empty, and otherwise returns the integer at the front of the low priority queue. Throws an exception if both queues are empty.
pop()
Removes and returns the integer at the fron of the high priority queue if non-empty, and otherwise removes and returns the integer at the front of the low-priority queue. Throws an exception if both queues are empty.
Now consider a high-low priority task manager. Each task has an integer identification number
id
, a string describing the task, and a string describing its status (“Enqueued”,”In Progress”,”Completed”,”Removed”). Write aTask
object that incorporates these features.A
Task
can either be added to a low or high priority queue. Using your previously writtenHighLowQueue
, write an efficientHighLowTaskQueue
object that performs the following operations in constant time (average-case is perfectly fine).push_low(t)
Adds task
t
to the low-priority queue with associatedid
integer. Throws an exception if there already exists a task with the sameid
in the system.push_high(t)
Adds task
t
to the high-priority queue with associatedid
integer. Throws an exception if there already exists a task with the sameid
in the system.peek()
Returns the
Task
object from the front of theHighLowQueue
. Throws an exception if the queue is empty.pop()
Removes and returns the
Task
object from the front of theHighLowQueue
. Throws an exception if the queue is empty.get(id)
Returns the
Task
object with associatedid
integer. Throws an exception if the task does not exist.remove(id)
Removes the
Task
object with associatedid
integer from the queue, but allows it to stay in the system with the “Removed” status. A removed task should never be returned bypeek
orpop
operations. Throws an exception if the task does not exist.
You must use the
HighLowQueue
data structure you wrote before, but you may use another data structure to keep track of allTask
objects in the system.
All data structures and objects should be thoroughly tested.
Web framework¶
Now that you have created a HighLowTaskQueue
, it is time to use a
web framework to implement it using REST. In particular, implement the
following operations.
GET
taskqueue/<name>
Returns the status of the task queue stored at the URL
taskqueue/<name>
. This is a human-readable representation of theHighLowTaskQueue
object, which at the very least involves the current task (usingpeek
) and the lengths of both queues.For example,
taskqueue/potato
should return the status of theHighLowTaskQueue
associated with potato.Raises HTTP Error 400 if the
<name>
does not exist.POST
taskqueue/<name>
Pushes a
Task
object to theHighLowTaskQueue
. Creates aHighLowTaskQueue
with given<name>
if it does not yet exist.The pushed task should have field names
id
,description
, andpriority
for the respective identification number, string description, and low or high priority. For example, the following HTML form could add a task toHighLowTaskQueue
potato:<form action="/taskqueue/potato" method="post"> <input type="number" name="id" size=4></input> <input type="text" name="description" size=10></input> <select name="priority"> <option value="low">Low Priority</option> <option value="high">High Priority</option> </select> <input type="submit"></input> </form>
GET
taskqueue/<name>/pop
Pops the element from the associated
HighLowTaskQueue
and displays the human-readable version of the task. If the queue is empty or non-existant, raise HTTP Error 400.GET
taskqueue/<name>/peek
Displays human-readable version of the task located at the top of the associated
HighLowTaskQueue
. If the queue is empty or non-existant, raise HTTP Error 400.GET
taskqueue/<name>/<id>
Displays the human-readable version of the task with identification number
<id>
in the associatedHighLowTaskQueue
. If the queue or identification number is empty or non-existant, raise HTTP Error 400.DELETE
taskqueue/<name>/<id>
Removes the task from the queue, and redirects to showing task with the updated status. If the queue or identification number is empty or non-existant, raise HTTP Error 400.
Again, these should be well tested.
Submission¶
Modify your README
or README.md
, adding how I can locally run
your web application and perform all the tests. At the very least,
create a new directory in your assignments repository.
I highly encourage you to try hosting your web application somewhere, either on a cloud server or using a cloud service. There are services such as Amazon Web Hosting and Heroku that provide some amount of hosting for free.
I will pull the most recent commit before Friday March 31, 5pm.