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 toComparable
. I get that I need a separate class
Yes, that is the difference, a separate class.
- Implementing
Comparable
is done by adding a methodcompareTo
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 suchComparator
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.