// Generic Binary Search Tree with Duplicates in Java

import java.awt.*;
import java.io.*;

public class TreeGUI extends Frame { 
Abs_tree tree;
boolean is_new_tree=true;
Choice tree_kind, element_kind;
TextField input_elem, min_text, max_text;
String nodeValue;
Panel inputPanel;
OutputPanel outputPanel;
Button clear;
Button exit;
Button minButton, maxButton;
int last_x, last_y;

public static void main(String [] x) {
	TreeGUI g = new TreeGUI();
	}

public TreeGUI() {
	Label tree_kind_label, elem_kind_label, input_elem_label;
	Panel input1, input2;

	// set layout of applet to borderlayout
	setLayout(new BorderLayout());

	//create input panel to take input from user.
	inputPanel = new Panel();
	inputPanel.setLayout(new BorderLayout());

	input1 = new Panel();
	tree_kind_label = new Label("Tree Kind:");
	input1.add(tree_kind_label);
	tree_kind = new Choice();
	tree_kind.addItem("Normal Tree");
	tree_kind.addItem("Dup Tree");
	input1.add(tree_kind);
	elem_kind_label = new Label("   Element Kind:");
	input1.add(elem_kind_label);
	element_kind = new Choice();
	element_kind.addItem("Integer");
	element_kind.addItem("String");
	input1.add(element_kind);
	input_elem_label = new Label("   Input value:");
	inputPanel.add(input_elem_label);
	input_elem = new TextField(10);
	input1.add(input_elem);

	input2 = new Panel();
	minButton = new Button("Minimum");
	input2.add(minButton);
	min_text = new TextField(10);
	min_text.setEditable(false);
	input2.add(min_text);
	maxButton = new Button("Maximum");
	input2.add(maxButton);
	max_text = new TextField(10);
	max_text.setEditable(false);
	input2.add(max_text);
	clear = new Button("Clear");
	input2.add(clear);
	exit = new Button("Exit");
	input2.add(exit);

	inputPanel.add("North", input1);
	inputPanel.add("South", input2);

	add("North", inputPanel);

	//create panel to draw the tree (output).
	outputPanel = new OutputPanel();
	add("Center", outputPanel);
	pack();
	setVisible(true);

	// Insert elements one by one
	int[] list = {25, 40, 5, 18, 56, 30, 16, 37, 15, 28, 35, 8};
	
	tree = new Tree(new IntElem(list[0]));
	outputPanel.drawTree(tree);
	
	for (int i=1; i<list.length; i++) {
  	  tree.insert(new IntElem(list[i]));
   	  outputPanel.drawTree(tree);
	}

}

//Actions to perform when the user presses keys

public boolean action(Event e, Object what) { 
  // Exit
  if (e.target.equals(exit))
    { System.exit(0); }
  if (e.target.equals(minButton))
    { if (!is_new_tree) min_text.setText(tree.min().get_value());
      else min_text.setText("");
      return true; 
    }
  if (e.target.equals(maxButton))
	{ if (!is_new_tree) max_text.setText(tree.max().get_value());
	  else max_text.setText("");
	  return true;
	}
  // Clear the output to start on a new tree
  if (e.target.equals(clear))
	{ is_new_tree = true;
	  input_elem.setText("");
	  min_text.setText("");
	  max_text.setText("");
	  outputPanel.clearPanel();
	}
  // On pressing return on input field...
  if (e.target.equals(input_elem))
	{ String s = (String)what;
	  int index = element_kind.getSelectedIndex();

	  //call insert/new with correct element type
	   try {
		if (is_new_tree)
		   {if (index == 0)
		     {if (tree_kind.getSelectedIndex() == 0)
		         tree=new Tree(new IntElem(Integer.parseInt(s)));
		      else tree=new Duptree(new IntElem(Integer.parseInt(s))); 
		     }
		    else {if (tree_kind.getSelectedIndex() == 0)
			      tree=new Tree(new StringElem(s));
			  else tree=new Duptree(new StringElem(s));
			 }
		    is_new_tree = false;
		   } //end of if is_new_tree
		else {if (index==0) 
			 tree.insert(new IntElem(Integer.parseInt(s)));
		      else tree.insert(new StringElem(s));
		     }
		} //end of try

	   catch(Exception exception) 
		{ 
		  input_elem.selectAll();
		  return true;
		}

	   outputPanel.drawTree(tree);
	   input_elem.selectAll();
	   return true;
	} //end of if target.equals(input_elem)

   return true;
   } //end of method action
} //end of class

//The output area, where the tree is drawn
class OutputPanel extends Panel {
Image treeImage;    //buffer to keep the latest tree representation
int imageWidth, imageHeight;

public void paint(Graphics g) {
 if (treeImage == null)
 { Dimension d = this.size(); // Initialize image buffer
   treeImage = createImage(d.width, d.height);
   imageWidth = d.width; imageHeight = d.width;
   Graphics gr = treeImage.getGraphics();
   gr.setColor(getBackground());
   gr.fillRect(0, 0, imageWidth, imageHeight);
   gr.setColor(Color.black);
 }
 g.drawImage(treeImage, 0, 0, this);
 }

public void clearPanel() {
 Graphics g;
 //Clear the image
 g = treeImage.getGraphics();
 g.setColor(getBackground());
 g.fillRect(0, 0, imageWidth, imageHeight);
 g.setColor(Color.black);
 getGraphics().drawImage(treeImage, 0, 0, this);
 }

// draw the tree on the output panel
public void drawTree(Abs_tree tree) {
 Graphics g;
 Dimension d = this.size();
 if (imageWidth != d.width || imageHeight != d.height)
    { treeImage = createImage(d.width, d.height);
      imageWidth = d.width; imageHeight = d.height;
    };
 //Clear the image
 g = treeImage.getGraphics();
 g.setColor(getBackground());
 g.fillRect(0, 0, d.width, d.height);
 g.setColor(Color.black);

 drawNode(g, imageWidth/2, tree, imageWidth/2, 0);
 getGraphics().drawImage(treeImage, 0, 0, this);
 }

private void drawNode(Graphics g, int subtreeW, Abs_tree tree, int x, int y) {
 Abs_tree left, right;
 g.drawString(tree.get_value(), x-10, y+10);
 left = tree.get_left();
 right = tree.get_right();
 if (left != null)
    { g.drawLine(x, y+10, x-subtreeW/2, y+50);
      drawNode(g, subtreeW/2, left, x-subtreeW/2, y+50);
    };
 if (right != null)
    { g.drawLine(x, y+10, x+subtreeW/2, y+50);
      drawNode(g, subtreeW/2, right, x+subtreeW/2, y+50);
    }
 }
}


// **************************************************
// Generic Binary Search Tree with Duplicates in Java
// **************************************************


abstract class Abs_tree {
 public Abs_tree(Element n) { node = n; left = null; right = null;} 
 public void insert(Element n) {
      if (node.equal(n)) count_duplicates();
      else if (node.less_than(n)) 
	 	if (right == null) right = add_node(n);
         	else right.insert(n);
      else if (left == null) left = add_node(n);
              else left.insert(n);
 	} 
	
 public Element min() { 
 	if (left != null) return left.min();
 	else return node;
 	}

 public Element max() { 
 	if (right != null) return right.max();
 	else return node;
 	}

 public void print()   {
 	if (left != null) left.print();
 	this.print_node();
 	if (right != null) right.print();
 	}

 public Abs_tree get_left() {
	 return left;
 }

 public Abs_tree get_right() {
	 return right;
 }

 protected Element node;
 protected Abs_tree left;
 protected Abs_tree right;

 protected abstract void count_duplicates();
 protected abstract Abs_tree add_node(Element n);
 protected abstract void print_node();

 public abstract String get_value();
}

//*************************  Tree   ******************************

class Tree extends Abs_tree {
 public Tree(Element n) {super(n);}
 protected Abs_tree add_node(Element n) {return new Tree(n);}
 protected void count_duplicates() {}
 protected void print_node() { System.out.print(node.get_value() + "  "); }

 public String get_value() { return(node.get_value()); }
}

//************************  Duptree ******************************

class Duptree extends Abs_tree {
 public Duptree(Element n) {super(n); count = 1;}
 protected Abs_tree add_node(Element n) {return new Duptree(n);}
 protected void count_duplicates() {count++;}
 protected void print_node() {
	 System.out.print(node.get_value() + "/" + count + "  ");
 }

 public String get_value() { return(node.get_value() + '/' + count); }

 protected int count;
}

//*********************** Tree Element definitions *******************
interface Element
{
 public boolean equal(Element n);
 public boolean less_than(Element n);
 public String get_value();
}

class IntElem implements Element
{
 private int value;
 public IntElem(int i) { value=i; }
 public boolean equal(Element n) {
	 return(this.value == ((IntElem)n).getValue());
 }
 public boolean less_than(Element n) {
	 return(this.value < ((IntElem)n).getValue());
 }
 public String get_value() { return(String.valueOf(value)); }
 public int getValue() { return value; }
}

class StringElem implements Element
{
 private String value;
 public StringElem(String s) { value=s; }
 public boolean equal(Element n) {
	 return(this.value.equals(((StringElem)n).get_value()));
 }
 public boolean less_than(Element n) {
	 return(value.compareTo(((StringElem)n).get_value()) < 0);
 }
 public String get_value() { return(value); }
}