import java.util.*;
im port java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class Scheduler {

    Comparator<Process> comparator = new Comparator<Process>()
    {
        public int compare(Process a, Process b)
        {
            return a.arrivalTime < b.arrivalTime ? -1 : a.arrivalTime > b.arrivalTime ? 1 : 0;
        }
    };
    Comparator<Process> priorityComparator = new Comparator<Process>()
    {
        public int compare(Process a, Process b)
        {
            return a.priority < b.priority ? 1 : a.priority > b.priority ? -1 : 0;
        }
    };


    Average priorityScheduling (ArrayList<Process> processes) {

        Collections.sort(processes, comparator);

        PriorityQueue<Process> pq = new PriorityQueue<Process>(processes.size(), priorityComparator);

        int time = processes.get(0).arrivalTime;
        int i = 0;
        while (true) {
            if(pq.isEmpty() && i == processes.size()) break;
            while(i < processes.size() && processes.get(i).arrivalTime == time) {
                pq.add(processes.get(i));
                ++i;
            }
            while (!pq.isEmpty()) {
                ++time;//context swithcing
                while(i < processes.size() && processes.get(i).arrivalTime == time) {
                    pq.add(processes.get(i));
                    ++i;
                }
                Process process = pq.poll();
                process.waitingTime = time - process.arrivalTime;
                time += process.burstTime;
                while(i < processes.size() && processes.get(i).arrivalTime == time) {
                    pq.add(processes.get(i));
                    ++i;
                }
            }
            ++time;
        }
        double averageWaitingTime = 0, averageTurnaroundTime = 0;
        i = 0;
        while(i < processes.size()){
            processes.get(i).executionOrder = i+1;
            processes.get(i).turnaroundTime += processes.get(i).waitingTime;
            averageWaitingTime += processes.get(i).waitingTime;
            averageTurnaroundTime += processes.get(i).turnaroundTime;
            ++i;
        }
        averageWaitingTime /= processes.size();
        averageTurnaroundTime /= processes.size();
        Average average = new Average(averageWaitingTime, averageTurnaroundTime);
        return average;
    }

    Average roundRobinScheduling (ArrayList<Process> processes, int timeQuantum) {

        Collections.sort(processes, comparator);

        Queue<Process> q = new LinkedList<>();

        int time = processes.get(0).arrivalTime;
        int i = 0;
        while (true){
            if (q.isEmpty() && i == processes.size()) break;
            while (i < processes.size() && processes.get(i).arrivalTime <= time) {
                q.add(processes.get(i));
                ++i;
            }
            while (!q.isEmpty()){
                ++time;//context swithcing
                while (i < processes.size() && processes.get(i).arrivalTime <= time) {
                    q.add(processes.get(i));
                    ++i;
                }
                Process process = q.poll();
                process.waitingTime += time - process.arrivalTime;
                process.burstTime = (timeQuantum >= process.burstTime)?0 :process.burstTime-timeQuantum;
                time += timeQuantum;
                while (i < processes.size() && processes.get(i).arrivalTime <= time) {
                    q.add(processes.get(i));
                    ++i;
                }
                if (process.burstTime > 0){
                    process.arrivalTime = time;
                    q.add(process);
                }
            }
            ++time;
        }
        double averageWaitingTime = 0, averageTurnaroundTime = 0;
        i = 0;
        while(i < processes.size()){
            processes.get(i).executionOrder = i+1;
            processes.get(i).turnaroundTime += processes.get(i).waitingTime;
            averageWaitingTime += processes.get(i).waitingTime;
            averageTurnaroundTime += processes.get(i).turnaroundTime;
            ++i;
        }
        averageWaitingTime /= processes.size();
        averageTurnaroundTime /= processes.size();
        Average average = new Average(averageWaitingTime, averageTurnaroundTime);
        return average;
    }

    public static void shortesJobFirst(Process PA[],Comparator<Process> c)
    {
        ArrayList<Process> WaitingQueue = new ArrayList<Process>();
        Process running = null;
        int time = 0;

        Comparator<Process> comparator = new Comparator<Process>()
        {
            public int compare(Process a,Process b)
            {
                return a.burstTime < b.burstTime ? -1 : a.burstTime > b.burstTime ? +1 : 0;
            }
        };

        int numOfProcesses = 0,nextToQueue = 0;
        while(numOfProcesses<PA.length || WaitingQueue.size() != 0 || running != null)
        {
            while(nextToQueue < PA.length && PA[nextToQueue].arrivalTime == time)
            {
                int indx = Collections.binarySearch(WaitingQueue,PA[nextToQueue],comparator);
                if(indx < 0)
                    indx = -(indx + 1);
                WaitingQueue.add(indx,PA[nextToQueue++]);
                numOfProcesses++;
            }

            if(running == null)
            {
                if(WaitingQueue.size() > 0)
                    running = WaitingQueue.remove(0);
            }
            else
            {
                if(WaitingQueue.size() > 0 && running.burstTime == 0)
                    running = WaitingQueue.remove(0);
                else if(running.burstTime == 0)
                    running = null;
                else if(WaitingQueue.size() > 0 && WaitingQueue.get(0).burstTime < running.burstTime)
                {
                    int indx = Collections.binarySearch(WaitingQueue,running,comparator);
                    if(indx < 0)
                        indx = -(indx + 1);
                    WaitingQueue.add(indx,running);
                    running = WaitingQueue.remove(0);
                }
                else
                {
                    running.burstTime--;
                    running.turnaroundTime++;
                }
            }

            for(int i=0;i<WaitingQueue.size();i++)
            {
                WaitingQueue.get(i).waitingTime++;
                WaitingQueue.get(i).turnaroundTime++;
            }

            time++;
        }
    }

}