sortitem.java

java sort

/*
 * @(#)SortItem.java	1.17f 95/04/10 James Gosling
 *
 * Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted. 
 * Please refer to the file http://java.sun.com/copy_trademarks.html
 * for further important copyright and trademark information and to
 * http://java.sun.com/licensing.html for further important licensing
 * information for the Java (tm) Technology.
 * 
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 * 
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */

import java.awt.*;
import java.io.InputStream;
import java.util.Hashtable;
import java.net.*;

/**
 * A simple applet class to demonstrate a sort algorithm.
 * You can specify a sorting algorithm using the "alg"
 * attribyte. When you click on the applet, a thread is
 * forked which animates the sorting algorithm.
 *
 * @author James Gosling
 * @version 	1.17f, 10 Apr 1995
 * @history Modified by Pat Morin on Feb. 7 1996.
 */
public class SortItem extends java.applet.Applet  {

    Choice choice;
    SortPanel sortPanel;

    /**
     * The default constructor, builds a new SortItem.
     */
    public SortItem() {
	BorderLayout b = new BorderLayout();
	setLayout(b);
	choice = new Choice();
	choice.addItem("BozoSort");
	choice.addItem("PermSort");
	choice.addItem("StoogeSort");
	choice.addItem("QMSort");
	choice.addItem("BubbleSort");
	choice.addItem("SelectionSort");
	choice.addItem("CocktailSort");
	choice.addItem("InsertionSort");
	choice.addItem("ShakerSort");
	choice.addItem("ShakerSortTwo");
	choice.addItem("ShellSort");
	choice.addItem("QSort");
	choice.addItem("HeapSort");
	choice.addItem("JSort");
	choice.addItem("JiSort");
	choice.addItem("MergeSort");

       	add("North", choice);
	add("South", sortPanel = new SortPanel());
	Dimension size = b.preferredLayoutSize(this);
	resize(size.width, size.height);
    }

    public boolean handleEvent(Event evt) {
       if (evt.target.equals(choice) && evt.id == Event.ACTION_EVENT) {
	    System.out.println(evt);
	    String alg = choice.getSelectedItem();
	    sortPanel.setAlgorithm(alg);
	    return true;
	}
	return super.handleEvent(evt);
   }

    /**
     * Initialize the applet.
     */
    public void init() {
	String at = getParameter("alg");
	if (at == null) {
	    at = "BubbleSort";
	}
	choice.select(at);
	sortPanel.setAlgorithm(at);
    }
}

class SortPanel extends Panel implements Runnable {
    /**
     * The thread that is sorting (or null).
     */
    private Thread kicker;

    /**
     * The array that is being sorted.
     */
    int arr[];

    /**
     * The high water mark.
     */
    int h1 = -1;

    /**
     * The low water mark.
     */
    int h2 = -1;

    /**
     * The first comparison element.
     */
    int c1 = -1;

    /**
     * The second comparison element.
     */
    int c2 = -1;

    /**
     * The name of the algorithm.
     */
    String algName;

    /**
     * The sorting algorithm (or null).
     */
    SortAlgorithm algorithm;
 

    /**
     * The default constructor
     */
    SortPanel() {
	setAlgorithm("BubbleSort");
	resize(125, 100);
    }

    public Dimension preferredSize() {
	return new Dimension(125, 100);
    }

    public Dimension minimumSize() {
	return new Dimension(125, 100);
    }

    /**
     * Set the sorting algorithm to use, possibly killing the
     * currently running algorithm.
     */
    void setAlgorithm(String alg) {
	if(kicker != null) {
	    kicker.stop();
	    kicker = null;
	}
	algName = alg + "Algorithm";
	scramble();
	repaint();
    }
	
    /**
     * Fill the array with random numbers from 0..n-1.
     */
    void scramble() {
	int a[] = new int[size().height / 2];
	double f = 100 / (double) a.length;
	for (int i = a.length; --i >= 0;) {
	    a[i] = (int)(i * f);
	}
	for (int i = a.length; --i >= 0;) {
	    int j = (int)(i * Math.random());
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        arr = a;
    }

    /**
     * Pause a while.
     * @see SortAlgorithm
     */
    void pause() {
        pause(-1, -1);
    }

    /**
     * Pause a while, and draw the high water mark.
     * @see SortAlgorithm
     */
    void pause(int H1) {
        pause(H1, -1);
    }

    /**
     * Pause a while, and draw the low&high water marks.
     * @see SortAlgorithm
     */
    void pause(int H1, int H2) {
        h1 = H1;
        h2 = H2;
        if (kicker != null) {
            repaint();
        }
        try {Thread.sleep(20);} catch (InterruptedException e){}
    }

    /**
     * Change the position of the comparison exchange marker.
     * @see SortAlgorithm
     */
    void compex(int C1, int C2) {
        c1 = C1;
        c2 = C2;
        pause(h1, h2);
    }
    
    /**
     * Paint the array of numbers as a list
     * of horizontal lines of varying lenghts.
     */
    public void paint(Graphics g) {
        int a[] = arr;
        int y = size().height - 1;
	int xoff = 20;

        // Erase old lines
        g.setColor(Color.lightGray);
        for (int i = a.length; --i >= 0; y -= 2) {
            g.drawLine(xoff+arr[i], y, size().width, y);
            g.drawLine(0, y, 19, y);
        }
        g.drawLine(4, 0, 4, size().height);

        // Draw new lines
        g.setColor(Color.black);
        y = size().height - 1;
        for (int i = a.length; --i >= 0; y -= 2) {
            g.drawLine(xoff, y, xoff+arr[i], y);
            if(i == c1 || i == c2) {
	g.drawLine(4, y, 17, y);
            }
        }

        if(c1 >= 0 && c2 >= 0) {
            g.setColor(Color.black);
            int y1 = c1 * 2 + 1;
            int y2 = c2 * 2 + 1;
            g.drawLine(4, y1, 4, y2);
        }

//        if (h1 >= 0) {
//            g.setColor(Color.red);
//            y = h1 * 2 + 1;
//            g.drawLine(xoff, y, size().width, y);
//        }
//        if (h2 >= 0) {
//            g.setColor(Color.blue);
//            y = h2 * 2 + 1;
//            g.drawLine(xoff, y, size().width, y);
//        }
    }

    /**
     * Update without erasing the background.
     */
    public void update(Graphics g) {
        paint(g);
    }

    /**
     * Run the sorting algorithm. This method is
     * called by class Thread once the sorting algorithm
     * is started.
     * @see java.lang.Thread#run
     * @see SortItem#mouseUp
     */
    public void run() {
        try {
	    algorithm = (SortAlgorithm)
		Class.forName(algName).newInstance();
	    algorithm.setParent(this);
	    algorithm.init();
            algorithm.sort(arr);
        } catch(Exception e) {
        }
    }

    /**
     * Stop the applet. Kill any sorting algorithm that
     * is still sorting.
     */
    public synchronized void stop() {
        if (kicker != null) {
            try {
		kicker.stop();
            } catch (IllegalThreadStateException e) {
		// ignore this exception
            }
            kicker = null;
        }
        if (algorithm != null){
            try {
		algorithm.stop();
            } catch (IllegalThreadStateException e) {
		// ignore this exception
            }
        }
    }


    /**
     * For a Thread to actually do the sorting. This routine makes
     * sure we do not simultaneously start several sorts if the user
     * repeatedly clicks on the sort item.    It needs to be
     * synchronoized with the stop() method because they both
     * manipulate the common kicker variable.
     */
    private synchronized void startSort() {
        if (kicker == null || !kicker.isAlive()) {
            scramble();
            repaint();
            kicker = new Thread(this);
            kicker.start();
        }
    }


    /**
     * The user clicked in the applet. Start the clock!
     */
    public boolean mouseUp(java.awt.Event evt, int x, int y) {
        startSort();
        return true;
    }
}