/*
 * Onion algorithm
 */

import java.util.*;

public class Onion {

    Vector chain,newChain; /* vertex chains */
    Vector room; /* list of faces */

    public int p; /* p-gons */
    public int q; /* q of each per vertex */

    public int myMod(int a, int b) {
	return( (a>=0) ? (a % b) : (b-1+((a+1) % b)) );
    }

    /*
    public class Segment {
	Vertex[] end;
	boolean isOpen;
	// Constructor 
	public Segment() {
	    end=new Vertex[2];
	    isOpen=false;
	}
    }
    */

    public class Vertex {
	Vertex[] neighbor; /* ordered list of neighboring vertices */
	Face[] face; /* ordered list of faces sharing this vertex */
	int[] ownIndex; /* what is the index of this vertex in the corresponding face */
	int faceCount; /* How many existing faces share this vertex */
	/* Constructor */
	public Vertex() {
	    neighbor=new Vertex[q];
	    face=new Face[q];
	    ownIndex=new int[q];
	    faceCount=0;
	}
    }

    public class Face {
	Face[] neighbor;
	boolean[] isOpen; /* is the segment from vertex n to n+1 an open door ? */
	Vertex[] vertex;
	int[] ownIndex; /* what is the index of this face in the corresponding vertex */
	/* Constructor */
	public Face() {
	    neighbor=new Face[p];
	    vertex=new Vertex[p];
	    ownIndex=new int[p];
	}
    }

    public void growOnce() {
	int initialChainLenght=chain.size();
//	newChain=(Vector) chain.clone();
	newChain=new Vector();

	for(int n=0; n<initialChainLenght; n++) {
//	    System.out.println("n = " + String.valueOf(n));
	    saturateVertex(n);
	}

	chain=newChain;
    }

    public void saturateVertex(int n) {
	for(int j=0; j<q; j++) {
//	    System.out.println("  j = " + String.valueOf(j));
	    if(((Vertex) chain.elementAt(n)).face[j]==null) {
		addFaceToVertex(n,j);
	    }
	}
    }

    public void argh() {
	System.out.println("Argh !");
	System.exit(-1);
    }

    /*
     * Link face f to vertex v
     * i is the index of f in v
     * j is the index of v in f
     */
    public void link(Vertex v, int i, Face f, int j) {
	f.vertex[j]=v;
	v.ownIndex[i]=j;
	v.face[i]=f;
	f.ownIndex[j]=i;
	v.faceCount++;
    }
   
    public void addFaceToVertex(int n, int j) {

	Vertex v=(Vertex) chain.elementAt(n);

	// First, check that the slot is empty
	if(v.face[j]!=null) argh(); // this should not happen
	//	if(v.faceCount>q-1) argh();

	// Create the object and add it to the global list of faces
	Face newFace=new Face();
	room.add(newFace);

	// Link the vertex and the face
	link(v,j,newFace,0);

	// Sew the boundary of the new face (iteratively)

	// For this work, there must be no "hole" in the structure
	Vertex w;
	Face f2;
	int t,k,m,j2;

	// scan forward
	t=0;
	j2=j;
	w=v;
//	System.out.println(String.valueOf(j2));
	f2=w.face[myMod(j2-1, q)];
	for(;f2!=null && t<p-1;) {
//	System.out.println("  t = "+String.valueOf(t));
	    k=myMod(v.ownIndex[myMod(j2-1,q)]-1,p);
//	System.out.println("  k = "+String.valueOf(k));
	    j2=myMod(f2.ownIndex[k]-1,q);
	    w=f2.vertex[k];
	    t++;

	    link(w,j2,newFace,t);

	    f2=w.face[myMod(j2-1,q)];
	}


	// scan backward
	int t2;
	t2=0;
	j2=j;
	w=v;
	f2=w.face[(j2+1) % q];
//	System.out.print("  j2 = "+String.valueOf(j2)+"\n");
	for(;f2!=null && t2>1-p;) {
//	System.out.print("  t2 = "+String.valueOf(t2));
//	System.out.print("  f2 = "+String.valueOf(room.indexOf(f2)));
	    k=(w.ownIndex[(j2+1) % q]+1) % p;
//	System.out.print("  k = "+String.valueOf(k));
	    j2=(f2.ownIndex[k]+1) % q;
//	System.out.print("  j2 = "+String.valueOf(j2)+"\n");
	    w=f2.vertex[k];
	    t2--;

	    link(w,j2,newFace,myMod(t2,p));

	    f2=w.face[(j2+1) % q];
	}

	//	System.out.println(String.valueOf(n)+" "+String.valueOf(j)+" "+String.valueOf(t)+","+String.valueOf(t2));

	// test whether more than all vertices of the new polygon were sewed
	if(1+t-t2>p) argh(); // should not happen

	/* Now, we add the missing vertices and udpate the chain */
	/*
	int nn=n % newChain.size();
	for(int i=t2+1; i<=t-1; i++) {
	    newChain.remove(nn);
	}
	for(int i=p+t2-1; i>=t+1; i--) {
	    v=new Vertex();
	    link(v,0,newFace,i);
	    newChain.insertElementAt(v,nn);
	}
	*/
	for(int i=t+1; i<=p+t2-1; i++) {
	    v=new Vertex();
	    link(v,0,newFace,i);
	    newChain.add(v);
	}
    }

    public void germ() {
	chain=new Vector();
	room=new Vector();
	Face f=new Face();
	room.add(f);
	for(int i=0; i<p; i++) {
	    Vertex v=new Vertex();
	    link(v,0,f,i);
	    chain.add(v);
	}
    }

    public void linkEverybody() {
...
    }

    public void generateMaze() {
	Iterator i;
	/* Let's set every door open */
	Face f;
	for(i=room.iterator();i.hasNext();) {
	    f=(Face) i.next();
	    for(int j=0; j<p; j++) {
		f.isOpen(j)=true;
	    }
	}
	/* Let's close every door on the boundary */
	Vertex v1,v2;
	for(i=chain.iterator();i.hasNext();) {
	    v=(Vertex) i.next();
	    for(int j=0; j<q && v.face[myMod(-j,q)]!=null; j++) {}
	    j=(j+1) % q;
	    f=v.face[j];
	    f.isOpen[v.ownIndex[j]]=false;
	}
	/* Let's grow the maze */
	// to be continued...
	// Ppe : on maintient une liste des vertex actifs
	// sur lesquels poussent aléatoirement des segments
	// on s'arrête quand plus aucun vertex n'est actif
...
    }
}