/*
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
.
*/
package splayTree;
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 TreePanel
* 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 keylist=null;
private static ArrayList 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
* Document
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 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 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((int)count);
actualList=new ArrayList();
int tempRandom=start+(int) (Math.random()*100);
int tempcount=0;
while(tempcount