import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
 * Breadth First Search Implementation for checking block crossing
 * distances of permutations
 * @author Martin Fink
 */
public class BlockCrossings {
	private static boolean monotoneBC = false;
	
	
	/**
	 * Call with parameter describing a permutation, e.g., "2 4 1 3", for computing
	 * the block crossing distance of this permutation.
	 * If called without parameter, all of our gadgets will be checked; this will take
	 * some time
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length > 0) {
			printDistance(args[0]);
		} else {
			checkClauseGadgetNonMonotone();
			checkSmallClauseGadgetNonMonotone();
			checkNegatorGadgetNonMonotone();
			checkVariableGadgetNonMonotone();

			checkClauseGadgetMonotone();
			checkSmallClauseGadgetMonotone();
			checkNegatorGadgetMonotone();
			// needs a lot of RAM (about 5 GB)!
			checkVariableGadgetMonotone();
		}
	}


	/**
	 * Breadth-first search in permutation set starting from identity permutation.
	 * if monotoneBC=true monotone block crossings are used.
	 * @param n length of permutations
	 * @param maxdist stop bfs when all permutations of distance <=maxdist are found;
	 *  permutations not found so far must have larger distance
	 * @return a HashMap with all the distances for permutations of distance <= maxdist
	 */
	private static HashMap<Permutation, Byte> bcBFS(int n, int maxdist) {
		Permutation id = new Permutation(n);
		for (byte i = 0; i < n; i++) {
			id.p[i] = (byte) (i + 1);
		}

		HashMap<Permutation, Byte> perms = new HashMap<Permutation, Byte>();
		LinkedList<Permutation> queue = new LinkedList<Permutation>();

		perms.put(id, (byte) 0);
		queue.addLast(id);

//		long time = System.currentTimeMillis();

		int distreached = 0;

		while (!queue.isEmpty()) {
			Permutation pi = queue.poll();
			int dist = perms.get(pi);

			if (dist > distreached) {
				distreached = dist;
				System.out.println("generated up to dist = " + dist);
			}

			// status message every second
//			if (time <= System.currentTimeMillis() - 1000) {
//				time = System.currentTimeMillis();
//				double perc = (double) queue.size() / (double) perms.size();
//				perc = ((double) Math.round(perc * 1000)) / 10;
//
//				System.err.println("Permutations in Queue: " + queue.size()
//						+ " / Permutations found: " + perms.size() + " ( "
//						+ perc + "%)");
//			}

			// all permutations of distance <= maxdist found; remaining ones
			// have larger distance
			if (dist >= maxdist) {
				break;
			}

			for (int i = 0; i < n - 1; i++) {
				for (int j = i + 1; j < n; j++) {
					for (int k = j + 1; k < n + 1; k++) {
						// BlockMove move = new BlockMove(i, j, k);

						if (monotoneBC && !isReverseMonotone(pi, i, j, k)) {
							break;
						}

						Permutation p = applyMove(pi, i, j, k);
						if (!perms.containsKey(p)) {
							perms.put(p, (byte) (dist + 1));
							queue.addLast(p);
						}
					}
				}
			}
		}

		return perms;
	}

	/**
	 * Check whether a given block move is "reverse monotone", that is,
	 * whether the block move that transforms the permutation back is monotone.
	 * We need this as our BFS starts at the identity and traverses all edges in
	 * opposite direction
	 * @param p current permutation
	 * @param i
	 * @param j
	 * @param k
	 * @return true iff the mvoe is reverse monotone
	 */
	private static boolean isReverseMonotone(Permutation p, int i, int j,
			int k) {
		int max1 = p.p[i];
		int min2 = p.p[j];

		for (int l = i + 1; l < j; l++) {
			if (p.p[l] > max1) {
				max1 = p.p[l];
			}
		}
		for (int l = j + 1; l < k; l++) {
			if (p.p[l] < min2) {
				min2 = p.p[l];
			}
		}

		return (max1 < min2);
	}
	
	/**
	 * Applies a block move on a permutation and outputs the resulting permutation
	 * @param p
	 * @param i
	 * @param j
	 * @param k
	 * @return resulting permutation
	 */
	private static Permutation applyMove(Permutation p, int i, int j, int k) {
		Permutation p2 = new Permutation(p.p.length);
		
		int m = 0;
		
		for (int l = 0; l < i; l++) {
			p2.p[m++] = p.p[l];
		}
		
		for (int l = j; l < k; l++) {
			p2.p[m++] = p.p[l];
		}
		
		for (int l = i; l < j; l++) {
			p2.p[m++] = p.p[l];
		}
		
		for (int l = k; l < p.p.length; l++) {
			p2.p[m++] = p.p[l];
		}
		
		return p2;
	}

	/**
	 * read distance from HashMap
	 * @param perms HashMap of distances
	 * @param p input permutation
	 * @param maxdist distance up to which permutations are contained in the HashMap
	 * @return distance of the permutation, or maxdist, if the permutation is not
	 * contained in the HashMap
	 */
	private static int getDistance(HashMap<Permutation, Byte> perms,
			Permutation p, int maxdist) {
		int d = (byte)(maxdist+1);

		if (perms.containsKey(p)) {
			d = perms.get(p);
		}

		return d;
	}
	
	/**
	 * read distance from HashMap
	 * @param perms HashMap of distances
	 * @param p input permutation
	 * @param maxdist distance up to which permutations are contained in the HashMap
	 * @return distance of the permutation, or maxdist, if the permutation is not
	 * contained in the HashMap
	 */
	private static int getDistance(HashMap<Permutation, Byte> perms, String p, int maxdist) {
		return getDistance(perms, permutationFromString(p), maxdist);
	}
	
	/**
	 * get String representing a permutation
	 * @param p
	 * @return
	 */
	private static String printPerm(Permutation p) {
		if (p.p.length == 0) {
			return "";
		}
		
		String output = "" + p.p[0];
		
		for (int i = 1; i < p.p.length; i++) {
			output += " " + p.p[i];
		}
		
		return output;
	}
	
	/**
	 * Tries to find a 4-tuple of permutations that could be used as a negator given the
	 * precomputed HashMap of distances.
	 * @param n
	 * @param perms precomputed distances
	 */
	private static void checkPermutationsForNegator(int n, HashMap<Permutation, Byte> perms) {
		for (Permutation p : perms.keySet()) {

			for (int i = 0; i < n - 3; i++) {
				for (int j = i + 2; j < n - 1; j++) {
					Permutation p2 = copy(p);
					Permutation p3 = copy(p);
					Permutation p4 = copy(p);

					swap(p2, i);
					swap(p2, j);

					swap(p3, i);

					swap(p4, j);

					int d1 = getDistance(perms, p, n);
					int d2 = getDistance(perms, p2, n);
					int d3 = getDistance(perms, p3, n);
					int d4 = getDistance(perms, p4, n);

					if (d1 == d2 && d1 < d3 && d1 < d4 &&
							p.get(i) < p.get(i + 1)	&& p.get(j) < p.get(j + 1)) {
						// if (d1 == d2 && d1 < d3 && d1 < d4) {
						System.out.println("found quadruple:");
						System.out
								.println(printPerm(p) + " : " + d1 + " steps");
						System.out.println(printPerm(p2) + " : " + d2
								+ " steps");
						System.out.println(printPerm(p3) + " : " + d3
								+ " steps");
						System.out.println(printPerm(p4) + " : " + d4
								+ " steps");
						System.out.println();
					}
				}
			}
		}
	}
	
	/**
	 * Tries to find an 8-tuple of permutations that could be used for the variable gadget
	 * given the precomputed HashMap of distances.
	 * @param n
	 * @param perms precomputed distances
	 */
	private static void checkPermutationsForVariableGadget(int n, HashMap<Permutation, Byte> perms) {
		for (Permutation p : perms.keySet()) {

			for (int i = 0; i < n - 5; i++) {
				for (int j = i + 2; j < n - 3; j++) {
					for (int k = j + 2; k < n - 1; k++) {
						Permutation p2 = copy(p);
						Permutation p3 = copy(p);
						Permutation p4 = copy(p);
						Permutation p5 = copy(p);
						Permutation p6 = copy(p);
						Permutation p7 = copy(p);
						Permutation p8 = copy(p);

						swap(p2, i);
						swap(p2, j);
						swap(p2, k);

						swap(p3, i);
						swap(p4, j);
						swap(p5, k);
						
						swap(p6,j);
						swap(p6,k);
						swap(p7,i);
						swap(p7,k);
						swap(p8,i);
						swap(p8,j);

						int d1 = getDistance(perms, p,  n);
						int d2 = getDistance(perms, p2, n);
						int d3 = getDistance(perms, p3, n);
						int d4 = getDistance(perms, p4, n);
						int d5 = getDistance(perms, p5, n);
						int d6 = getDistance(perms, p6, n);
						int d7 = getDistance(perms, p7, n);
						int d8 = getDistance(perms, p8, n);

						if (d1 == d2 && d1 < d3 && d1 < d4 && d1 < d5 && d1 < d6 && d1 < d7 && d1 < d8) {
							System.out.println("found 8-tuple:");
							System.out.println(printPerm(p ) + " : " + d1 + " steps");
							System.out.println(printPerm(p2) + " : " + d2 + " steps");
							System.out.println(printPerm(p3) + " : " + d3 + " steps");
							System.out.println(printPerm(p4) + " : " + d4 + " steps");
							System.out.println(printPerm(p5) + " : " + d5 + " steps");
							System.out.println(printPerm(p6) + " : " + d6 + " steps");
							System.out.println(printPerm(p7) + " : " + d7 + " steps");
							System.out.println(printPerm(p8) + " : " + d8 + " steps");
							System.out.println();
						}
					}
				}
			}
		}
	}
	
	/**
	 * Tries to find an 8-tuple of permutations that could be used for the clause gadget (3 variables)
	 * given the precomputed HashMap of distances.
	 * @param n
	 * @param perms precomputed distances
	 */
	private static void checkPermutationsForClauseGadget(int n, HashMap<Permutation, Byte> perms) {
		for (Permutation p : perms.keySet()) {

			for (int i = 0; i < n - 5; i++) {
				if (p.get(i) < p.get(i+1)) {
					break;
				}
				for (int j = i + 2; j < n - 3; j++) {
					if (p.get(j) < p.get(j+1)) {
						break;
					}
					for (int k = j + 2; k < n - 1; k++) {
						if (p.get(k) < p.get(k+1)) {
							break;
						}
						
						Permutation p2 = copy(p);
						Permutation p3 = copy(p);
						Permutation p4 = copy(p);
						Permutation p5 = copy(p);
						Permutation p6 = copy(p);
						Permutation p7 = copy(p);
						Permutation p8 = copy(p);

						swap(p2, i);
						swap(p2, j);
						swap(p2, k);

						swap(p3, i);
						swap(p4, j);
						swap(p5, k);
						
						swap(p6,j);
						swap(p6,k);
						swap(p7,i);
						swap(p7,k);
						swap(p8,i);
						swap(p8,j);

						int d1 = getDistance(perms, p,  n);
						int d2 = getDistance(perms, p2, n);
						int d3 = getDistance(perms, p3, n);
						int d4 = getDistance(perms, p4, n);
						int d5 = getDistance(perms, p5, n);
						int d6 = getDistance(perms, p6, n);
						int d7 = getDistance(perms, p7, n);
						int d8 = getDistance(perms, p8, n);

						if (d1 > d2 && d2 == d3 && d2 ==  d4 && d2 == d5 && d2 == d6 && d2 == d7 && d2 == d8) {
							System.out.println("found 8-tuple:");
							System.out.println(printPerm(p ) + " : " + d1 + " steps");
							System.out.println(printPerm(p2) + " : " + d2 + " steps");
							System.out.println(printPerm(p3) + " : " + d3 + " steps");
							System.out.println(printPerm(p4) + " : " + d4 + " steps");
							System.out.println(printPerm(p5) + " : " + d5 + " steps");
							System.out.println(printPerm(p6) + " : " + d6 + " steps");
							System.out.println(printPerm(p7) + " : " + d7 + " steps");
							System.out.println(printPerm(p8) + " : " + d8 + " steps");
							System.out.println();
						}
					}
				}
			}
		}
	}
	
	/**
	 * swap two neighboring positions in permutation
	 * @param pi
	 * @param i
	 */
	private static void swap(Permutation pi, int i) {
		byte temp = pi.get(i);
		pi.p[i] = pi.get(i+1);
		pi.p[i+1] = temp;
	}
	
	
	/**
	 * Reads a permutation from a String.
	 * @param sp
	 * @return
	 */
	private static Permutation permutationFromString(String sp) {
		StringTokenizer t = new StringTokenizer(sp, " ");
		Permutation pi = new Permutation(t.countTokens());
		int i = 0;
		while (t.hasMoreTokens()) {
			pi.p[i++] = Byte.parseByte(t.nextToken());
		}
		
		return pi;
	}

	/**
	 * Copy permutation.
	 * @param p
	 * @return
	 */
	private static Permutation copy(Permutation p) {
		Permutation p2 = new Permutation(p.p.length);
		for (int i = 0; i < p.p.length; i++) {
			p2.p[i] = p.p[i];
		}
		return p2;
	}
	
	/**
	 * Tries to find permutations for the negator gadget for monotone block crossings.
	 */
	private static void findNegatorGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 6
		// permutations that are not found have distances >= 7
		HashMap<Permutation, Byte> distances = bcBFS(10, 6);
		checkPermutationsForNegator(10, distances);
	}
	
	/**
	 * Tries to find permutations for the variable gadget for monotone block crossings.
	 */
	private static void findVariableGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 7
		// permutations that are not found have distances >= 8
		HashMap<Permutation, Byte> distances = bcBFS(11, 7);
		checkPermutationsForVariableGadget(11, distances);
	}	
	
	/**
	 * Tries to find permutations for the clause gadget for monotone block crossings.
	 */
	private static void findClauseGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(6, 4);
		checkPermutationsForClauseGadget(6, distances);
	}
	
	/**
	 * Tries to find permutations for the negator gadget for nonmonotone block crossings.
	 */
	private static void findNegatorGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(7, 4);
		checkPermutationsForNegator(7, distances);
	}
	
	/**
	 * Tries to find permutations for the variable gadget for nonmonotone block crossings.
	 */
	private static void findVariableGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(7, 4);
		checkPermutationsForVariableGadget(7, distances);
	}
	
	/**
	 * Tries to find permutations for the clause gadget for monotone block crossings.
	 */
	private static void findClauseGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(6, 4);
		checkPermutationsForClauseGadget(6, distances);
	}
	
	/**
	 * Checks the distances of the permutations used for our clause gadget
	 * with monotone block crossings.
	 */
	private static void checkClauseGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(6, 4);
		printDistance(distances, "3 1 5 2 6 4", 6);
		printDistance(distances, "3 1 5 2 4 6", 6);
		printDistance(distances, "3 1 2 5 6 4", 6);
		printDistance(distances, "3 1 2 5 4 6", 6);
		printDistance(distances, "1 3 5 2 6 4", 6);
		printDistance(distances, "1 3 5 2 4 6", 6);
		printDistance(distances, "1 3 2 5 6 4", 6);
		printDistance(distances, "1 3 2 5 4 6", 6);
	}
	
	/**
	 * Checks the distances of the permutations used for the 2-port version
	 * of our clause gadget with monotone block crossings.
	 */
	private static void checkSmallClauseGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(4, 2);
		printDistance(distances, "3 1 4 2", 4);
		printDistance(distances, "3 1 2 4", 4);
		printDistance(distances, "1 3 4 2", 4);
		printDistance(distances, "1 3 2 4", 4);
	}
	
	/**
	 * Checks the distances of the permutations used for our clause gadget
	 * with nonmonotone block crossings.
	 */
	private static void checkClauseGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(6, 4);
		printDistance(distances, "3 1 5 2 6 4", 6);
		printDistance(distances, "3 1 5 2 4 6", 6);
		printDistance(distances, "3 1 2 5 6 4", 6);
		printDistance(distances, "3 1 2 5 4 6", 6);
		printDistance(distances, "1 3 5 2 6 4", 6);
		printDistance(distances, "1 3 5 2 4 6", 6);
		printDistance(distances, "1 3 2 5 6 4", 6);
		printDistance(distances, "1 3 2 5 4 6", 6);
	}
	
	/**
	 * Checks the distances of the permutations used for the 2-port version
	 * of our clause gadget with nonmonotone block crossings.
	 */
	private static void checkSmallClauseGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(4, 2);
		printDistance(distances, "3 1 4 2", 4);
		printDistance(distances, "3 1 2 4", 4);
		printDistance(distances, "1 3 4 2", 4);
		printDistance(distances, "1 3 2 4", 4);
	}
	
	/**
	 * Checks the distances of the permutations used for our negator gadget
	 * with monotone block crossings.
	 */
	private static void checkNegatorGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 6
		// permutations that are not found have distances >= 7
		HashMap<Permutation, Byte> distances = bcBFS(10, 6);
		printDistance(distances, "4 8 1 6 9 2 5 10 3 7", 8);
		printDistance(distances, "4 8 1 9 6 5 2 10 3 7", 8);
		printDistance(distances, "4 8 1 6 9 5 2 10 3 7", 8);
		printDistance(distances, "4 8 1 9 6 2 5 10 3 7", 8);
	}
	
	/**
	 * Checks the distances of the permutations used for our negator gadget
	 * with nonmonotone block crossings.
	 */
	private static void checkNegatorGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(7, 4);
		printDistance(distances, "3 1 6 4 7 2 5", 6);
		printDistance(distances, "3 6 1 4 7 5 2", 6);
		printDistance(distances, "3 1 6 4 7 5 2", 6);
		printDistance(distances, "3 6 1 4 7 2 5", 6);
	}

	/**
	 * Checks the distances of the permutations used for our variable gadget
	 * with monotone block crossings.
	 */
	private static void checkVariableGadgetMonotone() {
		monotoneBC = true;
		// compute distances up to 7
		// permutations that are not found have distances >= 8
		HashMap<Permutation, Byte> distances = bcBFS(11, 7);
		printDistance(distances, "5 9 3 7 10 1 6 11 8 2 4", 9);
		printDistance(distances, "5 9 3 10 7 6 1 11 2 8 4", 9);
		printDistance(distances, "5 9 3 7 10 1 6 11 2 8 4", 9);
		printDistance(distances, "5 9 3 7 10 6 1 11 8 2 4", 9);
		printDistance(distances, "5 9 3 7 10 6 1 11 2 8 4", 9);
		printDistance(distances, "5 9 3 10 7 1 6 11 8 2 4", 9);
		printDistance(distances, "5 9 3 10 7 1 6 11 2 8 4", 9);
		printDistance(distances, "5 9 3 10 7 6 1 11 8 2 4", 9);
	}	

	/**
	 * Checks the distances of the permutations used for our variable gadget
	 * with nonmonotone block crossings.
	 */
	private static void checkVariableGadgetNonMonotone() {
		monotoneBC = false;
		// compute distances up to 4
		// permutations that are not found have distances >= 5
		HashMap<Permutation, Byte> distances = bcBFS(7, 4);
		printDistance(distances, "6 1 4 3 7 5 2", 6);
		printDistance(distances, "6 4 1 7 3 2 5", 6);
		printDistance(distances, "6 1 4 3 7 2 5", 6);
		printDistance(distances, "6 1 4 7 3 5 2", 6);
		printDistance(distances, "6 1 4 7 3 2 5", 6);
		printDistance(distances, "6 4 1 3 7 5 2", 6);
		printDistance(distances, "6 4 1 3 7 2 5", 6);
		printDistance(distances, "6 4 1 7 3 5 2", 6);
	}
	
	private static void printDistance(HashMap<Permutation, Byte> perms, String p, int maxdist) {
		System.out.println("distance of [" + p + "]: " + getDistance(perms, p, maxdist));
	}
	
	private static void printDistance(String string) {
		Permutation pi = permutationFromString(string);
		// largest distance must be smaller than n
		HashMap<Permutation, Byte> distances = bcBFS(pi.p.length, pi.p.length-2);
		printDistance(distances, printPerm(pi), pi.p.length-1);
	}
}

/**
 * Representation of a permutation as an array of bytes.
 * hashCode() is overwritten for ensuring that two objects representing the
 * same permutation are recognized as equal.
 * @author Martin Fink
 *
 */
class Permutation implements Comparable<Permutation> {
	public byte[] p;
	
	public Permutation(int n) {
		p = new byte[n];
	}
	
	public byte get(int i) {
		return p[i];
	}
	
	@Override
	public int hashCode() {
		int hashCode = 1;
		for (int i = 0; i < p.length; i++) {
			hashCode = 31*hashCode + p[i];
		}
        return hashCode;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof Permutation)) {
			return false;
		}
		Permutation p2 = (Permutation) obj;
		if (p2.p.length != p.length) {
			return false;
		}
		for (int i = 0; i < p.length; i++) {
			if (p[i] != p2.p[i]) {
				return false;
			}
		}
		return true;
	}

	@Override
	public int compareTo(Permutation o) {
		if (!(o instanceof Permutation)) {
			return -1;
		}
		Permutation p2 = (Permutation) o;
		if (p2.p.length > p.length) {
			return -1;
		}
		if (p2.p.length < p.length) {
			return 1;
		}
		for (int i = 0; i < p.length; i++) {
			if (p[i] < p2.p[i]) {
				return -1;
			} else if (p[i] > p2.p[i]) {
				return 1;
			}
		}
		return 0;
	}
}

.