#include "BIF_meshHE.h"
#include "HE_Operations.h"

#include "BKE_global.h" //for G.rt

#include "MEM_guardedalloc.h"

#include <stdio.h>

/*
Subdivision patterns.

SubD patterns work in a two-pass manner:
first pass subdivides then connects verts,
then you can optionally specify edges
to be subdivided *again* and conenct verts
again.
*/
typedef struct SubdivPattern {
	/*edge_template is the layout of new and old verts.
	  0 in the array means old, 1 means new.*/
	int *vert_template;
	int *connect_map; /* include connecting of new edges from split_map */
	int *split_map; /* split map is for doing extra splitting after the fact, like for
					  corner quad case. */
	int len; /*original face len, without new verts*/
	int newlen; /*new face len*/
	int finallen; /*final face len after processing.*/
} SubdivPattern;

/*naming convention: E[number of connecting edges]F[original number of verts]*/

/*do 2 edges on opposite side of a quad case*/
/*5 */
/*
 *0------n1-----2
 *|      |      |
 *|      |      |
 *|      |      |
 *|      |      |
 *|      |      |
 *5------n4-----3
 */

int ipat1[] = {0, 1, 0, 0, 1, 0};
int epat1[] = {-1, 4, -1, -1, -1, -1};
static SubdivPattern E1F4Opposite = {
	ipat1,
	epat1,
	NULL,
	4, 6, 6
};

/*do 2 edges on opposite side of a quad case*/
/*5 */
/*
 *0------n1-----2
 *|      \      |
 *|       /n6   |
 *|     /     \ n3
 *|   /         |
 *| /           |
 *5-------------4
 */

int ipat2[] = {0, 1, 0, 1, 0, 0, 0};
int epat2[] = {-1, 3, -1, -1, -1, -1, 5};
int smap2[] = {0, 0, 0, 0, 0, 0, 1};
static SubdivPattern E3F4Adjacent = {
	ipat2,
	epat2,
	smap2,
	4, 6, 7
};

/*do 2 edges on opposite side of a quad case*/
/*5 */
/*
 *0------n1-----2
 *|     /  \    |
 *|    /    \   |
 *|   /      \  |
 *|  /        \ |
 *| /          \|
 *4-------------3
 */

int ipat3[] = {0, 1, 0, 0, 0};
int epat3[] = {-1, 4, -1, 1, -1};
static SubdivPattern E2F4Single = {
	ipat3,
	epat3,
	NULL,
	4, 5, 5
};

/*do 2 edges on opposite side of a quad case*/
/*5 */
/*
 *0------n1-----2
 *|      | \    |
 *|      |   \  |
 *|      |     \n3
 *|      |   /  |
 *|      |/     |
 *4------n5-----4
 */

int ipat4[] = {0, 1, 0, 1, 0, 1, 0};
int epat4[] = {-1, 3, -1, 5, -1, 1, -1};
static SubdivPattern E3F4Three= {
	ipat4,
	epat4,
	NULL,
	4, 7, 7
};

/*do 2 edges on opposite side of a quad case
 * 0---n1--2
 * |  /\  /
 * | /  \/
 *n5/---n3
 * |   /
 * |  /
 * | /
 * 4
 *
 */

int ipat5[] = {0, 1, 0, 1, 0, 1};
int epat5[] = {-1, 5, -1, 1, -1, 3};
static SubdivPattern E3F3Full = {
	ipat5,
	epat5,
	NULL,
	3, 6, 6
};

/*do 2 edges on opposite side of a quad case
 *0-------1
 *|      /
 *|     /
 *n4---n2
 *|   /
 *|  /
 *| /
 *3
 *
 */

int ipat6[] = {0, 0, 1, 0, 1};
int epat6[] = {-1, -1, 4, -1, -1};
static SubdivPattern E1F3Part = {
	ipat6,
	epat6,
	NULL,
	3, 5, 5
};

/*do 2 edges on opposite side of a quad case
 *0-------1
 *| \    /
 *|  \  /
 *|   \n2
 *|   /
 *|  /
 *| /
 *3
 *
 */

int ipat7[] = {0, 0, 1, 0};
int epat7[] = {-1, -1, 0, -1};
static SubdivPattern E1F3Single = {
	ipat7,
	epat7,
	NULL,
	3, 4, 4
};

/*do 5-sided face cases */

/* single edge selected
 *0-------1-------2
 *|       |       |
 *|       |       |
 *|       |       |
 *|       |       |
 *|       |       |
 *|       |       |
 *5-------n4------3
 *
 */

int ipat8[] = {0, 0, 0, 0, 1, 0};
int epat8[] = {-1, 4, -1, -1, -1, -1};
static SubdivPattern E1F5Single = {
	ipat8,
	epat8,
	NULL,
	5, 6, 6
};

/* two adjacent edges selected
 *0-------1-------2
 *|            /  |
 *|          /    |
 *|       /       |
 *|      n7------n3
 *|    /  |       |
 *|   /   |       |
 *| /     |       |
 *6-------n5------4
 *
 */

int ipat9[] = {0, 0, 0, 1, 0, 1, 0, 0};
int epat9[] = {-1, -1, 6, -1, -1, 7, 0, 3};
int smap9[] = {0, 0, 0, 0, 0, 0, 0, 1};
static SubdivPattern E1F5DoubleAdj = {
	ipat9,
	epat9,
	smap9,
	5, 7, 8
};

static SubdivPattern *subd_patterns[] = {
	&E1F4Opposite,
	&E3F4Adjacent,
	&E2F4Single,
	&E3F4Three,
	&E3F3Full,
	&E1F3Part,
	&E1F3Single,
	&E1F5Single,
	&E4F5DoubleAdj
};

int subd_pattern_len = sizeof(subd_patterns) / sizeof(void*);

void HETool_SubdivideFlag(HE_EditMesh *em, int flag)
{
	HE_EditFace *efa, *efa2, *flist[1000];
	HE_EditEdge *eed, *start, *elist[6000];
	HE_EditEdgeInfo *ieed;
	HE_EditVert *vlist[6000];
	SubdivPattern *pat;
	int i, j, a, b, totnewfaces, c, d, ok;

	/*build counts of original number of verts in faces*/
	for (efa=em->faces.first; efa; efa=efa->next) {
		i = 0;
		efa->f1 = 0;
		eed = efa->edge;
		do {
			eed->f1 = 0;
			eed->ieed->f1 = 1;
			eed->ieed->f2 = 0;
			eed=eed->enext;
			i += 1;
		} while (eed != efa->edge);
		efa->tmp.i = i;
	}

	for (ieed=em->einfo.first; ieed; ieed=ieed->next) {
		if (ieed->f1 == 1 && (ieed->f & SELECT) != 0) {
			/*passing NULL as coordinate means new vert will be centered on edge.
			  eed is the new edge made in the edge split.*/
			eed = HEOP_makeVertInEdge(em, ieed->e1, NULL);
			eed->f1 = 1;
			eed->pair->enext->f1 = 1;
		}
	}

	for (efa=em->faces.first; efa; efa=efa->next) {
		if (efa->f1==1) continue; /*don't process new faces*/

		eed = efa->edge;
		i = 0;
		do {
			i += 1;
			eed=eed->enext;
		} while (eed != efa->edge);
		
		if (i != efa->tmp.i) {
			/*find matching subdivision pattern.*/
			ok = 0;
			for (j=0; j<subd_pattern_len; j++) {
				pat = subd_patterns[j];
				if (efa->tmp.i == pat->len && i == pat->newlen) {
					printf("found possible face!\n");
					/*loop over the face face_len*face_len times, starting at a different
					  place each time and check for compatibility with the pattern.  this
					  basically checks the pattern against the face with the first vert starting
					  at each vert in the face.*/
					start = efa->edge;
					for (a=0; a<pat->newlen; a++, start=start->enext)  {
						eed = start;
						ok = 1;
						b = 0;
						do {
							/*if the template wants a new vert, but we're not a new
							  vert (well, edge, but same thing with half-edges)
							  thens fail and break.*/
							if (pat->vert_template[b] != 0 && eed->f1==0) {
								ok = 0;
								break;
							/*if the template wants an old vert, but we're a new,
							  then fail and break.*/
							} else if (pat->vert_template[b] == 0 && eed->f1==1) {
								ok = 0;
								break;
							}
							eed=eed->enext;
							b += 1;
							printf("s3\n");
						} while (eed != start);
						if (ok) break;
					}

					if (ok) { /* *gasp*! we found a pattern match! yay!*/
						/*to make things *so* much simpler, we put the face verts in a
						  6000-limit array.
						  
						  We also do this with the edges for the post-processing split-edge
						  map.*/
						printf("ok: %d\n", ok);
						a = 0;
						eed = start;
						do {
							vlist[a] = eed->v1;
							elist[a] = eed;
							a += 1;
							eed=eed->enext;
							printf("s2\n");
						} while (eed != start);
						
						b = a;
						totnewfaces = 0;
						for (a=0; a<pat->newlen; a++) {
							printf("s\n");
							if (pat->connect_map[a] != -1 && pat->connect_map[a] < pat->newlen) {
								/*eek this might be pretty bad.
								  this assumes efa2->edge is the pair of the new
								  edge, I really need to find a better way to provide this 
								  feedback!*/
								
								if (HEOP_faceHasVert(efa, vlist[a]) &&
									HEOP_faceHasVert(efa, vlist[pat->connect_map[a]])) {
									efa2 = HEOP_splitFaceBetweenTwoVerts(em, efa, vlist[a], vlist[pat->connect_map[a]]);
									efa2->f1 = 1;
								} else {
									for (c=0; c<totnewfaces; c++) {
										if (HEOP_faceHasVert(flist[c], vlist[a]) &&
											HEOP_faceHasVert(flist[c], vlist[pat->connect_map[a]])) {
											efa2 = HEOP_splitFaceBetweenTwoVerts(em, flist[c], vlist[a], vlist[pat->connect_map[a]]);
											if (!efa2) return;
											efa2->f1 = 1;
											break;
										}
									}
								}

								flist[totnewfaces] = efa2;
								elist[b] = efa2->edge->pair;
								vlist[b] = efa2->edge->pair->v1;
								b += 1;
								totnewfaces += 1;
							}
						}

						printf("b: %d\n", b);
						if (pat->split_map){
							for (a=0; a<pat->finallen; a++) {
								if (pat->split_map[a]) {
									vlist[a] = HEOP_makeVertInEdge(em, elist[a], NULL)->v1;
								}
								printf("s4\n");
							}
							for (a=0; a<pat->finallen; a++) {
								if (a < pat->newlen && pat->connect_map[a] < pat->newlen) continue;

								if (pat->connect_map[a] != -1) {
									/*find correct face to split*/
									d = totnewfaces;
									for (c=0; c<d; c++) {
										printf("s5\n");
										if (HEOP_faceHasVert(flist[c], vlist[a]) &&
											HEOP_faceHasVert(flist[c], vlist[pat->connect_map[a]])) {
											printf("yay!\n");
											efa2 = HEOP_splitFaceBetweenTwoVerts(em, flist[c], vlist[a], vlist[pat->connect_map[a]]);
											if (!efa2) return;
											efa2->f1 = 1;
											//flist[d++] = efa2;
										}
									}
									//totnewfaces = d;
								}
							}
						}
						break;
					}
				}
			}
		}
	}

	printf("subdividing!\n");
}

/*
 *   ------------
 *|            /  
 *|          /      
 *|         /    |
 *|       /      |
 *|      s       |
 *|    /         |
 *|   /          s
 *|  /           |
 *| /            |
 * /             |
 * -----s------
 */