public class DPEnumeration {
	//smallest relation on right side
	//highest relation nr on left side
	static String[] strEdges = 
	{"00011",
	 "00101",
	 "01001",	 
	 "10010",
	 "01100",
	 "10100",
	 "11000"
	};
	
	static int[] edges;
	static int relations;
	
	static int[] getEdges() {
		int[] edges = new int[strEdges.length];
	
		for(int i = 0; i < strEdges.length; i++) { 
			edges[i] = Integer.parseInt(strEdges[i], 2);		
		}	
		
		return edges;
	}
	
	static int getRelations() {
		int r = 0;
		int[]e = getEdges();
		for(int i = 0; i < e.length; i++)
			r = r | e[i];
		
		return r;
	}
	
	public static String getRM(int i) {
		String members = "";
		
		if(i<=0)
			return members;
		
		int u = i;
		while(u > 0) {
			int hB = Integer.highestOneBit(u);
			u = u ^ hB;
			members += (int)(Math.log(hB) / Math.log(2));
		}
		return members;
	}

	// finds all relations that are smaller or equal to sequence of in i
	// that are part of relations in w (normally w is the set of all relations)
	// i and w as a bitvector
	private static int B(int i, int w) {
		int rel = 0;
		i = Integer.lowestOneBit(i);
		
		for(int c = 0; c < edges.length; c++) {			
			int lB = Integer.lowestOneBit(edges[c]);
			int hB = Integer.highestOneBit(edges[c]);            
			if(i >= lB && ((lB & w) == lB))
				rel = rel | lB;			
			if(i >= hB && ((hB & w) == hB))
				rel = rel | hB;			
		}			
		return rel;
	}
	
	private static int getNeighbourhood(int r) {
		int n = 0;		
		
		for(int b = r, bc = 0 ; b != 0; b = (b >> 1), bc++) {
			if((b & 1) == 0)
				continue;
			
			int bit = 1 << bc;
			for(int c = 0; c < edges.length; c++) {
				int lB = Integer.lowestOneBit(edges[c]);
				int hB = Integer.highestOneBit(edges[c]);
		
				if(bit == lB)
					n = n | hB;
				if(bit == hB)
					n = n | lB;
			}
		}
		
		// have to delete r itsself from the neighbourhood
		// take set difference
		n = n & (~r);	
		
		return n;
	}
	
	// generates compliments (as S2) of S1
	static void enumerateCmp(int s1) {
		int x = B(s1, relations) | s1;
		int n = getNeighbourhood(s1) & (~x);
		
				
		int u = n;
		while(u > 0) {
			int hB = Integer.highestOneBit(u);
			u = u ^ hB;
			System.out.println("   EnumerateCmp: emiting " + getRM(hB) +  
					" was called with s1 = " + Integer.toBinaryString(s1) + " original neighbourhood " + Integer.toBinaryString(getNeighbourhood(s1)) +					
					" B_min(s1) = x is " + Integer.toBinaryString(B(s1, relations)) + " resulting N " + Integer.toBinaryString(n));
			enumerateCsgRec(hB, x | B(hB, n), false, "");
		}		
	}
	
	static void enumerateCsgRec(int s, int x, boolean csg, String str) {
		str = str + (csg ? "S1: " : "   S2: ");
		
		int n = getNeighbourhood(s) & (~x);
		for(int subSet = n & - n; subSet != 0; subSet = n & (subSet - n)) {
			System.out.println(str + "EnumerateCsgRec: emiting: " + getRM(s | subSet) + " s=" + Integer.toBinaryString(s) + " x=" + Integer.toBinaryString(x) + " real neighbourhood =" +
					getRM(getNeighbourhood(s)) + " n=" + getRM(n) + " resulting subset =" + getRM(subSet));
			if(csg)
				enumerateCmp(s | subSet);
		}
		
		// enumerate all sub sets of n
		for(int subSet = n & - n; subSet != 0; subSet = n & (subSet - n)) {			
			enumerateCsgRec(s | subSet, x | n, csg, "-->");
		}
	}
	
	// basis routine of algorithm csg - cmp
	static void enumerateCsg() {
		for(int i = (int)(Math.log(relations) / Math.log(2)); i >= 0; i--) {
			System.out.println("EnumerateCsg: emiting " + getRM(1 << i) + " calling EnumerateCsgRec(G, " + Integer.toBinaryString(1 << i) 
					+ ", " + Integer.toBinaryString(B(1 << i, relations)) + " =" + getRM(B(1 << i, relations))  + ")");
			enumerateCmp(1 << i);
			enumerateCsgRec(1 << i, B(1 << i, relations), true, "");
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		edges = getEdges();
		relations = getRelations();

		enumerateCsg();
	}
}