8.5 Lab 15 - Priority Queue - Array with Insertion Sort

Module 8: Lab 15 - Priority Queue - Array with Insertion Sort

Cutting in Line

This lab only have one .java file, and you can download it below or copy and paste it into your preferred IDE.

Queues are a nice way to represent a collection of things that eventually need to be processed. But what if some things are more important than others, and we should be getting to them faster? What if we ran the world's worst ice cream shop and let people cut in line based on how much they donated to the owners? We'd need a priority queue rather than a regular queue. In fact, that unscrupulous ice cream shop is exactly what we're going to be making a reality in this lab.

By this point, you know the drill. We're going to be implementing a data structure using an array. Much of what you've already done in previous labs has been taken care of for you - the main problem in this lab is getting the queue to automatically sort its elements such that, whenever you do a pop or peek, the highest priority customer comes out. There are a few catches with this lab in particular, though, so be sure to read on.

The Customer is Always Right

The PriorityQueue you're going to be working with in this lab is not generic. It's meant to represent a queue of customers at a shop, so it only stores Customers, a special class we've made and filled out for you. But remember, our shop is rigged! The position people have in the queue is based on how much they've donated to the shop, and not necessarily the order they arrived at the queue. You will use a compareTo method to put them in order so that the person who has donated the most is in the front of the queue, the highest priority.

Coming Through!

It's not bad enough that some customers get preferential treatment - it's also possible for them to change their priority while in the queue. The bump() method takes in the index of a customer in the queue adds a certain amount of dollars to their donation, letting them potentially cut in line!

Comparables

You'll be making extensive use of compareTo in this lab. The Comparable interface specifies that compareTo should work in a certain way that can be a little hard to remember.

So here's a pro tip for remembering how to use compareTo: imagine you want to do the comparison

if (apple < orange)

All you need to do is replace the comparison operator with a call to compareTo, and then use the same comparison operator to compare the result of the compareTo to a 0. It looks like this:

if (apple.compareTo(orange) < 0)

As another example, apple >= orange would turn into apple.compareTo(orange) >= 0.

The PriorityQueue

Our priority queue stores two things: an array of customers (our main data array), and a count of how many customers are in the queue. The constructors have been handled for you.

We can use our array somewhat like a stack to implement the behavior we want. The array should stay in sorted order, keeping the highest priority customer at the beginning of the array and the lowest at the end of the array.

The queue needs to support the following operations:

• push(): Add a customer to the queue, putting it in the proper sorted place.
• pop(): Remove the highest priority customer from the queue.
• peek(): Return, but do not remove, the highest priority customer.
• bump(): Increase the donation amount of the customer at a given index by a given amount of money, moving the customer in the queue if necessary

Make sure your operations pay attention to how many customers are in the queue! Hint: exceptions need to be thrown if certain operations are called with no customers or if you try to add too many customers.

Here are few examples of these operations; note how the array always stays sorted, and the leftmost item (at index 0) is always what is popped off:

Exceptions

You will need to use exceptions in this lab on some of these methods. For example, if you try to insert an item when the capacity is full or when you try to take out an item when the queue is empty. Hint: we'll be testing these two scenarios. It's better to be specific when throwing exceptions, so you should use an IllegalStateException in the former case and a NoSuchElementException in the latter.

Wrapping Up

As is tradition, the main method is full of code you can use to test your implementation. Run it when you're done writing methods to see if you've done it right. If you get the same output as this:

Testing push Line should be: [$10.00, $5.00, $1.00, null, null, null] [$10.00, $5.00, $1.00, null, null, null] Line size should be 3 is: 3 Testing pop $10.00 $5.00 Testing bump $61.00 $45.00 $45.00 $20.00 $2.00 Line should be: [$10.00, $9.00, $8.00, $7.00, $7.00, null] [$10.00, $9.00, $8.00, $7.00, $7.00, null]

Then you've got it!

Submission

In Submit mode, select "Submit for grading" when you are ready to turn in your assignment.

import java.util.Arrays;

public class PriorityQueue {

/* This class is finished for you. */ public static class Customer implements Comparable { private double donation;

public Customer(double donation) { this.donation = donation; }

public double getDonation() { return donation; }

public void donate(double amount) { donation += amount; }

public int compareTo(Customer other) { double diff = donation - other.donation; if (diff < 0) { return -1; } else if (diff > 0) { return 1; } else { return 0; } }

public String toString() { return String.format("$%.2f", donation); } }

private Customer[] data; private int size;

public PriorityQueue(int capacity) { data = new Customer[capacity]; size = 0; } public PriorityQueue() { this(10); }

/* Add a customer to the queue. * Remember to do so in a way that keeps the queue in sorted order! */ public void push(Customer customer) {

}

/* Remove and return the highest priority customer from the queue. */ public Customer pop() { return null; }

/* Return, but don't remove, the highest priority item from the queue. */ public Customer peek() { return null; }

/* Given the index of a customer, increase their donation amount, letting * them cut in line if necessary. * * Refer to the Customer class to remind yourself the operations you can do * on a customer. */ public void bump(int customerIndex, double amount) { }

public String toString() { return Arrays.toString(data); } public int getSize() { return size; }

public static void main(String[] args) { PriorityQueue line = new PriorityQueue(6); System.out.println("Testing push"); line.push(new Customer(5.00)); line.push(new Customer(10.00)); line.push(new Customer(1.00)); System.out.println("Line should be: [$10.00, $5.00, $1.00, null, null, null]"); System.out.println(line); System.out.println("Line size should be 3 is: " + line.getSize()); System.out.println(); System.out.println("Testing pop");

System.out.println(line.pop()); System.out.println(line.pop()); System.out.println(); System.out.println("Testing bump");

line.push(new Customer(20.00)); line.push(new Customer(15.00)); line.push(new Customer(2.00));

line.bump(1, 30.00); line.bump(3, 60.00); System.out.println(line.pop()); System.out.println(line.peek()); System.out.println(line.pop()); System.out.println(line.pop()); System.out.println(line.pop()); System.out.println(); line.push(new Customer(7.00)); line.push(new Customer(8.00)); line.push(new Customer(9.00)); line.push(new Customer(7.00)); line.push(new Customer(10.00)); System.out.println("Line should be: [$10.00, $9.00, $8.00, $7.00, $7.00, null]"); System.out.println(line); } }