import java.util.ArrayList;
import java.util.HashSet;

class Simulation
{
	// We don't need to steenkin command line arguments, we got constants
	static final int REDS = 1000, BLACKS = 1000, NODES = REDS + BLACKS;
	static final int DEGREE = 10, JOINS = 5, COLUMNS = 20;
	static final int ROUNDS = 100, SWAPS_PER_ROUND = 1000 * 1000;
	static final int SWAP_RESET = 2000;
	static final boolean SHOW_BLACKS = true;
	
	static final int DRIFT_NODES=100;
	static final double DRIFT_PRESSURE=0.1;
	
	ArrayList<Node> reds, blacks, nodes;
	int[] loc = new int[COLUMNS];
	Node r0;
	Node b0;
	
	Simulation()
	{
		// Create two separate networks each covering the whole keyspace
		reds = new ArrayList<Node> (REDS);
		for (int i = 0; i < REDS; i++) reds.add (new Node());
		makeKleinbergNetwork (reds);
		blacks = new ArrayList<Node> (BLACKS);
		for (int i = 0; i < BLACKS; i++) blacks.add (new Node());
		makeKleinbergNetwork (blacks);
		
		// Join the networks at a few randomly chosen points
		for (int i = 0; i < JOINS; i++) {
			Node r = reds.get ((int) (Math.random() * REDS));
			Node b = blacks.get ((int) (Math.random() * BLACKS));
			r.neighbours.add (b);
			b.neighbours.add (r);
		}
		
		// Allow the networks to swap with each other
		nodes = new ArrayList<Node> (NODES);
		nodes.addAll (reds);
		nodes.addAll (blacks);
		
		r0=reds.get(0);
		b0=blacks.get(0);
		
		// See whether the locations become segregated
		for (int i = 0; i < ROUNDS; i++) {
			printLocations();
			swapLocations();
			//incurDrift();
		}
		System.err.println("END");
	}
	
	void printLocations()
	{
		// Print the location distribution of the reds
		for (Node r : reds) loc[(int) (r.location * COLUMNS)]++;
		for (int i = 0; i < COLUMNS; i++) {
			int val=loc[i];
			String padding="   ";
			if (val>=1000)
				padding="";
			else if (val>=100)
				padding=" ";
			else if (val>=10)
				padding="  ";
			System.out.print (padding+loc[i] + "  ");
			loc[i] = 0;
		}
		System.out.println("      reds [0]="+r0.location);
		
		if (SHOW_BLACKS) {
		// Print the location distribution of the blacks
		System.out.print("   ");
		for (Node b : blacks) loc[(int) (b.location * COLUMNS)]++;
		for (int i = 0; i < COLUMNS; i++) {
			int val=loc[i];
			String padding="   ";
			if (val>=1000)
				padding="";
			else if (val>=100)
				padding=" ";
			else if (val>=10)
				padding="  ";
			System.out.print (padding+loc[i] + "  ");
			loc[i] = 0;
		}
		System.out.println("  blacks[0]="+b0.location);
		}
	}
	
	void swapLocations()
	{
		for (int i = 0; i < SWAPS_PER_ROUND; i++) {
			Node a = nodes.get ((int) (Math.random() * NODES));
			Node b = nodes.get ((int) (Math.random() * NODES));
			if (shouldSwap (a, b)) {
				double temp = a.location;
				a.location = b.location;
				b.location = temp;
				/*
				if (Math.random()*SWAP_RESET<1.0)
					a.location=Math.random();
				// */
			}
		}
	}
	
	static double distance (Node a, Node b)
	{
		double x = a.location, y = b.location;
		if (x > y) return Math.min (x - y, y - x + 1.0);
		else return Math.min (y - x, x - y + 1.0);
	}
	
	boolean shouldSwap (Node a, Node b)
	{
		boolean inSameSubnet= (reds.contains(a) == reds.contains(b));
		
		/*much less likely to swap (e.g. routing too far away)
		if (!inSameSubnet && (Math.random()>(JOINS/REDS))) {
			return false;
		}
		// */
		
		double before = 1.0;
		for (Node c : a.neighbours) before *= distance (a, c);
		for (Node d : b.neighbours) before *= distance (b, d);
		
		double after = 1.0;
		for (Node c : a.neighbours) after *= distance (b, c);
		for (Node d : b.neighbours) after *= distance (a, d);
		
		if (after <= before) return true;
		else return Math.random() < before / after;
	}
	
	static void makeKleinbergNetwork (ArrayList<Node> nodes)
	{
		for (Node a : nodes) {
			// Normalise the probabilities
			double norm = 0.0;
			for (Node b : nodes) {
				if (a.location == b.location) continue;
				norm += 1.0 / distance (a, b);
			}
			// Create DEGREE/2 outgoing connections
			for (Node b : nodes) {
				if (a.location == b.location) continue;
				double p = 1.0 / distance (a, b) / norm;
				for (int i = 0; i < DEGREE / 2; i++) {
					if (Math.random() < p) {
						a.neighbours.add (b);
						b.neighbours.add (a);
						break;
					}
				}
			}
		}
	}
	
	public void incurDrift() {
		for (int i = 0; i < DRIFT_NODES/2; i++) {
			//Reds drift right
			Node r = reds.get ((int) (Math.random() * REDS));
			r.location+=DRIFT_PRESSURE;
			if (r.location>1.0)
				r.location-=1.0;
			//Blacks drift left
			Node b = blacks.get ((int) (Math.random() * BLACKS));
			b.location-=DRIFT_PRESSURE;
			if (b.location<0.0)
				b.location+=1.0;
		}		
	}
	
	public static void main (String[] args)
	{
		new Simulation();
	}
	
	static class Node
	{
		HashSet<Node> neighbours = new HashSet<Node>();
		double location = Math.random();
		String id;
	}
}