/*
 * Venn.java
 *
 * Created on August 9, 2009, 11:38 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

/**
 *
 * @author Khalegh
 */
public class Venn implements Comparable{
    
    private int[][] matrix;
    private int n;
    private int [][] codes;
    private int [] gCodes;
    private int length;
    private int no;
    private boolean polarSymmetric = false;
    
    /** Creates a new instance of GrunbamCode */
    public Venn(int [][] x) {
        n = x.length + 1;
        matrix = expandMatrix(x);
        generateCodes(matrix);
        polarSymmetric = isPolar();
        matrix = compressMatrix(matrix);
        no = -1;
    }
    
    private int [][] expandMatrix(int [][] matrix){
        int [][] x;
        int rows = matrix.length;
        int cols = matrix[0].length;
        x = new int[rows][cols * n];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                x[i][j] = matrix[i][j];
            }
        }
        
        for (int k = 1; k < n; k++) {
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    x[i][k*cols + j] = x[i][j];
                }
            }
        }
        return x;
    }
    
    private int [][] compressMatrix(int [][] matrix) {
        int [][] x;
        int rows = matrix.length;
        int cols = matrix[0].length / n;
        x = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                x[i][j] = matrix[i][j];
            }
        }
        
        return x;
    }
    
    private void decreasingSort(int k, int m) {
        int [] temp = new int[length];
        int row, j;
        
        row = k;
        j = 0;
        while (j < length && codes[k][j] == codes[m][j]) {
            j++;
        }
        if (j < length) {
            row = (codes[k][j] > codes[m][j]) ? m : k;
            
            if( row == m ) {
                for( j=0; j<length; j++ ) {
                    temp[j] = codes[m][j];
                }
                for( j=0; j<length; j++ ) {
                    codes[m][j] = codes[k][j];
                }
                for( j=0; j<length; j++ ) {
                    codes[k][j] = temp[j];
                }
            }
        }
    }
    
    private void generateCodes(int [][] x) {
        length = (n-1)*(n-1);
        codes = new int[4][length];
        gCodes = new int[4 * length];
        
        int rows = x.length;
        int cols = x[0].length;
        int [][] lines = new int[rows + 1][cols + 1];
        int innermost = 0;
        boolean touchBottom = false;
        
        for(int i = 0; i <= rows; i++ ) {
            lines[i][0] = i;
        }
        
        for(int j = 0; j < cols; j++ ) {
            for(int i = 0; i < rows; i++ ) {
                if( x[i][j] == 1 ) {
                    lines[i][j+1] = lines[i+1][j];
                    lines[i+1][j+1] = lines[i][j];
                    i++;
                } else {
                    lines[i][j+1] = lines[i][j];
                }
                if( x[rows-1][j] == 0 ) {
                    lines[rows][j+1] = lines[rows][j];
                }
            }
        }
        
        int [] temp = new int[n];
        int k=1;
        while( k < n ) {
            for(int j = 0; j < cols; j++ ) {
                if( x[0][j] == 1 ) {
                    temp[lines[0][(j+1)%cols]] = k % n;
                    k++;
                }
            }
        }
        
        //Relable the lines.
        for(int i=0; i <= rows; i++ ) {
            for(int j=0; j < cols; j++ ) {
                lines[i][j] = temp[lines[i][j]];
            }
        }
        
        int count = 0;
        for(int j = 0; j < cols; j++ ) {
            for(int i = 0; i < rows; i++ ) {
                if( x[i][j] == 1 ) {
                    if( lines[i][j] == 0 )  {
                        codes[0][count++] = lines[i+1][j];
                        if (i == rows-1 && !touchBottom) {
                            touchBottom = true;
                        } else if (!touchBottom) {
                            innermost++;
                        }
                    }
                    if( lines[i+1][j] == 0 )  {
                        codes[0][count++] = lines[i][j];
                        if( !touchBottom ) {
                            innermost++;
                        }
                    }
                    i++;
                }
            }
        }
        
 /* the row 2 of grunbaum enoding is a circular shift of
  * the row 0 of Grunbaum encoding.
  */
        int [] tempCodes = new int[length];
        for (int j = 0; j < length; j++) {
            codes[2][j] = codes[0][(j+innermost+1)%length];
        }
        
  /* by reversing order of strings and do reversing mapping on each bit
   * to get another two rows.
   */
        for (int i=1; i <= rows; i++) {
            temp[i] = rows + 1 - i;
        }
        temp[0] = 0;
        
        for (int i = 0; i < length; i++) {
            tempCodes[i] = temp[codes[0][length-1-i]];
        }
        
        for(int i = 0; i < length; i++ ) {
            codes[1][i] = tempCodes[i];
        }
        
        for(int i = 0; i < length; i++) {
            tempCodes[i] = temp[codes[2][length-1-i]];
        }
        
        for(int i = 0; i < length; i++ ) {
            codes[3][i] = tempCodes[i];
        }
        
        /* sort the Grunbaum encoding */
        decreasingSort( 0, 1 );
        decreasingSort( 2, 3 );
        decreasingSort( 0, 2 );
        decreasingSort( 1, 3 );
        decreasingSort( 1, 2 );
        
        for (int i = 0; i <= 3; i++ ) {
            for (int j = 0; j<length; j++ ) {
                gCodes[j+i*length] = codes[i][j];
            }
        }
    }
    
    private boolean isPolar() {
        for (int i = 0; i < codes[0].length; i++) {
            if (codes[0][i] != codes[1][i] || codes[2][i] != codes[3][i]) {
                return false;
            }
        }
        return true;        
    }
    
    public boolean isPolarSymmetric() {
        
        return polarSymmetric;
        
    }    
    
    public int getCode(int i, int j) {
        return codes[i][j];
    }
    
    public int length() {
        return length;
    }
    
    public void setNo(int number){
        no = number;
    }
    
    public int getNo() {
        return no;
    }
    
    public int [][] getMatrix() {
        return matrix;
    }
    
    public void printCodes() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < codes[i].length; j++) {
                System.out.print(codes[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("-----------------------------------------------------------------------");
    }
       
    public int compareTo(Object venn) throws ClassCastException {
        if (!(venn instanceof Venn))
            throw new ClassCastException("Class is not supported.");
        Venn x = (Venn) venn;
        int i = 0;
        while (i < length && codes[0][i] == x.codes[0][i]) {
            i++;
        }
        if (i == length) {
            return 0;
        }
        
        if (codes[0][i] > x.codes[0][i]) {
            return 1;
        }
        
        return -1;
    }
    
}