import java.io.*;

class SimpleLinearScheduler extends PreCompScheduler {

    // Methods and variables implemented from PreCompScheduler

    // Variables:
    //  public boolean _equalQuanta;
    //  protected Process[] _processes;
    //  protected int _pCount;
    //  protected int _clock;
    //  protected int _stepClock;
    //  protected int _schedClock;
    //  protected int _cpuCount;
    //  protected int[][] _schedule;
    //  protected int _availMem;

    // The optimal permutation of Processes
    protected PermNode _chosenPerm;

    // Constructor
    public SimpleLinearScheduler( Process[] processes, int availMem ) {

	super( processes, availMem );

    }

    // Compute the schedule, run until all Processes are complete, and print
    // a report
    public void runAndReport( ) throws IOException {

	makeSchedule( true );
	
	System.out.println("Schedule complete.  Beginning run.");
	System.out.println();

	runSchedule( );

	System.out.println("Ran for a total of " + _clock + " quanta.");
	System.out.println("Total CPU quanta given out: " + _cpuCount);
	System.out.println();
	System.out.println("Number of processes: " + _pCount);
	for ( int loop = 0; loop < _pCount; loop++ ) {

	    _processes[loop].report( );

	}
	System.out.println( );

    }

    // Compute a schedule, run for the given amount of time, and print a
    // report
    public void runAndReport( int time ) {

	makeSchedule( true );

	runSchedule ( time );

	System.out.println("Runtime for this step: " + _stepClock);
	System.out.println("Total runtime so far: " + _clock);
	System.out.println("Total CPU quanta given out so far: " + _cpuCount);
	System.out.println("Number of processes: " + _pCount);
	for ( int loop = 0; loop < _pCount; loop++ ) {

	    _processes[loop].report( );

	}
	System.out.println( );

    }

    // Print a detailed report on the progress of all Processes
    public void finalReport( ) {

	System.out.println("--- Final Report ---");
	System.out.println("Schedule " + _chosenPerm + ", with share length " +
			   _chosenPerm._shareLength + " and running time " +
			   _chosenPerm._schedLength
			   + ", ran a total of " +
			   _clock / _chosenPerm._schedLength
			   + " times, for a clock time of " + _clock + ".");
	System.out.println();
	for( int loop = 0; loop < _processes.length; loop++) {
	    
	    System.out.println("Process " + _processes[loop]._id +
			       " (share = " + _processes[loop]._goalShare +
			       ", runtime = " + _processes[loop]._runTime +
			       ") received " + _processes[loop]._quantaReceived
			       + "/" + _cpuCount + " = " +
			       (double)_processes[loop]._quantaReceived
			       /(double)_cpuCount + " of the CPU quanta given."
			       + " After it completed, it received " +
			       (_processes[loop]._quantaReceived -  
				_processes[loop]._runTime)  +
			       " spare CPU quanta.");
	    System.out.println();

	}

    }

    public String getType( ) {
	return "SL";
    }

    // Calculate the shortest possible schedule for the _processes.
    // If verbose == true, display information while running.
    protected void makeSchedule( boolean verbose ) {

	// Assign perms to a linked list of all possible permutations
	PermNode best = findBestPerm( verbose );

	_chosenPerm = best;

	if ( verbose ) {

	    System.out.println("Best permutation: " + best
			       + " with share length " + best._shareLength
			       + " and total time " + best._schedLength);

	}

	// Set the schedule length based on the share length
	_schedule = new int[3][best._schedLength];

	for (int row = 0; row < 3; row++)
	    for (int col = 0; col < _schedule[0].length; col++)
		_schedule[row][col] = -1;

	assert (_schedClock == 0);

	if (verbose) {

	    System.out.println("--- Creating Schedule ---");

	}

	ProcNode proc = best._procs;
	do {

	    // Add the Process's running time to the schedule
	    for (int loop = _schedClock;
                 loop < _schedClock + ( proc._share * best._shareLength );
		 loop++) {
		
		_schedule[0][loop] = proc._id;

	    }

	    if (verbose) {

		System.out.println(" Proc " + proc._id + ": run for " +
				   proc._share * best._shareLength);

	    }

	    // Add the previous Process's roll-out time to the schedule
	    for (int loop = _schedClock;
		 loop < _schedClock + proc.prev._ro;
		 loop++) {

		_schedule[2][loop] = proc.prev._id;

	    }

	    if (verbose) {

		System.out.println(" Proc " + proc.prev._id + ": RO for " +
				   proc.prev._ro);

	    }

	    _schedClock += ( proc._share * best._shareLength ) - proc.next._ri;

	    // Add the next Process's roll-in time to the schedule
	    for (int loop = _schedClock;
		 loop < _schedClock + proc.next._ri;
		 loop++) {

		_schedule[1][loop] = proc.next._id;

	    }

	    if (verbose) {
		
		System.out.println(" Proc " + proc.next._id + ": RI for " +
				   proc.next._ri);
		System.out.println("----------------");

	    }

	    _schedClock += proc.next._ri;
	    proc = proc.next;

	} while ( proc != best._procs );

	assert(_schedClock == _schedule.length - 1);

    }

    // Methods and variables unique to SimpleLinearScheduler

    // Returns a linked list of all possible permutations of processes.
    // Possible improvement:  Edit this so that it does not return 
    // permutations that are cycles of other permutations.
    // If verbose == true, display information while running.
    protected PermNode findBestPerm( boolean verbose ) {

	PermutationGenerator pGen = new PermutationGenerator( _pCount );
	int[] indices;
	PermNode currentPerm = null;
	PermNode bestPerm = null;
	int bestSchedLength = Integer.MAX_VALUE;
	ProcNode procs = null;

	if ( verbose ) {

	    System.out.println("Calculating best permutation.");

	}

	while ( pGen.hasMore( ) ) {

	    indices = pGen.getNext( );
	    
	    procs = null;

	    // Make a linked list of ProcNodes in the order determined by
	    // indices
	    for ( int loop = 0; loop < _pCount; loop++ ) {

		ProcNode newProc;

		if ( procs == null ) {

		    newProc = new ProcNode( _processes[indices[loop]],
						     null, null );
		    newProc.next = newProc;
		    newProc.prev = newProc;

		}

		else {

		    newProc = new ProcNode( _processes[indices[loop]],
						     procs, procs.prev );
		    procs.prev.next = newProc;
		    procs.prev = newProc;

		}

		procs = newProc;

	    }

	    currentPerm = new PermNode( procs, null );

	    if ( currentPerm.calcSchedLength() < bestSchedLength ) {

		bestPerm = currentPerm;
		bestSchedLength = currentPerm._schedLength;

	    }


	}
	
	return bestPerm;

    }

    public String getPerm() {

	return _chosenPerm.toString();

    }

    public int getSchedLength() {

	return _chosenPerm._schedLength;

    }

    // A PermNode represents one permutation in a linked list.  It holds its
    // permutation in the form of a linked list of ProcNodes, representing
    // Processes.
    private class PermNode {

        public ProcNode _procs;  // The permutation's Processes, in order
	public int _shareLength; // The permutation's share length; initially
	                         // set to -1, then calculated later
	public int _schedLength;

	public PermNode next;    // The next permutation in the list

	// Constructor
	public PermNode( ProcNode procs, PermNode n ) {

	    _procs = procs;
	    _shareLength = -1;
	    next = n;

	}

	// Calculate the total time for a schedule using this permutation
	// (The permutation's share length must already be calculated)
	public int calcSchedLength() {

	    calcShareLength();

	    int shareSum = 0;
	    ProcNode traverse = _procs;
	    do {

		shareSum += traverse._share;
		traverse = traverse.next;

	    } while ( traverse != _procs );

	    _schedLength = shareSum * _shareLength;

	    return _schedLength;

	}

	// Calculate the share length for this permutation
	public int calcShareLength() {

	    // Perform calculations on the processes to prepare them
	    prepProcs();

	    ProcNode traverse = _procs;
	    ProcNode biggestRatio = _procs;

	    // Traverse the processes and find the one with the largest
	    // ratio of minimum possible run-time to share

	    do {

		if ( traverse._ratio > biggestRatio._ratio ) {
		    biggestRatio = traverse;
		}

		traverse = traverse.next;

	    } while ( _procs != traverse );

	    int runtime = biggestRatio._runTime;
	    int share = biggestRatio._share;

	    // Round the share length up to the next largest integer

	    while ( runtime % share != 0 ) {

		runtime++;

	    }

	    _shareLength = runtime / share;
	    return _shareLength;

	}

	// Performs calculations on the processes to prepare to determine the
	// share length
	private void prepProcs() {

	    ProcNode traverse = _procs;

	    do {

		traverse.calcRunTime(false);
		traverse.calcRatio(false);

		traverse = traverse.next;

	    } while ( _procs != traverse );

	}

	// Returns the permutation as a string of Process ID's
	public String toString() {

	    ProcNode traverse = _procs;
	    StringBuffer s = new StringBuffer( );
	    
	    do {

		s.append( traverse._id );
		traverse = traverse.next;
		if( _procs != traverse )
		    s.append( "-" );

	    } while ( _procs != traverse );

	    return s.toString( );

	}

	// Check if this permutation is the same as another
	public boolean equals( String s ) {

	    return s.equals( this.toString() );

	}

    }

    // A ProcNode represents one Process in a linked list.
    private class ProcNode {

	public int _id;
	public int _share;
	public int _ri;
	public int _ro;
	public int _runTime;  // minimum possible run-time for this Process
	public double _ratio; // ratio of run-time to share

	public ProcNode next;
	public ProcNode prev;

	// Constructor
	public ProcNode(int id, int share, int ri, int ro, ProcNode n, 
            ProcNode p) {

	    _id = id;
	    _share = share;
	    _ri = ri;
	    _ro = ro;
	    _runTime = -1;
	    _ratio = -1;

	    next = n;
	    prev = p;

	}

	// Constructor
	public ProcNode( Process pro, ProcNode n, ProcNode p ) {

	    _id = pro.getID();
	    _share = pro.getGoalShare();
	    _ri = pro.riTime();
	    _ro = pro.roTime();
	    _runTime = -1;
	    _ratio = -1;

	    next = n;
	    prev = p;

	}

	// Calculate minimum possible run time for this Process, based on
	// the time it takes the previous Process to roll out and the next
	// Process to roll in
	public int calcRunTime( boolean verbose ) {

	    if (verbose) {

		System.out.print("RT for " + _id + ": " +
				   prev._ro + " (" + prev._id + "'s RO) + " +
				   next._ri + " (" + next._id + "'s RI) = ");

	    }

	    _runTime = prev._ro + next._ri;
	    
	    if (verbose) {
		System.out.println(_runTime);
	    }

	    return _runTime;

	}

	// Calculate the ratio of this Process's run-time to its share
	// (run-time must be calculated first)
	public double calcRatio( boolean verbose ) {

	    assert( _runTime != -1 );

	    _ratio = (double)_runTime / (double)_share;

	    if (verbose) {
		System.out.println("RT/S for " + _id + ": " + _runTime + "/" +
				   _share + " = " + _ratio);
	    }

	    return _ratio;

	}

    }

}