Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Queue with multi-field sorting on priority and time

Intent

Implement a task queue with sorting based on 1) priority and 2) time, specifically, time at which task was created or time-stamped (not inserted in the queue), giving preference to tasks with older time stamps.

enter image description here

Tried

This is what I got so far; much simpler than I thought having assumed it would require more than just a single PriorityQueue. In the comparator, if two priorities are equal, another comparison is made on Task.time, otherwise, comparison is based on just Task.priority.

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

public class QueueWithPriorityAndTimeSort {
   enum TaskPriority {
      High, Medium, Low
   }

   class Task implements Comparable<Task> {   
      long time;
      TaskPriority priority;

      Task(TaskPriority p, long t) {      
         time = t;
         priority = p;
      }

      public int compareTo(Task task2) {
         return priority.compareTo(task2.priority);
      }
   }

   class HighPriorityWithTimeComparator implements Comparator<Task> {
      public int compare(Task task1, Task task2) {
         int compareResult = task1.compareTo(task2);
         if( compareResult == 0){           
            //same priority, now compare on time
            if( task2.time < task1.time)
               compareResult = 1;
            else 
               compareResult = -1;
         }                          
         return compareResult;
      }
   }

   public void buildAndTestQueue(){
      PriorityQueue<Task> queue = 
            new PriorityQueue<Task>(3, new HighPriorityWithTimeComparator());
      queue.add(new Task(TaskPriority.High, 9));
      queue.add(new Task(TaskPriority.Low, 7));
      queue.add(new Task(TaskPriority.Low, 3));
      queue.add(new Task(TaskPriority.High, 2));
      queue.add(new Task(TaskPriority.Medium, 5));
      queue.add(new Task(TaskPriority.Medium, 4));
      queue.add(new Task(TaskPriority.High, 6));
      queue.add(new Task(TaskPriority.High, 8));
      queue.add(new Task(TaskPriority.Low, 15));
      queue.add(new Task(TaskPriority.Low, 10));

      Task m = null;
      while ((m = queue.poll()) != null)
         System.out.println(
            String.format("Priority: %s, %d", m.priority, m.time));     
   }

   public static void main(String args[]) {
      QueueWithPriorityAndTimeSort queueTest = 
         new QueueWithPriorityAndTimeSort();
      queueTest.buildAndTestQueue();
   }
}

Question

Is this a valid approach? I don't believe the added comparator logic changes the time complexity; aside from that, I don't see any glaring issues.

like image 957
raffian Avatar asked Mar 17 '23 02:03

raffian


1 Answers

My answer will address the following comment that you made :

Separating these concerns allows sorting based on specific needs for increased flexibility

There are better ways to separate the concerns and make your code even more flexible such that you can change the sorting strategy without changing your code. Sounds exciting?

Let's start by defining a Comparator just for comparaing priorities :

class HighPriorityComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            return task1.priority.compareTo(task2.priority);
        }
    }

Let's define a Comparator just for comparing time :

class TimeComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            int compareResult = 0;
            if (task2.time < task1.time)
                compareResult = 1;
            else
                compareResult = -1;

            return compareResult;
        }
    }

Now for the best part. Let's define a Comparator that will allow you to mix and match comparison logic.

class MixAndMatchComparator implements Comparator<Task> {

        List<Comparator<Task>> comparators;

        public MixAndMatchComparator(List<Comparator<Task>> comparators) {
            this.comparators=comparators;
        }

        @Override
        public int compare(Task o1, Task o2) {
            int compareResult = 0;
            for(Comparator<Task> comparator : comparators) {
                if(comparator.compare(o1, o2)!=0) {
                    return comparator.compare(o1, o2);
                }
            }
            return compareResult;
        }

    }

Now let's sort on priority and if priority is equal, then sort on time :

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on priority            
comparators.add(new HighPriorityComparator());
//then on time
comparators.add(new TimeComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);

Wait! You changed your mind? You now want to sort on time and if time is equal, then on priority? Just change the order in which you add the comprators to the list :

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on time    
comparators.add(new TimeComparator());
//then on priority
comparators.add(new HighPriorityComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);
like image 163
Chetan Kinger Avatar answered Mar 21 '23 16:03

Chetan Kinger