/* 
 * AVLTreeApplet
 * 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.
 * 
 * The program scans through the text, and for each word encountered,
 * processes it using AVL tree by executing a sequence of commands
 * such as FIND and INSERT. As a result, each word will be stored in
 * the AVL tree with a count of the occurences in the document.
 * And also, it demonstrates the process of building AVL tree for 
 * a document in the display pane.
 *
 * @author Hyung-Joon Kim, CSE 373, University of Washington
 * 
 */
   
 /* Here is a sample command sequence:

DELAY 500 ; pause 500 ms between updates.
RESET
INSERT ant 5
INSERT bear 2
INSERT chinchilla 1
INSERT dromedary 2
FIND chinchilla; returns chinchilla 1
FIND egret; return NOT FOUND
*/

/*
RESET
BEGIN-DOCUMENT
Ant bear ant chinchilla dromedary.
bear ant ant dromedary.
END-DOCUMENT
FIND chinchilla ; returns chinchilla 1
*/

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

public class AVLTreeApplet 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
	AVLTree theAVLTreeA;
	AVLTree theAVLTreeB;
	String sourceText;   // text used to build a AVL tree
	String sourceWord = "";
	
	// Characterized sets of words in two documents
	HashSet A_B = new HashSet();
	HashSet B_A = new HashSet();
	HashSet AIB = new HashSet();
	HashSet AUB = new HashSet();	
	String compareResult = "";
		
	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 = 200;  // default is to wait 200 ms between updates.
	Thread displayThread = null;
	
	// For AVLTree display:
	int nodeHeight = 15;  // For drawing the nodes.
	int nodeWidth = 80;  // How wide to plot pink rectangles
	int nodeVGap = 20;  // vertical space between successive nodes
	int nodeHGap = -20;  // horizontal space between successive nodes
	int nodeHorizSpacing = nodeWidth + nodeHGap;
	int nodeVertSpacing = nodeHeight + nodeVGap;
	int interTreeGap = 20;  // horizontal space between trees.
	int ycentering = 3;
	Color treeColor;
	Color treeColor1 = new Color(255,255,215);
	Color treeColor2 = new Color(255,223,223);
	static int m;  // variable used when computing columns for tree layouts.

	public void init() {
		setSize(700,400); // 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();
		
		theAVLTreeA = new AVLTree();   // create an instance of the AVLTree
		theAVLTreeB = new AVLTree();

		headingFont = new Font("Helvetica", Font.PLAIN, 20);		
		treeFont = new Font("Helvetica", Font.PLAIN, 11);
		history = new TextArea("AVLTreeApplet 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 AVLTreeApplet");
				history.setFont(new Font("Courier", Font.PLAIN, 12));
				historyFrame.getContentPane().add(history);
				historyFrame.setSize(new Dimension(500,400));
			}
			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")) { 
			theAVLTreeA = new AVLTree();
			theAVLTreeB = new AVLTree();		
			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().toLowerCase(); }
			arg2 = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) { arg2 = st.nextToken().toLowerCase(); }
			int ct = (new Integer(arg2)).intValue();
			
			// Assign data to the root node of AVLTree. This is the case that
			// the first attempt at insertion to the AVL tree is made.
			if (theAVLTreeA.word == null) {
				theAVLTreeA.word = arg1;
				theAVLTreeA.count = ct;
			}
			// Check if a word is already in the AVLTree. If so, Find method takes care
			// of increment of the word's count. If not, insert the word into the tree.
			else if (theAVLTreeA.Find(theAVLTreeA, arg1, ct) == null) {				
				theAVLTreeA = theAVLTreeA.Insert(theAVLTreeA, arg1, ct);				
			}						
			checkScrolledPanelSize();
			updateDisplay();
			return;			
		}
		if (firstToken.equals("FIND")) {
			arg1 = "UNDEFINED ELEMENT";
			if (st.hasMoreTokens()) { arg1 = st.nextToken().toLowerCase(); }
					
			// Check if a word is already in the AVLTree and display the result.
			AVLTree n = new AVLTree();
			n = theAVLTreeA.Find(theAVLTreeA, arg1);
			String msg = "";
			if (n == null) { msg = "NOT FOUND"; 	}
			else { msg = "FOUND: " + n.word + " " + n.count; }
			
			report(msg);							
			checkScrolledPanelSize();
			updateDisplay();			
			return;
		}		
		if (firstToken.equals("BEGIN-DOCUMENT-A")) { 
			sourceText = "";			
			command = lines.nextToken() + "\n";						
			history.appendText(command);
			while (! command.startsWith("END-DOCUMENT-A")) {							
				sourceText += command;
				command = lines.nextToken() + "\n";
				history.appendText(command);
			}				
			CreateAVLTreeOfDocumentA(sourceText);  // Create a AVL tree of the scaned document
			updateDisplay();
			statusLine.setText("The AVL tree of the documnet has been successfully created.");		
			return;
			
		}
		if (firstToken.equals("BEGIN-DOCUMENT-B")) {
			sourceText = "";
			command = lines.nextToken() + "\n";
			history.appendText(command);
			while (! command.startsWith("END-DOCUMENT-B")) {
				sourceText += command;
				command = lines.nextToken() + "\n";
				history.appendText(command);
			}
			CreateAVLTreeOfDocumentB(sourceText);  // Create a AVL tree of the scaned document
			updateDisplay();
			statusLine.setText("The AVL tree of the documnet has been successfully created.");
			return;
		}
		if (firstToken.equals("SIMPLE-COMPARE")) {			
			CompareDocument();						
			history.appendText(compareResult);
			statusLine.setText("See the comparison result in HISTORY window");
			checkScrolledPanelSize();
			updateDisplay();		
			return;
		}			
		history.appendText("[Unknown AVL tree command]\n");
		statusLine.setText("Unknown AVL tree command: " + command);		
	}
	
	/* Create two sets of all words in each document.
	 * Then, define new sets that characterize the comparison of
	 * two documents. Finally, based on the analysis method, determine
	 * how two documents are different or simillar.
	 */
	void CompareDocument() {
		HashSet wordA = new HashSet();
		HashSet wordB = new HashSet();
		// set of words in documents
		wordA = CreateWordSet(theAVLTreeA, wordA);
		wordB = CreateWordSet(theAVLTreeB, wordB);		
		CreateComparedSets(wordA, wordB);  // create characterized sets
		SimpleCompare();  // comparison report
	}
	
	/* Report four characterized sets for comparison and the cardinality of
	 * each set. Also, determine the set distance by using the formula. 
	 */ 
	void SimpleCompare() {
		Iterator iterAIB = AIB.iterator(); 	Iterator iterAUB = AUB.iterator();
		Iterator iterA_B = A_B.iterator(); 	Iterator iterB_A = B_A.iterator();
		
		compareResult = "\nWords in both Document A and B :\n" + "  ";
		while(iterAIB.hasNext()) {
			compareResult = compareResult + (String)iterAIB.next() + ", ";
		}
		compareResult = compareResult + "\nWords in either Document A or B :\n" + "  ";
		while(iterAUB.hasNext()) {
			compareResult = compareResult + (String)iterAUB.next() + ", ";
		}
		compareResult = compareResult + "\nWords in Document A but not in B :\n" + "  ";
		while(iterA_B.hasNext()) {
			compareResult = compareResult + (String)iterA_B.next() + ", ";
		}
		compareResult = compareResult + "\nWords in Document B but not in A :\n" + "  ";
		while(iterB_A.hasNext()) {
			compareResult = compareResult + (String)iterB_A.next() + ", ";
		}
		// set distance formula
		double ds = (double)(A_B.size() + B_A.size()) / (double)(1 + AIB.size());
		compareResult = compareResult + "\nCard(A intersection B) : " + AIB.size() + "\n" +
		                "Card(A union B) : " + AUB.size() + "\n" +
		                "Card(A - B) : " + A_B.size() + "\n" +
		                "Card(B - A) : " + B_A.size() + "\n" +
		                "Set Distance(A,B) : " + ds + "\n\n";	
	}
	
	/* Create a set of all words in a document.
	 * Data of the set are not in alphabetical order.
	 */ 
	HashSet CreateWordSet(AVLTree T, HashSet hs) {
		if (T != null) {
			CreateWordSet(T.leftSubtree, hs);
			hs.add(T.word);			
			CreateWordSet(T.rightSubtree, hs);
		}		
		return hs;		
	}
	
	/* Define four sets to compare two documents :
	 * AIB: words in both Document A and B
	 * AUB: words in either Document A or B
	 * A_B: words in A but not in B
	 * B_A: words in B but not in A 
	 */
	void CreateComparedSets(HashSet wordA, HashSet wordB) {		
		// Define a set of A intersection B
		if (wordA.size() < wordB.size()) {			
			Iterator iter = wordA.iterator();			
			while (iter.hasNext()) {
				String word = (String) iter.next();
                // Check if words in A also exist in B
				if (wordB.contains(word)) {
					AIB.add(word);  // add word to a set of A intersection B
				}				
			}			
		}
		else {
			// Check if words in B also exist in A
			Iterator iter = wordB.iterator();
			while (iter.hasNext()) {
				String word = (String) iter.next();
				if (wordA.contains(word)) {
					AIB.add(word);
				}
			}			
		}		
		// Define a set of A union B
		Iterator iterA = wordA.iterator();
		Iterator iterB = wordB.iterator();
		while (iterA.hasNext()) {
			String word = (String) iterA.next();
			AUB.add(word);
		}
		while (iterB.hasNext()) {
			String word = (String) iterB.next();
			AUB.add(word);
		}		
		// Define a set of A - B and B - A
		Iterator iterAIB = AIB.iterator();		
		while (iterAIB.hasNext()) {
			String word = (String) iterAIB.next();
			if (wordA.contains(word)) {
				wordA.remove(word);
			}
			if (wordB.contains(word)) {
				wordB.remove(word);
			}
		}
		A_B = wordA;
		B_A = wordB;		
	}	
	
	/* Create a AVLTree of a document which is scanned from the textarea 
	 * by extracting each word as a string from the document of one string.
	 * Ignore HTML tags, puntuations, newlines, whitespaces, and non-alphabetic 
	 * characters in a document.
	 */
	void CreateAVLTreeOfDocumentA(String sourceText) {
		sourceText = sourceText.toLowerCase();   // convert to lower case before insertion
		int i = 0, j = 0;
		// Scan through a document		
		while (i < sourceText.length()) {
			char c = sourceText.charAt(i);
			// Filter out any string inside HTML tags		
			if (c == '<') {
				if (c != ' ' && c != '\n' && c >= 97 && c <= 122 && c != '<' && c != '>') {
					sourceWord = sourceWord + sourceText.charAt(i);					
				}
				else {
					InsertionHelper(sourceWord);					
					sourceWord = "";					
				}				
				j = i+1;
				// Once an opening tag is encountered, skip character until hit a closing tag. 		
				while (c != '>') {					
					j++; c = sourceText.charAt(j);					
				}
				i = j+1; c = sourceText.charAt(i);
			}			
			if (c != ' ' && c != '\n' &&  c >= 97 && c <= 122 && c != '<' && c != '>') {
				sourceWord = sourceWord + sourceText.charAt(i);							
			}
			else {	
				InsertionHelper(sourceWord);				
				sourceWord = "";				
			}
			i++;
		}		
	}
	
	/* Insertion Helper method: 
	 * will be called while the program extracts each word in the scanned document.
	 * After each intermediate step of insertion, updates the display plane. 
	 */
	void InsertionHelper(String str) {		
		str = str.trim(); // trim whitespace at the end of each line
		if (str != "") {			
			if (theAVLTreeA.word == null) {
				theAVLTreeA.word = str;
				theAVLTreeA.count = 1;
			}
			else {				
				if (theAVLTreeA.Find(theAVLTreeA, str, 1) == null) {
					theAVLTreeA = theAVLTreeA.Insert(theAVLTreeA, str, 1);
				}
			}
			checkScrolledPanelSize();
			updateDisplay();
		}		
	}
	
	// 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();
		
		if (theAVLTreeB != null) {
			treesWidthNeeded += theAVLTreeA.getDisplayWidth() + theAVLTreeB.getDisplayWidth() + 20;
			int maxheight = Math.max(theAVLTreeA.getDisplayHeight(), theAVLTreeB.getDisplayHeight());
			treesHeightNeeded = Math.max(treesHeightNeeded, maxheight);					
		}
		else {
			treesWidthNeeded += theAVLTreeA.getDisplayWidth();			
			treesHeightNeeded = Math.max(treesHeightNeeded, theAVLTreeA.getDisplayHeight());					
		}
		// 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.
		}
	}

	/*  
	 * This inner class, AVLTree, is a data structure to store each word in
	 * a document and a count of the word's occurences in the document as the
	 * program scans through the text.
	 *  
	 */
	class AVLTree {
		
		// data members for AVL trees :		
		AVLTree leftSubtree, rightSubtree;
		String word;
		int count;
		int height;   // the current height of each node

		// 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
		AVLTree() {	}		
		
		// Constructor with given word and count: will be called in the insertion process		 
		AVLTree(String word, int count) {
			this.word = word; this.count = count;
		}		
		
		int height(AVLTree T) { 
			if (T == null) { return -1; }  // empty height -1
			else { return T.height; }
		}
		
		/* Set the height of a node by taking the maximun height of left child
		 * and right child and adding 1 to it.
		 */					
		void setHeight(AVLTree t1, AVLTree t2) {
			this.height = 1 + Math.max(height(t1), height(t2));		
		}
		
		boolean isExternal() { 
			return (leftSubtree == null && rightSubtree == null);
		}
		
		boolean isBalanced() {
			// Balance factor of a node of a AVL tree, between -1 and 1
			int bf = height(leftSubtree) - height(rightSubtree);
			return ((-1 <= bf) && (bf <= 1));
		}
				
		/* Find a given word in the AVL tree. If found, increment the count
		 * of the word by 1 and return the node which contains the word.
		 * If not found, return null. 
		 */
		AVLTree Find(AVLTree T, String wrd, int ct) {
			if (T == null) { return null; }
			else if (T.word.compareTo(wrd) == 0) {				
				T.count = T.count + ct;  // If a word is found, update its count.
				return T;
			}
			else if (T.word.compareTo(wrd) > 0) { return Find(T.leftSubtree, wrd, ct); 	}
			else return Find(T.rightSubtree, wrd, ct);						
		}
		
		/* Overloading Find method: will be called to retreive a word in the AVLTree 
		 * without insertion purpose.
		 */
		AVLTree Find(AVLTree T, String wrd) {
			if (T == null) { return null; }
			else if (T.word.compareTo(wrd) == 0) { return T; }
			else if (T.word.compareTo(wrd) > 0)  { return Find(T.leftSubtree, wrd); }
			else return Find(T.rightSubtree, wrd);			
		}
		
		/* Insert a word into the AVL tree. After insertion, keep the AVL tree
		 * balanced using the helper methods that rebalance the AVL tree by
		 * rotating the nodes, depending on where the insertion occurs. 
		 */
		AVLTree Insert(AVLTree T, String wrd, int ct) {			
			if (T == null) {
				// Create an external node with word and count initialized
				T = new AVLTree(wrd,ct);				
			}
			else if (T.word.compareTo(wrd) > 0) {				
				// Recuresive call to left subtree
				T.leftSubtree = Insert(T.leftSubtree, wrd, ct);								
				// Check if insertion makes the AVL tree keep balanced
				if (!T.isBalanced()) {
					if (T.leftSubtree.word.compareTo(wrd) > 0) {						
						T = RotateFromLeft(T);  // outside rotation
					}
					else {
						T = DoubleRotateFromLeft(T); // inside rotation
					}					
				}
			}
			else {			
				// Recursive call to right subtree
				T.rightSubtree = Insert(T.rightSubtree, wrd, ct);				
				// Check if insertion makes the AVL tree keep balanced
				if (!T.isBalanced()) {
					if (T.rightSubtree.word.compareTo(wrd) < 0) {					
						T = RotateFromRight(T);  // outside rotation
					}
					else {						
						T = DoubleRotateFromRight(T);  // inside rotation
					}
				}
			}
			T.setHeight(T.leftSubtree, T.rightSubtree);  // update the current height after insertion					
			return T;					
		}
		
		/* Single rotation from left: 
		 * @Insertion into left subtree of left child of a node.
		 */
		AVLTree RotateFromLeft(AVLTree node) {
			AVLTree temp = new AVLTree();
			temp = node.leftSubtree;
			node.leftSubtree = temp.rightSubtree;
			temp.rightSubtree = node;
			// Update the heights of node and temp		
			node.setHeight(node.leftSubtree, node.rightSubtree);
			temp.setHeight(temp.leftSubtree, node);			
			return temp;
		}
				
		/* Single rotation from right: 
		 * @Insertion into right subtree of right child of a node.
		 */
		AVLTree RotateFromRight(AVLTree node) {			
			AVLTree temp = new AVLTree();
			temp = node.rightSubtree;
			node.rightSubtree = temp.leftSubtree;
			temp.leftSubtree = node;			
			// Update the heights of node and temp		
			node.setHeight(node.leftSubtree, node.rightSubtree);
			temp.setHeight(temp.rightSubtree, node);						
			return temp;
		}
				
		/* Double rotation from left: first left child with its right
		 *   child, then node with new left child.
		 * @Insertion into right subtree of left child of a node.
		 */ 
		AVLTree DoubleRotateFromLeft(AVLTree node) {
			node.leftSubtree = RotateFromRight(node.leftSubtree);
			return RotateFromLeft(node);			
		}
		
		/* Double rotation from right: first right child with its left
		 *   child, then node with new right child.
		 * @Insertion into left subtree of right child of a node.
		 */		
		AVLTree DoubleRotateFromRight(AVLTree node) {
			node.rightSubtree = RotateFromLeft(node.rightSubtree);
			return RotateFromRight(node);		
		}		
		
		void paint(Graphics g, int xpos, int ypos) {
			treeColumns();
			paintHelper(g, xpos, ypos);
		}
		
		/* Actually paint tree by drawing line, rectangles, and string(data)		 
		 */
		void paintHelper(Graphics g, int xpos, int ypos) {
			if (word != null) {
				if (!isExternal()) {
					g.setColor(Color.blue);
					if (leftSubtree != null) {
						g.drawLine(xcenter + xpos, ycenter + ypos, 
									leftSubtree.xcenter + xpos,
									leftSubtree.ycenter + ypos -10);
					}
					if (rightSubtree != null) {
						g.drawLine(xcenter + xpos, ycenter + ypos,
									rightSubtree.xcenter + xpos,
									rightSubtree.ycenter + ypos -10);								
					}
					g.setColor(treeColor);					
					g.fillRect(xpos + column*nodeHorizSpacing,
								ypos + depth*nodeVertSpacing,
								nodeWidth, nodeHeight);
					g.setColor(Color.black);
				}				
				if (isExternal()) {
					String adjustedSymbol = word;
					if (word.equals("\n")) {
						adjustedSymbol = "\\n";
					}
					g.setColor(treeColor);
					g.fillRect(xpos + column*nodeHorizSpacing,
								ypos + depth*nodeVertSpacing,
								nodeWidth, nodeHeight);
					g.setColor(Color.black);
					g.drawString(adjustedSymbol + ", " + count,
				 				xpos + column*nodeHorizSpacing + leftOffset,
								ypos + depth*nodeVertSpacing + nodeHeight - ycentering);	
				}
				else {
					String adjustedSymbol = word;
					if (word.equals("\n")) { adjustedSymbol = "\\n"; }
					g.drawString(adjustedSymbol + ", " + count, xpos + column*nodeHorizSpacing + leftOffset,
								ypos + depth*nodeVertSpacing + nodeHeight - ycentering);
					
					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.
         * Returns 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;
			}
		}		
		
		int treeColumns() {
			m = 0;
			return traverse(0) + 1;
		}		
		int getDisplayWidth() {
			int hGap = nodeHorizSpacing - nodeWidth;
			int temp = treeColumns();
			int val = treeColumns() * (nodeHorizSpacing) - hGap;
			System.out.println("width" + val + "," + temp);
			return val;
		}		
		int getDisplayHeight() {
			int val = (maxdepth + 1) * nodeVertSpacing - nodeVGap;
			System.out.println("height" + val);
			return val;
		}
	} //////////////////// end of AVLTree class	
		
	
	// Paint the AVL 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;		
		
		if (theAVLTreeA.word != null) {
			g.setFont(headingFont);
			g.drawString("AVL Tree of Document A :", xpos, yTreeTops - 20);			
			g.setFont(treeFont);
			treeColor = treeColor1;
			theAVLTreeA.paint(g,xpos,ypos);
			xpos += interTreeGap;
			xpos += theAVLTreeA.getDisplayWidth();			
		}
		if (theAVLTreeB.word != null) {
			g.setFont(headingFont);
			g.drawString("AVL Tree of Document B :", xpos, yTreeTops - 20);			
			g.setFont(treeFont);
			treeColor = treeColor2;
			theAVLTreeB.paint(g,xpos,ypos);
			xpos += interTreeGap;
			xpos += theAVLTreeB.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");
	}
	
	/* Create a AVLTree of a document which is scanned from the textarea
	 * by extracting each word as a string from the document of one string.
	 * Ignore HTML tags, puntuations, newlines, whitespaces, and non-alphabetic 
	 * characters in a document.
	 */
	void CreateAVLTreeOfDocumentB(String sourceText) {
		sourceText = sourceText.toLowerCase();   // convert to lower case before insertion
		int i = 0, j = 0;
	 	// Scan through a document
	 	while (i < sourceText.length()) {
	 		char c = sourceText.charAt(i);
	 		// Filter out any string inside HTML tags
	 		if (c == '<') {
	 			if (c != ' ' && c != '\n' && c >= 97 && c <= 122 && c != '<' && c != '>') {
	 				sourceWord = sourceWord + sourceText.charAt(i);
	 			}
	 			else {
	 				InsertionHelperB(sourceWord);
	 				sourceWord = "";
	 			}
	 			j = i+1;
	 			// Once an opening tag is encountered, skip character until hit a closing tag.
	 			while (c != '>') {
	 				j++; c = sourceText.charAt(j);
	 			}
	 			i = j+1; c = sourceText.charAt(i);
	 		}
	 		if (c != ' ' && c != '\n' && c >= 97 && c <= 122 && c != '<' && c != '>') {
	 			sourceWord = sourceWord + sourceText.charAt(i);
	 		}
	 		else {
	 			InsertionHelperB(sourceWord);
	 			sourceWord = "";
	 		}
	 		i++;
	 	}
	}
	 
	/* Insertion Helper method:
	 * will be called while the program extracts each word in the scanned document.
	 * After each intermediate step of insertion, updates the display plane.
	 */
	 void InsertionHelperB(String str) {
	 	str = str.trim(); // trim whitespace at the end of each line
	  	if (str != "") {	  		
	  		if (theAVLTreeB.word == null) {
	  			theAVLTreeB.word = str;
	  			theAVLTreeB.count = 1;
	  		}
	  		else {
	  			if (theAVLTreeB.Find(theAVLTreeB, str, 1) == null) {
	  				theAVLTreeB = theAVLTreeB.Insert(theAVLTreeB, str, 1);
	  			}
	  		}
	  		checkScrolledPanelSize();
	  		updateDisplay();
	  	}
	 }	
}