Home > Software engineering >  Implementing Comparator for a PriorityQueue. It functions with comparable and I can not understand w
Implementing Comparator for a PriorityQueue. It functions with comparable and I can not understand w

Time:11-28

I'll preface by saying that this is a project for a class. The logic of the code all functions and, as it stands, currently outputs close to the correct solution (I stopped working on the output when I learned that I had used the wrong interface). The problem is, the requirements very explicitly state we must use comparator. Being new to Java, I used Comparable, not realizing there was an explicit difference. This is an algorithms class in Java, my background is in Python and there are definitely some differences that are going over my head - I'm sure that will be apparent in my code.

I've sort of come to understand the difference between the two, but if you asked me to ELI5, I don't think I could. Please help me understand how exactly to implement Comparator as opposed to Comparable. I get that I need a separate class but then I'm not exactly sure how that should be formatted and what to do with it once I have it.

I'm including below the code of the working solution that implements comparable. Any guidance would be extremely appreciated. TIA.

EDIT: Also, by all means, anything else in particular about my code that stands out as going against Java conventions, I'm happy to hear about.

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.io.File;
import java.util.Scanner;
import java.io.FileNotFoundException;

public class ProcessScheduling {

    public static class Process implements Comparable<Process> {
        
        private Integer priority;
        private int id;
        private int arrivalTime;
        private int duration;

        public Process(int ID, Integer Priority, int Duration, int ArrivalTime) {
            this.id = ID;
            this.priority = Priority;
            this.duration = Duration;
            this.arrivalTime = ArrivalTime;
        }

        public Integer getPriority() {return priority;}
        public int getId() {return id;}
        public int getArrivalTime() {return arrivalTime;}
        public int getDuration() {return duration;}
        
        public void setPriority(Integer priority) {this.priority = priority;}

        @Override
        public String toString() {
            return "Process ID = "   getId()
                  "\n\tPriority = "   getPriority()
                  "\n\tArrival = "   getArrivalTime()
                  "\n\tDuration = "   getDuration();
        }

        @Override
        public int compareTo(Process P) {
            if (this.getPriority() > P.getPriority()) {return 1;}
            else if (this.getPriority() < P.getPriority()) {return -1;}
            return 0;
        }
    }

    public static void main(String[] args) {
        // Create ArrayList D to store new processes
        ArrayList<Process> D = new ArrayList<Process>();
        // Read the input file
        try {
            File f = new File("process_scheduling_input.txt");
            Scanner reader = new Scanner(f);
            while (reader.hasNextLine()) {
                // Create new Processes and add them to ArrayList D
                String[] data = reader.nextLine().split(" ");
                Process newProcess = new Process(   Integer.valueOf(data[0]),
                                                    Integer.parseInt(data[1]),
                                                    Integer.parseInt(data[2]),
                                                    Integer.parseInt(data[3])
                );
                D.add(newProcess);
            }
            reader.close();
        }   catch (FileNotFoundException e) {
            System.out.println("An error occured. File does not exist.");
            e.printStackTrace();
        }

        // Print all processes
        for (int i = 0; i < D.size(); i  ) {
            Process current = D.get(i);
            System.out.print("Id = "   current.getId());
            System.out.print(", priority = "   current.getPriority());
            System.out.print(", duration = "   current.getDuration());
            System.out.println(", arrival time = "   current.getArrivalTime());
        }

        // Instantiate priorityQueue and some parameters
        int currentTime = 10;
        boolean running = false;
        int maxWaitTime = 30;
        float totalWaitTime = 0;
        int currentEndTime = 0;
        Process current = null;
        PriorityQueue<Process> Q = new PriorityQueue<Process>();

        // Print maxWaitTime
        System.out.println("\nMaximum wait time = "   maxWaitTime);

        // While D still has a process in it
        while (D.isEmpty() == false) {
            // Check if current running process has finished
            if (running == true && currentEndTime <= currentTime) {
                // Print that Process finished
                System.out.print("Process "   current.getId());
                System.out.println(" finished at time "   currentTime   "\n");
                // Update running flag
                running = false;
                // Update priority of Processes in Q that have been waiting longer than max wait time
                System.out.println("Update priority:");
                if (Q.isEmpty() == false) {
                    for (Process p : Q) {
                        int waitTime = currentTime - p.getArrivalTime();
                        if (waitTime >= maxWaitTime) {
                            Integer priority = p.getPriority();
                            int id = p.getId();
                            System.out.print("PID = "   id);
                            System.out.print(", wait time = "   waitTime);
                            System.out.println(", current priority = "   priority);
                            priority -= 1;
                            p.setPriority(priority);
                            System.out.print("PID = "   id);
                            System.out.println(", new priority = "   priority);
                        }
                    }
                }
            }
            // Find process with earliest arrivalTime in D
            Process earliest = D.get(0);
            for (int i = 1; i < D.size(); i  ) {
                if (D.get(i).getArrivalTime() < earliest.getArrivalTime()) {
                    earliest = D.get(i);
                }
            }
            // Check if arrivalTime of earliest is <= to currentTime
            if (earliest.getArrivalTime() <= currentTime) {
                // Add to Q and remove from D if yes
                Q.add(earliest);
                D.remove(earliest);
            }
            // Check if Q is not empty and running flag is false
            if (Q.isEmpty() == false && running == false) {
                // Remove process in Q with smallest priority
                current = Q.poll();
                int waitTime = currentTime - current.getArrivalTime();
                totalWaitTime  = waitTime;
                currentEndTime = currentTime   current.getDuration();
                // Process removed from priority queue, print info
                System.out.print("\nProcess removed from queue is: id = "   current.getId());
                System.out.print(", at time "   currentTime);
                System.out.print(", wait time = "   waitTime);
                System.out.println(" Total wait time = "   totalWaitTime);
                System.out.println(current);
                running = true;
            }
            if (D.isEmpty() == true) {
                System.out.println("\nD becomes empty at time "   currentTime   "\n");
            }
            currentTime  ;
        }

        // D is now empty, all processes are in Q
        while (Q.isEmpty() == false) {
            // Check if current running process has finished
            if (running == true && currentEndTime >= currentTime) {
                // Update running flag
                running = false;
                // Update priority of Processes in Q that have been waiting longer than max wait time
                System.out.println("Update priority:");
                if (Q.isEmpty() == false) {
                    for (Process p : Q) {
                        if (p.getArrivalTime() - currentTime >= maxWaitTime) {
                            p.priority = p.getPriority() - 1;
                        }
                    }
                }
            }
            // If no Process running, start a new one
            if (running == false){
                current = Q.poll();
                int waitTime = currentTime - current.getArrivalTime();
                totalWaitTime  = waitTime;
                currentEndTime = currentTime   current.getDuration();
                // Process removed from priority queue, print info
                System.out.print("\nProcess removed from queue is: id = "   current.getId());
                System.out.print(", at time "   currentTime);
                System.out.print(", wait time = "   waitTime);
                System.out.println(" Total wait time = "   totalWaitTime);
                System.out.println(current);
                running = true;
            }
            currentTime  ;




            currentTime  ;
        }

    }

}

CodePudding user response:

The biggest differences between Comparator and Comparable is that a Comparator can order objects of different classes. Comparable generally can only order the same type of objects.

So, I'd say you're well on your way, it's not as big a jump as you expected.

CodePudding user response:

tl;dr

Comparator.comparing( Process :: getPriority )

Details

You said:

how exactly to implement Comparator as opposed to Comparable. I get that I need a separate class

Yes, that is the difference, a separate class.

  • Implementing Comparable is done by adding a method compareTo within the class of the objects being sorted. That means you are limited one single approach to sorting.
  • Implementing Comparator is done in a separate class. So we can more than one such Comparator implementation, for as many ways as we wish to sort our objects.

For example, a class Student representing people enrolled in a school might implement Comparable by adding a compareTo method that sorts by last name, and secondarily by first name. But in some contexts we might want to sort students by their grade level, and in other contexts by the date in which they first enrolled, and in yet other contexts we might sort by the distance between their home and the schoolhouse. For this other contexts we would write various classes implementing Comparator.

If you want to compare by a getPriority method that returns an int primitive, then your separate Comparator class might look like this.

class ProcessByPriorityComparator implements Comparator< Process > {  
    public int compare( Process p1 , Process p2 ){  
        if( p1.getPriority() == p2.getPriority() )  
        {
            return 0;  
        } 
        else if ( p1.getPriority() > p1.getPriority() )
        {
            return 1;  
        }
        else  
        { 
            return -1;  
        }  
    }
}  

Or simplify:

class ProcessByPriorityComparator implements Comparator< Process > {  
    public int compare( Process p1 , Process p2 ){  
        return Integer.compare( p1.getPriority() , p2.getPriority() ) ;  
    }
}  

Example usage:

Comparator< Process > processByPriorityComparator = 
        new ProcessByPriorityComparator() ;
Collections.sort( listOfProcesses , processByPriorityComparator ) ;

Or simply:

Collections.sort( listOfProcesses , new ProcessByPriorityComparator() ) ;

The lambda functional functional features in Java makes it quite easy to define a Comparator locally rather than formally defining a separate class.

Greatly helping to simplify this work are the static methods on Comparator such as comparing. So defining a Comparator can be as simple as using a method reference for an accessor “getter” method to sort by a particular property of the object.

This is quite appropriate in your particular case. We can use a method reference for the Process#getPriority method.

Comparator< Process > processByPriorityComparator = 
        Comparator.comparing( Process :: getPriority );
Collections.sort( listOfProcesses , processByPriorityComparator ) ;

Or, more simply, drop the named variable holding the comparator.

Collections.sort( listOfProcesses , Comparator.comparing( Process :: getPriority ) )

By the way, other issues with your code…

Do yourself a favor and move that huge main method out to its own class. Create a separate class named something like Main or App.

public class App {
    public static void main( String[] args ) {
        …
    }
} 

And I see no need for Process to be static nor be nested.

I suspect you feel some compulsion to have everything squeezed into a single class or file. Not so in Java. In Java you should generally have many classes, smaller and separate.

Eventually, as your app grows, organize the many classes by using packages and possible modules.

  • Related