// MyDrawPanel.java
//
// Panel for the drawing area
//
// this one handles the mouse events
//
// Student Name: Aleman Meza, Boanerges

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

/**
* Class DrawPanel for Binary Tree
*/
public class DrawPanel extends JPanel
{
   protected Node root;
   boolean firstTime;
   private int maxx;
   private int maxy;

   /**
   * DrawPanel default constructor
   */
   public DrawPanel()
   {
      setBackground(Color.white);
      root = null;
      firstTime = true;
      maxx = 600;
      maxy = 400;
      repaint();
   }

   /**
   * Gets the component preferred size
   * @return a <code>Dimension</code> with the size
   */
   public Dimension getPreferredSize()
   {
      return new Dimension(maxx, maxy);
   }

   /**
   * Paints the tree graphic visualization
   * @param g the Graphics context
   */
   public void paint(Graphics g)
   {
      super.paint(g);
      int xleft = 0;
      int xright = 0;
      int ydown = 0;
      boolean changesize = false;
      if(firstTime && root != null)
      {
         FontMetrics fm = g.getFontMetrics();
         root.setMetrics(fm.getHeight(), fm.getMaxAdvance(), fm.getAscent());
         firstTime = false;
      }
      if(root != null)
      {
         xleft = Math.abs(root.getMinx(0));
         xright = Math.abs(root.getMaxx(0)) + 60;
         ydown = root.getMaxy(0) + root.getHeight() * 3;
      }
      if(maxx < (xright + xleft))
      {
         maxx = (xright + xleft);
         changesize = true;
      }
      if(maxy < ydown)
      {
         maxy = ydown;
         changesize = true;
      }
      if(changesize == true)
      {
         setSize(maxx, maxy);
      }
      if(root != null)
         root.inorder(g, xleft + 20, 16);
      else
      {
         int y = 16;
         xleft = 30;
         g.drawString("root", xleft - 12, y);
         g.drawLine(xleft, y + 2, xleft, y + 16);
         g.drawLine(xleft, y + 16, xleft - 4, y + 16 - 4);
         g.drawLine(xleft, y + 16, xleft + 4, y + 16 - 4);
         g.drawString("null", xleft - 12, y + 28);
      }
   }

   /**
   * Adds an element
   * @param elem the element
   * @return <code>true</code> if the element is added successfully
   */
   public boolean addElement(String s)
   {
      boolean retValue;
      if(root == null)
         root = new Node(s);
      retValue = root.add(s);
      repaint();
      return retValue;
   }

   /**
   * Gets the Pre-Order traversal
   * @return a <code>String</code> representation of the pre-order traversal
   */
   public String getPreOrder()
   {
      String temp;
      if(root == null)
         return "";
      temp = root.txtPreorder();
      return temp.substring(1, temp.length());
   }


   /**
   * Gets the In-Order traversal
   * @return a <code>String</code> representation of the in-order traversal
   */
   public String getInOrder()
   {
      String temp;
      if(root == null)
         return "";
      temp = root.txtInorder();
      return temp.substring(1, temp.length());
   }

   /**
   * Gets the Post-Order traversal
   * @return a <code>String</code> representation of the post-order traversal
   */
   public String getPostOrder()
   {
      String temp;
      if(root == null)
         return "";
      temp = root.txtPostorder();
      return temp.substring(1, temp.length());
   }

   /**
   * Clears the tree
   */
   public void clear()
   {
      root = null;
      firstTime = true;
      repaint();
   }

   /**
   * Finds an element
   * @param elem the element
   * @return <code>true</code> if the element was found
   */
   public boolean findElement(String elem)
   {
      if(root == null)
         return false;
      return root.findElement(elem);
   }

   /**
   * Deletes an element
   * @param elem the element
   * @return <code>true</code> if the element was deleted successfully
   */
   public boolean deleteElement(String elem)
   {
      if(root == null)
         return false;

      Node current = root;
      Node parent = root;
      boolean isLeftChild = true;
    
      while(! current.data.equals(elem))
      {
         parent = current;
         
         if(current.data.compareTo(elem) > 0)
         {
            isLeftChild = true;
            current = current.left;
         }
         else
         {
            isLeftChild = false;
            current = current.right;
         }
         if(current == null)
            return false;
      }
      if(current.left == null && current.right == null)
      {
         if(current == root)
            root = null;
         else
            if(isLeftChild)
            {
               parent.left = null;
               parent.numLeftChilds = 0;
            }
            else
            {
               parent.right = null;
               parent.numRightChilds = 0;
            }
      }
      else if(current.right == null)
         if(current == root)
            root = current.left;
         else if(isLeftChild)
            parent.left = current.left;
         else
            parent.right = current.left;
      else if(current.left == null)
         if(current == root)
            root = current.right;
         else if(isLeftChild)
            parent.left = current.right;
         else 
            parent.right = current.right;
      else
      {
         Node successor = getSuccessor(current);
         if(current == root)
            root = successor;
         else if(isLeftChild)
            parent.left = successor;
         else
            parent.right = successor;
         successor.left = current.left;
      }
      if(root != null)
      {
         root.setNumChildsNull();
         root.adjustNumChilds();
      }
      repaint();
      return true;
   }

   /**
   * Gets the node successor
   * @parma delNode the node
   * @return a <code>Node</code> reference to the successor
   */
   private Node getSuccessor(Node delNode)
   {
      Node successorParent = delNode;
      Node successor = delNode;
      Node current = delNode.right;
      while(current != null)
      {
         successorParent = successor;
         successor = current;
         current = current.left;
      }
      if(successor != delNode.right)
      {
         successorParent.left = successor.right;
         successor.right = delNode.right;
      }
      return successor;
   }

   /**
   * Does the tree has elements
   * @return <code>true</code> if the tree has elements
   */
   public boolean hasElements()
   {
      return root != null;
   }

}

/**
* Class Node
* implements a tree node
*/
class Node
{
   protected String data;
   protected int numLeftChilds;
   protected int numRightChilds;
   protected Node left;
   protected Node right;

   private int width;
   private int height;
   private int strHeight;
   private int strWidth;
   private int strAscent;
   private int arrow;
   private int margin;
   private final int rounded = 4;
   private final int ptrline = 8;
   private final int maxLetters = 2;

   /**
   * Class Node constructor
   * @param d the data
   */
   public Node(String d)
   {
      data = d;
      left = null;
      right = null;
      numLeftChilds = 0;
      numRightChilds = 0;
   }

   /**
   * Class Node constructor
   * @param d the data
   * @param h the height
   * @param w the width
   * @param a the ascent
   */
   public Node(String d, int h, int w, int a)
   {
      data = d;
      left = null;
      right = null;
      setMetrics(h, w, a);
   }

   /**
   * Sets the metrix for the node
   * @param h the height
   * @param w the width
   * @param a the ascent
   */
   public void setMetrics(int h, int w, int a)
   {
      width = h * maxLetters;
      height = 12 + h;
      strHeight = h;
      strWidth = w;
      strAscent = a;
      arrow = ptrline;
      margin = 2;
   }

   /**
   * Adds a 
   * @param d the data
   * @param h the height
   * @param w the width
   * @param a the ascent
   */
   public boolean add(String o)
   {
      boolean retValue = true;
      if(data.equals(o))
      {
         retValue = false;
      }
      else
      {
         if(data.compareTo(o) > 0)
         {
            if(left == null)
            {
               left = new Node(o, strHeight, strWidth, strAscent);
               numLeftChilds++;
            }
            else
            {
               retValue = left.add(o);
               if(retValue)
                  numLeftChilds++;
            }
         }
         else
         {
            if(right == null)
            {
               right = new Node(o, strHeight, strWidth, strAscent);
               numRightChilds++;
            }
            else
            {
               retValue = right.add(o);
               if(retValue)
                  numRightChilds++;
            }
         }
      }
      return retValue;
   }


   public boolean findElement(String o)
   {
      boolean retValue = false;
      if(data.equals(o))
         return true;
      if(data.compareTo(o) > 0)
      {
         if(left != null)
            retValue = left.findElement(o);
      }
      else
      {
         if(right != null)
            retValue = right.findElement(o);
      }
      return retValue;
   }

   public String txtInorder()
   {
      String retValue = "";
      if(left != null)
         retValue += left.txtInorder();
      if(data != null)
         retValue += "," + data;
      if(right != null)
         retValue += right.txtInorder();
      return retValue;
   }

   public String txtPreorder()
   {
      String retValue = "";
      if(data != null)
         retValue += "," + data;
      if(left != null)
         retValue += left.txtPreorder();
      if(right != null)
         retValue += right.txtPreorder();
      return retValue;
   }

   public String txtPostorder()
   {
      String retValue = "";
      if(left != null)
         retValue += left.txtPostorder();
      if(right != null)
         retValue += right.txtPostorder();
      if(data != null)
         retValue += "," + data;
      return retValue;
   }

   public void setNumChildsNull()
   {
      numLeftChilds = -1;
      numRightChilds = -1;
      if(left != null)
         left.setNumChildsNull();
      if(right != null)
         right.setNumChildsNull();
   }

   public void adjustNumChilds()
   {
      if(numLeftChilds == -1)
      {
         if(left == null)
            numLeftChilds = 0;
         else
         {
            left.adjustNumChilds();
            numLeftChilds = left.numLeftChilds + left.numRightChilds + 1;
         }
      }
      if(numRightChilds == -1)
      {
         if(right == null)
            numRightChilds = 0;
         else
         {
            right.adjustNumChilds();
            numRightChilds = right.numLeftChilds + right.numRightChilds + 1;
         }
      }
   }


   public void inorder(Graphics g, int x, int y)
   {
      g.drawString("root", x - 12, y);
      g.drawLine(x, y + 2, x, y + 16);
      g.drawLine(x, y + 16, x - 4, y + 16 - 4);
      g.drawLine(x, y + 16, x + 4, y + 16 - 4);
      inorder(g, x, y + 16, false);
   }

   public void inorder(Graphics g, int x, int y, boolean t)
   {
      int strWidth, xn, yn;
      String tmpStr = data.substring(0, (data.length() < maxLetters ? data.length() : maxLetters));
      g.drawRoundRect(x - width / 2, y, width, height, rounded, rounded);
      g.drawLine(x - width / 2, y + height - ptrline, x + width / 2, y + height - ptrline);
      g.drawLine(x, y + height - ptrline, x, y + height);
      FontMetrics fm = g.getFontMetrics();
      strWidth = fm.stringWidth(tmpStr);
      g.drawString(tmpStr, x - strWidth / 2, y + height - ptrline - strAscent / 2);
      if(left == null)
      {
         g.drawLine(x - width / 2, y + height - ptrline, x, y + height);
         g.drawLine(x, y + height - ptrline, x - width / 2 + 1, y + height - 1);
      }
      else
      {
         xn = x - width * (left.numRightChilds + 1) - arrow;
         yn = y + height + ptrline;
         g.drawLine(x - width / 4, y + height - ptrline / 2, xn, yn);
         left.inorder(g, xn, yn, false);
      }
      if(right == null)
      {
         g.drawLine(x + width / 2, y + height - ptrline, x, y + height);
         g.drawLine(x, y + height - ptrline, x + width / 2 - 1, y + height - 1);
      }
      else
      {
         xn = x + width * (right.numLeftChilds + 1) + arrow;
         yn = y + height + ptrline;
         g.drawLine(x + width / 4, y + height - ptrline / 2, xn, yn);
         right.inorder(g, xn, yn, false);
      }
   }

   public int getMinx(int x)
   {
      int xn;
      if(left != null)
         xn = x - width * (numLeftChilds + 1) - arrow;
      else
         xn = x - width;
      return Math.min(x, xn);
   }

   public int getMaxx(int x)
   {
      int xn;
      if(right != null)
         xn = x + width * (numRightChilds + 1) + arrow;
      else
         xn = x + width;
      return Math.max(x, xn);
   }

   public int getMaxy(int y)
   {
      int yleft = y, yright = y, yn;
      if(left != null)
      {
         yn = y + height + ptrline;
         yleft = left.getMaxy(yn);
      }
      if(right != null)
      {
         yn = y + height + ptrline;
         yright = right.getMaxy(yn);
      }
      return Math.max(Math.max(yright, yleft), y);
   }

   public int getHeight()
   {
      return height;
   }

}