The PriorityQueue and LinkedList Classes 2 – Collections: Part II

The static method comparing() extracts a comparator that uses the getName() method of the Task class, and the default method reversed() reverses this comparator.

The priority queues pq5 and pq6 use total ordering based on multiple fields of the Task class: on the task number, followed by the task name. This ordering is defined for pq5 and pq6 by a lambda expression at (6) and by methods of the Comparator<E> interface at (7), respectively. The latter implementation first extracts a comparator based on the task number, and chains it with one based on the task name:

Click here to view code image

PriorityQueue<Task> pq6 = new PriorityQueue<>(                          // (7)
      Comparator.comparing(Task::getTaskNumber)
                .thenComparing(Task::getTaskName)
);

We leave it to the reader to verify that the output conforms to the priority ordering of priority queues at (3) through (7).

Example 15.7 Using Priority Queues

Click here to view code image

/** Represents a task. */
public class Task implements Comparable<Task> {
  private Integer taskNumber;
  private String  taskName;
  public Task(Integer tp, String tn) {
    taskNumber = tp;
    taskName   = tn;
  }
  @Override
  public boolean equals(Object obj) {// Equality based on the task number.
    return (this == obj)
        || (obj instanceof Task other
            && this.taskNumber.equals(other.taskNumber));
  }
  @Override
  public int compareTo(Task task2) { // Natural ordering based on the task number.
    return this.taskNumber.compareTo(task2.taskNumber);
  }
  @Override
  public int hashCode() {            // Hash code based on the task number.
    return this.taskNumber.hashCode();
  }
  @Override
  public String toString() { return taskNumber + “@” + taskName; }

  public String  getTaskName()   { return taskName; }
  public Integer getTaskNumber() { return taskNumber;}
}

Click here to view code image

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import static java.lang.System.out;
/** Executes tasks. */
public class TaskExecutor {
  public static void main(String[] args) {
    // Array with some tasks.                                                  (1)
    Task[] taskArray = {
        new Task(200, “lunch”), new Task(200, “tea”),
        new Task(300, “dinner”), new Task(100, “breakfast”),
    };
    out.println(“Array of tasks: ” + Arrays.toString(taskArray));
    out.println(“Priority queue using natural ordering (task number).”);
    PriorityQueue<Task> pq1 = new PriorityQueue<>();                        // (2)
    testPQ(taskArray, pq1);
    out.println(“Priority queue using reverse natural ordering.”);          // (3)
    PriorityQueue<Task> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
    testPQ(taskArray, pq2);
    out.println(“Priority queue using reversed ordering”
        + ” on task name (lambda expression).”);
    PriorityQueue<Task> pq3 = new PriorityQueue<>(                          // (4)
        (task1, task2) -> {
          String taskName1 = task1.getTaskName();
          String taskName2 = task2.getTaskName();
          return -taskName1.compareTo(taskName2);
         }
      );
    testPQ(taskArray, pq3);
    out.println(“Priority queue using reversed ordering”
        + ” on task name (extracted comparator).”);
    PriorityQueue<Task> pq4 = new PriorityQueue<>(                          // (5)
        Comparator.comparing(Task::getTaskName).reversed()
    );
    testPQ(taskArray, pq4);
    out.println(“Priority queue using total ordering based on task number,”
        + “\nfollowed by task name (lambda expression).”);
    PriorityQueue<Task> pq5 = new PriorityQueue<>(                          // (6)
      (task1, task2) -> {
        Integer taskNumber1 = task1.getTaskNumber();
        Integer taskNumber2 = task2.getTaskNumber();
        if (!taskNumber1.equals(taskNumber2))
          return taskNumber1.compareTo(taskNumber2);
        String taskName1 = task1.getTaskName();
        String taskName2 = task2.getTaskName();
        if (!taskName1.equals(taskName2))
          return taskName1.compareTo(taskName2);
        return 0;
       }
    );
    testPQ(taskArray, pq5);
    out.println(“Priority queue using total ordering based on task number,”
        + “\nfollowed by task name (extracted comparators).”);
    PriorityQueue<Task> pq6 = new PriorityQueue<>(                          // (7)
        Comparator.comparing(Task::getTaskNumber)
                  .thenComparing(Task::getTaskName)
    );
    testPQ(taskArray, pq6);
  }
  // Runs tasks.
  private static void testPQ(Task[] taskArray, PriorityQueue<Task> pq) {    // (8)
    // Load the tasks:                                                         (9)
    for (Task task : taskArray)
      pq.offer(task);
    out.println(“Queue before executing tasks: ” + pq);
    // Peek at the head:                                                      (10)
    out.println(“Task at the head: ” + pq.peek());
    // Do the tasks:                                                          (11)
    out.print(“Doing tasks: “);
    while (!pq.isEmpty()) {
      Task task = pq.poll();
      out.print(task + ” “);
    }
    out.println();
    out.println();
  }
}

Output from the program:

Click here to view code image Array of tasks: [200@lunch, 200@tea, 300@dinner, 100@breakfast]
Priority queue using natural ordering (task number).
Queue before executing tasks: [100@breakfast, 200@lunch, 300@dinner, 200@tea]
Task at the head: 100@breakfast
Doing tasks: 100@breakfast 200@tea 200@lunch 300@dinner
Priority queue using reverse natural ordering.
Queue before executing tasks: [300@dinner, 200@tea, 200@lunch, 100@breakfast]
Task at the head: 300@dinner
Doing tasks: 300@dinner 200@tea 200@lunch 100@breakfast
Priority queue using reversed ordering on task name (lambda expression).
Queue before executing tasks: [200@tea, 200@lunch, 300@dinner, 100@breakfast]
Task at the head: 200@tea
Doing tasks: 200@tea 200@lunch 300@dinner 100@breakfast
Priority queue using reversed ordering on task name (extracted comparator).
Queue before executing tasks: [200@tea, 200@lunch, 300@dinner, 100@breakfast]
Task at the head: 200@tea
Doing tasks: 200@tea 200@lunch 300@dinner 100@breakfast
Priority queue using total ordering based on task number,
followed by task name (lambda expression).
Queue before executing tasks: [100@breakfast, 200@lunch, 300@dinner, 200@tea]
Task at the head: 100@breakfast
Doing tasks: 100@breakfast 200@lunch 200@tea 300@dinner
Priority queue using total ordering based on task number,
followed by task name (extracted comparators).
Queue before executing tasks: [100@breakfast, 200@lunch, 300@dinner, 200@tea]
Task at the head: 100@breakfast
Doing tasks: 100@breakfast 200@lunch 200@tea 300@dinner