// Tod Semple
// shear.java
//

import java.awt.*;
import java.applet.*;
import java.io.*;
import java.net.*;
import java.lang.*;

class shearSort
{
	public int array[][];
    int N;

    shearSort(int N_arg)
    {
        N=N_arg;

 		int x,y;

		array = new int[N][N];

		for (x=0;x<N;x++)
			for (y=0;y<N;y++)
				array[x][y] = 0;
    }

    public void start()
    {
 		int x,y;
		for (x=0;x<N;x++)
			for (y=0;y<N;y++)
                array[x][y] = (int)(Math.random() * 100);
        done=false;
    }

    public boolean done;

    public void next()
    {
        done=true;

        // sort rows

        int line[] = new int[N];
 		int x,y;
		for (y=0;y<N;y++)
        {
            if (y%2==0)
            {
                // forwards sort row
                for (x=0;x<N;x++) line[x] = array[x][y];
                sort(line);
                for (x=0;x<N;x++) array[x][y] = line[x];
            }
            else
            {
                // backwards sort row
                for (x=0;x<N;x++) line[N-x-1] = array[x][y];
                sort(line);
                for (x=0;x<N;x++) array[x][y]=line[N-x-1];
            }
        }

        // sort columns

        for (x=0;x<N;x++)
        {
            for (y=0;y<N;y++) line[y] = array[x][y];
            sort(line);
            for (y=0;y<N;y++) array[x][y]=line[y];
        }
    }

    void sort(int line[])
    {
        // sorta bubble sort the array

        for (int j=0;j<line.length-1;j++)
            for (int i=0;i<line.length-1-j;i++)
                if (line[i]>line[i+1])
                    swap(line,i,i+1);
    }

    void swap(int line[], int a,int b)
    {
        done=false;
        int temp;
        temp = line[a];
        line[a] = line[b];
        line[b] = temp;
    }
}

class shearSortCanvas extends Canvas
{
    shearSort theSorter;

    shearSortCanvas(shearSort shearSort_arg)
    {
        theSorter = shearSort_arg;
    }

    public void paint(Graphics g)
    {
        // Clear the canvas
        g.setColor(Color.white);
		g.fillRect(0,0,size().width,size().height);

        int x,y;

        int xSpacing = size().width/(theSorter.N+1);
        int ySpacing = size().height/(theSorter.N+1);

        // draw the zig zag

        g.setColor(Color.red);
		for (y=0;y<theSorter.N;y++)
        {
            g.drawLine(xSpacing+5, (int)((y+.7)*ySpacing), 
                    xSpacing*theSorter.N+5, (int)((y+.7)*ySpacing));

            if (y==theSorter.N-1)
                continue;

            if (y%2==1)
            {
                g.drawLine(xSpacing+5, (int)((y+.7)*ySpacing), 
                           xSpacing+5, (int)((y+1.7)*ySpacing));
            }
            else
            {
                g.drawLine(xSpacing*theSorter.N+5, (int)((y+.7)*ySpacing), 
                           xSpacing*theSorter.N+5, (int)((y+1.7)*ySpacing));
            }
        }
        
        // draw the numbers in the array

        g.setFont(new java.awt.Font("", Font.BOLD, 14));
        g.setColor(Color.black);
		for (x=0;x<theSorter.N;x++)
			for (y=0;y<theSorter.N;y++)
    	        g.drawString("" + theSorter.array[x][y],
                             (x+1)*xSpacing,(y+1)*ySpacing);

        if (theSorter.done)
        {
            g.drawString("Already Sorted!!!!",
                     size().width/2-50,size().height-5);
        }
    }
}

public class shear extends java.applet.Applet implements Runnable 
{
    final int N = 8;
    shearSort theSorter;

    String stringStart = "Start Again";
    String stringNext = "Next Iteration";

    shearSortCanvas sortCanvas;

    public void init() 
    {
        theSorter = new shearSort(N);
	    resize(300,300);

        setLayout(new BorderLayout(10,10));
        add("North",new Button(stringStart));
        sortCanvas = new shearSortCanvas(theSorter);
        add("Center",sortCanvas);
        add("South",new Button(stringNext));

        theSorter.start();
        repaint();
    }

    public Insets insets() 
    {
        return new Insets(10,10,10,10);
    }

    public void paint(Graphics g)
    {
        sortCanvas.repaint();
    }

    public void update(Graphics g) 
	{
	    g.clearRect(0, 0, size().width, size().height);
        paintAll(g);
    }

    public boolean action(Event evt, Object arg)
    {
        // catch button presses

        if (evt.target instanceof Button)
        {
            if (((String)arg).equals(stringNext))
            {
                theSorter.next();
                repaint();
            }
            else if (((String)arg).equals(stringStart))
            {
                theSorter.start();
                repaint();
            }
        }

        return true;
    }

    public void start() 
	{
		requestFocus();
    }

    public String getAppletInfo() 
	{
       return "_____Shear Sort____\n" +
              "___by Tod Semple___\n" +
              "_(tsemple@hmc.edu)_\n" +
              "_____3/26/95_______\n";
    }

    public void run() {}
}