/*
 * AllVenn.java
 *
 * Created on June 30, 2009, 8:48 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

/**
 *
 * @author Khalegh
 */
import java.io.*;

public class AllVenn {
    private int n;
    private int [] p;
    private int columns;
    private int [][] dIndex = { {-1, -1, 1, 1}, {-1, 1, -1, 1} };
    private int [] p2;
    private VennList vennList;
    //private int [] samVenn;
    
    /** Creates a new instance of AllVenn */
    public AllVenn(int n) {
        this.n = n;
        columns = ((1 << n) - 2) / n;
        p = new int[n];
        
        p2 = new int[n + 2];
        p2[0] = 1;
        for (int i = 1; i < n + 2; i++) {
            p2[i] = p2[i-1] << 1;
        }
        vennList = new VennList();
        //samVenn = new int[100];
        createFile(getFileName(0), n);
    }
    
    public boolean isVenn(int [][] matrix) {
        //int visited = 0;
        boolean [] gotIt = new boolean[p2[n]];
        
        for (int i = 0; i < gotIt.length; i++) {
            gotIt[i] = false;
        }
        
        int [] rank = new int[n];
        for (int i = 0; i < rank.length; i++) {
            rank[i] = p2[i + 1] - 1;
        }
        
        int [] perm = new int[n];
        for (int i = 0; i< perm.length; i++) {
            perm[i] = i;
        }
        
        for (int sec = 0; sec < n; sec++) {
            for (int col = 0; col < matrix[0].length; col++ ) {
                for (int row = 0; row < n - 1; row++) {
                    if (matrix[row][col] == 1) {
                        swap(row , row + 1, perm);
                        rank[row] += p2[perm[row]] - p2[perm[row + 1]];
                        if (gotIt[rank[row] - 1]) {
                            return false;
                        }
                        gotIt[rank[row] - 1] = true;
                        //visited++;
                    }
                }
            }
        }
        
        return true;
        
    }
    
    public VennList generateAll(){
        int [][] x = new int[n + 1][columns + 2];
        for (int i = 1; i < x.length - 1; i++) {
            for (int j = 1; j < x[i].length / 2; j++) {
                x[i][2 * j - i % 2] = 2;
            }
        }
        
        x[1][1] = 1;
        int [] ones = new int[n-1];
        ones[0] = 0;
        for (int i = 1; i < n-1; i++) {
            ones[i] = BinomialCoeff.biCoeff(n, i + 1) / n;
        }
        findIt(x, ones, 1, 1);
        
        return vennList;
    }
        
    private void findIt(int [][] matrix, int [] ones, int row, int col) {
        if (noExtraOne(ones)) {
            determinePermutation(matrix, p);
            if (isCircular(p)) {
                checkIt(matrix);
            }
            return;
        }
        
        int [][] neighbors = new int[4][2];
        int nLen = 0 ;
        for (int i = 0; i < 4; i++) {
            if (isFeasible(matrix, ones, row + dIndex[0][i], col + dIndex[1][i])) {
                neighbors[nLen][0] = row + dIndex[0][i];
                neighbors[nLen][1] = col + dIndex[1][i];
                nLen++;
            }
        }

        
        for (int nc = 1; nc < p2[nLen]; nc++) {
            int nb = 0;
            int val = nc;
            while (val > 0) {
                int bit = val & 1;
                int nRow = neighbors[nb][0];
                int nCol = neighbors[nb][1];
                if (bit == 0) {
                    if (matrix[nRow][nCol] == 1) {
                        ones[nRow - 1]++;                        
                    }
                }
                else {
                    if (matrix[nRow][nCol] == 2) {
                        ones[nRow - 1]--;
                    }
                }
                matrix[nRow][nCol] = 2 - bit;
                nb++;
                val = val >> 1;
            }
            nb = 0;
            val = nc;
            while (val > 0) {
                int bit = val & 1;
                if ( bit == 1) {
                    int nRow = neighbors[nb][0];
                    int nCol = neighbors[nb][1];
                    int r = matrix.length;
                    int c = matrix[0].length;
                    int [ ] yeks = new int[r - 2];
                    int [][] x = new int[r][c];
                    for (int k = 1; k < r - 1; k++) {
                        yeks[k - 1] = ones[k - 1];
                        for (int l = 1; l < c - 1; l++)
                            x[k][l] = matrix[k][l];
                    }
                    findIt(x, yeks, nRow, nCol);                    
                }
                nb++;
                val = val >> 1;
            }
        }
        
    }
    
    public boolean isFeasible( int [][] matrix, int [] ones, int row, int col) {
        if (matrix[row][col] == 2 && ones[row - 1] > 0) {
            return true;
        }
        return false;
    }
    
    private boolean noExtraOne(int[] ones) {
        for (int i = 0; i < ones.length; i++) {
            if (ones[i] != 0)
                return false;
        }
        return true;
    }
    private boolean isCircular(int [] p){
        int n = p.length;
        int x, cnt;
        x = p[0];
        cnt = 0;
        
        do {
            cnt++;
            x = p[x];
        } while (x != p[0]);
        
        return cnt == n;
    }
    
    private void swap(int i, int j, int[] p) {
        int t = p[i];
        p[i] = p[j];
        p[j] = t;
    }
    
    private void determinePermutation(int [][] mx, int [] p) {
        int n = mx.length;
        int c = mx[0].length;
        for (int i = 0; i < n - 1; i++) {
            p[i] = i;
        }
        
        for (int col = 1; col < c - 1; col++) {
            for (int row = 1; row < n - 1; row++) {
                if (mx[row][col] == 1) {
                    swap(row - 1, row, p);
                }
            }
        }
    }
    
  
    private void checkIt(int [][] matrix) {
       // int [] codes;
        int maxCol = 0;
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 2) {
                    matrix[i][j] = 0;
                }
                if (matrix[i][j] == 1 && j > maxCol) {
                    maxCol = j;
                }
            }
        }
        
        int [][] mx = new int[n - 1][maxCol];
        for (int i = 0; i < mx.length; i++) {
            for (int j = 0; j <  mx[0].length; j++) {
                mx[i][j] = matrix[i + 1][j + 1];
            }
        }
        
        if (isVenn(mx)) {
            Venn venn = new Venn(mx);
            int no = vennList.size();
            venn.setNo(no);
            vennList.add(venn);
            if (venn.getNo() == no) {
                createFile(getFileName(no + 1), n);
                addToFile(getFileName(0), mx);
            }
                addToFile(getFileName(venn.getNo()+ 1), mx);
        }
        
    }    
/*
 Diagrams input/output functions.
 */
    
 private String getFileName(int fileNo) {
     if (fileNo == 0) {
         return "AllVenn.txt";
     }
     else {
         return String.format("Data/Venn_%02d.txt", fileNo);
     }
 }
 
 private void createFile(String fileName, int n) {
        PrintWriter file = null;
        try {
            file = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
        } catch (java.io.IOException e) { } 
        
        file.println(n);
        file.close();
 }
 
 private void addToFile(String fileName, int[][] mx) {
        PrintWriter file = null;
        try {
            file = new PrintWriter(new BufferedWriter(new FileWriter(fileName, true)));
        } catch (java.io.IOException e) { }
        
        file.println(mx[0].length);
        for (int i = 0; i < mx.length; i++) {
            for (int j = 0; j < mx[i].length; j++) {
                file.print(mx[i][j] + " ");
            }
            file.println();
        }
        file.close();
 }
          
}