import java.util.HashSet;

class SimpleRoutingTest
{
	final static int NODES = 1000;
	final static int DEGREE = 10;
	final static int MESSAGES = 10000;
	final static int HTL = 15;
	
	Node[] nodes = new Node [NODES];
	
	public SimpleRoutingTest()
	{
		for (int i = 0; i < NODES; i++)
			nodes[i] = new Node ((double) i / NODES);
		makeKleinbergNetwork();
	}
	
	static int latticeDistance (int a, int b)
	{
		if (a > b) return Math.min (a - b, b - a + NODES);
		else return Math.min (b - a, a - b + NODES);
	}
	
	void makeKleinbergNetwork()
	{
		// Calculate the normalising constant
		double norm = 0.0;
		for (int i = 1; i < NODES; i++)
			norm += 1.0 / latticeDistance (0, i);
		
		// Add DEGREE shortcuts per node, randomly with replacement
		for (int i = 0; i < NODES; i++) {
			for (int j = 0; j < i; j++) {
				double p = 1.0 / latticeDistance (i, j) / norm;
				for (int k = 0; k < DEGREE; k++) {
					if (Math.random() < p) {
						nodes[i].connect (nodes[j]);
						nodes[j].connect (nodes[i]);
						break;
					}
				}
			}
		}
	}
	
	void testForwarding()
	{
		for (int i = 0; i < MESSAGES; i++) {
			Node n = nodes[(int)(Math.random() * NODES)];
			double target = nodes[(int)(Math.random() * NODES)].loc;
			if (Node.TRACE) System.err.print (target + ": ");
			n.forward (target, HTL, new HashSet<Node>());
		}
		for (Node n : nodes) n.printLoad();
	}
	
	public static void main (String[] args)
	{
		new SimpleRoutingTest().testForwarding();
	}
}