///////////////////////////////////////////////////////////////////////
//
//  Arvutiv6rkude kodut66 nr. 1
//  IP paketi liikumine l2bi lyyside
//
//  Risto Erik
//  020452
//  IAPB-21
//  dh@bsd.ee
// 
///////////////////////////////////////////////////////////////////////


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


public class Av extends Applet
{
	public static Font font, smFont;	// 10 pt, 8 pt
	public static Color gray, darkGray;	// 0xe0e0e0, 0xc0c0c0
	public static String statusMsg[];	// 3 rida teksti
	public static int statusId;			// rea number
	public static int W, H;				// appleti laius ja k6rgus
	public static int maxNodes;			// max v6rgu objektide arv (k.a. src ja dst)
	public static int fpos;				// XXX: kasutu vist
	public int last_x, last_y;			// viimane kursori asukoht lohistamisel
	public NetNode tmpNode;				// objekt, kust lohistama hakati
	public Button restartBtn, initBtn, nextBtn;	// nupud
	public static Av avObj;				// viit (vms) staatilistes meetodites mittestaatikale ligi p22semiseks
	public boolean theEnd, order_done;	// a.s.d.f.
	public boolean theEndError;
	public boolean kammkala;

	public NetNode hopNodes[][];
	public int hopNodeCount[];
	public int hopNodePtr[];
	public int hopCount;
	public int hopPtr;
	public Packet thePacket;
	public int packets;

	public int activeLinks[][][];
	public int activeLinkCount; 

	public void printf(String s) { System.out.print(s); }
	public void init()
	{
		Av.avObj = this;
		
		Av.font = new Font("Verdana", Font.PLAIN, 10);
		Av.smFont = new Font("Verdana", Font.PLAIN, 8);
		Av.gray = new Color(0xe0e0e0);
		Av.darkGray = new Color(0xc0c0c0);

		Av.statusMsg = new String[3];
		Av.statusMsg[0] = null;
		Av.statusMsg[1] = null;
		Av.statusMsg[2] = null;
		Av.statusId = 0;

		Av.W = bounds().width;		// deprecated
		Av.H = bounds().height;		// ...

		theEnd = false;
		theEndError = false;
		order_done = false;
		tmpNode = null;
		last_x = last_y = 0;

		hopCount = 0;
		hopPtr = -1;
		Av.fpos = 0;
		thePacket = null;
		packets = 0;
		kammkala = false;

		restartBtn = new Button("Restart");
		initBtn = new Button("Init Network");
		nextBtn = new Button("Next");
		this.add(restartBtn);
		this.add(initBtn);
		this.add(nextBtn);

		String arg = getParameter("maxnodes");
		if (arg != null) {
			try { Av.maxNodes = Integer.parseInt(arg); }
			catch (NumberFormatException e)	{ Av.maxNodes = 12; }
		} else Av.maxNodes = 12;
		
		activeLinks = new int[Av.maxNodes][2][2];
		activeLinkCount = 0;
		
		NetNode.init(this);
	}

	// aDraw* meetodid olid enne clear() meetodis
	public void paint(Graphics g) 
	{
		this.setBackground(Av.gray);
		aDrawGrid(g);
		aDrawLinks(g);
		aDrawNodes(g);
		aDrawStatus(g);
  	}


	public void aDrawStatus(Graphics g)
	{
		int s = 0;

		g.setColor(getBackground());
		g.fillRect(2, Av.H - 38, Av.W - 4, 36);
		g.setFont(Av.smFont);
		if (Av.statusMsg[0] != null) {
			g.setColor(Color.blue);
			g.drawString(Av.statusMsg[0], 4, Av.H - (++s * 10) + 4);
			if (Av.statusMsg[1] != null) {
				g.setColor(Color.black);
				g.drawString(Av.statusMsg[1], 4, Av.H - (++s * 10) + 4);
				if (Av.statusMsg[2] != null)
					g.drawString(Av.statusMsg[2], 4, Av.H - (++s * 10) + 4);
			}
		}
	}

	public void aDrawGrid(Graphics g)
	{
		g.setColor(getBackground());
		g.fillRect(0, 0, Av.W, Av.H);
		g.setColor(Av.darkGray);
		for (int y = 40; y < Av.H; y += 40) {
			for (int x = 40; x < Av.W; x += 40)
				g.drawLine(x, 0, x, Av.H);
			g.drawLine(0, y, Av.W, y);
		}
	}
	
	public void aDrawLinks(Graphics g)
	{
		for (int i = 0; i < NetNode.nodeCount; i++)
			(NetNode.nodes[i]).drawLinks(g);
		g.setColor(Color.yellow);
		for (int i = 0; i < activeLinkCount; i++) {
			g.drawLine(activeLinks[i][0][0], activeLinks[i][0][1], activeLinks[i][1][0], activeLinks[i][1][1]);
			g.drawLine(activeLinks[i][0][0]-1, activeLinks[i][0][1], activeLinks[i][1][0]-1, activeLinks[i][1][1]);
		}
	}

	public void aDrawNodes(Graphics g)
	{
		g.setFont(Av.font);
		for (int i = 0; i < NetNode.nodeCount; i++)
			(NetNode.nodes[i]).drawNode(g);
	}

	public void showShortestPath()
	{
		NetNode n = NetNode.findNode("DST");
		int i = 0;
		NetNode src, dst;
		Graphics g = getGraphics();
		String str = null;

		if (kammkala) return;
		kammkala = true;

		activeLinkCount = 0;
		if (n.packet.nodeCount < 1) {
			Av.status("[BUG] MINGI ILGELT VASTIK BUG ON V6RGUS!");
			return;
		}
		// printf("Shortest path:\n");

		g.setColor(Color.yellow);
		src = n.packet.nodes[0];
		str = "Lyhim tee: SRC -> ";
		for (i = 1; i < n.packet.nodeCount; i++) {
			dst = n.packet.nodes[i];
			// printf("> "+ (i+1) +": "+ src.getName()+" -> "+ dst.getName() +"\n");
			str += dst.getName() +" -> ";
			activeLinks[i-1][0][0] = src.getRealX();
			activeLinks[i-1][0][1] = src.getRealY();
			activeLinks[i-1][1][0] = dst.getRealX();
			activeLinks[i-1][1][1] = dst.getRealY();
			// g.drawLine(src.getRealX(), src.getRealY(), dst.getRealX(), dst.getRealY());
			// g.drawLine(src.getRealX(), src.getRealY()-1, dst.getRealX(), dst.getRealY()-1);
			src = n.packet.nodes[i];
		}
		dst = n;
		str += " DST  ("+ (i - 1);
		if ((i - 1) > 1) str += " hypet)";
		else str += " hype)";
		Av.status(str);
		activeLinks[i-1][0][0] = src.getRealX();
		activeLinks[i-1][0][1] = src.getRealY();
		activeLinks[i-1][1][0] = dst.getRealX();
		activeLinks[i-1][1][1] = dst.getRealY();
		activeLinkCount = i;
		// printf("> "+ (i+1) +": "+ src.getName()+" -> "+ dst.getName() +"\n");
		// g.drawLine(src.getRealX(), src.getRealY(), dst.getRealX(), dst.getRealY());
		// g.drawLine(src.getRealX(), src.getRealY()-1, dst.getRealX(), dst.getRealY()-1);

		// printf("Total packets sent: "+ packets +"+, useful packets: "+ i +", useless: "+ (packets - i) +"+\n");
		str = "Saadeti vahemalt "+ packets +" paketti, neist kasulikke oli "+ i +" ja kasutuid";
		if ((packets - i - 1) > 1) str += " v2hemalt "+ (packets - i - 1);
		else str += " 0";
		Av.status(str);
		// printf("\n");
		paint(g);
	}

	public static void status(String msg)
	{
		if (msg == null) return;
		if (Av.statusMsg[0] != null) {
			if (Av.statusMsg[1] != null)
				Av.statusMsg[2] = Av.statusMsg[1];
			Av.statusMsg[1] = Av.statusMsg[0];
		}
		Av.statusMsg[0] = "("+ Av.statusId +") "+ msg;
		Av.statusId++;
		Av.avObj.paint(Av.avObj.getGraphics());
	}

	public void progress(String msg)
	{
//		Graphics g = getGraphics();
//		FontMetrics fm;
//		int h, w;
//		
//		if (msg == null) return;
//		g.setColor(Color.black);
//		g.setFont(Av.smFont);
//		fm = g.getFontMetrics();
//		w = fm.stringWidth(msg);
//		h = fm.getHeight();
//		g.setColor(Av.gray);
//		g.fillRect(2, ((Av.fpos) * h) + 2, w + 2, h);
//		g.setColor(Color.black);
//		g.drawString(msg, 2, ((Av.fpos + 1) * h) + 2);
//		Av.fpos++; 
//		paint(getGraphics());
	}

	public boolean action(Event e, Object obj)
	{
		if (e.target == restartBtn) doRestart(); 
		else if (e.target == nextBtn) doNext();
		else if (e.target == initBtn) doInit();
		else return false;
		return true;
	}

	public boolean mouseDrag(Event e, int x, int y)
	{
		Graphics g = getGraphics();

		if (order_done) return false;

		g.setColor(Av.darkGray);
		g.drawLine(x, y, last_x, last_y);
		last_x = x;
		last_y = y;

		return true;
	}

	public boolean mouseDown(Event e, int x, int y)
	{
		Graphics g = getGraphics();
		int xc, yc;
		NetNode n;

		if (order_done) return false;

		last_x = x;
		last_y = y;
		xc = x / 40;
		yc = y / 40;
		if ((x % 40) > 20) xc++;
		if ((y % 40) > 20) yc++;

		n = NetNode.findNode(xc, yc);
		if (n == null) {
			n = new NetNode(NetNode.NetNodeId++, NetNode.GW, xc, yc);
			NetNode.addNode(n);
			tmpNode = null;
			paint(g);
		} else if (tmpNode == null) tmpNode = n;
		
		return true;
	}

	public boolean mouseUp(Event e, int x, int y)
	{
		Graphics g = getGraphics();
		int xc, yc;
		NetNode n;

		if (order_done) return false;
		last_x = x;
		last_y = y;
		xc = x / 40;
		yc = y / 40;
		if ((x % 40) > 20) xc++;
		if ((y % 40) > 20) yc++;

		n = NetNode.findNode(xc, yc);
		if (n != null && tmpNode != null) {
			if (NetNode.connectNodes(tmpNode, n))
				status("Connected node "+ tmpNode.getName() +" with "+ n.getName());
			tmpNode = null;
			paint(g);
			return true;
		}
		
		paint(g);
		return false;
	}

	//
	//
	//
	//
	//

	public void doRestart()
	{
		NetNode.clean();
		NetNode.init(this);
		for (int i = 0; i < 3; i++)
			Av.statusMsg[i] = null;
		Av.statusId = 0;
		tmpNode = null;
		Av.fpos = 0;
		last_x = last_y = 0;
		theEnd = false;
		theEndError = false;
		order_done = false;
		activeLinkCount = 0;
		thePacket = null;
		packets = 0;
		kammkala = false;

		paint(getGraphics());
		Av.status("[restarted]");
	}

	public void doNext()
	{
		Graphics g = getGraphics();
		NetNode nodes[] = new NetNode[NetNode.nodeCount];
		NetNode n;
		int count = 0, i;
		
		while (true) {
			if (theEnd) {
				if (!theEndError)
					showShortestPath();
				return;
			}

			if (hopNodePtr[hopPtr] >= hopNodeCount[hopPtr])
				hopPtr++;
		
			if (hopPtr >= hopCount) {
				Av.status("V6rk on vigane.. SRC pole DST'ga yhendatud!");
				theEnd = true;
				theEndError = true;
				return;
			}

			paint(g);
			n = hopNodes[hopPtr][(hopNodePtr[hopPtr])];
			if (n.startFlood(g, n.packet)) {
				(hopNodePtr[hopPtr])++;
				return;
			}
			(hopNodePtr[hopPtr])++;
		}
	}

	public void doInit() 
	{
		NetNode n;

		if (!order_done) {
			travelOrder();
			order_done = true;
			for (int i = 0; i < hopCount; i++)
				hopNodePtr[i] = 0;
			hopPtr = 0;
			n = NetNode.findNode("SRC");
			Av.status("Created packet for SRC");
			n.packet = new Packet(this);
		}
	}

	public void travelOrder()
	{
		NetNode n;
		int i, count;

		n = NetNode.findNode("SRC");

		n.hops = 0;
		for (i = 0; i < n.linkCount; i++) (n.links[i]).hops = 1;
		for (i = 0; i < n.linkCount; i++) order(n.links[i], 2);

		Av.fpos = 0;
		hopCount = 0;
		hopPtr = 0;

		hopNodes = new NetNode[maxNodes+1][maxNodes+1];
		hopNodeCount = new int[maxNodes+1];
		hopNodePtr = new int[maxNodes+1];
		
		while (true) {
			System.out.print("maxNodes = "+ maxNodes +" hopCount = "+ hopCount +"\n");
			hopNodeCount[hopCount] = 0;
			count = 0;
			for (i = 0; i < NetNode.nodeCount; i++) {
				n = NetNode.nodes[i];
				if (n.hops == hopCount) {
					hopNodes[hopCount][count++] = n;
					progress(n.getName() +" hops: "+ n.hops);
				}
			}
			hopNodeCount[hopCount] = count;
			if (count == 0) break;
			hopCount++;
		}
		Av.status("travelOrder() done. max hops = "+ hopCount);
		Av.fpos = 0;
		activeLinkCount = 0;
	}

	public void order(NetNode n, int hops)
	{
		NetNode nodes[] = new NetNode[maxNodes];
		int count = 0, i;
		
		for (i = 0; i < n.linkCount; i++) {
			if ((n.links[i]).hops < 0 || (n.links[i]).hops > hops) {
				(n.links[i]).hops = hops;
				nodes[count++] = (n.links[i]);
			}
		}

		for (i = 0; i < count; i++)
			order((nodes[i]), hops + 1);
	}
}



//
//
//
//
//

class NetNode 
{
	public static final int SRC = 0;
	public static final int GW = 1;
	public static final int DST = 2;
	public static int nodeCount;
	public static NetNode nodes[];
	public static Av avObj;
	public static int NetNodeId;
	//
	private int id;
	private int xCoord;
	private int yCoord;
	private int type;
	private Color color;
	private String name;
	//
	public NetNode links[];
	public int linkCount;
	public boolean flooded, dont_flood, ready;
	public int floodedBy[];
	public int floodedByCount;
	public int hops;
	public Av av;
	public Packet packet;

	public NetNode(int nId, int nType, int x, int y)
	{
		av = NetNode.avObj;
		id = nId;
		type = nType;
		xCoord = x;
		yCoord = y;
		hops = -1;
		switch (type) {
			case NetNode.SRC:
				name = new String("SRC");
				color = Color.blue;
				break;
			case NetNode.GW:
				name = new String("GW"+ id);
				color = Color.green;
				break;
			case NetNode.DST:
				name = new String("DST");
				color = Color.red;
				break;
			default: System.exit(1); break;
		}
		links = new NetNode[av.maxNodes];
		linkCount = 0;
		flooded = false;
		dont_flood = false;
		floodedBy = new int[av.maxNodes];
		floodedByCount = 0;
		av.status("Created node with id="+ id +" name="+ name);
	}
	
	public static void init(Av obj)
	{
		NetNode n;

		NetNode.avObj = obj;
		NetNode.nodeCount = 0;
		NetNode.nodes = new NetNode[obj.maxNodes+2];
		NetNode.NetNodeId = 0;
		
		n = new NetNode(NetNode.NetNodeId++, NetNode.SRC, 1, (obj.H / 40) / 2);
		n.flooded = true;
		NetNode.addNode(n);
		
		n = new NetNode(obj.maxNodes + 1, NetNode.DST, (obj.W / 40) - 1, (obj.H / 40) / 2);
		n.dont_flood = true;
		NetNode.addNode(n);
	}

	public static void clean()
	{
		for (int i = 0; i < NetNode.avObj.maxNodes; i++)
			NetNode.nodes[i] = null;
		NetNode.nodeCount = 0;
		NetNode.NetNodeId = 0;
	}

	public static void addNode(NetNode n)
	{
		if (NetNode.nodeCount >= NetNode.avObj.maxNodes) {
			NetNode.avObj.status("Max ("+ NetNode.avObj.maxNodes +") nodes already created");
			return;
		}
		for (int i = 0; i < NetNode.nodeCount; i++) {
			if ((NetNode.nodes[i]).getId() == n.getId()) {
				NetNode.avObj.status("Node with id "+ n.getId() +" already created.");
				return;
			}
		}
		NetNode.nodes[NetNode.nodeCount] = n;
		NetNode.nodeCount++;
	}

	public static NetNode findNode(int id)
	{
		for (int i = 0; i < NetNode.nodeCount; i++) {
			if ((NetNode.nodes[i]).getId() == id)
				return NetNode.nodes[i];
		}
		return null;
	}
	
	public static NetNode findNode(int xc, int yc)
	{
		NetNode n;

		for (int i = 0; i < NetNode.nodeCount; i++) {
			n = NetNode.nodes[i];
			if (n.getX() == xc && n.getY() == yc) return n;
		}
		
		return null;
	}

	public static NetNode findNode(String str)
	{
		for (int i = 0; i < NetNode.nodeCount; i++) {
			if ((NetNode.nodes[i]).getName().equals(str))
				return NetNode.nodes[i];
		}

		return null;
	}
	
	public static boolean connectNodes(String src, String dst)
	{
		NetNode srcNode, dstNode;

		srcNode = findNode(src);
		dstNode = findNode(dst);
		return NetNode.connectNodes(srcNode, dstNode);
	}

	public static boolean connectNodes(NetNode src, NetNode dst)
	{
		if (src == null || dst == null) {
			NetNode.avObj.status("[BUG] src == null || dst == null");
			return false;
		}
		if (src.getId() == dst.getId()) {
			NetNode.avObj.status("Can't connect node "+ src.getName() +" with itself");
			return false;
		}

		if (!src.connectTo(dst) || !dst.connectTo(src))
			return false;
		return true;
	}

    public boolean startFlood(Graphics g, Packet p)
	// public boolean startFlood(Graphics g)
	{
		NetNode n;
		int count = 0;
		String str = null, by = null;
		boolean asdf = false;

		av.printf("FLOODER: "+ name +" :: flooded="+ flooded +" floodedByCount="+ floodedByCount +"\n");

		if (name.equals("DST")) {
			av.progress(name +": THE END");
			// av.status("THE END");
			av.theEnd = true;
			return false;
		}
		
		if (dont_flood) {
			av.progress(name +" won't flood anymore");
			return false;
		}

		if (id == 0) {
			av.progress(name +": START");
		}
		       
		//		else if (linkCount <= 1) {
		//		    // dead end. purge packet
		//		    p.purge();
		//		    return false;
		//		}

		if (!flooded) {
			av.progress(name +": not ready to flood");
			return false;
		}

		str = "[aeg = "+ av.hopPtr +"] "+ getName() +" floodib: ";
		dont_flood = true;

		by = null;
		for (int i = 0; i < linkCount; i++) {
			n = links[i];
			asdf = false;
			for (int j = 0; j < floodedByCount; j++) {
				if (n.getId() == floodedBy[j]) {
					asdf = true;
					if (by == null) {
						NetNode node = NetNode.findNode(floodedBy[0]);
						by = node.getName();
						// av.progress(name +":X: I was flooded by "+ n.getName());
						// Av.status(name +" was already flooded by "+ by +" with this packet");
					}
					av.printf(name +" was already flooded by "+ by +" with this packet\n");			
					break;
				}
			}
			if (asdf) continue;
			av.packets++;

			// av.progress(name +": flooding "+ n.getName());
			g.setColor(Color.yellow);
			g.drawLine(getRealX(), getRealY(), n.getRealX(), n.getRealY());
			g.drawLine(getRealX()-1, getRealY(), n.getRealX()-1, n.getRealY());
			av.activeLinks[count][0][0] = getRealX();
			av.activeLinks[count][0][1] = getRealY();
			av.activeLinks[count][1][0] = n.getRealX();
			av.activeLinks[count][1][1] = n.getRealY();
			n.flooded = true;
			n.floodedBy[n.floodedByCount++] = id;
			if (n.packet == null || n.packet.nodeCount > p.nodeCount + 1) {
				n.packet = p.copy();
				n.packet.addNode(this);
				// av.printf("["+ n.getName() +"] Copying packet: count "+ (n.packet.nodeCount - 1) +" vs "+ p.nodeCount +"\n");
			} else {
				// av.printf("["+ n.getName() +"] NOT copying packet: count "+ (n.packet.nodeCount - 1) +" vs "+ p.nodeCount +"\n");
			}
			if (count == 0) str += "{ "+ n.getName();
			else str += " "+ n.getName();
			count++;
		}
		if (count > 0) str += " }";
		if (by != null) str += ", "+ name +" ise sai paketi "+ by +" poolt";
		if (count == 0) return false;
		av.activeLinkCount = count;
		av.paint(g);
		Av.status(str);
		return true;
	}

	public void drawNode(Graphics g)
	{
		int x = getRealX(), y = getRealY();

		g.setColor(color);
		g.fillOval(x - 4, y - 4, 8, 8);
		g.setColor(Color.black);
		g.drawString(name, x - 10, y - 6);
	}

	public void drawLinks(Graphics g)
	{
		int x = getRealX(), y = getRealY();

		g.setColor(Color.black);
		for (int i = 0; i < linkCount; i++)
			g.drawLine(x, y, (links[i]).getRealX(), (links[i]).getRealY());
	}

	public boolean connectTo(NetNode n)
	{
		if (n.getId() == id) {
			av.status("Can't connect node "+ name +" with itself");
			return false;
		}

		if (linkCount >= av.maxNodes) {
			av.status("Max ("+ av.maxNodes +") link count reached");
			return false;
		}

		for (int i = 0; i < linkCount; i++) {
			if ((links[i]).getId() == n.getId()) {
				av.status("Node "+ n.getName() +" already connected with "+ name);
				return false;
			}
		}
		links[linkCount] = n;
		linkCount++;
		return true;
	}

	public int getId() { return id; }
	public int getX() { return xCoord; }
	public int getY() { return yCoord; }
	public int getRealX() { return xCoord * 40; }
	public int getRealY() { return yCoord * 40; }
	public int getType() { return type; }
	public String getName() { return name; }
}



class Packet
{
    public NetNode nodes[];
    public int nodeCount;
    public Av av;

    // create new Packet 
    public Packet(Av obj) 
    {
		av = obj;
		nodes = new NetNode[obj.maxNodes];
		nodeCount = 0;
    }

    // duplicate packet (p.clone() ?)
    public Packet copy()
    {
		Packet p = new Packet(av);
	
		for (int i = 0; i < nodeCount; i++)
			p.nodes[i] = nodes[i];
		p.nodeCount = nodeCount;

		return p;
    }

    public boolean addNode(NetNode n)
    {
		if (nodeCount >= av.maxNodes) {
			Av.status("[BUG] too many nodes in path!");
			return false;
		}
		for (int i = 0; i < nodeCount; i++) {
			if (nodes[i].getId() == n.getId()) {
				Av.status("Node "+ n.getName() +" already in path!");
				return false;
			}
		}
		nodes[nodeCount++] = n;
		return true;
    }
}