PriorityQueue and Comparable interface example

clayh

I couldn't find good examples of an implementation of PriorityQueue for Processing and some of the online Java examples aren't great and/or are misleading. So, here's an example of how to use a PriorityQueue and implement the required compareTo method on a custom class.

import java.util.PriorityQueue;

public class FancyClass implements Comparable {

  // Required when implementing Comparable
  public int compareTo(FancyClass other) {
    return this.somenumber.compareTo(other.somenumber);
  }

  // This must be an Integer and not an int primitive
  // or compareTo will throw an exception.
  Integer somenumber;
  String name;

  FancyClass(String _name) {
    name = _name;
  }

  // Custom print value for the class
  public String toString() {
    return name + ": " + somenumber;
  }
}



FancyClass fc1, fc2, fc3, fc4;
PriorityQueue pq;

void setup() {
  fc1 = new FancyClass("fc1");
  fc2 = new FancyClass("fc2");
  fc3 = new FancyClass("fc3");
  fc4 = new FancyClass("fc4");

  fc1.somenumber = 12;
  fc2.somenumber = -1;
  fc3.somenumber = 7;
  fc4.somenumber = 99;

  // Here we do not need to implement a comparator because FancyClass implements Comparable
  // and the compareTo method, which is the "natural ordering" for the FancyClass class.
  // The 5 is simply the capacity of the priority queue.
  pq = new PriorityQueue(5);

  // offer() and add() are the same for PriorityQueue
  pq.offer(fc1);
  pq.offer(fc2);
  pq.offer(fc3);
  pq.offer(fc4);
}

void draw() {
  // Note, this will NOT print them in order!!
  println(pq);
  
  // You can only get them in order by polling the queue.
  while (!pq.isEmpty ()) {
    println("Item: " + pq.poll());
  }
  
  noLoop();
}

The output:

[fc2: -1, fc1: 12, fc3: 7, fc4: 99]
Item: fc2: -1
Item: fc3: 7
Item: fc1: 12
Item: fc4: 99

There's another way to do this if you don't want the compareTo method in your class. You write a Comparator, which requires importing another Java library. You then can provide the Comparator as a parameter to PriorityQueue, effectively allowing you to have many different ways for comparing objects of the same class.

import java.util.PriorityQueue;
import java.util.Comparator;

public class FancyClass {

  // This doesn't need to be an Integer in this case
  int somenumber;
  int someothernumber;
  String name;

  FancyClass(String _name) {
    name = _name;
  }

  // Custom print value for the class
  public String toString() {
    return name + ", somenumber:" + somenumber + ", someothernumber: " + someothernumber;
  }
}

// The Comparators that look at different numbers in FancyClass
static class FancySortOne implements Comparator {
  public int compare(FancyClass one, FancyClass two) {
    return one.somenumber - two.somenumber;
  }
}

static class FancySortTwo implements Comparator {
  public int compare(FancyClass one, FancyClass two) {
    // Note the difference
    return one.someothernumber - two.someothernumber;
  }
}

FancyClass fc1, fc2, fc3, fc4;
PriorityQueue pq, pq2;

void setup() {
  fc1 = new FancyClass("fc1");
  fc2 = new FancyClass("fc2");
  fc3 = new FancyClass("fc3");
  fc4 = new FancyClass("fc4");

  fc1.somenumber = 12;
  fc2.somenumber = -1;
  fc3.somenumber = 7;
  fc4.somenumber = 99;

  fc1.someothernumber = 2;
  fc2.someothernumber = 17;
  fc3.someothernumber = 79;
  fc4.someothernumber = 4;

  FancySortOne fs1 = new FancySortOne();
  FancySortTwo fs2 = new FancySortTwo();

  // Provide the Comparator as a parameter
  pq  = new PriorityQueue(5, fs1);
  pq2 = new PriorityQueue(5, fs2);

  // offer() and add() are the same for PriorityQueue
  pq.offer(fc1);
  pq.offer(fc2);
  pq.offer(fc3);
  pq.offer(fc4);

  pq2.offer(fc1);
  pq2.offer(fc2);
  pq2.offer(fc3);
  pq2.offer(fc4);
}

void draw() {
  // Note, this will NOT print them in order!!
  println(pq);

  // You can only get them in order by polling the queue.
  while (!pq.isEmpty ()) {
    println("Item: " + pq.poll());
  }

  // Now look at the other comparator
  println("\n------------------------------------------\n");

  // Note, this will NOT print them in order!!
  println(pq2);

  // You can only get them in order by polling the queue.
  while (!pq2.isEmpty ()) {
    println("Item: " + pq2.poll());
  }

  noLoop();
}

The output:

[fc2, somenumber:-1, someothernumber: 17, fc1, somenumber:12, someothernumber: 2, fc3, somenumber:7, someothernumber: 79, fc4, somenumber:99, someothernumber: 4]
Item: fc2, somenumber:-1, someothernumber: 17
Item: fc3, somenumber:7, someothernumber: 79
Item: fc1, somenumber:12, someothernumber: 2
Item: fc4, somenumber:99, someothernumber: 4

------------------------------------------

[fc1, somenumber:12, someothernumber: 2, fc4, somenumber:99, someothernumber: 4, fc3, somenumber:7, someothernumber: 79, fc2, somenumber:-1, someothernumber: 17]
Item: fc1, somenumber:12, someothernumber: 2
Item: fc4, somenumber:99, someothernumber: 4
Item: fc2, somenumber:-1, someothernumber: 17
Item: fc3, somenumber:7, someothernumber: 79

GoToLoop

• I've already dabbled in ArrayDeque twice or thrice, but never before a PriorityQueue. :-?
• Almost all of sketches we create just need to traverse some animated object container in any order for displaying them.
• Even regular FIFO & LIFO are pretty rare. Much less a Queue based on a custom remove() order!
• And if we wish to web-deploy it under "JS Mode" (PJS), it's outta question! :(
• Just for the sake of curiosity, I've made some tweaks on it. Hope you like it! :-bd

// forum.processing.org/two/discussion/10244/priorityqueue-and-comparable-interface-example

import java.util.Queue;
import java.util.PriorityQueue;

static final int QTY = 4;
final Queue<FancyClass> pq = new PriorityQueue(QTY + 1);
final FancyClass[] fancies = new FancyClass[QTY];

void setup() {
  for (int vals[] = {12, -1, 7, 99}, i = 0; i != QTY
    ; pq.add( fancies[i] = new FancyClass("fc" + i, vals[i++]) ));

  print("Fancy Array[]:  ");
  println(fancies);
  println("PriorityQueue: ", pq, '\n');

  frameRate(1);
}

void draw() {
  if (pq.isEmpty())  exit();
  else               println(pq.remove());
}

class FancyClass implements Comparable<FancyClass> {
  String name;
  int num;

  FancyClass(String s, int n) {
    name = s;
    num  = n;
  }

  @ Override int compareTo(FancyClass other) {
    return Integer.compare(num, other.num); // or faster: 'return num - other.num;'
  }

  @ Override String toString() {
    return name + ": " + num;
  }
}

GoToLoop

I'm back just to highlight that we don't need a formal class in order to instantiate an interface.
We can do instead an anonymous instantiation as long as we provide implementation for each demanded abstract method on it: :D

import java.util.Comparator;
static final Comparator<FancyClass> FANCY_SORT_A = new Comparator<FancyClass>() {
  @ Override int compare(FancyClass a, FancyClass b) {
    return a.num - b.num;
  }
};

clayh

Cool, thanks for the additions and efficiencies! I tend to try to be as explicit as possible when I write examples for myself, else I spend too much time trying to understand loops, etc. :D

For what it's worth, I was implementing A* and wanted a PriorityQueue so that I could explore the frontier more efficiently.