class FaceGroup{
public:
	int    ID;
	int    birthStage;
	Face **face;
	int    faceSize;
	Vector normal;

	FaceGroup( FILE *fp ){ ID = 0; birthStage = 0; face = new Face *[faceSize = 1]; face[0] = new Face( fp ); normal.unitZ(); }// for the original face

	// pick and adjustDiagonal
	void closestVertex( Line &line, Vertex * &closest, double &distance ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<faceSize; i++ ){
			double d;
			Vertex *v;
			face[i]->closestVertex( line, v, d );
			if( d < distance ){
				closest = v;
				distance = d;
			}
		}
	}
	void labelPickedCandidate( Vector &position ){ for( int i=0; i<faceSize; i++ ) face[i]->labelPickedCandidate( position ); }

	// adjustVertex
	void closestVertex( Vector &position, Vertex * &closest, double &distance ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<faceSize; i++ ){
			double d;
			Vertex *v;
			face[i]->closestVertex( position, v, d );
			if( d < distance ){
				closest = v;
				distance = d;
			}
		}
	}
	// adjustDiagonal
	void closestVertex( Line &line, Vertex * &closest, double &distance, Vector &except, double apartMargin=1.0 ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<faceSize; i++ ){
			double d;
			Vertex *v;
			face[i]->closestVertex( line, v, d, except, apartMargin );
			if( d < distance ){
				closest = v;
				distance = d;
			}
		}
	}

	Face **pickedFaceList( Vertex &pickedVertex ){
		int n = 0, i;
		for( i=0; i<faceSize; i++ ) if( face[i]->include( pickedVertex ) ) n++;
		Face **faceList = new Face *[n+1];
		n = 0;
		for( i=0; i<faceSize; i++ ) if( face[i]->include( pickedVertex ) ) faceList[n++] = face[i];
		faceList[n++] = NULL;
		return faceList;
	}

	Edge *closestEdge( double &distance, Vector &p0, Vector &p1 ){
		Edge *closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<faceSize; i++ ){
			double d;
			Edge *e = face[i]->closestEdge( d, p0, p1 );
			if( d < distance ){
				closest = e;
				distance = d;
			}
		}
		return closest;
	}

	// renew
	VertexLabels labelVertices( Fold &fold ){
		bool allMoved = true;
		bool allFixed = true;
		for( int i=0; i<faceSize; i++ ){
			switch( face[i]->labelVertices( fold ) ){
				case AllMoved: allFixed = false; break;
				case AllFixed: allMoved = false; break;
				case MovedAndFixed : allMoved = allFixed = false; break;
			}
		}
		return allMoved ? AllMoved : allFixed ? AllFixed : MovedAndFixed;
	}

	void clearEdgeAndFaceLabels(){ for( int i=0; i<faceSize; i++ ) face[i]->clearEdgeAndFaceLabels(); }

	RenewResult renewFoldUp( int birthStage, Fold &fold ){
		int renewDone = 1;
		for( int i=0; i<faceSize; i++ ){
			for( int j=i+1; j<faceSize; j++ ){
				//face[i]->print();
				//face[j]->print();
				if( face[i]->label == MovedFace && face[i]->overlap( *face[j] ) || face[i]->label == DividedFace && face[i]->children[0]->overlap( *face[j] ) ){
					switch( face[j]->renew( birthStage, ID, fold ) ){
						case RenewSuccess: renewDone = 0; break;
						case RenewFailure: return RenewFailure;
					}
				}
			}
		}
		return renewDone ? RenewDone : RenewSuccess;
	}

	RenewResult renewFoldDown( int birthStage, Fold &fold ){
		int renewDone = 1;
		for( int i=faceSize-1; i>=0; i-- ){
			for( int j=i-1; j>=0; j-- ){
				if( face[i]->label == MovedFace && face[i]->overlap( *face[j] ) || face[i]->label == DividedFace && face[i]->children[0]->overlap( *face[j] ) ){
					switch( face[j]->renew( birthStage, ID, fold ) ){
						case RenewSuccess: renewDone = 0; break;
						case RenewFailure: return RenewFailure;
					}
				}
			}
		}
		return renewDone ? RenewDone : RenewSuccess;
	}

	RenewResult renewTuckIn( int birthStage, Fold &fold ){
		int renewDone = 1;

		int lowest = 0;
		while( face[lowest]->label != MovedFace && face[lowest]->label != DividedFace && lowest < faceSize-1 ) lowest++;
		int highest = faceSize-1;
		while( face[highest]->label != MovedFace && face[highest]->label != DividedFace && highest > 0 ) highest--;
		//printf("l %d h %d\n",lowest, highest );
		for( int i=lowest+1; i<highest; i++ ){
			if( face[lowest]->label == MovedFace && face[lowest]->overlap( *face[i] ) || face[lowest]->label == DividedFace && face[lowest]->children[0]->overlap( *face[i] ) ){
				switch( face[i]->renew( birthStage, ID, fold ) ){
					case RenewSuccess: renewDone = 0; break;
					case RenewFailure: return RenewFailure;
				}
			}
		}
		return renewDone ? RenewDone : RenewSuccess;
	}

	RenewResult renew( int birthStage, Fold &fold ){
		if( this->labelVertices( fold ) != MovedAndFixed )  return RenewFailure;
		this->clearEdgeAndFaceLabels();
		bool renewFailure = false;
		if( fold.pickedFace()->renew( birthStage, ID, fold ) == RenewFailure ) renewFailure = true;
		else if( fold.pickedFace()->label == FixedFace ) renewFailure = true;
		else{
			switch( fold.type ){
			case FoldUp:   if ( this->renewFoldUp  ( birthStage, fold ) == RenewFailure ) renewFailure = true; break;
			case FoldDown: if ( this->renewFoldDown( birthStage, fold ) == RenewFailure ) renewFailure = true; break;
			case TuckIn:   if ( this->renewTuckIn  ( birthStage, fold ) == RenewFailure ) renewFailure = true; break;
			case BendUp:   if ( this->renewFoldUp  ( birthStage, fold ) == RenewFailure ) renewFailure = true; break;
			case BendDown: if ( this->renewFoldDown( birthStage, fold ) == RenewFailure ) renewFailure = true; break;
			}
		}
		if( renewFailure ){
			this->reset( ID+1 );
			return RenewFailure;
		}
		return RenewSuccess;
	}

	void constructFoldUp( FaceGroup &parentFaceGroup ){
		normal = parentFaceGroup.normal;
		face = new Face *[parentFaceGroup.faceSize*2];
		faceSize = 0;
		int i;
		for( i=0; i<parentFaceGroup.faceSize; i++ ){
			if( parentFaceGroup.face[i]->label == FixedFace || parentFaceGroup.face[i]->label == UndoneFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[1];
			}
		}
		for( i=parentFaceGroup.faceSize-1; i>=0; i-- ){
			if( parentFaceGroup.face[i]->label == MovedFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[0];
			}
		}
	}

	void constructFoldDown( FaceGroup &parentFaceGroup ){
		normal = parentFaceGroup.normal;
		face = new Face *[parentFaceGroup.faceSize*2];
		faceSize = 0;
		int i;
		for( i=parentFaceGroup.faceSize-1; i>=0; i-- ){
			if( parentFaceGroup.face[i]->label == MovedFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[0];
			}
		}
		for( i=0; i<parentFaceGroup.faceSize; i++ ){
			if( parentFaceGroup.face[i]->label == FixedFace || parentFaceGroup.face[i]->label == UndoneFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[1];
			}
		}
	}

	void constructBend0( FaceGroup &parentFaceGroup ){
		normal = parentFaceGroup.normal;
		face = new Face *[parentFaceGroup.faceSize];
		faceSize = 0;
		for( int i=0; i<parentFaceGroup.faceSize; i++ ){
			if( parentFaceGroup.face[i]->label == FixedFace || parentFaceGroup.face[i]->label == UndoneFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[1];
			}
		}
	}

	void constructBend1( FaceGroup &parentFaceGroup ){
		normal = parentFaceGroup.normal;
		face = new Face *[parentFaceGroup.faceSize];
		faceSize = 0;
		for( int i=0; i<parentFaceGroup.faceSize; i++ ){
			if( parentFaceGroup.face[i]->label == MovedFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[0];
			}
		}
	}

	void constructTuckIn( FaceGroup &parentFaceGroup ){
		normal = parentFaceGroup.normal;
		face = new Face *[parentFaceGroup.faceSize*2];
		faceSize = 0;
		int lowest = 0;
		while( parentFaceGroup.face[lowest]->label != MovedFace && parentFaceGroup.face[lowest]->label != DividedFace ) lowest++;
		int highest = parentFaceGroup.faceSize-1;
		while( parentFaceGroup.face[highest]->label != MovedFace && parentFaceGroup.face[highest]->label != DividedFace ) highest--;
		int middle = ( lowest + highest ) / 2;

		int i;
		for( i=0; i<=middle; i++ ){
			if( parentFaceGroup.face[i]->label == FixedFace || parentFaceGroup.face[i]->label == UndoneFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[1];
			}
		}
		for( i=middle; i>=0; i-- ){
			if( parentFaceGroup.face[i]->label == MovedFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[0];
			}
		}
		for( i=parentFaceGroup.faceSize-1; i>middle; i-- ){
			if( parentFaceGroup.face[i]->label == MovedFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[0];
			}
		}
		for( i=middle+1; i<parentFaceGroup.faceSize; i++ ){
			if( parentFaceGroup.face[i]->label == FixedFace || parentFaceGroup.face[i]->label == UndoneFace ){
				face[faceSize++] = parentFaceGroup.face[i];
			}else if( parentFaceGroup.face[i]->label == DividedFace ){
				face[faceSize++] = parentFaceGroup.face[i]->children[1];
			}
		}
	}

	void renewPointer(){ for( int i=0; i<faceSize; i++ ) face[i]->renewPointer( ID ); }

	FaceGroup( int birthStage, FaceGroup &parentFaceGroup, Fold &fold, int groupNumber = -1 ){
		this->ID = groupNumber == -1 ? parentFaceGroup.ID : groupNumber;
		this->birthStage = birthStage;
		switch( fold.type ){
			case FoldUp: this->constructFoldUp( parentFaceGroup ); break;
			case FoldDown: this->constructFoldDown( parentFaceGroup ); break;
			case TuckIn: this->constructTuckIn( parentFaceGroup ); break;
			case BendUp: groupNumber == -1 ? this->constructBend0( parentFaceGroup ) : this->constructBend1( parentFaceGroup ); break;
			case BendDown: groupNumber == -1 ? this->constructBend0( parentFaceGroup ) : this->constructBend1( parentFaceGroup ); break;
		}
		this->renewPointer();
	}

	//reset
	~FaceGroup(){ delete face; }

	void reset( int deleteStage ){
		int i;
		for( i=0; i<faceSize; i++ ) face[i]->resetPointer( deleteStage );
		for( i=0; i<faceSize; i++ ) face[i]->reset( deleteStage, ID );
	}

	//draw
	int visibleSide( Vector &eyePosition ){ Vector n = face[0]->vertex( 0 )->position - eyePosition; return normal * n < 0 ? 0 : 1; }

	FaceLocation whichSide( Plane &plane ){
		bool infront=false, behind=false, onIntersection=false;
		for( int i=0; i<faceSize; i++ ){
			switch( face[i]->whichSide( plane ) ){
				case InfrontApart: infront = true; break;
				case InfrontContact: infront = onIntersection = true; break;
				case Across: infront = behind = true; break;
				case BehindContact: behind = onIntersection = true; break;
				case BehindApart: behind = true; break;
			}
		}
		if( infront && !behind ) return onIntersection ? InfrontContact : InfrontApart;
		else if( !infront && behind ) return onIntersection ? BehindContact : BehindApart;
		else return Across;
	}

	int sort( FaceGroup &faceGroup, Vector &eyePosition ){
		Plane plane;
		plane.normal = faceGroup.visibleSide( eyePosition ) == 0 ? faceGroup.normal : -faceGroup.normal;
		plane.passage = faceGroup.face[0]->vertex( 0 )->position;
		FaceLocation side0 = this->whichSide( plane );
		plane.normal = this->visibleSide( eyePosition ) == 0 ? normal : -normal;
		plane.passage = face[0]->vertex( 0 )->position;
		FaceLocation side1 = faceGroup.whichSide( plane );
		//printf( "side0 %d side1 %d\n", side0, side1 );
		if( (side0==InfrontApart || side0==InfrontContact) && (side1==Across || side1==BehindContact) ) return 0;
		if( (side1==BehindApart || side1==BehindContact) && (side0==Across || side0==InfrontContact) ) return 0;
		return 1;
	}

	void FaceGroup::draw( Vector &eyePosition, FaceProperty &faceProperty ){
		if( (face[0]->vertex( 0 )->position - eyePosition) * normal < 0.0 ){
			for( int i=0; i<faceSize; i++ ) face[i]->draw( normal, faceProperty );
		}else{
			Vector frontNormal = - normal;
			for( int i=faceSize-1; i>=0; i-- ) face[i]->draw( frontNormal, faceProperty );
		}
	}
};

// ------------------------- other classes member functions -----------------------------------------
bool Fold::setPick( FaceGroup &faceGroup, Vector &viewDirection ){
	if( viewDirection * faceGroup.normal > 0 ){
		for( int i=0; i<faceGroup.faceSize; i++ ){
			if( this->setPick(*faceGroup.face[i]) ){
				face = faceGroup.face[faceID=i];
				this->faceGroup = &faceGroup;
				return true;
			}
		}
	}else{
		for( int i=faceGroup.faceSize-1; i>=0; i-- ){
			if( this->setPick(*faceGroup.face[i]) ){
				face = faceGroup.face[faceID=i];
				this->faceGroup = &faceGroup;
				return true;
			}
		}
	}
	return false;
}

bool Fold::update( double margin ){
	boundary.equidistance( vertex->position, destination );
	if( boundary.normal.abs() < margin ) return true; //error
	if( type == BendDown || type == FoldDown ) angle = - 2.0 * boundary.normal.angle( -faceGroup->normal );
	else angle = 2.0 * boundary.normal.angle( faceGroup->normal );
	if( fabs(angle+360.0)<rad(10.0) || fabs(angle)<rad(10.0) || fabs(angle-360.0)<rad(10.0) ) return true;
	Plane pickedPlane(faceGroup->normal, vertex->position);
	axis.intersection( pickedPlane, boundary );
	return false;
}

bool Fold::update( Vector &destination, Vector &eyePosition, bool inBending ){
	Plane pickedPlane(faceGroup->normal, vertex->position);
	Vector viewLine = pickedPlane.passage - eyePosition;
	if( Key.down('t') ) type = TuckIn;
	else if( inBending ) type = viewLine * pickedPlane.normal > 0 ? BendDown : BendUp;
	else{
		if( this->isBend() && pickedPlane.signedDistance( destination ) * viewLine * pickedPlane.normal < 0 ){
			type = viewLine * pickedPlane.normal > 0 ? BendDown : BendUp;
		}else{
			Vector v = destination + viewLine;
			Line line( destination, v );
			destination.intersection( pickedPlane, line );
			type = viewLine * pickedPlane.normal > 0 ? FoldDown : FoldUp;
		}
	}
	this->destination = destination;
	return this->update();
}

void Fold::save( FILE *fp ){
	char c;
	switch( type ){
		case FoldUp   : c = 'F'; break;
		case FoldDown : c = 'f'; break;
		case TuckIn   : c = 'T'; break;
		case BendUp   : c = 'B'; break;
		case BendDown : c = 'b'; break;
		default: c = 'U';
	}
	fwrite( &c, 1, 1, fp );
	fwrite( &faceGroup->ID, 4, 1, fp );
	fwrite( &faceID,      4, 1, fp );
	fwrite( &vertexID,    4, 1, fp );
	destination._fwrite( fp );
}

bool Fold::load( FILE *fp, FaceGroup ** &faceGroup ){
	char c;
	if( fread( &c, 1, 1, fp ) < 1 ) return false;
	switch( c ){
		case 'F' : type = FoldUp;   break;
		case 'f' : type = FoldDown; break;
		case 'T' : type = TuckIn;   break;
		case 'B' : type = BendUp;   break;
		case 'b' : type = BendDown; break;
	}
	int faceGroupID;
	fread( &faceGroupID, 4, 1, fp );
	fread( &faceID, 4, 1, fp );
	fread( &vertexID, 4, 1, fp );
	destination._fread( fp );
	this->faceGroup = faceGroup[faceGroupID];
	face = faceGroup[faceGroupID]->face[faceID];
	vertex = face->vertex( vertexID );
	this->update();
	this->backup(); // for animation
	return true;
}

void Fold::print(){
	printf("Picked faceGroupID %d\n",faceGroup->ID);
	printf("Picked faceID %d\n",faceID);
	face->print();
	printf("Picked vertexID %d\n",vertexID);
	vertex->position.print();
	printf("Destination ");
	destination.print();
	printf("Fold type ");
	switch( type ){
		case FoldUp   : printf("FoldUp");     break;
		case FoldDown : printf("FoldDown");   break;
		case TuckIn   : printf("FoldTuckIn"); break;
		case BendUp   : printf("BendUp");     break;
		case BendDown : printf("BendDown");   break;
		default: printf("N/A");
	}
	printf("\n");
	printf("Boundary ");
	boundary.print();
	printf("Axis ");
	axis.print();

	printf("Angle %f\n", angle);
}