import java.io.*;

class TwoHeapScheduler extends HeuristicScheduler {

    public TwoHeapScheduler( Process[] processes, int availMem ) {

	super( processes, availMem );
	_active = new Heap( true );
	_passive = new Heap( false );
	_currentActive = 0;
	_activeCount = 0;
	_currentMem = 0;
	_activeIndex = new Process[1];

    }

    public void runAndReport() {

	runProcs( true, null, -1 );

    }

    public void runAndReport( int time ) {

	runProcs( true, null, time );

    }

    public void finalReport() {

        System.out.println("Final report not yet implemented.");

    }

    public void run() {

	runProcs( false, null, -1 );
	
    }

    public void run( int time ) {

	runProcs( false, null, time );

    }

    public void run( String name ) throws IOException {

	runProcs( false, name, -1 );

    }

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

    protected void runProcs( boolean verbose,
			     String filename,
			     int time ) {

	boolean files = false;
	PrintStream cpuOut = null, shareOut = null, integralOut = null;

	if ( time != -1 ) {
	    System.out.println("Partial runs not yet implemented.");
	    System.exit(0);
	}

	if ( filename != null ) {

	    files = true;

	    // Create names for the files to be generated
	    
	    String cpuName, shareName, integralName;
	    StringBuffer buffer = new StringBuffer();
	    
	    buffer.append( "../data/" ).append( filename )
		.append( "-" ).append( getType() ).append( "cpu.dat" );
	    cpuName = buffer.toString();
	    
	    buffer = buffer.delete( cpuName.lastIndexOf("c"),buffer.length() );
	    buffer.append( "share.dat" );
	    shareName = buffer.toString();

	    buffer = buffer.delete( shareName.lastIndexOf("s"),
				    buffer.length() );
	    buffer.append( "integral.dat" );
	    integralName = buffer.toString();
	    
	    // Create PrintStreams to output to the three files
	    
	    try {

		cpuOut = 
		    new PrintStream (
		      new BufferedOutputStream (
			new FileOutputStream ( cpuName )));
		
		shareOut = 
		    new PrintStream (
		      new BufferedOutputStream (
			new FileOutputStream ( shareName )));
		
		integralOut =
		    new PrintStream (
		      new BufferedOutputStream (
			new FileOutputStream ( integralName )));	
		
	    }
	    catch( IOException e ){
		System.out.println("Error: problem opening file.");
		System.exit(1);
	    }
	    
	}
    
	// Select the first set of active processes: keep rolling in processes
	// until no more will fit, and add each to the activeIndex and
	// the active heap.

	for( int loop = 0; loop < _pCount; loop++ ) {

	    if( _processes[loop].getWorkingSet() + _currentMem <= _availMem ) {

		roll( true, _processes[loop], verbose, files, cpuOut, shareOut,
		      integralOut );

		addActive( _processes[loop], verbose );

	    }
	    
	}
	
	if( verbose ) {
	    System.out.println("Active heap initialized.");
	}

	// Add the rest of the processes to the passive heap.

	for( int loop = 0; loop < _pCount; loop++ ){

	    if( _processes[loop]._active == false ){

		_passive.insert( _processes[loop] );

	    }

	}

	if( verbose ) {

	    System.out.println("Passive heap initialized.");
	    System.out.println("Beginning run.");

	}
	
	// Run through the processes over and over, giving quanta to the active
	// ones, and constantly swapping the top processes of the two heaps
	
	while( !finished( ) ) {

	    if( verbose ){

		printActive();
		printPassive();

	    }

	    // Take the top process from the passive heap.

	    Process newProc = getPassive();

	    // Remove processes from the top of the active heap, roll them out,
	    // and  add them to the passive heap until there's room for
	    // the new process.

	    while( _currentMem + newProc.getWorkingSet() > _availMem ) {

		// If the current active process has a smaller ratio of actual
		// share to desired share than the new process, stop rolling in
		// and out and give the active processes quanta until it has a
		// larger ratio

		Process oldProc = getActive();

		boolean pause = false;

		if( oldProc.lessThan( newProc ) && verbose ) {
		    
		    System.out.println( oldProc + " < " + newProc +
					" - pausing RIRO until ratios even out."
					);
		    pause = true;

		}
		
		while( oldProc.lessThan( newProc ) ) {

		    giveQuanta( verbose );

		}

		if( pause && verbose ) {
		    System.out.println("Ratios evened.  Continuing run.");
		}
		
		remActive( oldProc, verbose );

		roll( false, oldProc, verbose, files, cpuOut, shareOut,
		      integralOut );

	    }

	    // Roll in the new process and add it to the active heap.

	    roll( true, newProc, verbose, files, cpuOut, shareOut,
		  integralOut );

	    addActive( newProc, verbose );

	    // Check if any other passive processes can be fit into the active
	    // heap; if so, roll them in and add them

	    Process[] passives = new Process[_passive.size()];
	    int passiveCount = 0;

	    while( _passive.size() > 0 ){

		Process filler = getPassive();

		if( filler.getWorkingSet() + _currentMem <= _availMem ) {
		    
		    roll( true, filler, verbose, files, cpuOut, shareOut,
			  integralOut );
		    
		    addActive( filler, verbose );

		}
		else {
		    passives[ passiveCount ] = filler;
		    passiveCount++;
		}

	    }

	    // Take all the passive processes that didn't fit and put them back
	    // in the passive heap

	    for( int loop = 0; loop < passiveCount; loop++ ){
		_passive.insert( passives[ loop ] );
	    }
	    
	}
	
	if( files ) {
	    
	    // Add the total run and idle times to the bottom of the share file
	    shareOut.println( _clock );
	    shareOut.println( _idleTime );

	    cpuOut.close();
	    shareOut.close();
	    integralOut.close();
    
	}

    }


    // Rolls in or out the given process
    protected void roll( boolean in, Process p, boolean verbose, boolean files,
			 PrintStream cpuOut, PrintStream shareOut,
			 PrintStream integralOut ){
	
	if( verbose ){
	    System.out.print("Rolling ");
	    if( in ) System.out.print("in ");
	    else System.out.print("out ");
	    System.out.println("Process " + p.getID());
	}

	int time;
	if( in ) time = p.riTime();
	else time = p.roTime();

	for( int loop = 0; loop < time; loop++ ){
	    
	    if( in ) p.rollIn();
	    else p.rollOut();

	    _clock++;
	    
	    giveQuanta( verbose );
	    
	    if( files ) {

		try {

		    cpusToFile( cpuOut );
		    sharesToFile( shareOut, integralOut );

		}
		catch( IOException e ){
		    
		    System.out.println("Error: problem writing to files.");
		    System.exit(1);

		}

	    }
	    
	}
	
    }

    // Gives one quanta to the current active process
    protected void giveQuanta( boolean verbose ){

	if( _activeCount > 0 ) {

	    if( _activeIndex[ _currentActive ]._active == false ) {
		System.out.println("---Error!  Trying to give quanta to a "
				   + " passive process!--------------"
				   + "----------" );
	    }

	    _activeIndex[ _currentActive ].giveQuanta();
	    _activeIndex[ _currentActive ]._counter++;

	    _cpuCount++;

	    if( verbose ){
		System.out.println("Process " + 
				   _activeIndex[_currentActive].getID() +
				   " ran for one quanta. Counter: " + 
				   _activeIndex[_currentActive]._counter );
	    }
	    
	    // Update the current process's actual share 
	    // using exponential averaging
	    _activeIndex[ _currentActive ].updateShare( true );

	    // Update all the other processes' actual shares
	    // using exponential averaging
	    for( int loop = 0; loop < _pCount; loop++ ){

		if( _processes[loop] != _activeIndex[_currentActive] ) {

		    _processes[loop].updateShare( false );

		}

	    }

	    // If the current active process has received its share of quanta,
	    // advance _currentActive to the next active process
	    
	    if( _activeIndex[ _currentActive ]._counter >= 
		_activeIndex[ _currentActive ].getShare() ) {

		_activeIndex[ _currentActive ]._counter = 0;

		if( _currentActive < _activeCount - 1 ){		
		    _currentActive++;		
		}
		else {
		    _currentActive = 0;
		}

	    }

	    
	}
	else {
	    if( verbose ){
		System.out.println("CPU sat idle one quanta.");
	    }

	    _idleTime++;
	}
	
    }

    // Returns the top Process from the active heap
    protected Process getActive() {

	_active.resort();

	if( _active.size() > 0 )
	    return (Process)_active.remove();

	return null;

    }

    // Returns the top Process from the passive heap
    protected Process getPassive() {

	_passive.resort();
	
	if( _passive.size() > 0 )
	    return (Process)_passive.remove();

	return null;

    }

    // Makes a Process active
    protected void addActive( Process p, boolean verbose ) {

	p._active = true;

	_active.insert( p );

	_currentMem += p.getWorkingSet();

	_activeCount++;

	// Resizes _activeIndex, if necessary
	if( _activeCount >= _activeIndex.length ) {

	    Process[] newIndex = new Process[ _activeIndex.length * 2 ];
	    for( int loop = 0; loop < _activeCount - 1; loop++ ) {
		
		newIndex[ loop ] = _activeIndex[ loop ];

	    }

	    _activeIndex = newIndex;

	}

	_activeIndex[ _activeCount - 1 ] = p;

	if( verbose ) {
	    System.out.println( "Process " + p.getID() + " moved to the " +
				"active heap.");
	    System.out.println( "ActiveCount = " + _activeCount );
	}

    }

    // Makes a Process passive
    protected void remActive( Process p, boolean verbose ) {

	p._active = false;

	_passive.insert( p );

	_currentMem -= p.getWorkingSet();

	_activeCount--;

	// Remove p from _activeIndex and push all the processes following it
	// to the left
	
	int pLoc = 0;
	
	while( _activeIndex[ pLoc ] != p ) {
	    pLoc++;
	}

	for( int loop = pLoc; loop < _activeCount; loop++ ) {

	    _activeIndex[ loop ] = _activeIndex[ loop + 1 ];

	}

	// If the current active process is now outside of the active index,
	// make the first active process the current active process

      	if( _currentActive >= _activeCount ) {

	    _currentActive = 0;

	} 

	if( verbose ) {
	    System.out.println( "Process " + p.getID() + " moved to the " +
				"passive heap.");
	}


    }

    // Prints all the processes in the active heap
    public void printActive() {

	System.out.println("Active heap: " + _active);

    }

    // Prints all the processes in the passive heap
    public void printPassive() {

	System.out.println("Passive heap: " + _passive);

    }
    
    protected Heap _active;
    protected Heap _passive;
    protected int _currentActive;
    protected int _currentMem;
    protected int _activeCount;
    protected Process[] _activeIndex;

}