/*
 * Sorting.java by Burton Rosenberg
 * 24 September 1996 (c) all rights reserved
 *
*/

import java.awt.* ;
import java.applet.Applet ;

public class Sorting extends Applet implements Runnable {

    Panel controls = new Panel() ;
    Button shakeButton = new Button("Shake"),
           stepButton = new Button("Step"),
           sortButton = new Button("Selection Sort") ;

    final int N = 20 ;
    final int P = 23 ;
    final int M = 7 ;

    static final int SWAPPING = 1 ;
    static final int SWAPPED = 2 ;

    int [] table = new int[N] ;
    int [] status = new int[N] ;
    SortingView sortingView = new SortingView(table,status) ;
   
    public void init() {
        //controls.add( shakeButton ) ;
        //controls.add( stepButton ) ;
        controls.add( sortButton ) ;
        setLayout( new BorderLayout() ) ;
        add( "North", controls ) ;
        add( "Center", sortingView ) ;
        initialize( table, status ) ;
        validate() ;
        
    }
 
    void initialize( int [] table, int [] status ) {
	for ( int i = 0 ; i < table.length; i++ ) 
	{
	   table[i] = (int)(Math.random()*((double)table.length)) ;
	   status[i] = 0 ;
	}
        nextIndexToSort = 0 ;
    }
   
    public boolean action (Event e, Object a ) {

        if ( e.target==shakeButton ) {
            if ( runThread != null ) return true ;
            initialize( table, status ) ;
            sortingView.repaint() ;     
            return true ;
        }
        if ( e.target==stepButton ) {
            if ( runThread != null ) return true ;        
            sortOneStep( table, status ) ;
            sortingView.repaint() ;
            return true ;
        }
        if ( e.target==sortButton ) {
            if ( runThread == null ) {
               runThread = new Thread(this) ;
               initialize( table,status ) ;
               runThread.start() ;
            }
            return true ;
        }
        return false ;
    }
 
    int nextIndexToSort ;

    boolean sortOneStep( int [] table, int [] status ) {
        int i ;

        // get min in nextIndexToSort .. table.length-1
        if ( nextIndexToSort >= table.length ) return false ;

        boolean willSwap = false ;
        int swap1, swap2 ;
        swap1 = swap2 = -1 ;

        for ( i = 0; i <table.length; i++ )
        {
           if ( status[i]==SWAPPING ) {
              willSwap = true ;
              swap1 = swap2 ;
              swap2 = i ;
           }
           if ( status[i]==SWAPPED ) status[i] = 0 ;
        }

        if ( willSwap ) {
           if ( swap1<0 ) swap1 = swap2 ;
           int t = table[swap1] ;
           table[swap1] = table[swap2] ;
           table[swap2] = t ;
           status[swap1] = SWAPPED ;
           status[swap2] = SWAPPED ;
        }
        else
        {
	    int j = nextIndexToSort ;
	    for ( int k=j+1 ; k<table.length; k++ ) 
	       if ( table[k]<table[j] ) j = k ;
            status[j] = SWAPPING ;
            status[nextIndexToSort] = SWAPPING ;
	    nextIndexToSort++ ;
        }
        return true ;
    }

    Thread runThread ;

    public void run() {
        
        while ( sortOneStep( table, status ) ) { 
	    sortingView.repaint() ;
            try {
	       runThread.sleep(300) ;
	    } catch ( InterruptedException e ) { 
            }
        }
        runThread = null ;
    }
    
}

class SortingView extends Panel {
    int [] table ;
    int [] status ;
    int BOX ;
    final Color BOXCOLOR = Color.blue ;

    SortingView( int [] table, int [] status ) {
       this.table = table ;
       this.status = status ;
    }

    public void paint( Graphics gc ) {

        Dimension d = size() ;        
        int wOff = d.width/8 ;
        int hOff = d.height/8 ;
        gc.setColor( Color.black ) ;
        gc.drawRect( wOff, hOff, (3*d.width)/4, (3*d.height)/4 ) ;

        int max = table[0] ;
        int i ;
        for ( i=0; i<table.length; i++) if ( table[i]>max ) max=table[i] ;
        max++ ;

        int w = (3*d.width)/(4*table.length) ;
        int h = (3*d.height)/(4*max) ;
        BOX = w ;
        if ( h<BOX ) BOX = h ;

        for ( i=0; i< table.length; i++ ) {
           gc.setColor( Color.blue ) ; 
           if ( status[i] == Sorting.SWAPPING ) gc.setColor( Color.red ) ;
           if ( status[i] == Sorting.SWAPPED ) gc.setColor( Color.green ) ; 
           gc.fillRect( i*w+wOff, (7*hOff)-table[i]*h, BOX, BOX ) ;
        }

    }

}