import java.awt.*;
import java.applet.*;
import java.util.*;

public class AlphaBeta extends Applet{
	DynamicNode topnode;
	Random r;
	int state;
	DoTheDeed doit;
	

	public void start(){
		state = 0;
		r = new Random();
		topnode = new DynamicNode(3,3,0,1000,30, r);
	
	}

	public void paint(Graphics g){
		topnode.drawMe(g);
	}

	public boolean mouseUp(Event e, int x, int y){
		if(state == 0){
			state = 1;
			doit = new DoTheDeed(this, topnode);
			doit.start();
		}
		return true;
	}
	
}

class DoTheDeed extends Thread{
	Applet theApplet;
	DynamicNode top;

	public DoTheDeed(Applet a, DynamicNode t){
		theApplet = a;
		top = t;
	}


	public void run(){
		top.alphabeta(-20, 20, theApplet, 4);
	}
}

abstract class Node{
	int xleft, xright;			// Space allocated for this node
	int yloc;					// Vertical	location
	Color myColor;
	void setLocation(int xl, int xr, int y){					    
		xleft = xl;
		xright = xr;
		yloc = y;
	}

	abstract void drawMe(Graphics g);

	abstract int alphabeta(int a, int b, Applet t, int l);

}

class StaticNode extends Node{
	int value;

	Random r;

	public StaticNode(int xl, int xr, int y, Random r){
	
		value = Math.abs(r.nextInt()%20) - 10;
		setLocation(xl, xr, y);
		myColor = Color.black;
	}

	public void setValue(){
		value = r.nextInt()%20 - 10;
	}

	public int alphabeta(int alpha, int beta, Applet theApplet, int level){
		// Turn red when alphabeta reaches a terminal node
		myColor = Color.red;
  		theApplet.repaint();
		try{
			Thread.sleep(1000);
		}
		catch(InterruptedException e){
		}

		return value;

	}

	public void drawMe(Graphics g){
		g.setColor(myColor);
		int middle = (xleft + xright)/2;
		g.drawRect(middle-10,yloc,20,36);
		g.drawString(" " + value, middle-9, yloc+20);
	}

}
	

class DynamicNode extends Node{
	int alpha, beta;
	int nkids;
	
	boolean shouldShow;		// True if values of alpha and beta should be drawn

	Node child[];

	public DynamicNode(int numberChildren, int level, int xl, int xr, int y, Random r){
		int i;
		myColor = Color.black;
		alpha = -100;
		beta = 100;
		nkids = numberChildren;
		int width = xr-xl;
		setLocation(xl, xr, y);
		if(level > 1){
			child = new DynamicNode[numberChildren];
			for( i = 0; i < numberChildren; i++){
				child[i] = new DynamicNode(numberChildren, level - 1, 
					xl + width * i / numberChildren,
					xl + width * (i + 1) / numberChildren,
					y + 65, r);
			}
		}
		else {
			child = new StaticNode[numberChildren];
			for( i = 0; i < numberChildren; i++){
				child[i] = new StaticNode(xl + width * i / numberChildren,
					xl + width * (i + 1) / numberChildren,
					y + 65, r);
			}
		}
		shouldShow = false;
	}


	int alphabeta(int alphaIn, int betaIn, Applet theApplet, int level){
		int i;
		int retval;
		alpha = alphaIn;
		beta = betaIn;
		// Turn green when alphabeta gets here
		myColor = Color.green;
		shouldShow = true;
		theApplet.repaint();
		try{
			Thread.sleep(1000);
		}
		catch(InterruptedException e){
		}
		for( i = 0; i < nkids; i++){
			retval = child[i].alphabeta(alpha, beta, theApplet, level -1);
			if( level % 2 == 0 && retval > alpha){
				alpha = retval;
				theApplet.repaint();
				try{
					Thread.sleep(1000);
				}
				catch(InterruptedException e){
				}

			}
			else if(level % 2 != 0 && retval < beta){
				beta = retval;
				theApplet.repaint();
				try{
					Thread.sleep(1000);
				}
				catch(InterruptedException e){
				}

			}

			if(alpha >= beta)  {
				// Turn red when we are done here.
				myColor = Color.red;
				theApplet.repaint();
				try{
					Thread.sleep(1000);
				}
				catch(InterruptedException e){
				}


				return (level % 2 == 0) ? alpha : beta;
			}
		}
		// Turn red when we are done here.
		myColor = Color.red;
		theApplet.repaint();
		try{
			Thread.sleep(1000);
		}
		catch(InterruptedException e){
		}

		return (level % 2 == 0) ? alpha : beta;

	}

	public void drawMe(Graphics g){
		int i;
		g.setColor(myColor);
		String s = "alpha ";
		if(shouldShow) s = s + alpha;
		int middle = (xleft + xright)/2;
		g.drawRect(middle-30,yloc,60,50);
		g.drawString(s, middle - 25, yloc+20);
		s = "beta ";
		if(shouldShow)s = s + beta;
		g.drawString(s, middle - 25, yloc+40);
		for( i = 0; i < nkids; i++){
			child[i].drawMe(g);
			g.setColor(Color.black);
			g.drawLine(middle, yloc+50, (child[i].xleft + child[i].xright)/2, child[i].yloc);
		}
	}

}