// Visualization of sorting algorithms; JDK 1.1
// sestoft@dina.kvl.dk 1997-05-08, 1998-08-23

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

public class Visualsort extends Applet {
  public static void main(String[] args) {
    Visualsort vs = new Visualsort();
    SortFrame sf = new SortFrame();
    vs.initGUI(sf);
    sf.pack();
    sf.show();
  }

  public void init() 
  { initGUI(this); }

  private void initGUI(Container c) {
    final int size = 150;
    SortCanvas canvas = new SortCanvas(size);
    Sorter[] sorters = { new Selectionsort(canvas),
			 new Bubblesort(canvas),
			 new Quicksort(canvas),
			 new Heapsort(canvas)};
    SortControls controls = new SortControls(sorters);
    c.add(canvas);
    c.add(controls);
  }
}

class SortFrame extends Frame {

  public SortFrame() {
    super("Some sorting algorithms");
    setLayout(new FlowLayout());
    addWindowListener(new WindowAdapter() {
      public void windowClosing(WindowEvent e) {
	dispose(); System.exit(0);
      }
    });
  }
}

// A SortCanvas is created with a reference to an array of integers.
// It has three methods: (1) show two-sided comparison, (2) show
// one-sided comparison, (3) show element swap.  These are called with
// the index of the array which is affected by the operation.

// The idea is to show the comparisons by vertical blue lines through
// the elements being compared, and to show the swaps just by
// redrawing the pictures after the actual swap has been made in the
// arrays.
 
// Assumption: at any time the array contains a permutation of
// the set { 0, ..., arr.length-1 }

class SortCanvas extends Canvas {
  private final int unit = 2;
  private int size, compare1, compare2;
  private int[] arr;

  // For double buffering
  private Image buffer;
  private Graphics buffer_g;
 
  public SortCanvas(int size) {
    this.size = size;
    setSize(size*unit, size*unit);
    compare1 = compare2 = -1;
  }

  public void update(Graphics g) 
  { paint(g); }

  public void paint(Graphics g) { 
    if (buffer == null) {
      buffer = createImage(size*unit, size*unit);
      buffer_g = buffer.getGraphics();
    }
    buffer_g.setColor(Color.white);
    buffer_g.fillRect(0, 0, size*unit, size*unit);
    buffer_g.setColor(Color.black);
    if (arr != null) {
      for (int i = 0; i < size; i++)
	buffer_g.fillRect(i*unit, (size-1-arr[i])*unit, unit, unit);
      buffer_g.setColor(Color.blue.brighter());
      if (compare1 >= 0)
	buffer_g.fillRect(compare1*unit+(unit-1)/2, 0, 1, size*unit);
      if (compare2 >= 0)
	buffer_g.fillRect(compare2*unit+(unit-1)/2, 0, 1, size*unit);
    }
    compare1 = compare2 = -1;
    g.drawImage(buffer, 0, 0, this);
  }

  public void setArray(int[] arr) { 
    compare1 = compare2 = -1;
    this.arr = arr; 
  }

  public void showcompare1(int s) {
    compare1 = s;
    repaint();
  }

  public void showcompare2(int s, int t) {
    compare1 = s; 
    compare2 = t;
    repaint();
  }

  public int getCells() 
  { return size; }
}

class SortControls extends Panel {
  Button start = new Button("Start");
  Button pause = new Button("Continue");
  Choice algorithm = new Choice();
  Scrollbar speed = new Scrollbar(Scrollbar.HORIZONTAL);
  Sorter[] sorters;
  Sorter sorter;
  Thread animator;

  SortControls(Sorter[] sorters) {
    this.sorters = sorters;
    setLayout(new BorderLayout());
    add(speed, BorderLayout.CENTER);
    speed.setValues(50, 5, 0, 100);
    for (int i=0; i<sorters.length; i++)
      algorithm.addItem(sorters[i].getName());
    Panel bottom = new Panel();
    bottom.add(algorithm); bottom.add(pause); bottom.add(start); 
    add(bottom, BorderLayout.SOUTH);
    pause.addActionListener(new PauseListener());
    algorithm.addItemListener(new AlgorithmListener());
    start.addActionListener(new StartListener());
    speed.addAdjustmentListener(new SpeedListener());
  }

  // A change to the speed scrollbar calls the setDelay of the current sorter
  class SpeedListener implements AdjustmentListener {
    public void adjustmentValueChanged(AdjustmentEvent e) {
      setDelay();
    }
  }

  // When choosing a new algorithm, stop the old one and blank the canvas
  class AlgorithmListener implements ItemListener {
    public void itemStateChanged(ItemEvent e) {
      if (animator != null) {
	animator.stop();
	animator = null; 
	sorter.blank();
      }
    }
  }

  // To start an animation, stop the old one, then start the selected sorter
  class StartListener implements ActionListener {
    public void actionPerformed(ActionEvent e) {
      if (animator != null) 
	animator.stop();
      sorter = sorters[algorithm.getSelectedIndex()];
      animator = new Thread(sorter);
      animator.start();
      setDelay();
      pause.setLabel("Pause"); 
    }
  }

  // The pause button toggles between Pause and Continue
  class PauseListener implements ActionListener {
    public void actionPerformed(ActionEvent e) {
      if (animator != null)
	if (e.getActionCommand().equals("Pause")) {
	  pause.setLabel("Continue");
	  animator.suspend();
	} else {
	  pause.setLabel("Pause");
	  animator.resume();
	}
    }
  }

  void setDelay() {
    int pos = speed.getValue();
    sorter.setCompareDelay((int)(5 * Math.pow(1.5, 10-0.1*pos)));
  }
}

abstract class Sorter implements Runnable {
  private final int swapdelay = 8;	// in ms
  private int comparedelay;		// in ms

  SortCanvas canvas;

  public abstract void showsort(int[] arr, int n);

  public abstract String getName();

  void showswap(int[] arr, int s, int t) {
    int tmp = arr[s];  arr[s] = arr[t];  arr[t] = tmp;
    canvas.repaint();
    // try { Thread.sleep(swapdelay); } catch (InterruptedException e) {}; 
  }

  public void run() {
    int[] arr = randompermutation(canvas.getCells());
    canvas.setArray(arr);
    showsort(arr, canvas.getCells());
  }

  // Operations on the canvas

  public void blank() {
    canvas.setArray(null);
    canvas.repaint();
  }

  public void setCompareDelay(int delay) 
  { comparedelay = delay; }

  public void showcompare1(int s) {
    canvas.showcompare1(s);
    try { Thread.sleep(comparedelay); } catch (InterruptedException e) {}; 
  }

  public void showcompare2(int s, int t) {
    canvas.showcompare2(s, t);
    try { Thread.sleep(comparedelay); } catch (InterruptedException e) {}; 
  }

  // Generate a random permutation of the numbers 0..n-1

  private int[] randompermutation(int n) {
    int [] arr = new int[n];
    for (int i = 0; i < n; i++)
      arr[i] = i;
    for (int i = n; 0 < i; i--)
      swap(arr, i-1, (int) (Math.random() * i));
    return arr;
  }

  private void swap(int[] arr, int s, int t)
  { int tmp = arr[s];  arr[s] = arr[t];  arr[t] = tmp; }
}

class Selectionsort extends Sorter {

  public Selectionsort(SortCanvas canvas)
  { this.canvas = canvas; }

  public void showsort(int[] arr, int n) {
    for (int i = 0; i < n; i++) {                                         
      int least = i;                             
      for (int j = i+1; j < n; j++) { 	
	if (arr[j] < arr[least])		
	  least = j;			
	showcompare2(i, j);			
      }					
      showswap(arr, i, least);                    
    }                                         
  }

  public String getName() 
  { return "Selection sort"; }
}

class Bubblesort extends Sorter {

  public Bubblesort(SortCanvas canvas)
  { this.canvas = canvas; }

  public void showsort(int[] arr, int n) {
    for (int i = n-1; 0 < i; i--) {					
      for (int j = 0; j < i; j++) {			
	showcompare1(j+1);
	if (arr[j] > arr[j+1])	
	  showswap(arr, j, j+1);	
      }				
    }                                 
  }
  
  public String getName() 
  { return "Bubble sort"; }
}

class Quicksort extends Sorter {

  public Quicksort(SortCanvas canvas)
  { this.canvas = canvas; }

  private void qsort(int[] arr, int a, int b) {
    if (a < b) { 
      int i = a, j = b;
      int x = arr[(i+j) / 2];                 
      do {                                    
	while (arr[i] < x) { showcompare2(i,j); i++; }
	while (arr[j] > x) { showcompare2(i,j); j--; }
	if (i <= j) {					
	  showswap(arr, i, j);		
	  i++; j--;				
	}                                    
      } while (i <= j);                       
      qsort(arr, a, j);                       
      qsort(arr, i, b);                       
    }                                         
  }
  
  public void showsort(int[] arr, int n)
  { qsort(arr, 0, n-1); }

  public String getName() 
  { return "Quicksort"; }
}

class Heapsort extends Sorter {

  public Heapsort(SortCanvas canvas)
  { this.canvas = canvas; }
  
  private void heapify(int[] arr, int i, int k) {
    int j = 2 * i + 1;                          
    if (j <= k) { 
      if (j+1 <= k) { 
	showcompare2(j, j+1);
	if (arr[j] < arr[j+1]) 
	  j++;
      }                 
      if (arr[i] < arr[j]) {			
	showcompare2(i, j);		
	showswap(arr, i, j);                    
	heapify(arr, j, k);                 
      }           				
    }                                         
  }

  public void showsort(int[] arr, int n) {
    for (int m=n/2; m >= 0; m--) 
      heapify(arr, m, n-1);
                                                
    for (int m=n-1; m >= 1; m--) {                                         
      showswap(arr, 0, m);                        
      heapify(arr, 0, m-1);                   
    }                                         
  }

  public String getName() 
  { return "Heap sort"; }
}