Custom Java PriorityQueue Comparator

Question

In my PriorityQueue, I have 2 types of clients, VIP and regular. I want to serve the VIP first, and then regularly.

If CustomerID <100 is considered VIP.

If the client is VIP, he goes at the end of the VIP part of the queue

If the customer is constant, he goes to the end of the line.

In other words, I want to sort by boolean VIP value, while preserving the order in which the clients entered.

Here is my class

public class Order implements Comparable<Order> { private final int customerID; private final int amount; private final boolean vip_status; public Order(int customerID, int amount) { this.customerID = customerID; this.amount = amount; this.vip_status = customerID < 100 ? true : false; } @Override public int compareTo(Order o) { if (vip_status && !o.vip_status) { return -1; } if (!vip_status && o.vip_status) return 1; return 0; } public int getCustomerID() { return customerID; } public int getAmount() { return amount; } public boolean isVip_status() { return vip_status; } } 

Here is my attempt to fill the queue:

 import java.util.PriorityQueue; public class MyPriorityQueue { public static void main(String[] args) { PriorityQueue<Order> queue = new PriorityQueue<>(); Order o1 = new Order(1, 50); Order o2 = new Order(5, 30); Order o3 = new Order(4, 10); Order o4 = new Order(150, 5); Order o5 = new Order(2, 5); Order o6 = new Order(200, 5); queue.add(o1); queue.add(o2); queue.add(o3); queue.add(o4); queue.add(o5); queue.add(o6); while(!queue.isEmpty()){ Order s = queue.poll(); System.out.printf("VIP Status: %s CustomerID: %s Amount: %s%n", s.isVip_status(), s.getCustomerID(), s.getAmount()); } } } 

RESULT I get (which is wrong):

 VIP Status: true CustomerID: 1 Amount: 50 VIP Status: true CustomerID: 5 Amount: 30 VIP Status: true CustomerID: 2 Amount: 5 VIP Status: true CustomerID: 4 Amount: 10 VIP Status: false CustomerID: 150 Amount: 5 VIP Status: false CustomerID: 200 Amount: 5 

This is what I expected to see (CustomerID 2 and 4 should be in the same order they entered):

 VIP Status: true CustomerID: 1 Amount: 50 VIP Status: true CustomerID: 5 Amount: 30 VIP Status: true CustomerID: 4 Amount: 10 VIP Status: true CustomerID: 2 Amount: 5 VIP Status: false CustomerID: 150 Amount: 5 VIP Status: false CustomerID: 200 Amount: 5 

UPDATE: I do not want to sort by any column other than VIP. I don’t want to add a “date” because it seems like a hack, not an understanding of how Java works.

Answer 1

It looks like the PriorityQueue class that java ships with the box can reorder items if they are compared as equal to each other .

^{(This is not “how Java works,” it's just a little perversion on behalf of the particular class that ships with the Java Runtime.)}

So here is something that will probably work:

• Introduce a new OrderPlacement class containing a) a Order and b) a int priority .

• In PriorityQueue add OrderPlacement objects instead of Order objects.

• When you create a new OrderPlacement , enter a new priority for it, increasing the counter.

Then your OrderPlacement object may have a compareTo() method, which looks like this:

 @Override public int compareTo( OrderPlacement o ) { int d = -Boolean.compare( order.vip_status, o.order.vip_status ); if( d != 0 ) return d; return Integer.compare( priority, o.priority ); } 

Answer 2

If you must do this using a priority queue, the code below will solve your problem. Please note that I use a static counter to maintain the correct order of items with the same VIP status, since the same items are supported randomly in the priority queue. This is because the priority queue uses the min / max heap data structure, and it only cares about placing the min / max element at the top of the heap and does not worry about ordering the same elements.

 import java.util.PriorityQueue; public class Order implements Comparable<Order> { private final int customerID; private final int amount; private final int vip_status; private final int score; private static int counter = 0; public Order(int customerID, int amount) { this.customerID = customerID; this.amount = amount; this.vip_status = customerID < 100 ? 0 : 1; this.score = counter++; } @Override public String toString() { return customerID + " : " + amount + " : " + vip_status; } @Override public int compareTo(Order o) { int status = ((Integer) this.vip_status).compareTo(o.vip_status); status = status == 0 ? ((Integer) this.score).compareTo(o.score) : status; return status; } public static void main(String[] args) { Order o1 = new Order(1000, 100); Order o2 = new Order(500, 100); Order o3 = new Order(99, 100); Order o4 = new Order(10, 100); Order o5 = new Order(200, 100); Order o6 = new Order(1, 100); PriorityQueue<Order> orderQueue = new PriorityQueue<>(); orderQueue.offer(o1); orderQueue.offer(o2); orderQueue.offer(o3); orderQueue.offer(o4); orderQueue.offer(o5); orderQueue.offer(o6); System.out.println(orderQueue.poll()); System.out.println(orderQueue.poll()); System.out.println(orderQueue.poll()); System.out.println(orderQueue.poll()); System.out.println(orderQueue.poll()); System.out.println(orderQueue.poll()); } } 

`

Output Example:

 99 : 100 : 0 10 : 100 : 0 1 : 100 : 0 1000 : 100 : 1 500 : 100 : 1 200 : 100 : 1 

Note: you should be aware that the score may eventually reach Integer.MAX_VALUE