import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;

class E3Solns {
  public static void main( String [] args ) {
    System.out.println();
    Q5();
    System.out.println();
    Q6();
    System.out.println();
    Q7();
    System.out.println();
    Q8();
    System.out.println();
    Q9();
    System.out.println();
    Q10();
    System.out.println();
    Q11();
    System.out.println();
  }
  
  // Test Q5
  public static void Q5() {
    System.out.println( "Testing Q5");
    System.out.println( "==========");
    System.out.println( "The stack has: \"me\", \"you\", \"min\", and \"max\"." );
    String [] test = new String[]{ "me", "you", "min", "max" };
    Stack list = new Stack();
    for ( int i = 0; i < test.length; ++i ) {
      list.push( test[i] );
    }
    E3Q5 q5 = new E3Q5();
    Comparable min = q5.minimum( list );
    System.out.println( "The min is \"" + (String)min + "\"!" );
  }
  
  // Test Q6
  public static void Q6() {
    System.out.println( "Testing Q6");
    System.out.println( "==========");
    E3Q6 q6 = new E3Q6();
    System.out.println();
  }

  // Test Q7
  public static void Q7() {
    System.out.println( "Testing Q7");
    System.out.println( "==========");
    Random rand = new Random();
    int size = rand.nextInt(19) + 2;
    Stack list = new Stack();
    E3Q7Q8 q7 = new E3Q7Q8();
    System.out.print( "The data are:" );
    for ( int i = 0; i < size; ++i ) {
      Integer val = new Integer( rand.nextInt(21) );
      System.out.print( " " + val );
      q7.insert( list, val );
    }
    System.out.println();
    System.out.print( "The sorted stack is:" );
    while ( !list.empty() ) {
      System.out.print( " " + list.pop() );
    }
    System.out.println();
  }

  // Test Q8
  public static void Q8() {
    System.out.println( "Testing Q8");
    System.out.println( "==========");
    Random rand = new Random();
    int size = rand.nextInt(19) + 2;
    Stack list = new Stack();
    E3Q7Q8 q8 = new E3Q7Q8();
    System.out.print( "The data in the unsorted stack are:" );
    for ( int i = 0; i < size; ++i ) {
      Integer val = new Integer( rand.nextInt(21) );
      System.out.print( " " + val );
      list.push( val );
    }
    System.out.println();
    list = q8.insertionSort( list );
    System.out.print( "The sorted stack is:" );
    while ( !list.empty() ) {
      System.out.print( " " + list.pop() );
    }
    System.out.println();
  }

  // Test Q9
  public static void Q9() {
    System.out.println( "Testing Q9");
    System.out.println( "==========");
    Random rand = new Random();
    //int size = rand.nextInt(19) + 2;
    int size = 16;
    int [] test = new int[size];
    System.out.print( "The unsorted array is: " );
    for ( int i = 0; i < size; ++i ) {
      test[i] = rand.nextInt(21);
      System.out.print( " " + test[i] );
    }
    System.out.println();
    E3Q9 q9 = new E3Q9();
    q9.mergeSort( test );
    System.out.print( "The sorted array is: " );
    for ( int i = 0; i < size; ++i ) {
      System.out.print( " " + test[i] );
    }
  }
  
  // Test Q10
  public static void Q10() {
    System.out.println( "Testing Q10");
    System.out.println( "===========");
    E3Q10 q10 = new E3Q10();
    System.out.println();
  }

  // Test Q11
  public static void Q11() {
    System.out.println( "Testing Q11");
    System.out.println( "===========");
    E3Q11 q11 = new E3Q11();
    System.out.println();
  }
}



/**
 * Q5. [14 pts] Create the method public Comparable minimum(Stack list).  
 * The method will find and return the minimum comparable element on the 
 * stack given.  After the method completes, the stack will be unchanged, 
 * each element (including the minimum) having been left in its original 
 * position on the stack.  Recall you have the methods empty, pop, and 
 * push available form the class Stack.
 */
class E3Q5 {
  public Comparable minimum(Stack list) {
    if ( list.empty() ) return null;
    Stack temp = new Stack();
    Comparable min = (Comparable)list.pop();
    temp.push( min );
    while ( !list.empty() ) {
      Comparable obj = (Comparable)list.pop();
      if ( min.compareTo( obj ) > 0 ) min = obj;
      temp.push( obj );
    }
    while ( !temp.empty() ) {
      list.push( temp.pop() );
    }
    return min;
  }
}



/**
 * Q6. [16 pts] Create a GUI that will display to the user a field for 
 * receiving data, a button, and another component of your choice to display 
 * a response to the user.  Place the data entered onto a stack.  Then call 
 * the method implemented in the previous question, displaying to the user 
 * the toString value of the minimum object found on the stack.
 */
class E3Q6 extends JFrame implements ActionListener {
  public E3Q5 met = new E3Q5();
  public Stack data = new Stack();
  JTextField input;
  JButton    btn;
  JTextField output;
  public E3Q6() {
    input  = new JTextField(40);
    btn    = new JButton( "Enter" );
    output = new JTextField(40);
    getContentPane().setLayout( new FlowLayout() );
    getContentPane().add( input );
    getContentPane().add( btn );
    getContentPane().add( output );
    btn.addActionListener( this );
    setTitle( "Q6" );
    pack();
    setVisible( true );
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }
  
  public void actionPerformed( ActionEvent e ) {
    String str = input.getText();
    if ( str != null ) data.push( str );
    output.setText( (String)met.minimum( data ) );
  }
}



/**
 * Q7. [12 pts] Create the method public void insert(Stack list, Comparable 
 * element).  The method will receive a comparable element and place it 
 * within its sorted position within the stack.  The stack passed to the 
 * method is already sorted into ascending order from top to bottom.
 */
/**
 * Q8. [12 pts] Create a solution to the method insertionSort.  
 * Using the insertion sort algorithm, sort a stack of comparable 
 * elements passed to the method.  Return the sorted stack.
 */
class E3Q7Q8 {
  
  // Q7
  public void insert(Stack list, Comparable element) {
    if ( list.empty() ) {
      list.push(element);
      return;
    }
    Stack temp = new Stack();
    while ( !list.empty() ) {
      Comparable obj = (Comparable)list.pop();
      if ( obj.compareTo( element ) < 0 ) {
        list.push( obj );
        list.push( element );
        break;
      }
      else if ( list.empty() ) {
        temp.push(obj);
        list.push( element );
        break;
      }
      else {
        temp.push(obj);
      }
    }
    while ( !temp.empty() ) {
      list.push( temp.pop() );
    }
  }

  // Q8
  public Stack insertionSort(Stack list) {
    Stack stack = new Stack();
    while( !list.empty() ) {
      insert( stack, (Comparable)list.pop() );
    }
    return stack;
  }
  
}



/**
 * Q9. [12 pts] Create a solution to the method mergeSort.  Using the merge 
 * sort algorithm, sort an int array passed to the method.  For your 
 * assistance, you are given the method to merge two arrays:
 * merge(int a[], int b[], int left, int middle, int right) 
 * and the method to copy a subset of one array into another array: 
 * copy(int a[], int b[], int left, int right).
 */
class E3Q9 {
  public void mergeSort( int [] array ) {
    int [] sorted = new int[array.length];
    for (int i = 1; i < array.length; i *= 2) {
      for(int j = 0; j < array.length; j = j + (2 * i)) {
        merge(array, sorted, j, (j + (i - 1)), (j + ((2 * i) - 1)));
      }
      copy( sorted, array, 0, array.length );
    }
  }
    
  public void merge(int unSorted[], int sorted[], int left, int middle, int right) {
    int start1 = left;
    int end1   = middle;
    int end2   = right;
    int start2 = end1 + 1, result = start1;

    while ((start1 <= end1) && (start2 <= end2)) {
      if (unSorted[start1] <= unSorted[start2]) {
        sorted[result] = unSorted[start1];
        result++;
        start1++;
      }
      else {
        sorted[result] = unSorted[start2];
        result++;
        start2++;
      }
    }

    if (start1 <= end1) {
      for(; start1 <= end1; start1++, result++) {
        sorted[result] = unSorted[start1];
      }
    }
    else {
      for(; start2 <= end2; start2++, result++) {
        sorted[result] = unSorted[start2];
      }
    }
  }
  
  public void copy(int[] source, int[] dest, int left, int right) {
    for ( int i = left; i < right; ++i ) {
      dest[i] = source[i];
    }
  }
}



/**
 * Q10. [14 pts] Create a GUI that displays a 3 by 3 grid of buttons and 
 * two labels.  The grid represents a tic-tac-toe board.  The labels 
 * represent the current number of wins for two players of the game.  
 * Display the board in a mid game state, where an even number of the 
 * buttons display Os and Xs.  Do not include any game or interactive 
 * functionality, just the displayed state.
 */
class E3Q10 extends JFrame {
  public E3Q10() {
    // Scores
    JPanel scoreBoard = new JPanel();
    JLabel user1 = new JLabel("45");
    JLabel user2 = new JLabel("46");
    scoreBoard.setLayout( new FlowLayout() );
    scoreBoard.add( user1 );
    scoreBoard.add( user2 );
    
    // Board
    JPanel board = new JPanel();
    JButton [][] btn = new JButton[3][3];
    board.setLayout( new GridLayout(3,3) );
    for ( int i = 0; i < 3; ++i ) {
      for ( int j = 0; j < 3; ++j ) {
        btn[i][j] = new JButton();
        board.add( btn[i][j] );
      }
    }
    btn[0][0].setText( "O" );
    btn[0][1].setText( "X" );
    btn[1][1].setText( "O" );
    btn[2][2].setText( "X" );
    btn[1][0].setText( "O" );
    btn[1][2].setText( "X" );
    
    // Game board
    getContentPane().setLayout( new BorderLayout() );
    getContentPane().add( scoreBoard, BorderLayout.NORTH );
    getContentPane().add( board, BorderLayout.CENTER );
    setTitle( "Q10 -- Tic-Tac-Toe" );
    setSize( 400, 400 );
    setVisible( true );
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }
}



/**
 * Q11. [14 pts] Create a GUI that will display a list structure to the user 
 * (either a menu, drop down list, check box or radio button series).  
 * In the list, place the string values for the numbers one, two three, four 
 * and five.  When the user selects one of the values, respond by updating a 
 * counter on the display with the current summed value of all the selections 
 * made so far.
 */
class E3Q11 extends JFrame implements ActionListener {
  JComboBox  cb;
  JTextField result;
  int sum;
  public E3Q11() {
    sum = 0;
    result = new JTextField( 10 );
    result.setText( "0" );
    String[] counts = { "one", "two", "three", "four", "five" };
    cb = new JComboBox( counts );
    cb.addActionListener( this );
    getContentPane().setLayout( new FlowLayout() );
    getContentPane().add( cb );
    getContentPane().add( result );
    setTitle( "Q11" );
    pack();
    setVisible( true );
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }
  
  public void actionPerformed( ActionEvent e ) {
    sum += cb.getSelectedIndex() + 1;
    result.setText( "" + sum );
  }
}