Assignment 2

Due Friday, March 31 at 5pm.

High-low priority task queue

1. 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.

2. 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 efficient HighLowQueue 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.

3. 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 a Task object that incorporates these features.

   A Task can either be added to a low or high priority queue. Using your previously written HighLowQueue, write an efficient HighLowTaskQueue 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 associated id integer. Throws an exception if there already exists a task with the same id in the system.

   • push_high(t)

     Adds task t to the high-priority queue with associated id integer. Throws an exception if there already exists a task with the same id in the system.

   • peek()

     Returns the Task object from the front of the HighLowQueue. Throws an exception if the queue is empty.

   • pop()

     Removes and returns the Task object from the front of the HighLowQueue. Throws an exception if the queue is empty.

   • get(id)

     Returns the Task object with associated id integer. Throws an exception if the task does not exist.

   • remove(id)

     Removes the Task object with associated id integer from the queue, but allows it to stay in the system with the “Removed” status. A removed task should never be returned by peek or pop 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 all Task 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 the HighLowTaskQueue object, which at the very least involves the current task (using peek) and the lengths of both queues.

  For example, taskqueue/potato should return the status of the HighLowTaskQueue associated with potato.

  Raises HTTP Error 400 if the <name> does not exist.

• POST taskqueue/<name>

  Pushes a Task object to the HighLowTaskQueue. Creates a HighLowTaskQueue with given <name> if it does not yet exist.

  The pushed task should have field names id, description, and priority for the respective identification number, string description, and low or high priority. For example, the following HTML form could add a task to HighLowTaskQueue 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 associated HighLowTaskQueue. 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.