import java.awt.*;
import java.applet.Applet;
import java.util.Vector;
import java.util.Hashtable;
import java.util.Enumeration;
import java.math.BigInteger;

public class NetworkApplet extends Applet
{
	final Randomizer 	r = new Randomizer();
	Image 				offscreen;
	public final int	numNodes = 10;
	final Node			nodes[] = new Node[numNodes];

	public void init()
	{		
		offscreen = createImage(200, 200);
		
		Node	temp[] = new Node[numNodes];
		double	distances[] = new double[numNodes];
		
		// Give nodes random initial positions
		for(int k = 0; k < numNodes; k++)
			temp[k] = nodes[k] = new Node(r.nextInt(200) - 1, r.nextInt(200) - 1, k, this);
			
		// Link nodes to nearest neighbors
		for(int k = 0; k < numNodes; k++)
		{
			for(int j = 0; j < numNodes; j++)
				distances[j] = Math.sqrt(Math.pow(nodes[k].x() - temp[j].x(), 2) +
										 Math.pow(nodes[k].y() - temp[j].y(), 2) );
			Sort.sort(distances, temp, 0, numNodes, true);
			
			int numLinks = r.nextInt(3, 4);
			
			for(int i = 1; i <= numLinks; i++)
			{
				nodes[k].link(temp[i], distances[i]);
				temp[i].link(nodes[k], distances[i]);
			}
			
		}
		
		// Start them all up
		for(int k = 0; k < numNodes; k++)
			nodes[k].start();
	
		repaint();
	}
	
	public void update(Graphics g) // Override clearing behavior
	{
		paint(g);
	}
	
	public void paint(Graphics G)
	{
		Graphics g = offscreen.getGraphics();
		g.setClip(0, 0, 200, 200);
		
		g.setColor(Color.white);
		g.fillRect(0, 0, 200, 200);
		
		for(int k = 0; k < numNodes; k++)
			nodes[k].paintMessages(g);
		
		for(int k = 0; k < numNodes; k++)
			nodes[k].paintLinks(g);
		
		for(int k = 0; k < numNodes; k++)
			nodes[k].paintActive(g);
		
		for(int k = 0; k < numNodes; k++)
			nodes[k].paintSelf(g);
			
		G.drawImage(offscreen, 0, 0, null);
	}

}

public class Node extends Thread
{
	final NetworkApplet	network;
	final int			x, y, id;
	Link				active;		// Link currently being transmitted on
	Hashtable			links;		// Links to other processors
	PriorityQueue		times[];	// Estimates of times via various routes
	final Pool			messages = new Pool(new PriorityQueue(new NewerMessage())); // Messages waiting to leave
	final Randomizer 	r = new Randomizer();
	Messager			process;	// The process being run by this node
	
	private class Link
	{
		public Node		neighbor;
		public double	distance;
		
		public Link(Node n, double d)
		{
			neighbor = n;
			distance = d;
		}
	}
	
	private class Message
	{
		public int			destination;
		public final Vector	path = new Vector();	// path taken from origin node
		public long			timestamp;				// time it was queued
		public long			traveltime;				// time it took to reach destination
		public boolean		routed;					// if true, follow path in reverse, else use algorithm
		public Object		data;					// the message itself
		
		public Message(int dest, Object Data)
		{
			destination = dest;
			timestamp = System.currentTimeMillis();
			routed = false;
			data = Data;
		}
	}
	
	private class NewerMessage implements LTEQ
	{
		// Return true if the first message is newer than the second message.
		public boolean lteq( Object first, Object second )
		{
			return ((Message)first).timestamp >= ((Message)second).timestamp;
		}
	}
	
	// Generic messager, does nothing useful
	private class Messager extends Thread
	{
		public void run()
		{
			try
			{
				int dest = r.nextInt(0, network.numNodes-1);
				while (dest == id)
					dest = r.nextInt(0, network.numNodes-1);
				
				// Repeatedly message other nodes, more likely to message last node messaged
				while (true)
				{
					if (r.nextFloat() < .35)
					{
						dest = r.nextInt(0, network.numNodes-1);
						while (dest == id)
							dest = r.nextInt(0, network.numNodes-1);
					}
					messages.release(new Message(dest, null));	
					
					network.repaint();			
					sleep(r.nextInt(1000, 5000));
				}
			}
			catch (InterruptedException e)
			{
				return;
			}
		}
		
		public void accept(Message m)
		{
			// maybe respond to incoming message
			if (r.nextFloat() < 0.5)
				messages.release(new Message(((Integer) m.path.elementAt(0)).intValue(), null));
			network.repaint();
		}	
	}
	
	private class RSAMessage
	{
		int			sourceID;
		boolean		request;
		BigInteger	number;
		BigInteger	pq;
		BigInteger	e0, e1, o0, o1;
	}
	
	private class Server extends Messager
	{
		final Pool	myMessages = new Pool(); // Messages I need to process
	
		public void run()
		{
			try
			{
			
			// Log start time
			long time = System.currentTimeMillis();
			
			// Some constants to work with
			final BigInteger zero = new BigInteger("0");
			final BigInteger one = new BigInteger("1");
			final BigInteger blockSize = new BigInteger("10000");
			
			// Pick two primes to get modulus, another to yield encryption key
			final BigInteger p = new BigInteger("4093");
			final BigInteger q = new BigInteger("1021");
			final BigInteger n = p.subtract(one).multiply(q.subtract(one));
			final BigInteger pq = p.multiply(q);
			final BigInteger e = new BigInteger("8573");
			final BigInteger d = e.modInverse(n);
			
			// Create a message and convert it to 16-bit chunks
			String message="This is the decrypted message.";
			BigInteger original[] = new BigInteger[15];
			for (int k = 0; k < 15; k++)
				original[k] = BigInteger.valueOf(256*(long)message.charAt(2*k) + (long)message.charAt(2*k+1));
			
			// Encrypt the chunks
			BigInteger encrypted[] = new BigInteger[15];
			for (int k = 0; k < 15; k++)
				encrypted[k] = original[k].modPow(e, pq);
				
			BigInteger power = new BigInteger("0");
			RSAMessage m;
				
			while (true)
			{
				m = (RSAMessage) myMessages.acquire();
				
				if (m.request)
				{
					if (power.compareTo(pq) < 1 )
					{
						m.number = power;
						m.pq = pq;
						m.e0 = encrypted[0];
						m.e1 = encrypted[1];
						m.o0 = original[0];
						m.o1 = original[1];
						messages.release(new Message(m.sourceID, m));
						
						power = power.add(blockSize);	
					}
					else
						break; // Exhausted Keyspace, all blocks farmed out
				}
				else
					break; // Someone found the key!
			}
			
			// Flush all requests for blocks
			while (m.request)
				m = (RSAMessage) myMessages.acquire();
			
			power = m.number;
			System.out.println("Decryption key:  " + power);			
			
			// Decrypt using the key we found
			BigInteger decrypted[] = new BigInteger[15];
			for (int k = 0; k < 15; k++)
				decrypted[k] = encrypted[k].modPow(power, pq);
				
			// Extract characters from 16-bit chunks
			StringBuffer output = new StringBuffer(30);
			for (int k = 0; k < 15; k++)
			{
				long t = decrypted[k].longValue();
				output.append((char) (t/256));
				output.append((char) (t%256));
			}
			
			// Output the decoded message
			System.out.println(output);
			
			// Note total time taken
			System.out.println("Time taken:  " + ((System.currentTimeMillis() - time)/1000.0) + " seconds");
			
			}
			catch (InterruptedException e)
			{
				return;
			}
		}
		
		public void accept(Message m)
		{
			myMessages.release(m.data);
		}	
	}
	
	private class Client extends Messager
	{
		final Pool	myMessages = new Pool(); // Messages I need to process
	
		public void run()
		{
			try
			{
				// Some constants to work with
				final BigInteger one = new BigInteger("1");
				final BigInteger blockSize = new BigInteger("10000");
				
				RSAMessage m;
					
				while (true)
				{
					m = new RSAMessage();
					
					m.sourceID = id;
					m.request = true;
					
					messages.release(new Message(0, m));
					
					m = (RSAMessage) myMessages.acquire();
					
					BigInteger power = m.number;
					BigInteger limit = power.add(blockSize);
					synchronized(network)
					{
						System.out.println("Block " + power + " @ Node " + id);
					}
					for (; power.compareTo(limit) < 1 ; power = power.add(one))
					{
						if ((m.e0.modPow(power, m.pq)).compareTo(m.o0) == 0 &&
							(m.e1.modPow(power, m.pq)).compareTo(m.o1) == 0)
						{
							m.number = power;	// the key
							m.request = false;	// this is not a request
							messages.release(new Message(0, m));
							return;				// we're done
						}
					}
				}
			}
			catch (InterruptedException e)
			{
				return;
			}
		}
		
		public void accept(Message m)
		{
			myMessages.release(m.data);
		}	
	}
	
	// Avg time to reach some destination via the given node
	private class Time
	{
		public int 	id;
		public long	time;
		
		public Time (int ID, long TIME)
		{
			id = ID;
			time = TIME;
		}
	}
	
	private class HigherTime implements LTEQ
	{
		// Return true if the first time is larger than the second time.
		public boolean lteq( Object first, Object second )
		{
			return ((Time)first).time >= ((Time)second).time;
		}
	}
	
	public Node(int X, int Y, int ID, NetworkApplet na)
	{
		x = X;
		y = Y;
		id = ID;
		network = na;
		links = new Hashtable();
		times = new PriorityQueue[network.numNodes];
		HigherTime ht = new HigherTime();
		for (int k = 0; k < network.numNodes; k++)
			times[k] = new PriorityQueue(ht);
	}
	
	public int x()
	{
		return x;
	}
	
	public int y()
	{
		return y;
	}
	
	public int id()
	{
		return id;
	}
	
	// Create initial links to other nodes
	public void link(Node n, double distance)
	{
		if (!links.containsKey(new Integer(n.id())))
		{
			links.put(new Integer(n.id()), new Link(n, distance));
			for (int to = 0; to < network.numNodes; to++)
				if (to == n.id())
					times[to].enqueue(new Time(n.id(), 10 * (long) distance)); // almost exact time
				else
					times[to].enqueue(new Time(n.id(), 100 * (long) distance)); // rough approximation of time
		}
	}
	
	// Called by other nodes when transmitting a message to this node
	public void receive(Message m)
	{
		messages.release(m);
	}
	
	// Send a message to another node
	private void transmit(Message m, Link l) throws InterruptedException
	{
		active = l;
		network.repaint();
		sleep(10 * (long) l.distance);	// Simulate transmission time
		l.neighbor.receive(m);
		active = null;
	}
	
	// main loop, passes messages around as needed
	public void run()
	{
		//process = new Messager();
		if (id == 0)
			process = new Server();
		else
			process = new Client();
		process.start();
		try
		{
			while (true)
			{
				Message m;
			
				m = (Message) messages.acquire();
				
				if (m.destination == id)	// if intended for this node
					if (m.routed)			// and it's a response to a previously sent message
					{
						// Synchronize on main applet to prevent multiple threads from
						// interleaving path information, yielding gibberish
						synchronized(network)
						{
							System.out.println( ">> " + id ); // note that we received a response
						}
						
						// Update routing information
						int k = 0;
						// Find where I originally sent it to
						int hop = ((Integer) m.path.elementAt(1)).intValue();
						// Find the correct data in my routing table
						while (((Time) times[m.destination].elementAt(k)).id != hop)
							k++;
						// Copy it out
						Time t = (Time) times[m.destination].elementAt(k);
						// Delete it (need to do this to preserve ordering)
						times[m.destination].removeElementAt(k);
						// Update it via averaging
						t.time = (t.time + m.traveltime) / 2;
						// Restore updated information
						times[m.destination].enqueue(t);
					}
					else // it's for me!
					{						
						m.traveltime = System.currentTimeMillis() - m.timestamp;
						m.routed = true;
						m.destination = ((Integer) m.path.firstElement()).intValue();
						m.path.addElement(new Integer(id));
						
						// Synchronize on main applet to prevent multiple threads from
						// interleaving path information, yielding gibberish
						synchronized(network)
						{
							System.out.print(m.path.elementAt(0));
							for (int k = 1; k < m.path.size(); k++)
								System.out.print( " -> " + m.path.elementAt(k) );
							System.out.println();
						}
						
						m.path.addElement(new Integer(-1)); // Dummy invalid node #
					
						// Have our process deal with the message
						process.accept(m);
						
						// Send back the response time
						messages.release(m);
					}
				else // Not for me, must be passed on
					if (m.routed) // Easy, just send back along path
					{
						// Invariant - last node in path is one I sent it to originally, I am second from end
						m.path.removeElementAt(m.path.size()-1);		// Remove guy I sent it to
						transmit(m, (Link) links.get((Integer) m.path.elementAt(m.path.size()-2)));
					}
					else // Need to find out where to send it
					{
						// Note that it passed through me
						m.path.addElement(new Integer(id));
						// If the destination is my neighbor, send it direct
						if (links.containsKey(new Integer(m.destination)))
							transmit(m, (Link) links.get(new Integer (m.destination)));
						else
						{
							// Non-deterministically choose next node to send to, preferring those that
							// have given lower transmission times to destination in past.  Non-determinism
							// avoids infinite loops and helps explore untried paths
							int l = 0;
							while (r.nextFloat() < .35 && l < times[m.destination].size())
								l++;
							if (l == times[m.destination].size())
								l--;
							Integer hop = new Integer(((Time) times[m.destination].elementAt(l)).id);
							// If it hasn't been there before, send it
							if (m.path.indexOf(hop) == -1)
								transmit(m, (Link) links.get(hop));
							else // If it has, find the one with the lowest transmission time, and send it there
							{
								l = 0;
								while ( l < times[m.destination].size())
								{
									if (m.path.indexOf(new Integer(((Time) times[m.destination].elementAt(l)).id)) == -1)
										break;
									l++;
								}
								if (l == times[m.destination].size()) // if we ran out of links (this packet has been to all)
									transmit(m, (Link) links.get(hop)); // just use the one from above
								else
									transmit(m, (Link) links.get(new Integer(((Time) times[m.destination].elementAt(l)).id))); // else the fastest unused one
							}
						}
					}
				
				network.repaint();
			}
		}
		catch (InterruptedException e)
		{
			return;
		}
	}

	public void paintMessages(Graphics g)
	{
		g.setColor(Color.red);
		final int m = (int) messages.permits();
		g.fillOval(x-1-m, y-1-m, 3+2*m, 3+2*m);
	}
	
	public void paintActive(Graphics g)
	{
		if (active != null)
		{
			g.setColor(Color.pink);
			g.drawLine(x, y, active.neighbor.x(), active.neighbor.y() );
		}
	}
	
	public void paintSelf(Graphics g)
	{
		g.setColor(Color.black);
		g.fillOval(x-1, y-1, 3, 3);
		g.drawString("" + id, x+2, y);
	}
	
	public void paintLinks(Graphics g)
	{		
		g.setColor(Color.gray);
		
		for (Enumeration e = links.elements() ; e.hasMoreElements() ;)
		{
				Link l = (Link) e.nextElement();
                g.drawLine(x, y, l.neighbor.x(), l.neighbor.y() );
		}
	}
}