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

/**
 * This program demonstrates stack and queue operations.  The program shows
 * a grid of squares.  When the user clicks on one of the squares, a computation
 * is begun that visits all the squares of the grid.   As the squares
 * are "encountered", they are colored red.  Red squares have been encountered
 * but not yet processed.  A square is processed by adding its horizontal
 * and vertical neighbors to the set of encountered squares, if they have
 * not previously been encountered.  Once a square has been processed in
 * this way, it is "finished", and it is colored gray.  At the end of the
 * process, all the squares are gray.
 *    The question is, how does the program decide which red square to
 * process?  There can be many red squares waiting for processing.
 * The user can specify one of three methods for deciding which square
 * to process:  with a stack, with a queue, or at random.  If the random
 * method is chosen, then a red square is chosen for processing at random
 * from among all the red squares.  If a queue is used, the red squares
 * are stored on a queue and are processed in FIFO order.  If a stack
 * is used, then the squares are processed in LIFO order.
 *    (Note:  If the user clicks on a white square while a computation is
 * already running, then that square will be "encountered" and added to
 * the set of red squares.)
 *    This class contains a main() routine that allows it to be run as a
 * standalone application.
 */
public class DepthBreadth extends JPanel implements MouseListener, ActionListener {


    /**
     * main() routine just opens a window with a DepthBreadth panel
     * as its content pane.
     */
    public static void main(String[] args) {
        JFrame window = new JFrame("Stack and Queue Demo");
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.setContentPane( new DepthBreadth(334,380) );
        window.pack();
        window.setResizable(false);
        window.setLocation(150,100);
        window.setVisible(true);
    }


    /**
     * Represents one square in the grid, by specifying the
     * row number and column number where it is found.
     */
    private static class Location {
        // 
        int row;
        int column;
        Location(int r, int c) {
                // Constructor, specifying the row and column of a square.
            row = r;
            column = c;
        }
    }  // end nested class Location


    /**
     * Represents a node in a linked list of Locations.  Both the
     * Stack and the Queue class use this type of linked list.
     */
    private static class Node {
        Location loc;  // Represents one square in the grid.
        Node next;     // Pointer to next Node in the linked list.
    }  // end nested class Node


    /**
     * A stack of Locations, with the standard operations,
     * plus a getSize() method that returns the number of 
     * Locations on the stack.
     */
    private static class Stack {
        private Node top = null;  // Pointer to the top of the stack.
        private int size = 0;     // Number of items on the stack.
        void push(Location loc) {
                // Add the specified location to the top of the stack.
            Node newTop = new Node();
            newTop.loc = loc;
            newTop.next = top;
            top = newTop;
            size++;
        }
        Location pop() {
                // Remove and return the top Location on the stack.
                // (Note that this can throw a NullPointerException if
                // it is called when the stack is empty.)
            Location topItem = top.loc;
            top = top.next;
            size--;
            return topItem;
        }
        boolean isEmpty() {
            // Return true if the stack is empty.
            return top == null;
        }
        int getSize() {
            // Return the number of Locations on the stack. 
            return size;
        }
    }  // end nested class Stack


    /**
     * A queue of Locations, with the standard operations,
     * plus a getSize() method that returns the number of 
     * Locations on the queue.
     */
    private static class Queue {
        private Node head = null;  // Points to first Node in the queue.
        private Node tail = null;  // Points to last Node in the queue.
        private int size;   // Number of items on the queue.
        void enqueue(Location loc) {
                // Add the specified Location to the end of the queue.
            Node newTail = new Node();
            newTail.loc = loc;
            if (head == null) {
                head = newTail;
                tail = newTail;
            }
            else {
                tail.next = newTail;
                tail = newTail;
            }
            size++;
        }
        Location dequeue() {
                // Remove and return the first item in the queue.
                // (Note that this will throw a NullPointerException
                // if the queue is empty.)
            Location firstItem = head.loc;
            head = head.next;
            if (head == null)
                tail = null;
            size--;
            return firstItem;
        }
        boolean isEmpty() {
            // Return true if the queue is empty.
            return head == null;
        }
        int getSize() {
            // Return the number of items on the queue.
            return size;
        }
    }  // end nested class Queue




    private final static int SQUARE_SIZE = 12;  // Size of one square in the grid.

    private int rows;     // Number of rows in the grid.  This depends on the size of the panel.
    private int columns;  // Number of columns in the grid.  This depends on the size of the panel.

    private boolean[][] encountered;  // encountered[r][c] is set to true when a square is
                                      //   first encountered.  (See comment at top of file.)
                                      //   A square that has been encountered but not
                                      //   finished is red.

    private boolean[][] finished;   // finished[r][c] is set to true when a square is
                                    //   finished (i.e. processed).  Finished squares are gray.

    private JButton abortButton;  // User can click this to terminate the computation.

    private JLabel message;   // For displaying information to the user.

    private JComboBox<String> methodChoice; // For selecting the method of 
                                            //   selecting which red square to process.

    private final static int STACK = 0,     // Possible values for the method.
            QUEUE = 1,
            RANDOM = 2;

    private int method; // Used to hold the selected method while a
                        //    computation is running.

    private Timer timer;  // A timer that drives the computation.
                          // When no computation is in progress, timer is null.                          

    private Queue queue;                     // Exactly one of these is used to store the
    private Stack stack;                     //   red squares while the computation is running.
    private ArrayList<Location> randomList;  //   Which one is used depends on the method.


    /**
     * Construct the panel.
     * @param width the width of the panel
     * @param height the height of the panel.  The height and width must be passed
     * as parameters because they are needed to determine how many rows and columns 
     * are drawn.  The height and width also become the preferred size of the panel.
     */
    public DepthBreadth(int width, int height) {

        setLayout(null);
        setBackground(new Color(220,220,255));
        setPreferredSize(new Dimension(width,height));
        setBorder(BorderFactory.createMatteBorder(2,2,2,2,Color.BLUE));
        addMouseListener(this);

        /* Determine the number of rows and columns and create the
                  encountered and finished arrays. */

        rows = (height - 100) / SQUARE_SIZE;
        columns = (width - 20) / SQUARE_SIZE;

        encountered = new boolean[rows][columns];
        finished = new boolean[rows][columns];

        /* Create the components. */

        Font labelFont = new Font("SansSerif",Font.PLAIN,14);

        message = new JLabel("Click any square to begin.",JLabel.CENTER);
        message.setForeground(Color.blue);
        message.setFont(labelFont);

        methodChoice = new JComboBox<String>();
        methodChoice.addItem("Stack");
        methodChoice.addItem("Queue");
        methodChoice.addItem("Random");
        methodChoice.setBackground(Color.WHITE);

        abortButton = new JButton("Abort");
        abortButton.setEnabled(false);
        abortButton.addActionListener(this);
        abortButton.setBackground(Color.LIGHT_GRAY);

        JLabel lb = new JLabel("Use:", JLabel.RIGHT);  // An unchanging informational label.
        lb.setForeground(Color.BLUE);
        lb.setFont(labelFont);

        /* Add the components to the panel and set their sizes and positions. */

        add(message);
        add(lb);
        add(methodChoice);
        add(abortButton);

        message.setBounds(15, height-80, width-30, 18);
        lb.setBounds(15, height-54, 50, 18);
        methodChoice.setBounds(75, height-56, width-150, 22);
        abortButton.setBounds(75, height-29, width-150, 22);

    } // end init();


    /**
     * The user has clicked the mouse on the panel.  If the user has clicked on 
     * a position in the grid, start a computation to start processing from that 
     * square, or if a computation is already running, "encounter" the square.
     */
    public void mousePressed(MouseEvent evt) {
        int row = (evt.getY() - 10) / SQUARE_SIZE;
        int col = (evt.getX() - 10) / SQUARE_SIZE;
        if (row < 0 || row >= rows || col < 0 || col >= columns)
            return;
        if (timer == null) {
                // Start a new computation at the point where the user clicked.
            startComputation(row,col);
        }
        else {
                // A computation is already in progress.
                // Mark the square where the user clicked as encountered.
            encounter(row,col);
            repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE);
        }
    } // end mousePressed()


    /**
     * When the user clicks the button, call doAbort().  Otherwise, this 
     * is a Timer event, so do the next step in the computation.
     */
    public void actionPerformed(ActionEvent evt) {
        if (evt.getSource() == abortButton)
            doAbort();
        else
            continueComputation();
    }


    /**
     * Begin a new computation.  Set all the squares back to unencountered 
     * and start a timer that will process the squares beginning with
     * the square at (startRow,startCol).
     */    
    void startComputation(int startRow, int startCol) {
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < columns; c++) {
                encountered[r][c] = false;
                finished[r][c] = false;  
            }
        method = methodChoice.getSelectedIndex();
        switch (method) {
        case STACK:
            stack = new Stack();
            message.setText("Using a stack.");
            break;
        case QUEUE:
            queue = new Queue();
            message.setText("Using a queue.");
            break;
        case RANDOM:
            randomList = new ArrayList<Location>();
            message.setText("Using a randomized list.");
            break;
        }
        abortButton.setEnabled(true);
        methodChoice.setEnabled(false);
        encounter(startRow,startCol);
        repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE);
        timer = new Timer(75,this);
        timer.start();
    }


    /**
     * Do one step in a computation, by processing
     * one location from the stack, queue, or arraylist.
     * If no more items are available, finish the computation.
     */
    public void continueComputation() {
        Location loc = removeItem();
        if (loc != null) {
            finish(loc.row, loc.column);
        }
        else {
                // All squares have already been "finished".  The
                // computation is complete.
            timer.stop();
            timer = null;
            methodChoice.setEnabled(true);
            abortButton.setEnabled(false);
            message.setText("Click any square to begin.");
            queue = null;
            stack = null;
            randomList = null;
        }
        repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE);
    }


    /**
     * Stop the computation, if one is running.  This is called
     * when the user clicks the Abort button.
     */
    void doAbort() {
        if (timer != null) {
            timer.stop();
            timer = null;
            methodChoice.setEnabled(true);
            abortButton.setEnabled(false);
            message.setText("Click any square to begin.");
            queue = null;
            stack = null;
            randomList = null;
        }
    }


    /**
     * Get the next item to be processed from the appropriate data structure.  
     * The data structure that is being used depends on the method.  If the data 
     * structure is empty, return null.  Also, display the size of the data 
     * structure to the user.
     */
    Location removeItem() {
        Location loc = null;
        switch (method) {
        case STACK:
            if ( ! stack.isEmpty() )
                loc = stack.pop();
            message.setText("Stack size is " + stack.getSize());
            break;
        case QUEUE:
            if ( ! queue.isEmpty() )
                loc = queue.dequeue();
            message.setText("Queue size is " + queue.getSize());
            break;
        case RANDOM:
            if ( randomList.size() > 0 ) {
                int index = (int)(randomList.size()*Math.random());
                loc = randomList.get(index);
                randomList.remove(index);
            }
            message.setText("List size is " + randomList.size());
            break;
        }
        return loc;
    }


    /**
     * If there is a square at (r,c) that has not already been encountered,
     * encounter it and add it to the data structure.  The data structure
     * that is used depends on the method.  Also, display the size of the 
     * data structure.
     */
    void encounter(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= columns || encountered[r][c] == true)
            return;
        Location loc = new Location(r,c);
        switch (method) {
        case STACK:
            stack.push(loc);
            message.setText("Stack size is " + stack.getSize());
            break;
        case QUEUE:
            queue.enqueue(loc);
            message.setText("Queue size is " + queue.getSize());
            break;
        case RANDOM:
            randomList.add(loc);
            message.setText("List size is " + randomList.size());
            break;
        }
        encountered[r][c]  = true;
    }


    /**
     * Process the red square at (r,c) by encountering its horizontal and 
     * vertical neighbors. 
     */
    void finish(int r, int c) {
        encounter(r-1,c);
        encounter(r+1,c);
        encounter(r,c-1);
        encounter(r,c+1);
        finished[r][c] = true;
    }


    public void mouseReleased(MouseEvent e) { }  // Methods required by MouseListener interface
    public void mouseClicked(MouseEvent e) { }
    public void mouseEntered(MouseEvent e) { }
    public void mouseExited(MouseEvent e) { }


    /**
     * Paint the grid of squares.  (Other components contained in the panel paint themselves.)
     */
    public void paintComponent(Graphics g) {

        super.paintComponent(g);   //Fill with background color

        /* Fill the area occupied by the grid with white, then draw
               black lines around this area and between the squares of
               the grid. */

        g.setColor(Color.white);
        g.fillRect(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE);

        g.setColor(Color.black);
        for (int i = 0; i <= rows; i++)
            g.drawLine(10, 10 + i*SQUARE_SIZE, columns*SQUARE_SIZE + 10, 10 + i*SQUARE_SIZE);
        for (int i = 0; i <= columns; i++)
            g.drawLine(10 + i*SQUARE_SIZE, 10, 10 + i*SQUARE_SIZE, rows*SQUARE_SIZE + 10);

        /* Fill "encountered" squares with red and "finished" squares with gray.
               Other squares remain white.  */

        for (int r = 0; r < rows; r++)
            for (int c = 0; c < columns; c++) {
                if (finished[r][c]) {
                    g.setColor(Color.gray);
                    g.fillRect(11 + c*SQUARE_SIZE, 11 + r*SQUARE_SIZE, SQUARE_SIZE - 1, SQUARE_SIZE - 1);
                }
                else if (encountered[r][c]) {
                    g.setColor(Color.red);
                    g.fillRect(11 + c*SQUARE_SIZE, 11 + r*SQUARE_SIZE, SQUARE_SIZE - 1, SQUARE_SIZE - 1);
                }
            }

    } // end paintComponent();



} // end class DepthBreadth
