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

public class AVLTree extends JFrame implements ActionListener {
	protected AVLNode root,parent,node;
	File file;
	private AVLTree tree;
	String [] word,meaning;
	
	JTextField fs=new JTextField("enter word you want to search for");
	JTextField fd=new JTextField ("enter word you want to delete");
	JButton btree= new JButton("construct the tree");
	JButton bprint= new JButton("print");
	JButton bresult= new JButton("print result");
	JButton bsearch= new JButton("do search");
	JButton bs= new JButton ("DO SEARCH");
	JButton bdel= new JButton("delete");
	JButton bd= new JButton ("DELETE");
	JButton bdraw= new JButton("draw the tree");
	JButton bin= new JButton("print inorder");
	JButton bpre= new JButton("print preorder");
	JButton bpost= new JButton("print postorder");

	/*
	 * default constructor
	*/
	public AVLTree(){
		root=null;
		JPanel p= new JPanel ();
		p.setLayout(new GridLayout(6,1,10,20));
		p.add(btree);
		p.add(bprint);
		p.add(bresult);
		p.add(bsearch);
		p.add(bdel);
		p.add(bdraw);
		
		
		add(p);
		
		btree.addActionListener(this);
		bprint.addActionListener(this);
		bresult.addActionListener(this);
		bsearch.addActionListener(this);
		bdel.addActionListener(this);
		bdraw.addActionListener(this);
		bin.addActionListener(this);
		bpre.addActionListener(this);
		bpost.addActionListener(this);
		
	}

	public AVLNode getRoot(){
		return root;
	}
	
	// Insert value into the AVL tree
	public AVLNode insert(String value,AVLNode t) {
		
		if( t == null ){
			//if the Root is Null Create New Node
			t = new AVLNode(value);
			t.left=null;
			t.right=null;	
		}
		else if (value.compareTo(t.key)<0){
	    	t.left=insert(value,t.left);
	    	if( t.left.height - t.right.height == 2 ) {
	            if( value.compareTo( t.left.key ) < 0 )
	            	t = singleRotation(t, 1);
	            else
	                t = doubleRotation(t, 1);
	        }
	    }	
	    else if (value.compareTo(t.key)>0){
	    	t.right=insert(value,t.right);
	    	if( t.right.height - t.left.height == 2 ) {
	            if( value.compareTo( t.right.key ) > 0 )
	            	t = singleRotation(t, 1);
	            else
	                t = doubleRotation(t, 1);
	        }
	    }
	    else
	    	t.height=Math.max(t.left.height,t.right.height)+1;
	    return t;
	}

    /** In order traversal from a subtree */
    private void inorder(AVLNode root) {
    	if (root != null){
    		inorder(root.left);
    		System.out.println(root.key + " ");
        	inorder(root.right);
    	}
    }
	
    /** Pre order traversal from a subtree */
    private void preorder(AVLNode root) {
    	if (root != null){
    		System.out.println(root.key + " ");
    		preorder(root.left);
    		preorder(root.right);
    	}
    }
	
    /** Post order traversal from a subtree */
    private void postorder(AVLNode root) {
    	if (root == null) {
    		postorder(root.left);
    		postorder(root.right);
    		System.out.println(root.key + " ");
    	}
    }
 
	public AVLNode search(String s){
		AVLNode current = root;  // start at root
		while (s!=current.key){
			if(s.compareTo(current.key) <0)  // go left
				current = current.left;
			else                             // or go right
				current = current.right;
			if(current == null){  // if no child
				System.out.println("Not found");
				return null;    // didn't find it
			}
		}
		return current;    // found
	}
		
	public void delete(String s){
		AVLNode current=root;
		parent=root;
		boolean isLeft=false;
		while(s!=current.key){        // search for node
			parent = current;
			if(s.compareTo(current.key) <0)         // go left?
				current = current.left;
            else                            // or go right?
            	current = current.right;
			if(current == null)             // end of the line,
				System.out.println("NOT found"); // didn't find it
        }  // end while
		
		// if no children, simply delete it
	    if(current.left==null &&current.right==null){
	         if(current == root) // if root,
	            root = null;     // tree is empty
	         else if(isLeft){
	            parent.left = null;
	            if( current.left.height - current.right.height == 2 ) {
	            	if( s.compareTo( current.left.key ) < 0 )
	            		current = singleRotation(current, 1);
	                else
	                    current = doubleRotation(current, 1);
	            }
	         }   
	         else{                         
	            parent.right = null;
	            if( current.right.height - current.left.height == 2 ) {
	            	if( s.compareTo( current.right.key ) > 0 )
	            		current = singleRotation(current, 1);
	                else
	                    current = doubleRotation(current, 1);
	            }
	         }   
	         } 
		
	}	
	
	public int getHeight1(){
		return getHeight1(getRoot(), 0);
	}

	public int getHeight1(AVLNode p, int currentHeight){
		if(p == null)
			return currentHeight;
		else
			return max(getHeight1(p.getLeft(), currentHeight ), getHeight1(p.getRight(), currentHeight));
	}

	public int max(int aValue, int bValue){
		return aValue > bValue ? aValue : bValue;
	}

	public boolean isEmpty(){
		return root == null;
	}
	
	private AVLNode singleRotation (AVLNode node, int side){
		AVLNode temp = node; // Just to declare
	    if (side == 0){ // Left Rotation
	    	temp = node.left;
	        node.left = temp.right;
	        temp.right = node;
	        node.height = Math.max( node.left.height, node.right.height ) + 1;
	        temp.height = Math.max( temp.left.height, node.height ) + 1;
	    }
	    else if (side == 1){ // Right Rotation
	    	temp = node.right;
	        node.right = temp.left;
	        temp.left = node;
	        node.height = Math.max( node.left.height, node.right.height ) + 1;
	        temp.height = Math.max( temp.right.height, node.height ) + 1;
	    }
	    return temp;
	}
	
	private AVLNode doubleRotation(AVLNode node, int side) {
		if (side == 0){ //Double Left Rotation
			node.left = singleRotation( node.left, 1 );        
	        return singleRotation( node, 0 );
	    }
	    else if (side == 1){ //Double Right Rotation
	    	node.right = singleRotation( node.right, 0 );
	        return singleRotation( node, 1 );
	    }
	        
	    return node;
	}
	
	// count method to compute the number of lines in a file
    public int count(File filename) throws IOException {    
    	InputStream is = new BufferedInputStream(new FileInputStream(filename));   
    	byte[] c = new byte[1024];    
    	int count = 0;    
    	int readChars = 0;    
    	while ((readChars = is.read(c)) != -1) {        
    		for (int i = 0; i < readChars; i++) {            
    			if (c[i] == '\n')                
    				++count;       
    		}   
    	}    
    	return count;
    }
    
	 /** Main method */
	public static void main(String[] args)  {
		JFrame frame = new AVLTree();
		frame.setTitle("What to do");
		frame.setLocationRelativeTo(null); // Center the frame
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setSize(300, 300);
		frame.setResizable(false);
		frame.setVisible(true);
	} 
	
	public void actionPerformed(ActionEvent e) {
		if(e.getSource()==btree){
			//read nodes from file
            JFileChooser fb = new JFileChooser();
            fb.showOpenDialog(null);
            file = fb.getSelectedFile();
            FileInputStream fis = null;
            BufferedInputStream bis = null;
            DataInputStream dis = null;

            try {
                fis = new FileInputStream(file);
                bis = new BufferedInputStream(fis);
                dis = new DataInputStream(bis);
                int no_nodes = count (file);
                String [] words= new String[no_nodes];
                while (dis.available() != 0) {
                	for (int i = 0; i < words.length; i++){
                		tree=new AVLTree();
                		words[i]= dis.readLine();
                		System.out.println("\n"+words[i]);
                		while (words[i]!=":"){
                			word[i]=words[i];
                			meaning[i]=words[i];
                		}	
                		node=insert(word[i],node);
                	}
                }    
                   
                fis.close();
                bis.close();
                dis.close();
            } catch (FileNotFoundException e1) {
                e1.printStackTrace();
            } catch (IOException e1) {
                e1.printStackTrace();
            }   
            
		}
		
		if(e.getSource()==bprint){
			JFrame f = new JFrame();
			f.setTitle("How to print the tree");
			f.setLocationRelativeTo(null);
			f.setSize(300,200);
			f.setVisible(true);
			
			JPanel p1= new JPanel ();
			p1.setLayout(new GridLayout(3,1,10,10));
			p1.add(bin);
			p1.add(bpre);
			p1.add(bpost);
			
			f.add(p1);
		}
		
		if(e.getSource()==bresult){
			char a ='A';
			try {
			int no_nodes = count (file);
			for (int i=0; i<no_nodes; i++){
				
			}
			a++;
			}catch (FileNotFoundException e1) {
                e1.printStackTrace();
            } catch (IOException e1) {
                e1.printStackTrace();
            }   
			
		}
		
		if(e.getSource()==bsearch){
			JFrame f1 = new JFrame ();
			f1.setTitle("SEARCH");
			f1.setLocationRelativeTo(null);
			f1.setSize(300,200);
			f1.setVisible(true);
			
			JPanel p= new JPanel();
			p.setLayout(new GridLayout(2,1,10,10));
			p.add(fs);
			p.add(bs);
			
			f1.add(p);
		}
		
		if (e.getSource()==bs){
			String a= fs.getText();
			node= search(a);
			JOptionPane.showMessageDialog(null,"The wanted word is:"+node+"\t"+"and the meaning is"+meaning);
		}
		
		if(e.getSource()==bdel){
			JFrame f1 = new JFrame ();
			f1.setTitle("DELETE");
			f1.setLocationRelativeTo(null);
			f1.setSize(300,200);
			f1.setVisible(true);
			
			JPanel p= new JPanel();
			p.setLayout(new GridLayout(2,1,10,10));
			p.add(fd);
			p.add(bd);
			
			f1.add(p);
		}
		
		if (e.getSource()==bd){
			String a= fd.getText();
			delete(a);
		}
		
		if(e.getSource()==bdraw){
			
		}
		
		if(e.getSource()==bin){
			System.out.println("The inorder form of the tree (sorted alphabetically) is"+"\t");
			tree.inorder(node);
		}
		
		if(e.getSource()==bpre){
			System.out.println("The preorder form of the tree is"+"\t");
			tree.preorder(node);
		}
		
		if(e.getSource()==bpost){
			System.out.println("The postorder form of the tree is"+"\t");
			tree.postorder(node);
		}
	}
           
	/*
	* AVLNode class 
	*/
	class AVLNode {

		protected String key;
		protected int height;
		protected AVLNode left, right,parent;

		public AVLNode(String aKey){
			key = aKey;
			left = right = null;
		}

		public AVLNode(){
			key = "";
			height = 0;
			right = left = parent = null;
		}

		public AVLNode(String element, AVLNode left, AVLNode right){
			key = element;
			this.left = left;
			this.right = right;
		}

		public void setKey(String aKey){
			key = aKey;
		}

		public String getKey(){
			return key;
		}

		public void setLeft(AVLNode leftNode){
			left = leftNode;
		}

		public AVLNode getLeft(){
			return left;
		}

		public void setRight(AVLNode rightNode){
			right = rightNode;
		}

		public AVLNode getRight(){
			return right;
		}

		public void setParent(AVLNode parentNode){
			parent = parentNode;
		}

		public AVLNode getParent(){
			return parent;
		}

		public void setHeight(int aHeight){
			 height= aHeight;
		}

		public int getHeight(){
			return height;
		}
	}
}