package verifier;

import java.util.*;


public class Configuration extends BaseClass{

    /**
     * the black edges of the configuration
     * each has a position in the edgeOrder
     */
    class BlackEdge{
        int pos;//its position in the edge order
        private BlackEdge next;
        private BlackEdge prev;
        BlackEdge(int p, BlackEdge pr){
            pos = p;
            next = null;
            setPrev(pr);
        }
        // SET METHODS
        void setPrev(BlackEdge p){
            prev = p;
            if ( prev != null )
                prev.next = this;
        }
        void setNext(BlackEdge n){
            next = n;
            if ( next != null )
            next.prev = this;
        }
        // GET METHODS
        BlackEdge getPrev(){return prev;}
        BlackEdge getNext(){return next;}

        //CHANGE THE DIRECTION OF THE BLACK EDGE
        void changeDirection(){
            BlackEdge tmp = prev;
            prev = next;
            next = tmp;
        }

        //SWAP THE POINTERS BETWEEN THE TWO EDGES
        void swapNextPointers(BlackEdge b){
            BlackEdge tmp = next;
            setNext(b.next);
            b.setNext(tmp);
        }
        void swapPrevPointers(BlackEdge b){
            BlackEdge tmp = prev;
            setPrev(b.prev);
            b.setPrev(tmp);
        }
    }

    /***
     * The order of the black edges on the circle
     * 
     */
    private BlackEdge edgeOrder[];

    /********************************************
     * CONSTRUCTORS
     */
    public Configuration(String str){
        DEBUG(str);
        List createdEdges = new LinkedList();


        // READ ALL BLACK EDGES
        int indexInStr = 0;
        while ( true ){
            indexInStr = str.indexOf('(',indexInStr);
            if ( indexInStr == -1 ) break;
            int startIndex = indexInStr;
            indexInStr = str.indexOf(')',indexInStr);
            
            StringTokenizer tok = new StringTokenizer(str.substring(startIndex+1,indexInStr));

            //start reading the numbers of the cycle
            BlackEdge firstEdge = new BlackEdge(Integer.parseInt(tok.nextToken()),null);
            createdEdges.add(firstEdge);
            BlackEdge prev = firstEdge;
            while ( tok.hasMoreTokens() ){
                prev = new BlackEdge(Integer.parseInt(tok.nextToken()),prev);
                createdEdges.add(prev);
            }
            firstEdge.setPrev(prev);
        }

        //FIX THE EDGE ORDER
        edgeOrder = new BlackEdge[createdEdges.size()];
        Iterator iter = createdEdges.iterator();
        while ( iter.hasNext() ){
            BlackEdge b = (BlackEdge) iter.next();
            edgeOrder[b.pos] = b;
        }

        ASSERTCONFIGURATION();
    }

    public Configuration(Configuration conf){
        this(conf.toString());
        if ( !this.equals(conf) )
            throw new Error("IMPLEMENTATION ERROR:  Copy constructor not correct");
    }


    /******************************
     * NUM BLACK EDGES
     */
    
    public int getNumBlackEdges(){
        return edgeOrder.length;
    }

    /***********************************
     * ASSERTCONFIGURATION
     * To be used to check that the configuration really is
     * a configuration. I.e. that the data structures are correct.
     * It throws an Error if something is wrong.
     * THIS IS CALLED IN EVERY METHOD TO ASSERT
     * THAT THERE ARE NO IMPLEMENTATION ERRORS
     */
    private void ASSERTCONFIGURATION(){

        //1. Check that the position indices are correct
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeOrder[i].pos != i )
                throw new Error("IMPLEMENTATION ERROR:  BlackEdge position incorrect  i="+i+ "  edgeOrder[i].pos "+edgeOrder[i].pos);
        }

        //2. Check that the next and previous pointers are correct
        boolean edgeUsed[] = new boolean[edgeOrder.length];
        
        // Follow all cycle structures
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeUsed[i] ) continue;

            BlackEdge first = edgeOrder[i];
            edgeUsed[first.pos] = true;
            BlackEdge tmp = first.getNext();

            //check pointers correct
            if ( tmp.getPrev() != first )
                throw new Error("IMPLEMENTATION ERROR:  BlackEdge != BlackEdge.getNext().getPrev()");
                
            while ( tmp != first ){
                edgeUsed[tmp.pos] = true;

                //check that edge part of the edgeOrder
                if ( edgeOrder[tmp.pos] != tmp )
                    throw new Error("IMPLEMENTATION ERROR:  edgeOrder[BlackEdge.pos] != BlackEdge");

                //check that pointers correct
                if ( tmp.getNext().getPrev() != tmp )
                    throw new Error("IMPLEMENTATION ERROR:  BlackEdge != BlackEdge.getNext().getPrev()");

                tmp = tmp.getNext();
            }
        }

    }
    
    /*******************************
     * NUM ODD CYCLES
     */
    public int getNumOddCycles(){
        boolean edgeUsed[] = new boolean[edgeOrder.length];

        int numOddCycles = 0;
        // Follow all cycle structures and 
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeUsed[i] ) continue;

            BlackEdge first = edgeOrder[i];
            edgeUsed[first.pos] = true;
            int len = 1;
            BlackEdge tmp = first.getNext();
            while ( tmp != first ){
                edgeUsed[tmp.pos] = true;
                tmp = tmp.getNext();
                len++;
            }

            if ( len % 2 == 1 )
                numOddCycles++;
            
        }

        ASSERTCONFIGURATION();
        return numOddCycles;
    }

    /*******************************
     * GET OPEN GATES
     * Returns the positions of the blackedges
     * for which be.next.pos == be.pos+1
     */
    public int[] getOpenGates(){

        ArrayList edges = new ArrayList();
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeOrder[i].next == edgeOrder[(edgeOrder.length+i-1)%edgeOrder.length] )
                edges.add(edgeOrder[i]);
        }
        int gates[] = new int[edges.size()];
        for ( int i = 0 ; i < gates.length ; i++ )
            gates[i] = ((BlackEdge) edges.get(i)).pos;
        
        ASSERTCONFIGURATION();
        return gates;
    }
    /**************************************
     * TO STRING
     */ 
    public String toString(){
        StringBuffer buff = new StringBuffer();
        
        boolean edgeUsed[] = new boolean[edgeOrder.length];
        
        // Follow all cycle structures and 
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeUsed[i] ) continue;
            buff.append("(");

            BlackEdge first = edgeOrder[i];
            buff.append(""+first.pos);
            edgeUsed[first.pos] = true;

            BlackEdge tmp = first.getNext();
            while ( tmp != first ){
                edgeUsed[tmp.pos] = true;
                buff.append(" "+tmp.pos);
                tmp = tmp.getNext();
            }

            buff.append(")");
            
        }

        ASSERTCONFIGURATION();
        return buff.toString();
    }

    /*****************************
     * IS SIMPLE PERMUTATATION
     * i.e. returns true if all cycles have length
     * <= 3.
     */
    public boolean isSimplePermutation(){
        boolean edgeUsed[] = new boolean[edgeOrder.length];

        // Follow all cycle structures and 
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeUsed[i] ) continue;

            BlackEdge first = edgeOrder[i];
            edgeUsed[first.pos] = true;
            int len = 1;
            BlackEdge tmp = first.getNext();
            while ( tmp != first ){
                edgeUsed[tmp.pos] = true;
                tmp = tmp.getNext();
                len++;
            }

            if ( len > 3 )
                return false;
            
        }

        ASSERTCONFIGURATION();
        return true;
    }


    /*****************************************
     * TRANSPOSE
     */
    public void transpose(int i1, int i2, int i3){

        //make sure that i1 < i2 < i3
        int indices[] = new int[]{i1,i2,i3};
        Arrays.sort(indices);
        i1 = indices[0]; i2 = indices[1]; i3 = indices[2];

        BlackEdge b1 = edgeOrder[i1];
        BlackEdge b2 = edgeOrder[i2];
        BlackEdge b3 = edgeOrder[i3];
        
        //Fix the next and prev pointers.
        b1.swapPrevPointers(b2);
        b2.swapNextPointers(b3);


        //Fix the edge order and the pos variables
        //1. Edges outside the interval [i1,i3] aren't changed
        //2. Edges in position i1 and i3 are not changed.
        //3  All edges in the interval [i1+1,i2] are moved to [i2-i1+i3,i3-1]
        //4. All edges in the interval [i2+1,i3-1] are moved to [i1+1,i2-i1+i3-1]
        BlackEdge newOrder[] = new BlackEdge[edgeOrder.length];
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            //1 and 2
            if ( i <= i1 || i >= i3){
                newOrder[i] = edgeOrder[i];
                continue;
            }
            if ( i == i2 ){
                edgeOrder[i2].pos = i1+(i3-i2);
                newOrder[edgeOrder[i2].pos] = edgeOrder[i2];
                continue;
            }
            //3.
            if ( i < i2 ){
                edgeOrder[i].pos = i+(i3-i2);
                newOrder[edgeOrder[i].pos] = edgeOrder[i];
                continue;
            }

            //4
            if ( i < i3 ){
                edgeOrder[i].pos = i1+i-i2;
                newOrder[edgeOrder[i].pos] = edgeOrder[i];
                continue;
            }

            //shouldn't come here
            throw new Error("IMPLEMENTATION ERROR unexpected index ");
        }

        //Copy the new order into the real order
        System.arraycopy(newOrder,0,edgeOrder,0,edgeOrder.length);

        ASSERTCONFIGURATION();
    }

    /*****************************************
     * EQUALS
     * If the two configurations are exactly the same
     * NOT considering circular shifts and mirroring
     */
    public boolean equals(Configuration conf){

        boolean edgeUsed[] = new boolean[edgeOrder.length];
        
        // Follow all cycle structures and check that the positions are the same
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            if ( edgeUsed[i] ) continue;

            BlackEdge first = edgeOrder[i];
            BlackEdge confFirst = conf.edgeOrder[i];
            edgeUsed[first.pos] = true;

            BlackEdge tmp = first.getNext();
            BlackEdge confTmp = confFirst.getNext();
            while ( tmp != first ){
                edgeUsed[tmp.pos] = true;
                if ( tmp.pos != confTmp.pos )
                    return false;
                tmp = tmp.getNext();
                confTmp = confTmp.getNext();
            }
        }

        conf.ASSERTCONFIGURATION();
        ASSERTCONFIGURATION();
        return true;
    }

    /*****************************************
     * EQUIVALENT EQUALS
     * Checks if the two configurations are equal
     * under circular shift and mirroring
     * If they are then they are equal in a sorting sence
     * according to the Hartman paper.
     */

    public boolean equivalentEquals(Configuration conf){

        //Check all regular shifts
        Configuration cpy = new Configuration(conf);
        int shift = 0;
        do{
            if ( this.equals(cpy) )
                return true;
            cpy.shiftEdgeOrder();
            shift++;
        }while ( shift < edgeOrder.length );

        //Check all shifts of the mirrror
        cpy = new Configuration(conf);
        cpy.mirrorConfiguration();
        shift = 0;
        do{
            if ( this.equals(cpy) )
                return true;
            cpy.shiftEdgeOrder();
            shift++;
        }while ( shift < edgeOrder.length );

        conf.ASSERTCONFIGURATION();
        ASSERTCONFIGURATION();
        return false;
    }

    /*************************************
     * SHIFT EDGE ORDER
     * I.e. circular shift the position of the black edges
     * one step.
     */
    private void shiftEdgeOrder(){
        BlackEdge prev = edgeOrder[edgeOrder.length-1];
        for ( int i = 0 ; i < edgeOrder.length ; i++ ){
            BlackEdge tmp = edgeOrder[i];
            edgeOrder[i] = prev;
            prev.pos = i;
            prev = tmp;
        }
        ASSERTCONFIGURATION();
    }
    /****************************************
     * MIRROR CONFIGURATION
     * I.e. change it into the configuration
     * you get when rotating the circle around the vertical
     * middle.
     * This entails that the direction of the black edges are changed.
     */
    private void mirrorConfiguration(){


        //Change the direction of all black edges.
        //such that be.next becomes be.prev
        for ( int i = 0 ; i < edgeOrder.length ; i++ )
            edgeOrder[i].changeDirection();

        //Change the positions of the edges such that
        //those on the first half ends up on the second half
        //and vice versa.
        int mid = edgeOrder.length/2;
        //if odd length then the edge in position mid is not moved
        for ( int i = 0 ; i < mid ; i++ ){
            int mirrorPos = edgeOrder.length-1-i;
            BlackEdge tmp = edgeOrder[i];
            edgeOrder[i] = edgeOrder[mirrorPos];
            edgeOrder[i].pos = i;
            edgeOrder[mirrorPos] = tmp;
            tmp.pos = mirrorPos;
        }

        
        
        ASSERTCONFIGURATION();
    }



    /*****************************
     * ADD UNORIENTED 3-CYCLE
     * Adds an unoriented 3-cycle before each of the positions
     * it doesn't matter in which order the indices are given
     * the cycle will still be made unoriented.
     */
    public void addUnoriented3Cycle(int p1, int p2, int p3){

        //the new cycle should be oriented so the edges have to
        //occur counter clockwise around the circle i.e p3 >= p2 >= p1
        int indices[] = new int[]{p1,p2,p3};
        Arrays.sort(indices);
        p1 = indices[0];
        p2 = indices[1];
        p3 = indices[2];
        
        BlackEdge newOrder[] = new BlackEdge[edgeOrder.length+3];

        //create the cycle so that it is unoriented
        BlackEdge b1 = new BlackEdge(-1,null);
        BlackEdge b3 = new BlackEdge(-1,b1);
        BlackEdge b2 = new BlackEdge(-1,b3);
        b1.setPrev(b2);

        newOrder[p1] = b1;
        newOrder[p2+1] = b2;
        newOrder[p3+2] = b3;

        //Move the old edges over to the new edge order array
        int ei = 0;
        int enew = 0;
        for ( ; enew < newOrder.length ; enew++ ){
            if (  newOrder[enew] != null ) continue;
            newOrder[enew] = edgeOrder[ei];
            ei++;
        }

        //switch the vectors
        edgeOrder = newOrder;
        
        //update the position variables
        for ( int i = 0 ; i < edgeOrder.length ; i++ )
            edgeOrder[i].pos = i;
        
        ASSERTCONFIGURATION();
    }
    

    /****************************
     * ADD CONFIGURATION
     * Adds the whole configuration in the given positoin
     */
    public void addConfiguration(int p, Configuration conf){

        BlackEdge newOrder[] = new BlackEdge[edgeOrder.length + conf.edgeOrder.length];

        //Create a copy of the conf and add its black edges to the
        //new order.
        Configuration cpy = new Configuration(conf);
        for ( int i = p ; i < p+cpy.edgeOrder.length ; i++ )
            newOrder[i] = cpy.edgeOrder[i-p];

        
        //Move the old edges over to the new edge order array
        int ei = 0;
        int enew = 0;
        for ( ; enew < newOrder.length ; enew++ ){
            if (  newOrder[enew] != null ) continue;
            newOrder[enew] = edgeOrder[ei];
            ei++;
        }

        //switch the vectors
        edgeOrder = newOrder;
        
        //update the position variables
        for ( int i = 0 ; i < edgeOrder.length ; i++ )
            edgeOrder[i].pos = i;
        
        conf.ASSERTCONFIGURATION();
        ASSERTCONFIGURATION();
    }
    /****************************************
     * GET COMPONENTS
     * Returns the an array of arrays
     * int[i][] is the indices of the i'th component
     * ONLY WORKS FOR 3-cycles
     */
    public int[][] getComponents(){

	// STEP 1
	//Get one edge of each cycle to represent the cycle
	BlackEdge cycles[] = new BlackEdge[edgeOrder.length/3];
	int cycleIndex = 0;
	boolean edgeUsed[] = new boolean[edgeOrder.length];
	for ( int i = 0 ; i < edgeOrder.length ; i++ ){
	    if ( edgeUsed[i] ) continue;
	    //all edges of this cycle are used
	    edgeUsed[i] = true;
	    edgeUsed[edgeOrder[i].getNext().pos] = true;
	    edgeUsed[edgeOrder[i].getNext().getNext().pos] = true;
	    //let the first one represent the cycle
	    cycles[cycleIndex++] = edgeOrder[i];
	    //make sure that it is a 3 cycle
	    if ( edgeOrder[i].getNext().getNext().getNext() != edgeOrder[i] ){
		throw new Error("IMPLEMENTATION ERROR:  NOT 3 cycle");
			
	    }
	}
	DEBUG("num cycles: " + cycleIndex);

	// STEP 2
	//Every component is represented with a
	//HashSet of all cycles where each cycle is 
	//represented by its black edge in the cycles array 
	HashMap edge2Component = new HashMap();

	// STEP 3 
	// Initially each cycle is its own component
	for ( int i = 0 ; i < cycles.length ; i++ ){
	    HashSet component = new HashSet();
	    component.add(cycles[i]);
	    edge2Component.put(cycles[i],component);
	}

	// STEP 4
	// Start merging componets
	for ( int i = 0 ; i < cycles.length ; i++ ){
	    BlackEdge cyI = cycles[i];
	    HashSet component = (HashSet)edge2Component.get(cyI);
	    
	    //for the other cycles check if they intersect
	    //if so make sure that the two cycles and their
	    //components become one component
	    for ( int j = i+1 ; j < cycles.length ; j++ ){
		BlackEdge cyJ = cycles[j];
		if ( _3_cyclesIntersects(cyI, cyJ) ){
		    DEBUG("cycles intersect    cyI.pos = " + cyI.pos + "   cyJ.pos = "+cyJ.pos);
		    HashSet J_comp = (HashSet)edge2Component.get(cyJ);
		    //If the components are different merge them
		    if ( component != J_comp ){
			component.addAll(J_comp);
			//update all cycles of J_comp to be part of component
			Iterator iter = J_comp.iterator();
			while ( iter.hasNext() )
			    edge2Component.put(iter.next(), component);
		    }
		}
	    }
	}

	// STEP 5
	// make the array of arrays that represnt the components
	HashSet single_comps = new HashSet(edge2Component.values());
	int components[][] = new int[single_comps.size()][]; 
	
	Iterator compIter = single_comps.iterator();
	int compIndex = 0;
	while ( compIter.hasNext() ){
	    HashSet comp = (HashSet) compIter.next();
	    components[compIndex] = new int[comp.size()*3];//each cycle is 3-cycle

	    Iterator cyIter = comp.iterator();
	    int edgeIndex = 0;
	    while ( cyIter.hasNext() ){
		BlackEdge cy = (BlackEdge) cyIter.next();
		components[compIndex][edgeIndex++] = cy.pos;
		components[compIndex][edgeIndex++] = cy.getNext().pos;
		components[compIndex][edgeIndex++] = cy.getNext().getNext().pos;
	    }
	    Arrays.sort(components[compIndex]);
	    compIndex++;
	}

	ASSERTCONFIGURATION();
	return components;
    }
    /************************************************
     * PRINTING COMPONENTS
     */ 
    public static void printComponents(int components[][]){
	System.out.println("------------- components");
	for ( int i = 0 ; i < components.length ; i++ ){
	    System.out.print(i+": ");
	    for ( int j = 0 ; j < components[i].length ; j++ ){
		System.out.print(components[i][j]+ " ");
	    }
	    System.out.println();
	}
	System.out.println("------------- end components");
    }

    /****************************************
     * INTERSECT CYCLES
     * Only handles 3 cycles
     */
    public boolean _3_cyclesIntersects(BlackEdge c1, BlackEdge c2){
	// Look up the indices of each cycle
	int posFirst[] = new int[3];
	posFirst[0] = c1.pos; 
	posFirst[1] = c1.getNext().pos; 
	posFirst[2] = c1.getNext().getNext().pos;
	Arrays.sort(posFirst);

	int posSecond[] = new int[3];
	posSecond[0] = c2.pos; 
	posSecond[1] = c2.getNext().pos; 
	posSecond[2] = c2.getNext().getNext().pos;
	Arrays.sort(posSecond);

	int minFirst = posFirst[0];
	int maxFirst = posFirst[2];
	int minSecond = posSecond[0];
	int maxSecond = posSecond[2];
	
	//check if first cycle occurs inbetween positions in the second
	if ( maxFirst < posSecond[0] // minFirst maxFirst posSecond[0] ...
	     || minFirst > posSecond[0] && maxFirst < posSecond[1] //posSecond[0] minFirst maxFirst posSecond[1]
	     || minFirst > posSecond[1] && maxFirst < posSecond[2] ) //posSecond[1] minFirst maxFirst posSecond[2]
	    return false;
	//check if second cycle occurs inbetween positions in the first
	if ( maxSecond < posFirst[0] // minSecond maxSecond posFirst[0] ...
	     || minSecond > posFirst[0] && maxSecond < posFirst[1] //posFirst[0] minSecond maxSecond posFirst[1]
	     || minSecond > posFirst[1] && maxSecond < posFirst[2] ) //posSecond[1] minSecond maxSecond posFirst[2]
	    return false;
	
	//otherwise intersect
	return true;
    }

    /***************************************
     * MAIN METHOD FOR TESTING
     */ 
    public static void main(String args[]){
        Configuration conf = new Configuration("(0 1 2)(3 4 5)");
        int comps[][] = conf.getComponents();
        printComponents(comps);

        conf = new Configuration("[3](0 31 8)[3](1 5 3)[3](2 6 4)[3](7 11 9)[3](10 26 12)[3](13 20 18)[3](14 24 22)[3](15 19 17)[3](16 23 21)[3](25 29 27)[3](28 32 30)");	
        comps = conf.getComponents();
        printComponents(comps);
    }

}