/** An Exponential Queues(version 1) Scheduler for a CPU.  
 ** It maintains a linked list of jobs.  
 **
 ** This scheduler is remarkably similar to the DiskScheduler.
 **/
import java.io.*;
import java.util.*;

public class XQ1Scheduler extends Scheduler {

    /**
     * member: multilevel queues' head and tail
     */
    private Job[] pqHead = new Job[8];
    private Job[] pqTail = new Job[8];
    
    /**
     *constructor
     */
    public XQ1Scheduler(){
        super();
        for(int i=0; i<8; i++){
            pqHead[i] = null;
        }
    }
    
    /**
     *method: add a job to a queue which it should go
     */
    public boolean add(Job j, int timeLeft) {
	//lower j's priority by one level and double its time sclice
	//if its priority already is 7, no change. 
        int p = j.getPriority()+1;
        if (p == 8)
	    p = 7;
        else if (p > 0)
            j.setTimeSlice(2 * j.getTimeSlice());
        j.setPriority(p);

	//System.out.println("========>"+j.getTimeSlice());
        //System.out.println("========>Priority"+j.getPriority());

	//add job to the expected queue
        if(pqHead[p] == null){
            pqHead[p] = j;
        }
        else{
            pqTail[p].next = j;
            
        }
        pqTail[p] = j;
        j.next = null;

	//tell the queue change
        queueChanged(1);
        return false;
    }
    
    /**
     *method: remove a job from the top level queue
     */
    public Job remove() {
        // search unempty  highest  level queue  
        int i;
        for(i=0; i<8; i++){
            if(pqHead[i]!=null) {
                break;
            }
        }

	//all the queues are empty
        if(i==8){
            return null;
        }
        //return the right job
        Job result = pqHead[i];
        pqHead[i] = pqHead[i].next;
	//tell the queue change
        queueChanged(-1);
        return result;
    }
    
    /**
     *method: is it posible to reschdule the job
     */
    public boolean reschedule(Job job) {
        for(int i=0; i<8; i++){
            if(pqHead[i] != null){
                return true;
            }
        }
        return false;
    }

    /**
     *method: print queue
     */
    
    public void printQueue() {
        for(int i=0; i<8; i++){
            if(pqHead[i] == null)
                Sim.db("| CPU queue["+i+"]: empty");
            else {
                Sim.db("| CPU queue["+i+"]");
                for (Job j = pqHead[i]; j != null; j = j.next) {
                    Sim.db("|    " + j);
                }    
            }
        }
        
        
        if (head == null)
            Sim.db("| CPU queue: empty");
        else {
            Sim.db("| CPU queue:");
            for (Job j = head; j != null; j = j.next) {
                Sim.db("|    " + j);
            }
        }
    }
    
    //******************************************************************
    //following are the original code provided by instructor
    
    /** The queue of jobs awaiting service.
     ** If the queue is empty, head = null and the value of tail is undefined.
     **/
    private Job head = null;
    private Job tail;

    /** Add a new job wanting service.
     ** The second argument is the amount of time remaining before the
     ** job currently using the device will finish (-1 if the device is idle).
     ** Return TRUE if this scheduler would like to preempt the current
     ** job.
     **/
/*    public boolean add(Job j, int timeLeft) {
        if (head == null) {
            head = j;
        }
        else {
            tail.next = j;
        }
        tail = j;
        j.next = null;
        queueChanged(1);    // update queue-length statistics
        return false;       // RR scheduler only preempts on clock interrupts
    }
*/
    /** Retrieve (and remove) the next job to be served.
     ** Return null if there is no such job.
     **/
/*
    public Job remove() {
        if (head == null)
            return null;
        Job result = head;
        head = head.next;
        queueChanged(-1);   // update queue-length statistics
        return result;
    }
*/
    /** This method is called when there is a clock interrupt.
     ** It returns true if there is a reason to stop the current process
     ** and run another one instead.
     ** The argument is the amount of time left until the current job
     ** finishes service on the device.
     ** It is ignored for RR scheduling (we preempt if and only if there
     ** is some other job to run).
     **/
/*    public boolean reschedule(Job job) {
	    return (head != null);
    }
*/

    /** For debugging: print the queue of waiting jobs */
/*    public void printQueue() {
        if (head == null)
            Sim.db("| CPU queue: empty");
        else {
            Sim.db("| CPU queue:");
            for (Job j = head; j != null; j = j.next) {
                Sim.db("|    " + j);
            }
        }
    }
*/
    //********************************************************************



    /** For debugging: a concise version of the queue of waiting jobs */
    private String queueString() {
        Job j = head;
        if (j == null)
            return "[]";
        String res = "[" + j;
        for (j = j.next; j != null; j = j.next) {
            res += " " + j;
        }
        return res + "]";
    }
    
} // XQ1Scheduler