/******************************************************************************
Compare the following sort algorithms
   n**2    -- selection, bubble, insert
   n log n -- quicksort, heapsort, mergesort

Can select initial order as: ascending, descending, random.
Can select array sizes: 5, 10, 15, 20, 25 and 30.  Longer sizes take
excessively long for the n**2 sorts.

----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;

import java.awt.*;
import java.awt.event.*;
import FlexOr.container.*;
import FlexOr.utility.*;

@SuppressWarnings("serial")
public class SortComparison extends Frame {
  boolean compareAll = true;
  
  int arrayLength = 20;
  Integer[] array1 = new Integer[arrayLength];                                    
  Integer[] array2 = new Integer[arrayLength];
  Integer[] array3 = new Integer[arrayLength];
  Integer[] array4 = new Integer[arrayLength];
  Integer[] array5 = new Integer[arrayLength];
  Integer[] array6 = new Integer[arrayLength];
  Integer[] mergeSpace = new Integer[arrayLength];
  
  ButtonAdapter startBtn;
  ButtonAdapter startStepBtn;
  
  protected Choice sizeChoice = new Choice();

                                        
  protected Panel westPanel = new Panel(new GridLayout(0,1,0,10));
  protected Panel centerPanel = new Panel(new GridLayout(2,3));
  
  protected SelectionObs selectionObs =
                     new SelectionObs(array1, new IntegerLessThan());
  protected SortObserver selectionObserver =
                     new SortObserver(array1, selectionObs, "Selection");
                     
  protected BubbleObs bubbleObs =
                     new BubbleObs(array2, new IntegerLessThan());
  protected SortObserver bubbleObserver =
                     new SortObserver(array2, bubbleObs, "Bubble");
                     
  protected InsertObs insertObs =
                     new InsertObs(array3, new IntegerLessThan());
  protected SortObserver insertObserver =
                     new SortObserver(array3, insertObs, "Insert");
                     
  protected QuicksortObs quicksortObs =
                     new QuicksortObs(array4, new IntegerLessThan());
  protected SortObserver quicksortObserver =
                     new SortObserver(array4, quicksortObs, "Quick");
                     
  protected HeapsortObs heapsortObs =
                     new HeapsortObs(array5, new IntegerLessThan());
  protected SortObserver heapsortObserver =
                     new SortObserver(array5, heapsortObs, "Heap");
                     
  protected MergeObs mergeObs =
                     new MergeObs(array6, mergeSpace, new IntegerLessThan());
  protected MergeObserver mergeObserver =
                      new MergeObserver(array6, mergeSpace, mergeObs, "Merge");
         
  public SortComparison() {
    compareAll = true;
    setLayout(new BorderLayout());
    setFont(new Font("Helvetica", Font.PLAIN, 12));
    centerPanel.add(selectionObserver);
    centerPanel.add(bubbleObserver);
    centerPanel.add(insertObserver);
    centerPanel.add(quicksortObserver);
    centerPanel.add(heapsortObserver);
    centerPanel.add(mergeObserver);
    add("Center", centerPanel);
    
    startBtn = new ButtonAdapter("Start") {
      public void pressed(){ startAll(); }};
    startBtn.setEnabled(false);
    westPanel.add(startBtn);

    startStepBtn = new ButtonAdapter("Init Step") {
      public void pressed(){ startSingleStepAll(); }};
    startStepBtn.setEnabled(false);
    westPanel.add(startStepBtn);

    westPanel.add( new ButtonAdapter("Step") {
      public void pressed(){ stepAll();
    }});
    
    westPanel.add(new ButtonAdapter("InitAsc") {
      public void pressed(){
        initAsc(); repaintAll();
        startBtn.setEnabled(true);
        startStepBtn.setEnabled(true);
    }});
        
    westPanel.add(new ButtonAdapter("InitDesc") {
      public void pressed(){
        initDesc(); repaintAll();
        startBtn.setEnabled(true);
        startStepBtn.setEnabled(true);
    }});
        
    westPanel.add(new ButtonAdapter("InitRandom") {
      public void pressed(){
        initRandom(); repaintAll();
        startBtn.setEnabled(true);
        startStepBtn.setEnabled(true);
    }});
        
    sizeChoice.setBackground(Color.white);
    sizeChoice.addItem("5");
    sizeChoice.addItem("10");
    sizeChoice.addItem("15");
    sizeChoice.addItem("20");
    sizeChoice.addItem("25");
    sizeChoice.addItem("30");

    sizeChoice.select(3);
    westPanel.add(sizeChoice);
    
    add("West", westPanel);
    
    Label l1 = new Label("#s = number of swaps");
      l1.setBackground(Color.cyan);
    Label l2 = new Label("#c = number of comparisons");
      l2.setBackground(Color.magenta);
    Label l3 = new Label("#t = swaps + comparisons");
      
    Panel southPanel = new Panel();
    southPanel.add(l1); southPanel.add(l2); southPanel.add(l3);
    
    add("South", southPanel);
    
    addWindowListener(new WindowAdapter() {
      public void windowClosing(WindowEvent e) { dispose(); }
    });
  }

  private void initAsc() {
    arrayLength = Integer.parseInt(sizeChoice.getSelectedItem());
    array1 = new Integer[arrayLength];
    
    if (!compareAll) {
      int yshift = Math.min(450/arrayLength, 40);
      int height =  Math.min(450/arrayLength-2, 32);
      int scale = 295/arrayLength;
      int sleepTime = arrayLength > 25 ? 100 : 400;
    
      heapsortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      quicksortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      mergeObserver.change(yshift, height, scale, arrayLength, sleepTime);
    }
    
    for (int i = 0 ; i < arrayLength ; i++) {
      array1[i] = new Integer(i + 1);
    }
    makeCopies();
  }
  
  private void initDesc() {
    arrayLength = Integer.parseInt(sizeChoice.getSelectedItem());
    array1 = new Integer[arrayLength];
    
    if (!compareAll) {
      int yshift = Math.min(450/arrayLength, 40);
      int height =  Math.min(450/arrayLength-2, 32);
      int scale = 295/arrayLength;
      int sleepTime = arrayLength > 25 ? 100 : 400;
    
      heapsortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      quicksortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      mergeObserver.change(yshift, height, scale, arrayLength, sleepTime);
    }
    
    for (int i = 0 ; i < arrayLength ; i++) {
      array1[i] = new Integer(arrayLength - i);
    }
    makeCopies();
  }
    
  private void initRandom() {
    Integer tmp;
    int i, j;
    arrayLength = Integer.parseInt(sizeChoice.getSelectedItem());
    array1 = new Integer[arrayLength];
    
    if (!compareAll) {
      int yshift = Math.min(450/arrayLength, 40);
      int height =  Math.min(450/arrayLength-2, 32);
      int scale = 295/arrayLength;
      int sleepTime = arrayLength > 25 ? 100 : 400;
    
      heapsortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      quicksortObserver.change(yshift, height, scale, arrayLength, sleepTime);
      mergeObserver.change(yshift, height, scale, arrayLength, sleepTime);
    }

    for (i = 0 ; i < arrayLength ; i++) {
      array1[i] = new Integer(i + 1);
    }
    for (i = arrayLength-1 ; i > 0 ; i--) {
      j = rand(0, i);
      tmp = array1[i]; array1[i] = array1[j]; array1[j] = tmp;
    }
    makeCopies();
  }
  
  private int rand(int lower, int upper) {
    return (int)(Math.floor(Math.random()*upper + lower));
  }
  
  private void makeCopies() {
    array2 = new Integer[arrayLength];
    System.arraycopy(array1, 0, array2, 0, arrayLength);
    array3 = new Integer[arrayLength];
    System.arraycopy(array1, 0, array3, 0, arrayLength);
    array4 = new Integer[arrayLength];
    System.arraycopy(array1, 0, array4, 0, arrayLength);
    array5 = new Integer[arrayLength];
    System.arraycopy(array1, 0, array5, 0, arrayLength);
    array6 = new Integer[arrayLength];
    System.arraycopy(array1, 0, array6, 0, arrayLength);
    mergeSpace = new Integer[arrayLength];
    
    selectionObs.sortArray = selectionObserver.array = array1;
    bubbleObs.sortArray = bubbleObserver.array = array2;
    insertObs.sortArray = insertObserver.array = array3;
    quicksortObs.sortArray = quicksortObserver.array = array4;
    heapsortObs.sortArray = heapsortObserver.array = array5;
    mergeObs.sortArray = mergeObserver.array = array6;
    mergeObs.mergeSpace = mergeObserver.mergeSpace = mergeSpace;
      for (int i = 0 ; i < arrayLength ; i++) {
        mergeSpace[i] = new Integer(1);
      }
  }
  
  private void startAll() {
    selectionObserver.start(); selectionObs.start();
    bubbleObserver.start();  bubbleObs.start();
    insertObserver.start(); insertObs.start();
    quicksortObserver.start(); quicksortObs.start();
    heapsortObserver.start(); heapsortObs.start();
    mergeObserver.start(); mergeObs.start();
  }
  
  private void startSingleStepAll() {
    selectionObserver.startSingleStep(); selectionObs.start();
    bubbleObserver.startSingleStep();  bubbleObs.start();
    insertObserver.startSingleStep(); insertObs.start();
    quicksortObserver.startSingleStep(); quicksortObs.start();
    heapsortObserver.startSingleStep(); heapsortObs.start();
    mergeObserver.startSingleStep(); mergeObs.start();
  }
  
  private void stepAll() {
    selectionObserver.step();
    bubbleObserver.step();
    insertObserver.step();
    quicksortObserver.step();
    heapsortObserver.step();
    mergeObserver.step();
  }
  
  private void repaintAll() {
    selectionObserver.newArray();
    bubbleObserver.newArray();
    insertObserver.newArray();
    quicksortObserver.newArray();
    heapsortObserver.newArray();
    mergeObserver.newArray();
  }

}