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

public class RandomWalk extends Applet implements Runnable, ActionListener{
	public String getAppletInfo()
		{return "RandomWalk, written by Diego Moriarty Jun98";}
	public String[][] getParameterInfo(){
		String info[][]={
			{"defaultSeparation","integer","Separation from node to node when loaded"}};
		return info;
	}

	Frame f=new Frame("RandomWalk");
	Applet theApplet=this;
	Panel P=new Panel();

	int separation=2,sx=0,sy=0;
	Node m[], trace[];
	CyclerCanvas cyclerCanvas;
	Thread cyclerThread;
	Button moreB,lessB,dockB,improveB,cycleB;
	Label separationL=new Label("");
	Image traceImage;
	final static int shades=127;
	Node middle;
	
	public static void main(String[] args){
		RandomWalk R=new RandomWalk();
		R.createP();
		R.f.add("Center",R.P);
		R.f.setVisible(true);
	}

	public void init(){
		try{separation=Integer.parseInt(getParameter("separation"));}
		catch(NumberFormatException e){}
		createP();
		setLayout(new BorderLayout());
		add("Center",P);
	}
		
	public void createP(){
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		f.setSize(400,250);
		f.setLocation((screen.width-400)/2, (screen.height-250)/2);

		P.setLayout(new BorderLayout());
		cyclerCanvas=new CyclerCanvas();
		cyclerCanvas.addComponentListener(new ComponentAdapter(){
			public void componentResized(ComponentEvent e){
				createMap();
			}
		});
		cyclerCanvas.setBackground(Color.blue);		
		cyclerCanvas.addMouseListener(new MouseAdapter(){
			public void mouseClicked(MouseEvent e){
				if(cyclerThread!=null){cyclerThread.stop();cyclerThread=null;}
				walk(e.getY()/separation*sx+e.getX()/separation);
				cycleB.setEnabled(true);
			}
		});
		cyclerCanvas.addMouseMotionListener(new MouseMotionAdapter(){
			public void mouseDragged(MouseEvent e){
				if(cyclerThread!=null){
					cyclerThread.stop();cyclerThread=null;
					cycleB.setEnabled(true);
					cyclerCanvas.setImage(traceImage);
					trace(middle);
				}
				int x=e.getX(),y=e.getY();
				if(x<0||y<0||x>sx*separation||y>sy*separation) return;
				Node newTrace=m[e.getY()/separation*sx+e.getX()/separation];
				if(trace[newTrace.distance]==newTrace&&trace[newTrace.distance+1]==null)
				return;
				trace(newTrace);
			}
		});
		P.add("Center",cyclerCanvas);
		Panel p=new Panel();
		p.setLayout(new GridBagLayout());
		GridBagConstraints c=new GridBagConstraints();
		c.weightx=1;c.fill=c.HORIZONTAL;
		c.gridwidth=2;
		p.add(dockB=new Button("Float"),c);
		dockB.addActionListener(this);
		p.add(new Label("Separation:"),c);
		c.gridwidth=1;
		p.add(lessB=new Button("<"),c);
		lessB.addActionListener(this);
		separationL.setText(Integer.toString(separation));
		p.add(separationL,c);
		p.add(moreB=new Button(">"),c);
		moreB.addActionListener(this);
		c.gridwidth=2;
		p.add(improveB=new Button("Improve"),c);
		improveB.addActionListener(this);
		c.gridwidth=c.REMAINDER;
		p.add(cycleB=new Button("Cycle"),c);
		cycleB.addActionListener(this);
		
		P.add("South",p);
		
	}

	public void createMap(){
		if(cyclerThread!=null){cyclerThread.stop();cyclerThread=null;}
		int width=cyclerCanvas.getSize().width,height=cyclerCanvas.getSize().height;
		traceImage=P.createImage(width,height);
		sx=(width-1)/separation+1;
		sy=height/separation;
		m=new Node[sy*sx];
		trace=new Node[m.length];
		middle=m[sy/2*sx+sx/2];
		Vector to=new Vector();
		for(int i=0;i<sx*sy;i++)
			m[i]=new Node(separation*(i%sx),separation*(i/sx));
		for(int i=0;i<sx*sy;i++){
			to.removeAllElements();
			if(i%sx<sx-1) to.addElement(m[i+1]);
			if(i%sx>0) to.addElement(m[i-1]);
			if(i/sx<sy-1) to.addElement(m[i+sx]);
			if(i/sx>0) to.addElement(m[i-sx]);
			m[i].to=new Node[to.size()];
			m[i].haveit=new boolean[to.size()];
			for(int j=0;j<to.size();j++) m[i].to[j]=(Node)to.elementAt(j);
		}
		middle=m[sy/2*sx+sx/2];
		cyclerCanvas.setImage(traceImage);
		cycleB.setEnabled(false);
	}

	public void actionPerformed(ActionEvent e){
		Object source=e.getSource();
		if(source==lessB){
			if(separation>1){
				separation-=1;
				separationL.setText(Integer.toString(separation));
				createMap();
			}
		}else if(source==moreB){
			if(separation<40){
				separation+=1;
				separationL.setText(Integer.toString(separation));
				createMap();
			}
		}else if(source==dockB){
			if(dockB.getLabel()=="Dock"){
				f.setVisible(false);
				f.removeAll();
				dockB.setLabel("Float");
				theApplet.add("Center",P);
				validateTree();
			}else{
				theApplet.removeAll();
				dockB.setLabel("Dock");
				f.add("Center",P);
				f.setVisible(true);
			}
		}else if(source==improveB){
			if(cyclerThread!=null){
				cyclerThread.stop();cyclerThread=null;
				cycleB.setEnabled(true);
				cyclerCanvas.setImage(traceImage);
				trace(middle);
			}
			//send a packet that tries to improve on the current path
			//on arrival at a node the packet will be usually sent downstream
			//Once every ten (or so) a risk will be taken by sending it through an alternative node
			//The resulting cost info is sent down (the entrepeneur node can then adjust its tables)
			calcDistances(m);
			for(int i=0;i<m.length;m[i++].gotit=false);
			cyclerCanvas.setImage(traceImage);
			Graphics g=cyclerCanvas.getGraphics();
			Graphics og=traceImage.getGraphics();
			g.setColor(Color.lightGray);
			og.setColor(Color.lightGray);
			//choose a point to improve
			//in the real network this choice would be done by each node, here globally
			Node improve,risk,origin;
			int c=0;while(trace[c++]!=null);
			origin=trace[c-2];
			do{improve=trace[(int)(Math.random()*(c-1))];}
			while(improve.to.length<3); // can't send back, can't send forward
			trace(middle);
			do{risk=improve.to[(int)(Math.random()*improve.to.length)];}
			while(risk==improve.next||risk==improve.from);
			walk(g,og,risk);
			calcDistances(m);
			//after that improve has the old distance, risk is guaranteed to have one also
			//make node improve improve
			if(risk.distance<improve.next.distance){
				//rub old
				g.setColor(Color.white);
				og.setColor(Color.white);
				g.drawLine(improve.x,improve.y,improve.next.x,improve.next.y);
				og.drawLine(improve.x,improve.y,improve.next.x,improve.next.y);
				//repoint
				improve.next=risk;
				g.setColor(Color.lightGray);
				og.setColor(Color.lightGray);
				g.drawLine(improve.x,improve.y,improve.next.x,improve.next.y);
				og.drawLine(improve.x,improve.y,improve.next.x,improve.next.y);
			}
			calcDistances(m);
			trace(origin);
			
		}else if(source==cycleB){
			(cyclerThread=new Thread(RandomWalk.this)).start();
			cycleB.setEnabled(false);
		}
	}			
		
	public void stop(){
		if (cyclerThread!=null) {
			cyclerThread.stop();cyclerThread=null;
			cycleB.setEnabled(false);
			cyclerCanvas.setImage(traceImage);
		}
	}
	
	public void start(){
		if(cyclerThread==null) {(cyclerThread=new Thread(RandomWalk.this)).start();}
	}
	
	public void run(){
		//The only variables needed are shades m and c
		Graphics g=cyclerCanvas.getGraphics();
		Image cyclerImage=P.createImage(cyclerCanvas.getSize().width,cyclerCanvas.getSize().height);
		Graphics og=cyclerImage.getGraphics();
		og.setColor(Color.white);
		og.fillRect(0,0,cyclerCanvas.getSize().width,cyclerCanvas.getSize().height);
		int TT=0,TC=0;
		Color shadeColor[]=new Color[shades];
		for(int t=0;t<shades;t++){
			shadeColor[shades-1-t]=new Color(t*256/shades,t*256/shades,t*256/shades);
		}
		for(int p=0;p<m.length;p++){
			Node n=m[p];
			if(n.next!=null){
				int traceLength=n.distance;
				TT+=traceLength;TC++;
				og.setColor(shadeColor[traceLength%shades]);
				og.drawLine(n.x,n.y,n.next.x,n.next.y);
				g.setColor(shadeColor[traceLength%shades]);
				g.drawLine(n.x,n.y,n.next.x,n.next.y);
			}
		}
//		g.dispose();
//		og.dispose();
		//        try{System.out.println("averagelength="+TT/TC);
		//    }catch(ArithmeticException e){System.out.println("noaveragelength");}
		cyclerCanvas.setImage(cyclerImage);
		
		int[] pixels=new int[cyclerImage.getWidth(null)*cyclerImage.getHeight(null)];
		int rpixels[]=new int[pixels.length];
		try{ new PixelGrabber(cyclerImage,0,0,cyclerImage.getWidth(null)
			,cyclerImage.getHeight(null),pixels,0,cyclerImage.getWidth(null)).grabPixels();
		}catch(InterruptedException ie){}
		Image frame[]=new Image[shades];
		for(int f=0;f<shades;f++){
			int plusBlue=255-256*f/shades, plusGreen=plusBlue<<8, plusRed=plusBlue<<16, pixel;
			for(int i=pixels.length;i-->0;){
				pixel=pixels[i];
				if((pixel=pixels[i])!=0xffffffff )
				rpixels[i]=0xff000000
				|pixel+plusBlue&0x000000ff
				|pixel+plusGreen&0x0000ff00
				|pixel+plusRed&0x00ff0000;
				else rpixels[i]=0xff0000ff;
			}
			frame[f]=P.createImage(new MemoryImageSource(
				cyclerImage.getWidth(null),cyclerImage.getHeight(null)
				,ColorModel.getRGBdefault(),rpixels
				,0,cyclerImage.getWidth(null)));
			try{
				//System.out.println(""+f+" "+shades+" "+Runtime.getRuntime().freeMemory()+" "+Runtime.getRuntime().totalMemory());
//				synchronized(this){wait(1000);}
				cyclerCanvas.setImage(frame[f]);
			}catch(OutOfMemoryError oome){System.out.println("ouch!");
//			}catch(InterruptedException ie){
			}
		}
		
		int f=0;
		Graphics cg=cyclerCanvas.getGraphics();
		while(true){
			cyclerCanvas.img=frame[f];
			try{
				//System.out.println(""+f+" "+shades+" "+Runtime.getRuntime().freeMemory()+" "+Runtime.getRuntime().totalMemory());
//				synchronized(this){wait(2);}
				if(cg!=null) cg.drawImage(cyclerCanvas.img,0,0,null);
			}catch(OutOfMemoryError oome){System.out.println("gee!");
//			}catch(InterruptedException ie){System.out.println("interrupted");
			}
			f=(f+1)%frame.length;
			cyclerThread.yield();
		}
	}	
	
	
	public void walk(int p){
		for(int i=0;i<m.length;m[i++].next=null){
			for(int j=0;j<m[i].to.length;j++) m[i].haveit[j]=false;
			m[i].gotit=false;
		}
		for(int i=0;i<m.length;m[i++].distance=0); // clear distances in map
		for(int i=0;trace[i]!=null;trace[i++]=null);
		Graphics g=cyclerCanvas.getGraphics();
		Graphics og=traceImage.getGraphics();
		g.setColor(Color.white);
		g.fillRect(0,0,cyclerCanvas.getSize().width,cyclerCanvas.getSize().height);
		og.setColor(Color.white);
		og.fillRect(0,0,cyclerCanvas.getSize().width,cyclerCanvas.getSize().height);
		g.setColor(Color.lightGray);
		og.setColor(Color.lightGray);

		Node newTrace=m[p];
		walk(g,og,m[p]);
		
		g.dispose();
		og.dispose();
		calcDistances(m);
		trace(newTrace);
	}
	
	private void walk(Graphics g, Graphics og, Node I){
		Node t;
		int nchoice,free,c;
		Node previous=I;
		while(I!=null&&I!=middle){
			for(c=I.to.length;c-->0;)
				if(I.to[c]==previous) {
					I.haveit[c]=true;
					break;
				}
			if(I.gotit&&previous!=I.next){ //annoying neighbour
				t=previous; // return packet
				previous=I;
				I=t;
			}else{
				if(I.gotit){ //returned
					previous=I.from; //make it look like a query
				}else{ //new query
					g.drawLine(previous.x,previous.y,I.x,I.y);
					og.drawLine(previous.x,previous.y,I.x,I.y);
					if(I.next!=null) break; // found an old path
					I.gotit=true;I.from=previous;
				}
				free=0;
				for(c=0;c<I.haveit.length;c++)
					if(!I.haveit[c]) free++;
				if(free==0){
					I.next=I.from;previous=I;I=I.next; //return packet
				}else{
					do{nchoice=(int)(Math.random()*I.to.length);}
					while(I.haveit[nchoice]);
					I.next=I.to[nchoice];
					I.haveit[nchoice]=true;
					previous=I;
					I=I.next;
				}
			}
		}
		g.drawLine(previous.x,previous.y,I.x,I.y);
		og.drawLine(previous.x,previous.y,I.x,I.y);
	}

	void calcDistances(Node[] m){
		for(int i=0;i<m.length;m[i++].distance=0); // clear distances in map
		for(int p=0;p<m.length;p++){
			int d=0;
			for(Node h=m[p];;d++){
				if(h.distance!=0){d=d+h.distance;break;}
				if((h=h.next)==null) break;
			}
			for(Node h=m[p];h.distance!=d;h.distance=d--,h=h.next);
		}
	}

	public void trace(Node from){
		//tracing from middle is effectively erasing/reseting the trace
		Graphics g=cyclerCanvas.getGraphics();
		//the trace list should end with the from node and a null
		g.setColor(Color.lightGray);
		Node t;
		for(int i=from.distance;(t=trace[i])!=null;trace[i++]=null)
			g.drawLine(t.x,t.y,t.next.x,t.next.y);
		g.setColor(Color.black);
		for(int i=from.distance-1;i>=0&&(t=trace[i])!=from;i--,from=from.next){
			if(t!=null){
				g.setColor(Color.lightGray);
				g.drawLine(t.x,t.y,t.next.x,t.next.y);
				g.setColor(Color.black);
			}
			g.drawLine(from.x,from.y,from.next.x,from.next.y);
			trace[i]=from;
		}
		g.dispose();
	}

}

class CyclerCanvas extends Canvas{
	public Image img;
	public void update(Graphics g){paint(g);}
	public void setImage(Image img){
		this.img=img;
		Graphics g=getGraphics();
		if(g!=null){
			g.drawImage(img,0,0,null);
			g.dispose();
		}
	}        
	public void paint(Graphics g){
		if(img!=null) g.drawImage(img,0,0,this);
	}
	
}


class Node{
	int distance; //not of benefit to the node
	boolean gotit;
	Node from;
	int x,y;
	Node next, to[];
	boolean haveit[]; // it could be optimized out for this model
	// it represents the local knowledge of a node concerning a packet: as far as I know neighbor X have/had it
	Node(int x, int y){this.x=x;this.y=y;}
}