/** 
 * SplayTreeApplet:
 * 
 * The applet demonstrates the Splay Tree. It takes textual commands in a TextArea 
 * and when the user clicks on the Execute button, it processes the commands, updating
 * the display as it goes.
 * 
 * @author Hyung-Joon Kim. CSE373, University of Washington.
 * 
 * Copyrights Note: 
 * This applet is extended from FullHuffmanApplet created by Prof. Steve Tanimoto, 
 * Department of Computer Science and Engineering, University of Washington.  
 * The setup of applet panels and the tree display methods are apprecicatively reused.
 *  
 */
 
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class SplayTreeApplet extends JApplet implements ActionListener, Runnable {
    
	ScrolledPanel visPanel; //Where to paint graphics
	MyScrollPane msp;
	Button executeButton; 
	Button historyButton;
	TextArea userInputText;
	TextArea history;
	JFrame historyFrame;
	JTextField statusLine;
	
	// The data structure to be demonstrated
	SplayTree theSplayTree;
				
	Font headingFont, treeFont;	
	int topMargin = 40;  // Space above top of the tree.	
	int leftMargin = 20; // x value for left side of array.
	int rightMargin = leftMargin;
	int yTreeTops = topMargin + 10;  // y coord of top of trees.
	int bottomMargin = 10;  // Minimum space betw. bot. of visPanel and bot. of lowest cell.
	int leftOffset = 5;  // space between left side of cell and contents string.
	int delay = 1500;  // default is to wait 1500 ms between updates.
	Thread displayThread = null;
	
	// For SplayTree display:
	int nodeHeight = 25;  // For drawing the nodes.
	int nodeWidth = 25;  // How wide to plot pink rectangles
	int nodeVGap = 10;  // vertical space between successive nodes
	int nodeHGap = 10;  // horizontal space between successive nodes
	int nodeHorizSpacing = nodeWidth + nodeHGap;
	int nodeVertSpacing = nodeHeight + nodeVGap;
	int interTreeGap = 15;  // horizontal space between trees.
	int ycentering = 3;
	Color treeColor = new Color(255,255,215);	
	static int m;  // variable used when computing columns for tree layouts.
	
	public void init() {
		setSize(700,500); // default size of applet.
		visPanel = new ScrolledPanel();
		visPanel.setPreferredSize(new Dimension(400,400));		
		msp = new MyScrollPane(visPanel);
		msp.setPreferredSize(new Dimension(400,200));
		
		Container c = getContentPane();
		c.setLayout(new BorderLayout());
		c.add(msp, BorderLayout.CENTER);		
		JPanel buttons = new JPanel();	
		buttons.setLayout(new FlowLayout());
		JPanel controls = new JPanel();
		controls.setLayout(new BorderLayout());		
		executeButton = new Button("Execute");
		executeButton.addActionListener(this);
		buttons.add(executeButton);
		historyButton = new Button("History");
		historyButton.addActionListener(this);
		buttons.add(historyButton);
		userInputText = new TextArea("\n");			
		statusLine = new JTextField();
		statusLine.setBackground(Color.lightGray);		
		controls.add(buttons, BorderLayout.WEST);
		controls.add(userInputText, BorderLayout.CENTER);
		controls.add(statusLine, BorderLayout.SOUTH);
		controls.setPreferredSize(new Dimension(400,100));
		c.add(controls, BorderLayout.SOUTH);
		c.validate();
		
		theSplayTree = new SplayTree();   // create an instance of the SplayTree
		
		headingFont = new Font("Helvetica", Font.PLAIN, 20);		
		treeFont = new Font("Arial", Font.BOLD, 13);
		history = new TextArea("SplayTreeApplet history:\n", 20, 40); 
	}

	class ScrolledPanel extends JPanel {
		public void paintComponent(Graphics g) {
			super.paintComponent(g);			
			paintTrees(g);
		}
	}
		
	class MyScrollPane extends JScrollPane {
		MyScrollPane(JPanel p) {
			super(p,
				JScrollPane.VERTICAL_SCROLLBAR_ALWAYS,
				JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
		}
	}
	
	public void actionPerformed(ActionEvent e) {
		if (e.getActionCommand().equals("Execute")) {
			displayThread = new Thread(this);
			displayThread.start();
			return;
		}

		if (e.getActionCommand().equals("History")) {
			if (historyFrame == null) { 
				historyFrame = new JFrame("History of the SplayTreeApplet");
				history.setFont(new Font("Courier", Font.PLAIN, 12));
				historyFrame.getContentPane().add(history);
				historyFrame.setSize(new Dimension(500,500));
			}
			historyFrame.show();
		}
	}
	
	// The following is executed by a separate thread for the display.
	public void run() {
		String commands = userInputText.getText();
		String line = "";
		StringTokenizer lines;
		for (lines = new StringTokenizer(commands, "\n\r\f");
				lines.hasMoreTokens();) {
			line = lines.nextToken();
			process(line, lines);
		}
		userInputText.setText(""); // Erase all the processed input.
	}
	
	// Helper function called by the run method above:
	void process(String command, StringTokenizer lines) {
		String arg1 = ""; String arg2 = "";
		StringTokenizer st = new StringTokenizer(command);
		if (! st.hasMoreTokens()) { return; }
		String firstToken = st.nextToken();
		if (firstToken.startsWith(";")) { return; }
		history.appendText(command + "\n");
		statusLine.setText(command);
		if (firstToken.equals("RESET")) { 
			theSplayTree = new SplayTree();				
			updateDisplay(); return;			
		}		
		if (firstToken.equals("DELAY")) { 
			if (st.hasMoreTokens()) { 
				arg1 = st.nextToken();
				try { delay =(new Integer(arg1)).intValue(); }
				catch(NumberFormatException e) {
					delay = 0;
				}
				statusLine.setText("delay = " + delay);
			}
			history.appendText("; delay is now " + delay + "\n");
			return;
		}
		if (firstToken.equals("INSERT")) { 
			arg1 = "UNDEFINED ELEMENT";			
			if (st.hasMoreTokens()) { arg1 = st.nextToken(); }
			int data = (new Integer(arg1)).intValue();			
			if (data < 1 || data > 99) {
				String msg = "Input NOT valid. Should be between 1-99 integer number.";
				report(msg);
				return;
			}			
			theSplayTree.insert(data);  // insert an element	
					
			checkScrolledPanelSize();
			updateDisplay();						
			if (theSplayTree.statMode) {				
				OldFamilySplayTree fam = theSplayTree.getRoot().oldFam;				
				if (fam != null) {
					double currentDepth = fam.getFamilyDepth() / (double)fam.numFam;
					String msg2 = "Current(improved) average depth of old family: " + currentDepth;
					report(msg2);					
				}				
			}	
			theSplayTree.getRoot().oldFam = null;  // reset the old family of the root
			return;			
		}
		if (firstToken.equals("FIND")) {
			arg1 = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) { arg1 = st.nextToken(); }
			int data = (new Integer(arg1)).intValue();
			String msg = "";
					
			// Check if data is already in the SplayTree and display the result.				 
			SplayTree node = theSplayTree.find(data);							
			if ( node == null) {
				msg = "NOT FOUND: " + data + " is NOT in the Splay Tree";	
			}
			else {
				msg = "FOUND: " + node.element + " is in the Splay Tree.";				
			}			
			report(msg);							
			checkScrolledPanelSize();
			updateDisplay();			
			if (theSplayTree.statMode) {				
				OldFamilySplayTree fam = theSplayTree.getRoot().oldFam;				
				if (fam != null) {
					double currentDepth = fam.getFamilyDepth() / (double)fam.numFam;
					String msg2 = "Current(improved) average depth of old family: " + currentDepth;
					report(msg2);					
				}							
			}			
			theSplayTree.getRoot().oldFam = null;  // reset the old family of the root						
			return;
		}
		if (firstToken.equals("DELETE")) { 
			arg1 = "UNDEFINED ELEMENT";			
			if (st.hasMoreTokens()) { arg1 = st.nextToken(); }
			int data = (new Integer(arg1)).intValue();			
			
			theSplayTree.delete(data);  // delete an element	
			
			checkScrolledPanelSize();
			updateDisplay();			
			if (theSplayTree.statMode) {				
				OldFamilySplayTree fam = theSplayTree.getRoot().oldFam;				
				if (fam != null) {
					double currentDepth = fam.getFamilyDepth() / (double)fam.numFam;
					String msg2 = "Current(improved) average depth of old family: " + currentDepth;
					report(msg2);					
				}			
			}	
			theSplayTree.getRoot().oldFam = null;  // reset the old family of the root
			return;			
		}
		if (firstToken.equals("FIND-MIN")) {			
			SplayTree node = theSplayTree.findMin(theSplayTree.getRoot());
			theSplayTree.splay(node); // after find min, splay at the node	
								
			checkScrolledPanelSize();
			updateDisplay();
			if (theSplayTree.statMode) {				
				OldFamilySplayTree fam = theSplayTree.getRoot().oldFam;				
				if (fam != null) {
					double currentDepth = fam.getFamilyDepth() / (double)fam.numFam;
					String msg2 = "Current(improved) average depth of old family: " + currentDepth;
					report(msg2);					
				}			
			}			
			theSplayTree.getRoot().oldFam = null;  // reset the old family of the root
			return;			
		}
		if (firstToken.equals("FIND-MAX")) { 
			SplayTree node = theSplayTree.findMax(theSplayTree.getRoot());
			theSplayTree.splay(node);  // after find max, splay at the node	
								
			checkScrolledPanelSize();
			updateDisplay();
			if (theSplayTree.statMode) {				
				OldFamilySplayTree fam = theSplayTree.getRoot().oldFam;				
				if (fam != null) {
					double currentDepth = fam.getFamilyDepth() / (double)fam.numFam;
					String msg2 = "Current(improved) average depth of old family: " + currentDepth;
					report(msg2);					
				}			
			}	
			theSplayTree.getRoot().oldFam = null;  // reset the old family of the root
			return;			
		}
		if (firstToken.equals("STAT-MODE")) {
			if(delay < 2000) { delay = 2000; }
			theSplayTree.statMode = true;
			updateDisplay();		
			return;			
		}													
		history.appendText("[Unknown Splay Tree command]\n");
		statusLine.setText("Unknown Spaly Tree command: " + command);		
	}	
	
	// Here is a "middleman" method that updates the display waiting with
	// the current time delay after each repaint request.
	void updateDisplay() {
		visPanel.repaint();		
		if (delay > 0) {
			try { 
				Thread.sleep(delay);
			}
			catch(InterruptedException e) {}
		}
	}
		
	int getInt(String s) {
		int n = 1;
		try {
			Integer I = new Integer(s);
			n = I.intValue();
		}
		catch(Exception e) { n = 1; }
		return n;
	}
	
	/* The following computes the height of the display area needed by the current
	 * heap, and if it won't fit in the scrolled panel, it enlarges the scrolled panel.
	 */
	void checkScrolledPanelSize() {
		// Compute width needed for trees:
		int treesWidthNeeded = leftMargin + rightMargin;
		int treesHeightNeeded = 0;
		Dimension d = visPanel.getPreferredSize();
		int currentHeight = (int) d.getHeight();
		int currentWidth = (int) d.getWidth();
		
		treesWidthNeeded += theSplayTree.getRoot().getDisplayWidth();		
		treesHeightNeeded += Math.max(treesHeightNeeded, theSplayTree.getDisplayHeight() + 2*topMargin);
				
		// Enlarge scrolled panel if necessary:
		int widthNeeded = treesWidthNeeded;
		int heightNeeded = treesHeightNeeded;
		if ((heightNeeded  > currentHeight) || (widthNeeded > currentWidth)) { 
				visPanel.setPreferredSize(new Dimension(
					Math.max(currentWidth,widthNeeded), 
					Math.max(currentHeight,heightNeeded)));
			visPanel.revalidate(); // Adjust the vertical scroll bar.
		}				
	}

	/**
	 * Splay Tree Class: 
	 * 
	 * This inner class is a data structure to be demostrated. Integer numbers are assigned
	 * to the data field of Splay Tree, and each node of Splay Tree has left child, right child,
	 * and parent. When a data is accessed by any operations such as FIND, INSERT, etc, Splay Tree
	 * performs a sequence of self-reconstructing processes, so called 'splay', in order to bring
	 * the most-recently-accessed node to the root of the tree. As a result, the nodes near the most-
	 * recently-accessed node become available for a fast accesss in futre.  
	 * 
	 * @author Hyung-Joon Kim, CSE373, University of Washington.
	 *  
	 */
	public class SplayTree {
		
		// data members for Splay trees :		
		SplayTree root, leftSubtree, rightSubtree, parentTree;
		int element = 0;  // comparable data member (valid between 1-99);
		
		OldFamilySplayTree oldFam;
		String splayStat = ""; // for stat report when splaying is performed
		int rotateCount = 0;
		boolean statMode = false;
		
		// The following are used in display layout:		
		int depth;    // relative y position of this node in the display
		int column;   // relative x position in display, in units of nodes
		int maxdepth; // height of tree whose root is this node.
		int xcenter;  // position of center of root relative to left side of tree.
		int ycenter;
		
		/** 
		 * Default Constructor:
		 */
		SplayTree() {  }  // do nothing
		
		/**
		 * Constructor: Create a singleton node with data assigned. 
		 * @param x  comparable data(integer number)
		 */
		SplayTree(int x) {
			element = x;
		}

	   /**
	    * Check if a tree node is external - that is, the node has no subtrees.
	    * @return  true if the node is external, false otherwise.
	    */
	   boolean isExternal() {
		   return ((leftSubtree == null) && (rightSubtree == null));
	   }
	   
	   /**
	    * Check if a node is the root of the Splay Tree.
	    * @return  true if the node is the root, false otherwise.
	    */
	   boolean isRoot() {
		   return (parentTree == null);
	   }
	   
	   /**
	    * Set a node to the new root of the Splay Tree.
	    * @param node  a tree node which would have been promoted the root of the Splay Tree.
	    */
	   void setRoot(SplayTree node) {  root = node; }
	   
	   /**
	    * Get the root of the Splay Tree.
	    * @return  the root of the Splay Tree.
	    */
	   SplayTree getRoot() {  return root; }
	   
	   /**
	    * Check if a node is the left children of its parent.
	    * @return  true if the node is the left child of its parent, false otherwise.
	    */
	   boolean isLeftSubtree() {
		   return ((parentTree != null) && (parentTree.leftSubtree == this));
	   }
	   
	   /**
	    * Check if a node is the right children of its parent.
		* @return  true if the node is the right child of its parent, false otherwise.
		*/
	   boolean isRightSubtree() {
		   return ((parentTree != null) && (parentTree.rightSubtree == this));
	   }

	   /**
		* Find the minimum-valued data of the Splay Tree.
		* @param T  the node that roots the Splay Tree(or any subtree of the Splay Tree).
		* @return a node whose data is the minimum value in the Splay Tree.
		*/
	   SplayTree findMin(SplayTree T) {
		   if (T == null) {
			   return null;
		   }
		   else if (T.leftSubtree == null) {
			   return T;  // T is the node whose element is the minimum value
		   }
		   return findMin(T.leftSubtree); // Recursively find in left subtrees
	   }
		
	   /**
		* Find the maximum-valued data of the Splay Tree.
		* @param T  the node that roots the Splay Tree(or any subtree of the Splay Tree).
		* @return a node whose data is the maximum value in the Splay Tree.
		*/
	   SplayTree findMax(SplayTree T) {
		   if (T == null) {
			   return null;
		   }
		   else if (T.rightSubtree == null) {
			   return T;  // T is the node whose element is the maximum value
		   }
		   return findMax(T.rightSubtree); // Recursively find in right subtrees
	   }   
	   
	  /**
	   * Find a data element in the Splay Tree. If found, the Splay Tree performs sequential
	   * self-reconstructing processes, so called splay, in order to bring the most-
	   * recently-accessed data up to the root of the tree. 
	   * @param element  comparable data to find in the Splay Tree.
	   * @return  the node, if found, at which splaying is performed. null if not found.
	   */
	  SplayTree find(int element) {
			SplayTree T = root;
			// Find the element until the Splay Tree has no more subtrees, using the
			// properties of a normal BST.
			while (T != null) {				
				if (T.element == element) {  // Found				
					break;
				} 
				else if (T.element > element) {			
					T = T.leftSubtree;
				}
				else {
					T = T.rightSubtree;
				}
			}
			if (T == null) {  // Not Found
				return null;
			}
			else {
				splay(T);  // Splaying at the found node
				return T;        	
			}
		}
		
		/**
		 * Insert a node into the Splay Tree. After insertion, the Splay Tree performs sequential
		 * self-reconstructing processes, so called splay, in order to bring the inserted node 
		 * up to the root of the tree. 
		 * @param element  comparable data which will be inserted into the Splay Tree.
		 */    
		void insert(int element) {
			// Create a singleton tree node with the element to insert.	
			SplayTree node = new SplayTree(element);
			
			// If the Splay Tree is empty, set the node to the root of the tree.
			if (root == null) {
				root = node;
				return;  // Done, no need to splay
			}			
			SplayTree parent = null;			
			SplayTree T = root;
			// Find appropriate location to insert the node, using the properties of a normal BST. 
			while (T != null) {
				parent = T;
				if (T.element == node.element) { // Element is already in the Splay Tree				
					break;
				}
				else if (T.element > node.element) {
					T = T.leftSubtree;
				}
				else {
					T = T.rightSubtree;
				}
			}			
			if (node.element == parent.element) {
				String msg = parent.element + " is already in the Splay Tree.";
				report(msg);					
				splay(parent);  // Splaying at the node
				return;
			}
			// Insert the node into the Splay Tree by attaching the node to an external node
			// which would have been found in the above loop. 
			if (parent.element > node.element) {				
				parent.leftSubtree = node;
				if (node != null) {
					node.parentTree = parent;
				}				
			} else {
				parent.rightSubtree = node;
				if (node != null) {
					node.parentTree = parent;					
				}				
			}			
			splay(node);  // After insertion, splaying at the node						    
		}
		
		/**
		 * This is a helper method for Delete method. It replaces a node with a new node so that
		 * the new node is connected to the parent of the previous node. Note that it should take
		 * care of the pointers of both direction (parent <-> child).
		 * @param T  a node to be replaced.
		 * @param newT  a node to replace T.
		 */
		void replace(SplayTree T, SplayTree newT) {
			if (T.isRoot()) {
				// Update the root of the Splay Tree
				root = newT;  
				if (newT != null) {
					newT.parentTree = null;
				}
			}
			else {
				if (T.isLeftSubtree()) {
					// Make newT be a new left child of the parent of the previous node, T 
					T.parentTree.leftSubtree = newT;
					if (newT != null) {
						// Make newT have the parent of the previous node as a new parent
						newT.parentTree = T.parentTree;
					}
				}					
				else {					
					T.parentTree.rightSubtree = newT;
					if (newT != null) {
						newT.parentTree = T.parentTree;				
					}					
				}
			}		
		}
		
		/**
		 * Delete a node from the Splay Tree. When a node is deleted, its subtrees should
		 * be reconnected to the Splay Tree somehow without violating the properties of BST.
		 * If a node with two children is deleted, a node with the minimum-valued element
		 * in the right subtrees replaces the deleted node. It does NOT guarantee the balance
		 * of the Splay Tree. 
		 * @param x  an element to be deleted from the Splay Tree.
		 */		
		void delete(int x) {			
			boolean wasRoot = false;
			SplayTree node = root;				
			// Find the element to be deleted			
			while (node != null) {				
				if (node.element == x) {  // Found									
					break;
				} 
				else if (node.element > x) {			
					node = node.leftSubtree;
				}
				else {
					node = node.rightSubtree;
				}
			}			
			if (node == null) {
				String msg = x + " is NOT in the Splay Tree.";
				report(msg);	
			}
			else {				
				wasRoot = node.isRoot(); // Remember whether the node is the root or not			
				// The node has no subtrees, so just replace with null
				if (node.isExternal()) {
					replace(node, null);
				}
				// The node has at least one child, also the node might be the root	
				else if (node.leftSubtree == null) { // the node has only right child
					replace(node, node.rightSubtree);
				}
				else if (node.rightSubtree == null) { // the node has only left child
					replace(node, node.leftSubtree);
				}				
				else { // The node has two children
					// Get a successive node to replace the node that will be deleted
					SplayTree newNode = findMin(node.rightSubtree);
					
					// Special case: the successive node is actually right child of the node to be deleted
					// The successive node will carry its own right child when it replace the node.
					if (newNode == node.rightSubtree) {
						replace(node, newNode);
						newNode.leftSubtree = node.leftSubtree;						
					}
					else {
						// Now the succesive node should be replaced before it is used
						// Ensured that it has no left child since it's the minimum of subtrees
						if (newNode.rightSubtree == null) {
							replace(newNode, null);  
						}
						else { // The succesive node has right child to take care of																		
							replace(newNode, newNode.rightSubtree);
											
						}
						// Replace the node with the succesive node, updating subtrees as well
						replace(node, newNode);
						newNode.leftSubtree = node.leftSubtree;
						newNode.rightSubtree = node.rightSubtree;						
					}
				}				
				String msg = x + " is succesively deleted from the Splay Tree.";
				report(msg);
				// Finally, splaying at the parent of the deleted node.
				if (!wasRoot) {					
					splay(node.parentTree);					
				}
				else {
					splay(root);
				}
				// Delete the node completely				
				node.leftSubtree = null;
				node.rightSubtree = null;
				node.parentTree = null;								
			}
		}		
		
		/**
		 * Splay a node until it reaches up to the root of the Splay Tree. Depending on the location
		 * of a target node, parent, and grandparent, splaying applies one of Zig, Zig-Zig, or Zig-Zag
		 * rotation at each stage. This method is called when a data is accessed by any operations. 
		 * @param T  a target node at which splaying is performed.
		 */
		void splay(SplayTree T) {
			// Remember total depth of T's family before splaying
			// Family consists of parent, sibling, children, but not including T itself
			// This is to see how the data near the splayed data are improved for faster
			// accesss in future, after spalying 		
			T.oldFam = new OldFamilySplayTree(T);
			double oldFamDepth = T.oldFam.getFamilyDepth() /(double)T.oldFam.numFam;
			
			// Keep splaying until T reaches the root of the Splay Tree			
			while (!T.isRoot()) {				
				SplayTree p = T.parentTree;				
				SplayTree gp = p.parentTree;				
				// T has a parent, but no grandparent
				if (gp == null) {					
					splayStat = splayStat + "Zig ";
					if (T.isLeftSubtree()) { splayStat = splayStat + "from Left.  "; }
					else { splayStat = splayStat + "from Right.  "; }
					
					rotation(T);  // Zig rotation
					rotateCount++;				
				}
				else { // T has both parent and grandparent
					if (T.isLeftSubtree() == p.isLeftSubtree()) {					
						// T and its parent are in the same direction: Zig-Zig rotation
						splayStat = splayStat + "Zig-Zig " ;
						if (T.isLeftSubtree()) { splayStat = splayStat + "from Left,  "; }
						else { splayStat = splayStat + "from Right,  "; }
						
						rotation(p);  
						rotation(T);						
						rotateCount++;
					}
					else { 					
						// T and its parent are NOT in the same direction: Zig-Zag rotation
						splayStat  = splayStat + "Zig-Zag ";
						if (T.isRightSubtree()) { splayStat = splayStat + "from Left,  "; }
						else { splayStat = splayStat + "from Right,  "; }
						
						rotation(T);  
						rotation(T);						
						rotateCount++;
					}
				}
			}
			// Report additional statistics of rotations			
			if (statMode) {
				String stat = "Sequence of rotations: " + splayStat + "\n" + 
			                  "; Total number of rotations: " + rotateCount + "\n" +
			                  "; Average depth of old family: " + oldFamDepth;
			    report(stat);
			}
			splayStat = ""; rotateCount = 0;  // after splaying(and reporting), reset the variables
		}
		
		/**
		 * Rotate subtrees of the Splay Tree. It updates subtrees of a grandparent, if exists, for
		 * doulbe rotations, and performs single rotation depending on whether a node is left
		 * child or right child.
		 * @param T  a node at which single rotation should be performed.
		 */
		void rotation(SplayTree T) {	
			SplayTree p = T.parentTree;
			SplayTree gp = null;		
			if (p != null) {  gp = p.parentTree; }				
			if (!T.isRoot()) {
				// Remember whether T is originally left child or right child
				final boolean wasLeft = T.isLeftSubtree();
				// T has grandparent		
				if (gp != null) {
					// Replace subtree of grandparent with T for Double rotations					
					if (gp.leftSubtree == p) {
						gp.leftSubtree = T;
						T.parentTree = gp;
					}
					else {
						gp.rightSubtree = T;
						T.parentTree = gp;
					}
				}
				else {
					// T has no grandparent, set T to the new root.
					root = T;
					T.parentTree = null;
				}
				// Rotate from left
				if (wasLeft) {
					// Attach T's right child to its parent's left child
					p.leftSubtree = T.rightSubtree;
					if (T.rightSubtree != null) {						
						T.rightSubtree.parentTree = p;  // update the parent of T's subtree					
					}
					// Now rotate T, so T's parent becomes T's right child					
					T.rightSubtree = p;
					if (p != null) {
						p.parentTree = T;
					}										
				}
				else { // Rotate from right
					// Attach T's left child to its parent's right child
					p.rightSubtree = T.leftSubtree;					
					if (T.leftSubtree != null) {
						T.leftSubtree.parentTree = p; // update the parent of T's subtree
					}
					// Now rotate T, so T's parent becomes T's left child
					T.leftSubtree = p;
					if (p != null) {
						p.parentTree = T;						
					}					
				}
			}
		}			
			  
		/**
		 * Self painting method.
		 * @param g  graphic object
		 * @param xpos  x-cordinate of a node in cartesian plane
		 * @param ypos  y-cordinate of a node in cartesian plane
		 */
		void paint(Graphics g, int xpos, int ypos) {
			treeColumns();
			paintHelper(g, xpos, ypos);
		}
		
		/**
		 * Actually paint the tree by drawing line, node(circle), and data(integer)	
		 * @param g  graphic object
		 * @param xpos  x-cordinate of a node in cartesian plane
		 * @param ypos  y-cordinate of a node in cartesian plane
		 */
		void paintHelper(Graphics g, int xpos, int ypos) {
			String space = "";
			if (element < 10) { space = " "; }
			if (! isExternal()) {
				g.setColor(Color.blue);
				if (leftSubtree != null) {
					g.drawLine(xcenter + xpos - 10, ycenter + ypos,
						   		leftSubtree.xcenter + xpos,
								leftSubtree.ycenter + ypos - 10);
				}
				if (rightSubtree != null) {
					g.drawLine(xcenter + xpos + 10, ycenter + ypos,
								rightSubtree.xcenter + xpos,
								rightSubtree.ycenter + ypos - 10);								
				}
				g.setColor(new Color(102,0,204));						   
				g.fillOval(xpos + column*nodeHorizSpacing -1, ypos + depth*nodeVertSpacing -1,
						   nodeWidth+2, nodeHeight+2);				
				g.setColor(treeColor);
				g.fillOval(xpos + column*nodeHorizSpacing, ypos + depth*nodeVertSpacing,
				           nodeWidth, nodeHeight);
				g.setColor(Color.black);
			}
			if (isExternal()) {
				g.setColor(new Color(102,0,204));						   
				g.fillOval(xpos + column*nodeHorizSpacing -1, ypos + depth*nodeVertSpacing -1,
						   nodeWidth+2, nodeHeight+2);				
				g.setColor(treeColor);
				g.fillOval(xpos + column*nodeHorizSpacing, ypos + depth*nodeVertSpacing,
						   nodeWidth, nodeHeight);
									   
				g.setColor(Color.black);			
				g.drawString( space + element,
				 				xpos + column*nodeHorizSpacing + leftOffset,
				 				ypos + depth*nodeVertSpacing + nodeHeight - 8 );
			}
			else {
				g.drawString(space + element,
				            xpos + column*nodeHorizSpacing + leftOffset,
							ypos + depth*nodeVertSpacing + nodeHeight - 8);
				// recursive call to paint subtrees
				if (leftSubtree != null) {
					leftSubtree.paintHelper(g, xpos, ypos);
				}
				if (rightSubtree != null) {
					rightSubtree.paintHelper(g, xpos, ypos);
				}
			}			
		}
		
        /**
         * Inorder traversal, filling in the depth and the column index of each node
         * for display purposes. It should also deal with the case where a node has
         * only one child.
         * @param currentDepth  the current depth of a node
         * @return  the column index of the rightmost node.
         */
		int traverse(int currentDepth) {			
			depth = currentDepth;
			if (isExternal()) {				
				column = m; m++;
				maxdepth = depth; 
			}
			if (leftSubtree == null && rightSubtree != null) {
				column = m; m++;
			}
			if (leftSubtree != null){
				leftSubtree.traverse(depth + 1);				
				column = m; m++;				
			}			
			xcenter = column*nodeHorizSpacing + (nodeWidth / 2);
			ycenter = depth*nodeVertSpacing + nodeHeight - ycentering;
			if (rightSubtree != null) {					
				int rm = rightSubtree.traverse(depth + 1);
				if (leftSubtree == null) {
					maxdepth = rightSubtree.maxdepth;				
				}
				else {	maxdepth = Math.max(leftSubtree.maxdepth,
									rightSubtree.maxdepth);
				}				
				return rm;					
			}
			else {				
				return column;
			}
		}
		
		/**
		 * Determine total column index of each node, filling a column index of
		 * each node for display purpose.
		 * @return  total column index of the Splay Tree
		 */		
		int treeColumns() {
			m = 0;
			return traverse(0) + 1;
		}
		
		/**
		 * Determine the height of the Splay Tree
		 * @param T  a node that roots the Splay Tree
		 * @return  the height of the Splay Tree at the node
		 */
		int treeHeight(SplayTree T) {
			if (T == null) {
				return -1;
			}
			return (1 + Math.max( treeHeight(T.leftSubtree), treeHeight(T.rightSubtree)));			
		}
				
		/**
		 * Get the width needed to display the tree
		 * @return  the width of the entire Splay Tree
		 */
		int getDisplayWidth() {
			int hGap = nodeHorizSpacing - nodeWidth;			
			int val = treeColumns() * (nodeHorizSpacing) - hGap;			
			return val;
		}	
		/**
		 * Get the height needed to display the tree
		 * @return  the height of the entire Splay Tree
		 */	
		int getDisplayHeight() {
			int maxHeight = treeHeight(root);			
			int val = (maxHeight+1)* nodeVertSpacing - nodeVGap;			
			return val;
		}
	}  ////////////////////  End of SplayTree class  /////////////////////	
	
	
	/**
	 *  OldFamilySplayTree Class:
	 * 
	 * This inner class is to store old family members of a splayed node.
	 * Therefore, after splaying, we can track the old family of the new root
	 * and calculate the relative improvement in terms of depth. After splaying,
	 * the most-recently-accessed data becomes available for O(1) access in the
	 * next time. In addition, all family members also improve the access time 
	 * in future. This is a simple way to compare the cost of access to those
	 * family memembers before splaying and after splaying.
	 * 
	 * @author Hyung-Joon Kim
	 *  
	 */
	public class OldFamilySplayTree {
		// Family members of a node which will be splayed		
		SplayTree oldParent, oldSibling, oldLeftChild, oldRightChild;		
		int numFam;  // Numbers of family members
		
		/**
		 * Default Constructor:
		 * @param T  a node which will be splayed and needs to create old family of it
		 */
		OldFamilySplayTree(SplayTree T) {
			if (T.parentTree != null) {
				oldParent = T.parentTree;
				numFam++;
			}
			if (T.leftSubtree != null) {
				oldLeftChild = T.leftSubtree;
				numFam++;			
			}
			if (T.rightSubtree != null) {
				oldRightChild = T.rightSubtree;
				numFam++;	
			}			
			if (T.isLeftSubtree()) {
				if (T.parentTree != null && T.parentTree.rightSubtree != null) {
					oldSibling = T.parentTree.rightSubtree;
					numFam++;
				}			
			}
			else {
				if (T.parentTree != null && T.parentTree.leftSubtree != null) {
					oldSibling = T.parentTree.leftSubtree;
					numFam++;
				}				
			}			
		}
		
		/**
		 * Calculate the average depth of all family member nodes. 
		 * This method can calculate the depth before splaying by being called
		 * in the SPLAY method, and the depth after splaying by being called
		 * after repaiting the tree since the depth will is updated in the
		 * PAINT method.
		 * @return  the average depth of all family member nodes.
		 */
		double getFamilyDepth() {
			double famDepth = 0.0;
			if (oldParent != null) {
				famDepth = famDepth + (double)oldParent.depth;
			}
			if (oldSibling != null) {
				famDepth = famDepth + (double)oldSibling.depth;
			}
			if (oldLeftChild != null) {
				famDepth = famDepth + (double)oldLeftChild.depth;
			}
			if (oldRightChild != null) {
				famDepth = famDepth + (double)oldRightChild.depth;
			}
			return famDepth;
		}				
	}   ////////////////////  End of OldFamilySplayTree class  /////////////////////	
	
	
	// Paint the Splay tree in a left-to-right sequence of trees.	 
	void paintTrees(Graphics g) {
		g.setFont(treeFont);
		int ystart = yTreeTops; 
		int ypos = ystart;
		int xpos = leftMargin;
		
		g.setFont(headingFont);
		g.drawString("Splay Tree Demonstration :", xpos, yTreeTops - 20);		
		
		if (theSplayTree.getRoot() != null) {					
			g.setFont(treeFont);			
			theSplayTree.getRoot().paint(g,xpos,ypos);
			xpos += interTreeGap;
			xpos += theSplayTree.getRoot().getDisplayWidth();			
		}			
	}
	
	/* A handy function that reports a message to both the
	 * status line of the applet and the history window.
	 * Multiline messages are not fully visible in the status line.
	 */
	void report(String message) {
		statusLine.setText(message);
		history.appendText("; " + message + "\n");
	} 

}