/*
This file is part of the algoviz@vt collection of algorithm
visualizations.

This program is free software: you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation, either version 3
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this distribution. If not, see
<http://www.gnu.org/licenses/>.
*/

package bst;

import java.util.ArrayList;
import javax.swing.text.BadLocationException;
import javax.swing.text.DefaultStyledDocument;
import javax.swing.text.Style;
import javax.swing.text.StyleConstants;
import javax.swing.text.StyleContext;
import java.util.ArrayList;
import java.util.Collections;
import javax.swing.*;
import javax.swing.event.*;
import java.awt.*;
import java.awt.event.*;


/**
 * This is the main class behind the BST applet. It has a feedback panel, main
 * panel, and control panel. The main panel holds a <code>TreePanel</code>
 * which controls manipulation of the BST itself.
 * 
 * @see TreePanel
 * @author Andrew Whitaker (aawhitak@vt.edu)
 */
public class TreeApplet extends JApplet
{
	public static final int WIDTH = 2000;
	public static final int HEIGHT = 2000;
	
	/*
	 * Styles for feedback. INTERMEDIATE_STYLE = The style of an intermediate
	 * step in an operation. FINAL_STYLE = The style of the last step of an
	 * operation (could come in handy, not currently used). UNFOCUSED_STYLE =
	 * The style of an unfocused step thats displayed in feedback. For example,
	 * this style would be applied after a state is stepped over.
	 */
	public static Style INTERMEDIATE_STYLE, MAIN_STYLE, UNFOCUSED_STYLE,BLUE,GREEN,RED;
	private DefaultStyledDocument doc;
	private Container content;
	/* The main components of the TreeApplet. */
	private JPanel controlsPanel, feedbackPanel;
	/* Radio buttons the user will use to select an operation */
	private JRadioButton findRadioButton, deleteRadioButton, insertRadioButton;
	private JTextPane feedback;
	/* User-input text field */
	private JTextField insertTextField,startTextField;
	/*
	 * Not used, but could be used to display a message to the user in the
	 * controls panel
	 */
	private JLabel message;
	/* Control buttons */
	private JButton startButton, next, previous, first, last,resetButton,insertmany;
	/*
	 * Represents the current step number while iterating through a BST
	 * operation.
	 */
	private int stepNum;
	private int docPos;
	/* TreePanel holding/controlling the BST */
	public TreePanel treePanel;
        private static ArrayList<Integer> keylist=null;
private static ArrayList<Integer> actualList;
	private boolean goingForward = true;
	
	/**
	 * Creates a new TreeApplet. The applet has a BorderLayout with the
	 * TreePanel in the center, feedback to the right, and controls at the
	 * bottom.
	 */
	public TreeApplet()
	{
		super();
		/* Setup styles and other things necessary for feedback. */
		initializeFeedback();
		/* Set up applet */
		content = new Container();
                content.setPreferredSize(new Dimension(WIDTH,HEIGHT));
		content.setLayout(new BorderLayout());

		/* Controls */
		controlsPanel = new JPanel();
		controlsPanel.setLayout(new BoxLayout(controlsPanel, BoxLayout.X_AXIS));
		ButtonGroup modeGroup = new ButtonGroup();
		insertRadioButton = new JRadioButton("Insert");
		insertRadioButton.setBackground(Color.WHITE);
		insertRadioButton.addActionListener(new RadioButtonListener());
		findRadioButton = new JRadioButton("Find");
		findRadioButton.addActionListener(new RadioButtonListener());
		deleteRadioButton = new JRadioButton("Delete");
		deleteRadioButton.setBackground(Color.WHITE);
		deleteRadioButton.addActionListener(new RadioButtonListener());
		findRadioButton.setBackground(Color.WHITE);
		modeGroup.add(findRadioButton);
		modeGroup.add(deleteRadioButton);
		modeGroup.add(insertRadioButton);
		JPanel modePanel = new JPanel();
		modePanel.setLayout(new BoxLayout(modePanel, BoxLayout.Y_AXIS));
		modePanel.add(findRadioButton);
		modePanel.add(deleteRadioButton);
		modePanel.add(insertRadioButton);
		modePanel.setBackground(Color.WHITE);
		controlsPanel.add(modePanel);
		controlsPanel.setBackground(Color.WHITE);
		controlsPanel.setBorder(BorderFactory.createEtchedBorder());
		content.add(controlsPanel, BorderLayout.SOUTH);

		insertRadioButton.setSelected(true);
		
		/* Text field and buttons */
		JPanel inputPanel = new JPanel();
		JPanel stepsPanel = new JPanel(new FlowLayout());
		inputPanel.setLayout(new BoxLayout(inputPanel, BoxLayout.Y_AXIS));
		insertTextField = new JTextField(10);
		insertTextField.setRequestFocusEnabled(true);
		stepsPanel.add(insertTextField);
		startButton = new JButton("Start");
		//startButton.setEnabled(false);
		//insertTextField.setEnabled(false);
		stepsPanel.add(startButton);
		next = new JButton(">");
		previous = new JButton("<");
		first = new JButton("<<");
		last = new JButton(">>");
                resetButton=new JButton("RESET");
                insertmany=new JButton("Add");
		
		stepsPanel.add(first);
		stepsPanel.add(previous);
		stepsPanel.add(next);
		stepsPanel.add(last);
                stepsPanel.add(resetButton);
                JPanel inputGroup=new JPanel();
                inputGroup.setLayout(new GridLayout(2,1));
                inputGroup.add(stepsPanel);
		first.setEnabled(false);
		previous.setEnabled(false);
		next.setEnabled(false);
		last.setEnabled(false);
                startTextField=new JTextField();
                startTextField.setText("        ");
                JPanel startoff=new JPanel();
                startoff.setLayout(new FlowLayout());
                startoff.add(new JLabel("Add "));
                startoff.add(startTextField);
                startoff.add(new JLabel(" nodes into tree"));
                startoff.add(insertmany);
                inputGroup.add(startoff);
		JPanel messagePanel = new JPanel();
		message = new JLabel();
		message.setForeground(Color.RED);
		messagePanel.add(message);
		inputPanel.add(inputGroup);
		inputPanel.add(messagePanel);

		controlsPanel.add(inputPanel);
		/* Add Listeners */
		startButton.addActionListener(new ControlButtonListener());
                resetButton.addActionListener(new ControlButtonListener());
		next.addActionListener(new ControlButtonListener());
		previous.addActionListener(new ControlButtonListener());
		first.addActionListener(new ControlButtonListener());
		last.addActionListener(new ControlButtonListener());
                insertmany.addActionListener(new ControlButtonListener());

		/* End Controls */

		/* Feedback */
		feedbackPanel = new JPanel();
		feedbackPanel.setLayout(new BoxLayout(feedbackPanel, BoxLayout.Y_AXIS));
		JScrollPane scrollPanel = new JScrollPane(feedback);
		scrollPanel.setPreferredSize(new Dimension(200, 700));
		feedbackPanel.setBackground(Color.WHITE);
		JPanel labelPanel = new JPanel(new FlowLayout());
		labelPanel.add(new JLabel("Step History"));
		labelPanel.setBackground(Color.WHITE);
		feedbackPanel.add(labelPanel);
		feedbackPanel.add(scrollPanel);
		content.add(feedbackPanel, BorderLayout.EAST);
		setContentPane(content);
		/* End Feedback */

		/* Makes scrolling for large BST's possible */
		treePanel = new TreePanel(this);
                
		treePanel.setPreferredSize(new Dimension(WIDTH, HEIGHT));
		JScrollPane scroll = new JScrollPane(treePanel);
		// scroll.setPreferredSize(new Dimension(1200, 1200));
		content.add(scroll, BorderLayout.CENTER);


//                treePanel.insert(50);
//                treePanel.insert(30);
//                treePanel.insert(70);
//                treePanel.insert(15);
//                treePanel.insert(40);
//                treePanel.insert(60);
//                treePanel.insert(85);
//                treePanel.insert(10);
//                treePanel.insert(20);
//                treePanel.insert(35);
//                treePanel.insert(45);
//                treePanel.insert(55);
//                treePanel.insert(65);
//                treePanel.insert(80);
//                treePanel.insert(100);

	}

	/**
	 * Sets up styles and the Document that handles feedback. See the
	 * <code>Document</code> javadocs for more information on how Documents in
	 * Java work.
	 */
	private void initializeFeedback()
	{
		StyleContext sc = new StyleContext();
		doc = new DefaultStyledDocument(sc);
		docPos = 0;
		feedback = new JTextPane(doc);
		feedback.setEditable(false);

		INTERMEDIATE_STYLE = sc.addStyle("Intermediate", null);
		INTERMEDIATE_STYLE
		.addAttribute(StyleConstants.Foreground, Color.ORANGE);

		INTERMEDIATE_STYLE.addAttribute(StyleConstants.LeftIndent, 1.2);

                GREEN = sc.addStyle("Green", null);
		GREEN.addAttribute(StyleConstants.Foreground, Color.GREEN);
		GREEN.addAttribute(StyleConstants.LeftIndent, 1.2);

                BLUE = sc.addStyle("Green", null);
		BLUE.addAttribute(StyleConstants.Foreground, Color.BLUE);
		BLUE.addAttribute(StyleConstants.LeftIndent, 1.2);

                RED = sc.addStyle("Green", null);
		RED.addAttribute(StyleConstants.Foreground, Color.RED);
		RED.addAttribute(StyleConstants.LeftIndent, 1.2);

		MAIN_STYLE = sc.addStyle("Final", null);
		MAIN_STYLE.addAttribute(StyleConstants.Foreground, Color.BLUE);

		MAIN_STYLE.addAttribute(StyleConstants.LeftIndent, 1.2);

		UNFOCUSED_STYLE = sc.addStyle("Unfocused", null);
		UNFOCUSED_STYLE.addAttribute(StyleConstants.Foreground, Color.GRAY);

		UNFOCUSED_STYLE.addAttribute(StyleConstants.LeftIndent, 1.2);

	}

	/**
	 * Focuses a state in the current BST operation.
	 * 
	 * @see BasicState.java
	 * @param s The state to focus.
	 */
	public void focusState(State s, boolean goingForward)
	{
		String docText = new String(), text = s.getText();

		s.onStateFocused(treePanel, goingForward);
		
		try
		{
			docText = doc.getText(0, doc.getLength());
		}
		catch (BadLocationException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		String workingText = docText.substring(docPos);
		if (workingText.lastIndexOf(text) != -1)
		{
			doc.setCharacterAttributes(docText.lastIndexOf(text),
					text.length(), INTERMEDIATE_STYLE, true);
		}
		else
		{
			try
			{
				if(s.getText().contains("Node is")){
                                    if(s.getText().contains("GrandParent Node is")){
                                        doc.insertString(doc.getLength(), s.getText(),
						GREEN);
                                    }
                                    else if(s.getText().contains("Parent Node is")){
                                        doc.insertString(doc.getLength(), s.getText(),
						MAIN_STYLE);
                                    }
                                }
                                else if(s.getText().contains("Splaying Node")){
                                    doc.insertString(doc.getLength(), s.getText(),
						RED);
                                }
                                else{
                                    doc.insertString(doc.getLength(), s.getText(),
						INTERMEDIATE_STYLE);
                                }
			}
			catch (BadLocationException e1)
			{
				// TODO Auto-generated catch block
				e1.printStackTrace();
			}
		}
	}

	/**
	 * Unfocuses a state. Changes the color of the node and changes the selected
	 * text in the feedback area.
	 * 
	 * @see BasicState.java
	 * 
	 * @param s The State to focus
	 */
	public void unfocusState(State s)
	{
		s.onStateUnfocused(treePanel);
		
		String docText = new String(), text = s.getText();
		try
		{
			docText = doc.getText(0, doc.getLength());
		}
		catch (BadLocationException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
                if(!s.getText().contains("Parent Node is")&&!s.getText().contains("Splaying Node")){
                    doc.setCharacterAttributes(docText.lastIndexOf(text), text.length(),
				UNFOCUSED_STYLE, true);
                }
	}

	/**
	 * Listens to RadioButton clicks. This is only used when the application
	 * initially loads. At first, no radiobuttons are selected, but when the
	 * user selects one, the input text field should become visible, and so
	 * should the "Start" button.
	 * 
	 * @author Andrew Whitaker (aawhitak@vt.edu)
	 * 
	 */
	public class RadioButtonListener implements ActionListener
	{
		public void actionPerformed(ActionEvent e)
		{
			startButton.setEnabled(true);
			insertTextField.setEnabled(true);
		}

	}


	/**
	 * Internal class that handles control buttons (start, first, end, last,
	 * prev).
	 * 
	 * @author Andrew Whitaker (aawhitak@vt.edu)
	 *		   Andy Street 
	 */
	public class ControlButtonListener implements ActionListener
	{
		public void actionPerformed(ActionEvent e)
		{
			ArrayList<State> list = treePanel.getStateList();
			
			JButton src = (JButton) e.getSource();

                        if(src==resetButton){
                            System.out.println("ahel");
                            treePanel.clear();
                            try
                            {
                                    doc.remove(0, doc.getLength());
                            }
                            catch (BadLocationException ef)
                            {
                                    // TODO Auto-generated catch block
                                    ef.printStackTrace();
                            }
                        }
                        else if(src==insertmany){
                            if(startTextField.getText().trim().compareTo("")!=0){
                                generateRandomLists(1,100,Integer.parseInt(startTextField.getText().trim()));
                                for(int i=0;i<actualList.size();i++){
                                    treePanel.insert(actualList.get(i));
                                }
                                treePanel.paintComponent(treePanel.getGraphics());
                            }
                        }

                        
			/* Handle a start button click */
			if (src == startButton)
			{
				startButton.setEnabled(false);
				
				goingForward = true;
				
				if (insertTextField.getText().compareTo("")!=0)
				{
					ArrayList<State> l = treePanel.getStateList();
					if (l.size() > 0)
					{
						for (int n = 0; n < l.size(); n++)
						{
							unfocusState(l.get(n));
						}
					}
					Integer i = new Integer(insertTextField.getText());
					if (insertRadioButton.isSelected())
					{
						treePanel.insert(i);
						try
						{
							doc
							.insertString(doc.getLength(),
									"Operation: Insert " + i + "\n",
									MAIN_STYLE);
						}
						catch (BadLocationException e1)
						{
							// TODO Auto-generated catch block
							e1.printStackTrace();
						}
					}
					else if (findRadioButton.isSelected())
					{
						treePanel.find(i);
						try
						{
							doc.insertString(doc.getLength(),
									"Operation: Find " + i + "\n", MAIN_STYLE);
						}
						catch (BadLocationException e1)
						{
							// TODO Auto-generated catch block
							e1.printStackTrace();
						}
					}else if(deleteRadioButton.isSelected()){
						treePanel.delete(i);
						try
						{
							doc.insertString(doc.getLength(),
									"Operation: Delete " + i + "\n", MAIN_STYLE);
						}
						catch (BadLocationException e1)
						{
							// TODO Auto-generated catch block
							e1.printStackTrace();
						}
					}
					insertTextField.setText("");
					/* Reset the start number */
					stepNum = -1;
					docPos = doc.getLength();
					/* Set the buttons correctly */
					next.setEnabled(true);
					last.setEnabled(true);
					previous.setEnabled(false);
					first.setEnabled(false);
				}
			}
			/* Handle a next button click */
			else if (src == next)
			{
				
				if(!goingForward)
				{
					unfocusState(list.get(stepNum));
					focusState(list.get(stepNum), true);
					goingForward = true;

					previous.setEnabled(true);
					first.setEnabled(true);
					
					return;
				}
				
				stepNum++;
				previous.setEnabled(true);
				first.setEnabled(true);
				State s = list.get(stepNum);

                                if (stepNum > 0)
				{
                                    
					unfocusState(list.get(stepNum - 1));
				}

                                focusState(s, true);

				if (stepNum == list.size() - 1)
				{
					last.setEnabled(false);
					next.setEnabled(false);
					startButton.setEnabled(true);
				}


			}
			/* Handle a previous button click */
			else if (src == previous)
			{
				startButton.setEnabled(false);
				
				if(goingForward)
				{
					unfocusState(list.get(stepNum));
					
					next.setEnabled(true);
					last.setEnabled(true);
					
					focusState(list.get(stepNum), false);
					goingForward = false;
					
					return;
				}
				
				unfocusState(list.get(stepNum));
				stepNum--;
				if (stepNum == 0)
				{
					first.setEnabled(false);
					previous.setEnabled(false);
				}
				next.setEnabled(true);
				last.setEnabled(true);
				State s = list.get(stepNum);

				focusState(s, false);
			}
			/* Handles when the first ('<<') button is pressed */
			else if (src == first)
			{
				goingForward = true;
				
				stepNum = 0;
				State s = list.get(stepNum);
				s.draw(treePanel, true);
				
				enableButtons(true);
				first.setEnabled(false);
				previous.setEnabled(false);
				startButton.setEnabled(false);
			}
			else if (src == last)
			{
				// See "first" button action for details.
				stepNum = list.size() - 1;
				State s = list.get(stepNum);
				s.draw(treePanel, false);
				
				enableButtons(true);
				last.setEnabled(false);
				next.setEnabled(false);
				startButton.setEnabled(true);
			}
		}
	}
	
	public void enableButtons(boolean doIt)
	{
		last.setEnabled(doIt);
		next.setEnabled(doIt);
		previous.setEnabled(doIt);
		first.setEnabled(doIt);
		
		if (stepNum == 0)
		{
			first.setEnabled(false);
			previous.setEnabled(false);
		}
		
		if (stepNum == treePanel.getStateList().size() - 1 && goingForward)
		{
			last.setEnabled(false);
			next.setEnabled(false);
		}
	}

        public static int binarySearch(ArrayList list, int listLength, int searchItem) {
    int first=0;
    int last = listLength - 1;
    int mid=-1;
    boolean found = false;
    //Loop until found or end of list.
    while(first <= last &&!found) {
        //Find the middle.
        mid = (first + last) /2;
        //Compare the middle item to the search item.
        if(list.get(mid).equals((Integer)searchItem))
                found = true;
        else { //Not found, readjust search parameters, halving the size & start over.
            if((Integer)list.get(mid)>searchItem)
                last = mid -1;
            else
                first = mid + 1;
        }
    }
    return found?mid:-1;
}

public void generateRandomLists(int start, int end,int count){
        
        keylist=new ArrayList<Integer>((int)count);
        actualList=new ArrayList<Integer>();
        int tempRandom=start+(int) (Math.random()*100);
        int tempcount=0;
        while(tempcount<count){
                Collections.sort(keylist);
                int found=binarySearch(keylist,tempcount,tempRandom);
                if(found==-1){
                        keylist.add(tempcount, tempRandom);
                        actualList.add(tempcount,tempRandom);
                        tempcount++;

                }
                tempRandom=start+(int) (Math.random()*count);
        }
        System.out.println("Random lists generated");

}
}