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

public class BSTVisualization extends JFrame implements ActionListener, KeyListener {
	// Tree Root Node.
	private Node root;

	// private Color color;
	private JPanel topPanel, treePanel, infoPanel;
	private JPanel topLeftPanel, topRightPanel;
	private JButton btnAdd, btnDelete;
	private JTextField tf;
	private int X = 300, Y = 75;
	private Graphics2D g2;
	private Rectangle size;
	private JLabel labelInorder, labelPreorder, labelPostorder, labelHeight;
	private JLabel ansInorder, ansPreorder, ansPostorder, ansHeight;
	private FontMetrics fontMatrix;

	//Node Structure
	private static class Node {
		static int TEXT_WIDTH = 40;
		static int TEXT_HEIGHT = 40;

		JLabel data;
		Node left;
		Node right;
		Points p;

		Node(int info) {
			data = new JLabel(info + "", SwingConstants.CENTER);
			data.setFont(new Font("Arial", Font.BOLD, 20));
			data.setBorder(BorderFactory.createLineBorder(Color.black));
			data.setOpaque(true);
			data.setBackground(Color.green);
			p = null;
		}
	}

	//Points structure
	private static class Points {
		int x1 = 0, x2 = 0, y2 = 0, y1 = 0;

		Points(int x1, int y1, int x2, int y2) {
			this.x1 = x1;
			this.x2 = x2;
			this.y2 = y2;
			this.y1 = y1;
		}

		public String toString() {
			return "x1 = " + x1 + ", y1 = " + y1 + ", x2 = " + x2 + ", y2 = " + y2;
		}
	}

	// For storing the Height of the root,left and right child height.
	private static class Height {
		int root, left, right;

		Height() {
			this.root = 0;
			this.left = 0;
			this.right = 0;
		}

		Height(int left, int right) {
			this.left = left;
			this.right = right;
		}

		@Override
		public String toString() {
			return Integer.toString(this.root);
		}
	}

	public void paint(Graphics g) {
		super.paintComponents(g);

		g2 = (Graphics2D) g;
		g2.setStroke(new BasicStroke(3.0f));

		Stack<Node> s = new Stack<>();
		Node curr = root;
		Points pts;
		int offset = topPanel.getBounds().height;
		while (!s.isEmpty() || curr != null) {
			while (curr != null) {
				s.push(curr);
				curr = curr.left;
			}
			if (!s.isEmpty())
				curr = s.pop();
			pts = curr.p;
			g2.drawLine(pts.x1 + 7, pts.y1 + 30 + offset, pts.x2 + 3, pts.y2 + 10 + offset);
			curr = curr.right;
		}

		// x1 = label.getX()+7
		// y1 = label.getY()+30
	}

	public BSTVisualization() {
		// Initialize the frame.
		initialize();
	}

	private void initialize() {

		// setLayout(null); // layout
		setSize(1200, 700); //frame size

		size = getBounds();
		X = size.width / 2;

		topPanel = new JPanel(new BorderLayout());
		Rectangle top = topPanel.getBounds();

		topLeftPanel = new JPanel(new FlowLayout(FlowLayout.LEFT, 10, 10));
		topPanel.add(topLeftPanel, BorderLayout.WEST);

		topRightPanel = new JPanel(new FlowLayout(FlowLayout.RIGHT));
		topPanel.add(topRightPanel, BorderLayout.EAST);

		treePanel = new JPanel(null);
		treePanel.setPreferredSize(new Dimension(size.width, size.height - 300));

		infoPanel = new JPanel();
		infoPanel.setLayout(new BoxLayout(infoPanel, BoxLayout.Y_AXIS));
		infoPanel.setPreferredSize(new Dimension(size.width, 200));

		// Height of BST label
		labelHeight = new JLabel("BST Height : ");
		labelHeight.setFont(new Font("Calibri", Font.BOLD, 20));
		topLeftPanel.add(labelHeight);

		// Height of BST answer
		ansHeight = new JLabel("0");
		ansHeight.setFont(new Font("Calibri", Font.BOLD, 20));
		ansHeight.setPreferredSize(new Dimension(50, 30));
		topLeftPanel.add(ansHeight);

		//For geting data.
		tf = new JTextField("");
		tf.setFont(new Font("Arial", Font.BOLD, 20));
		tf.setPreferredSize(new Dimension(150, 30));
		tf.addKeyListener(this);
		topRightPanel.add(tf);

		//Add Button
		btnAdd = new JButton("Add");
		btnAdd.setFont(new Font("Arial", Font.BOLD, 20));
		// btnAdd.setBounds(size.width - 130, 20, 100, 30);
		btnAdd.addActionListener(this);
		topRightPanel.add(btnAdd);

		//Delete Button
		btnDelete = new JButton("Delete");
		btnDelete.setFont(new Font("Arial", Font.BOLD, 20));
		// btnDelete.setBounds(size.width - 130, 60, 100, 30);
		btnDelete.addActionListener(this);
		topRightPanel.add(btnDelete);

		// Inorder label
		labelInorder = new JLabel("Inorder :");
		labelInorder.setFont(new Font("Times New Roman", Font.BOLD, 20));
		infoPanel.add(labelInorder);

		infoPanel.add(Box.createRigidArea(new Dimension(7, 5)));

		// Inorder traversal answer
		ansInorder = new JLabel("BST is empty.");
		ansInorder.setFont(new Font("Arial", Font.PLAIN, 18));
		infoPanel.add(ansInorder);

		infoPanel.add(Box.createRigidArea(new Dimension(7, 15)));

		// Preorder label
		labelPreorder = new JLabel("Preorder :");
		labelPreorder.setFont(new Font("Times New Roman", Font.BOLD, 20));
		infoPanel.add(labelPreorder);

		infoPanel.add(Box.createRigidArea(new Dimension(7, 5)));

		// Preorder traversal answer
		ansPreorder = new JLabel("BST is empty.");
		ansPreorder.setFont(new Font("Arial", Font.PLAIN, 18));
		infoPanel.add(ansPreorder);

		infoPanel.add(Box.createRigidArea(new Dimension(7, 15)));

		// Postorder label
		labelPostorder = new JLabel("Postorder :");
		labelPostorder.setFont(new Font("Times New Roman", Font.BOLD, 20));
		infoPanel.add(labelPostorder);

		// Postorder traversal answer
		ansPostorder = new JLabel("BST is empty.");
		ansPostorder.setFont(new Font("Arial", Font.PLAIN, 18));
		infoPanel.add(ansPostorder);

		tf.requestFocusInWindow();

		add(topPanel, BorderLayout.NORTH);
		add(treePanel, BorderLayout.CENTER);
		add(infoPanel, BorderLayout.SOUTH);

		setTitle("Binary Search Tree Visualization"); //Title Frame
		setResizable(false);
		setLocationRelativeTo(null);
		setVisible(true);
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	}

	@Override
	public void actionPerformed(ActionEvent evt) {
		if (tf.isEnabled()) {
			try {
				int data = Integer.parseInt(tf.getText());
				if (evt.getSource() == btnAdd) {
					add(data);
				} else {
					delete(data);
				}
				tf.setText("");
				tf.requestFocusInWindow();
			} catch (Exception e) {
				JOptionPane.showMessageDialog(null, "Please Enter Integer.");
			}
		}
	}

	@Override
	public void keyTyped(KeyEvent evt) {
		char c = evt.getKeyChar();
		if (!tf.isEnabled()) {
			return;
		} else if (c == 'a' || c == 'A' || c == '\n') {
			try {
				String data = tf.getText();
				evt.consume(); // Not type 'a' or 'A' character in textfield
				if (!data.isEmpty()) {
					add(Integer.parseInt(data));
				} else {
					throw new Exception();
				}
				tf.requestFocusInWindow();
			} catch (Exception e) {
				JOptionPane.showMessageDialog(null, "Please Enter Integer.");
			}
			tf.setText("");
		} else if (c == 'd' || c == 'D') {
			try {
				String data = tf.getText();
				evt.consume(); // Not type 'd' or 'D' character in textfield
				if (!data.isEmpty()) {
					delete(Integer.parseInt(data));
				}
				tf.requestFocusInWindow();
			} catch (Exception e) {
				JOptionPane.showMessageDialog(null, "Please Enter Integer.");
			}
			tf.setText("");
		} else if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
			evt.consume();
	}

	@Override
	public void keyPressed(KeyEvent evt) {
	}

	@Override
	public void keyReleased(KeyEvent evt) {
	}

	//Add element in BST.
	public void add(int info) {
		Node newNode = new Node(info);
		int width = getWidth(newNode);

		if (root == null) {
			root = newNode;
			newNode.data.setBounds(treePanel.getBounds().width / 2, 10, width, 40);
			newNode.p = new Points(0, 0, 0, 0);
		} else {
			Node curr = root, pre = root;
			int currData;
			X = treePanel.getBounds().width / 2;
			while (curr != null) {
				pre = curr;
				currData = Integer.parseInt(curr.data.getText());
				if (info == currData) {
					JOptionPane.showMessageDialog(null, info + " is already exist.");
					return;
				} else if (currData > info) {
					curr = curr.left;
				} else {
					curr = curr.right;
				}
				X /= 2;
			}

			currData = Integer.parseInt(pre.data.getText());
			int x = pre.data.getX();
			int y = pre.data.getY();
			Dimension preDimension = pre.data.getSize();
			Dimension currDimension = new Dimension(width, Node.TEXT_HEIGHT);

			if (currData > info) {
				pre.left = newNode;
				newNode.data.setBounds(x - X, y + Y, width, 40);
				// x1=x;y1=y+20;x2=x-X+20;y2=y+Y+20;
				newNode.p = new Points(x, y + preDimension.height / 2, x - X + currDimension.width / 2, y + Y + currDimension.height / 2);
			} else {
				pre.right = newNode;
				newNode.data.setBounds(x + X, y + Y, width, 40);
				// x1=x+40;y1=y+20;x2=x+X+20;y2=y+Y+20;
				newNode.p = new Points(x + preDimension.width, y + preDimension.height / 2, x + X + currDimension.width / 2, y + Y + currDimension.height / 2);
			}
		}

		// Set all traversal and height of BST
		setInfo();

		// paint(treePanel.getGraphics());
		treePanel.add(newNode.data);
		treePanel.validate();
		treePanel.repaint();

		validate();
		repaint();
	}

	// Delete Node from BST
	public void delete(int data) {
		if (root == null) {
			JOptionPane.showMessageDialog(null, "BST is empty.");
		} else {
			Node curr = root, pre = root;

			while (curr != null) {
				int info = Integer.parseInt(curr.data.getText());
				if (info == data) {
					break;
				} else if (info > data) {
					pre = curr;
					curr = curr.left;
				} else {
					pre = curr;
					curr = curr.right;
				}
			}

			if (curr == null) { // data is not find.
				JOptionPane.showMessageDialog(null, data + " is not available.");
				return;
			} else if (curr.left == null || curr.right == null) { // data has 0 or 1 child

				treePanel.remove(curr.data);
				treePanel.validate();
				treePanel.repaint();

				validate();
				repaint();

				if (curr != root) {
					Node address = curr.left != null ? curr.left : curr.right;
					// curr.data>pre.data
					int preData = Integer.parseInt(pre.data.getText());
					int currData = Integer.parseInt(curr.data.getText());
					if (currData > preData) {
						pre.right = address;
					} else {
						pre.left = address;
					}
				} else {
					if (curr.left != null) {
						root = curr.left;
					} else {
						root = curr.right;
					}
				}

			} else { // data has 2 child.

				treePanel.remove(curr.data);
				treePanel.validate();
				treePanel.repaint();

				validate();
				repaint();

				/*
				 It set another node depending upon the height of left and right sub tree.
				 */
				Node nextRoot = null, preRoot = curr;
				Height height = calculateHeight(curr);

				/* For taking maximum element from the left Side. */
				if (height.left > height.right) {
					nextRoot = curr.left;
					while (nextRoot.right != null) {
						preRoot = nextRoot;
						nextRoot = nextRoot.right;
					}

					if (preRoot != curr) {
						preRoot.right = nextRoot.left;
					} else {
						preRoot.left = nextRoot.left;
					}
				} else { /* For taking minimum element from the right Side.*/
					nextRoot = curr.right;
					while (nextRoot.left != null) {
						preRoot = nextRoot;
						nextRoot = nextRoot.left;
					}

					if (preRoot != curr) {
						preRoot.left = nextRoot.right;
					} else {
						preRoot.right = nextRoot.right;
					}
				}

				curr.data = nextRoot.data;
			}
			reArrangeNode(root, root, treePanel.getBounds().width / 2);
		}

		// Set all traversal and height of BST
		setInfo();
	}

	// Set all traversal and height of BST
	private void setInfo() {
		Height height = calculateHeight(root);

		if (height.root == 0) {
			ansInorder.setText("BST is empty.");
			ansPostorder.setText("BST is empty.");
			ansPreorder.setText("BST is empty.");
		} else {
			ansInorder.setText(inorder(root));
			ansPostorder.setText(postorder(root));
			ansPreorder.setText(preorder(root));
		}

		ansHeight.setText(height.root + "");
	}

	private int getWidth(Node node) {
		fontMatrix = getFontMetrics(node.data.getFont());
		int width = fontMatrix.stringWidth(node.data.getText());
		return width < Node.TEXT_WIDTH ? Node.TEXT_WIDTH : (width + 5);
	}

	//Inorder logic
	private String inorder(Node root) {
		if (root == null)
			return "";

		return inorder(root.left) + root.data.getText() + " " + inorder(root.right);
	}

	//Preorder logic
	public String preorder(Node root) {
		if (root == null)
			return "";

		return root.data.getText() + " " + preorder(root.left) + preorder(root.right);
	}

	//Postorder logic
	public String postorder(Node root) {
		if (root == null)
			return "";

		return postorder(root.left) + postorder(root.right) + root.data.getText() + " ";
	}

	// Calculate Height of BST using recursive method.
	private Height calculateHeight(Node root) {
		if (root == null) {
			return new Height();
		}
		Height leftChild = calculateHeight(root.left);
		Height rightChild = calculateHeight(root.right);
		Height current = new Height(leftChild.root, rightChild.root);
		current.root = 1 + Math.max(leftChild.root, rightChild.root);
		return current;
	}

	// Rearrange nodes
	private void reArrangeNode(Node node, Node pre, int X) {
		if (node == null)
			return;

		int width = getWidth(node);

		if (root == node) {
			node.data.setBounds(X, 10, width, Node.TEXT_HEIGHT);
		} else {
			int x = pre.data.getX();
			int y = pre.data.getY();
			Dimension preDimension = pre.data.getSize();
			Dimension currDimension = new Dimension(width, Node.TEXT_HEIGHT);

			int preData = Integer.parseInt(pre.data.getText());
			int nodeData = Integer.parseInt(node.data.getText());
			if (nodeData < preData) {
				node.data.setBounds(x - X, y + Y, width, Node.TEXT_HEIGHT);
				node.p = new Points(x, y + preDimension.height / 2, x - X + currDimension.width / 2, y + Y + currDimension.height / 2);
			} else {
				node.data.setBounds(x + X, y + Y, width, Node.TEXT_HEIGHT);
				// node.p = new Points(x + 40, y + 20, x + X + 20, y + Y + 20);
				node.p = new Points(x + preDimension.width, y + preDimension.height / 2, x + X + currDimension.width / 2, y + Y + currDimension.height / 2);
			}
		}

		reArrangeNode(node.left, node, X / 2);
		reArrangeNode(node.right, node, X / 2);
	}

	public static void main(String arg[]) {
		BSTVisualization bst = new BSTVisualization();

		bst.add(500);
		bst.add(250);
		bst.add(350);
		bst.add(200);
		bst.add(750);
		bst.add(1000);
		bst.add(700);
		bst.add(740);
	}
}