// Melkman.cpp : Defines the entry point for the console application.
#include "Melkman.h"

#define POINTSIZE 10

//  Global variables:
GLubyte *file_data = NULL;
GLint viewport[4];
Extent world = {-1, 1, -1, 1};

//  keep track of the points
Point *points;
//  keep track of the points in the convex hull
Point **hull;
int pointCount = 0;
int hullCount = 0;

//  booleans for certain logic throughout the program
bool polygonMode = false;
bool closed = false;
bool moveMode = false;
bool left_button_down = false;
bool algorithm = false;

//  special variables for point moving mode
Point *pointToMove = NULL;
bool movingAPoint = false;

double xScreenToWorld(int x) {
	return ((world.r - world.l) * (x - viewport[0]) / viewport[2]) + world.l;
}

double yScreenToWorld(int y) {
	return ((world.t - world.b) * ((viewport[3] - y) - viewport[1]) / viewport[3]) + world.b;
}

//
// GLUT display function
// 
void initialize()
{
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(world.l, world.r, world.b, world.t);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	glGetIntegerv(GL_VIEWPORT, viewport);
}

void display() {
	glClear( GL_COLOR_BUFFER_BIT );
	glDisable(GL_TEXTURE_2D);  //fix for making the dots red...
	glEnable(GL_BLEND);

	glPointSize(5);
	glLineWidth(2);

	glColor3d(0,0,1);

	//  when in polygon mode, draw either a closed loop
	//  or an open poly-line based on whether or not closed mode is on
	if(polygonMode){
		if(closed){
			//glBegin(GL_POLYGON);
			glBegin(GL_LINE_LOOP);
		}
		else{
			glBegin(GL_LINE_STRIP);
		}
	}
	for(int i=0; i<pointCount; i++){
		glVertex2d(points[i].x, points[i].y);
	}
	glEnd();
	
	if(algorithm && pointCount >= 3){
		glColor3d(1,1,0);
		glBegin(GL_LINE_LOOP);
			for(int i=0; i<1+hullCount; i++){
				glVertex2d(hull[i]->x, hull[i]->y);
			}
		glEnd();
	}
	
	//  default color is red
	glColor3d(1,0,0);
	glBegin(GL_POINTS);
	for(int i=0; i<pointCount; i++){
		//  the last point drawn is white, this is so that the 
		//  user can reference for when he is holding shift
		//  so the next point can be aligned with it
		if(i == pointCount - 1)
			glColor3d(1,1,1);
		//  move mode... everything is green except the point
		//  we are currently moving, if any.  that is white
		if(moveMode)
			if(pointToMove == &(points[i]))
				glColor3d(1,1,1);
			else
				glColor3d(0,1,0);
			
		//  the point itself
		glVertex2d(points[i].x, points[i].y);
	}
	glEnd();	
    glFlush();	
    glutSwapBuffers();
    glutPostRedisplay();
}

//  function to increase the size of points array by POINTSIZE if necessary
void allocateMorePoints(){
	Point *old = points;
	points = (Point *)malloc(sizeof(Point) * (POINTSIZE*((pointCount/POINTSIZE)+1)));
	for(int i=0; i<pointCount; i++){
		points[i] = old[i];
	}
	free(old);
}

bool setPointPicked(double x, double y){
	//  determine if we've selected a point already in the list
	for(int i=0; i<pointCount; i++){
		if(fabs(points[i].x - x) <= .01 &&
		   fabs(points[i].y - y) <= .01){
			pointToMove = &(points[i]);
			return true;
		}
	}
	pointToMove = NULL;
	return false;
}

void clearAll(){
	glClearColor(0, 0, 0, 1);
	glClear( GL_COLOR_BUFFER_BIT );
	pointCount = 0;
	hullCount = 0;
	moveMode = false;
	free(points);
	points = (Point *)malloc(POINTSIZE * sizeof(Point));
	free(hull);
	hull = (Point **)malloc(POINTSIZE * sizeof(Point));
}

/*  Function to determine if point c is to the left
    of the infinite line formed by points a and b 
    This can be done with the sign of the determinant
    trick from homework problem 1a  
	returns > 0 if c is left of AB
	returns 0 if c ON AB
	returns < 0 if c is right of AB */
double isLeftOf(Point a, Point b, Point c){
	/* DEBUG
	std::cout << "a: (" << a.x << "," << a.y << ")" << std::endl;
	std::cout << "b: (" << b.x << "," << b.y << ")" << std::endl;
	std::cout << "c: (" << c.x << "," << c.y << ")\n--------" << std::endl;
	*/
	/*  determinant of
	| 1 ax ay |
	| 1 bx by |
	| 1 cx cy |  */
	return (b.sx*c.sy - b.sy*c.sx) - a.sx*(c.sy - b.sy) + a.sy*(c.sx - b.sx);
	// return (a.sx - b.sx)*c.sy + (a.sy - b.sy)*c.sx + a.sx*b.sy - a.sy*b.sx;
	// return (b.sx - a.sx)*(c.sy - a.sy) - (c.sx - a.sx)*(b.sy - a.sy);
}

void melkman(){
	Point **deque = (Point **)malloc((pointCount*2 + 1)*sizeof(Point *));
	int bottom = pointCount-2;
	int top = bottom+3;
	
	deque[bottom] = deque[top] = &points[2];
	if(isLeftOf(points[0], points[1], points[2]) > 0){
		deque[bottom+1] = &points[0];
		deque[bottom+2] = &points[1];
	}
	else{
		deque[bottom+1] = &points[1];
		deque[bottom+2] = &points[0];
	}

	for(int i=3; i < pointCount; i++){
		//  first, check if our new point is inside the current convex hull
		//  this case, we obviously do nothing more
		if(isLeftOf(*deque[bottom], *deque[bottom+1], points[i]) > 0 &&
			isLeftOf(*deque[top-1], *deque[top], points[i]) > 0){
			//std::cout << "New point inside current hull." << std::endl;
			continue;
		}
		
		while(isLeftOf(*deque[bottom], *deque[bottom+1], points[i]) <= 0){
			bottom++;
		}
		bottom--;
		deque[bottom] = &points[i];
		
		while(isLeftOf(*deque[top-1], *deque[top], points[i]) <= 0){
			top--;
		}
		top++;
		deque[top] = &points[i];
	}
	
	int count;
	
	free(hull);
	hull = (Point **)malloc(sizeof(Point*)*pointCount);
	for(count=0; count < top-bottom; count++)
		hull[count] = deque[bottom+count];
		//memcpy(&(hull[count]), &(deque[bottom+count]), sizeof(Point));
	
	hullCount = count-1;
	
	free(deque);
}
		
//
// GLUT mouse button function
// 
void onMouseButton(int button, int state, int x, int y) {
	//std::cout << "X" << x << " Y" << y << std::endl;
	if (button == GLUT_LEFT_BUTTON) {
		double xClick, yClick;
		xClick = xScreenToWorld(x);
		yClick = yScreenToWorld(y);
		if (state == GLUT_DOWN) {
			//  first, check if we're in "move" mode.  if so,
			//  we need to check if the user has clicked a point to drag
			if(moveMode){
				movingAPoint = setPointPicked(xClick, yClick);
			}
			else{
				//  first, set the points to the clicked value
				points[pointCount].x = xClick;
				points[pointCount].y = yClick;
				points[pointCount].sx = x;
				points[pointCount].sy = viewport[3] - y;
				
				void checkForShift();
				//  check to see if shift key was held down while
				//  the current point was entered, if so, the values for this
				//  point must be changed to be in line with the previous point
				int mod = glutGetModifiers();
				if(mod == GLUT_ACTIVE_SHIFT && pointCount > 0){
					//  first we have to get the x and y coordinate
					//  of the last point entered, so that we can re-use them
					double prevX = points[pointCount-1].x;
					double prevY = points[pointCount-1].y;
					double prevSX = points[pointCount-1].sx;
					double prevSY = points[pointCount-1].sy;
					double xDiff = xClick - prevX;
					double yDiff = yClick - prevY;
					//  now we need to determine which "cone" we're in
					//  are we in the horizontal cone?
					if(fabs( atan ( yDiff / xDiff ) ) <= PI/4){
						points[pointCount].y = prevY;
						points[pointCount].sy = prevSY;
						
					}
					else{  //  verical cone
						points[pointCount].x = prevX;
						points[pointCount].sx = prevSX;
					}
				}
				
				
				//if( isLeftOf (points[0], points[1], points[pointCount]) > 0 ){
					//printf("Y\n");
				//}
				//  update the number of points, check if we need to 
				//  increase the size of our points array
				pointCount++;
				if(pointCount % POINTSIZE == 0){
					allocateMorePoints();
				}
			}
			left_button_down = true;
		}
		else if(state == GLUT_UP){
			//  if we're moving a point, this is it's final location
			//  set this and then stop moving the point
			left_button_down = false;
			if(moveMode && movingAPoint){
				pointToMove->x = xClick;
				pointToMove->sx = x;
				pointToMove->y = yClick;
				pointToMove->sy = y;
				pointToMove = NULL;
				movingAPoint = false;
			}

			if(pointCount >= 3)
				melkman();
		}
	} 
	//  RIGHT CLICK RESETS ALL
	else if (button == GLUT_RIGHT_BUTTON) {
		if (state == GLUT_DOWN) {
            clearAll();
		}
	}
	glutPostRedisplay();
}

//
// GLUT keypress function
// 
void onKeyPress(unsigned char key, int x, int y) {
	if ( key == 'p' ) {
		polygonMode = !(polygonMode);
	}
	if ( key == 'c' ) {
		closed = !closed;
	}
	if ( key == 'm' ) {
		moveMode = !moveMode;
	}
	if ( key == 'a' ) {
		algorithm = !algorithm;
	}
	if ( key == 'r' ) {
		clearAll();
	}
	//  27 is ascii for ESC key
	else if ( key == 'q' || key == 27) {
		if ( points )
			delete points;
		exit( 0 );
	}
}

// GLUT mouse motion function during a click
void mouse_motion( int x, int y ) {
	//  check if we're moving a point currently
	//  if so, then let's redisplay it where the mouse
	//  is currently during its movement
    if ( left_button_down ) {
		if(moveMode && movingAPoint){
			pointToMove->x = xScreenToWorld(x);
			pointToMove->y = yScreenToWorld(y);
		}
    }
    glutPostRedisplay();
}

// GLUT motion function during no click
void mouse_passive( int x, int y ){
	//std::cout << "(" << x << "," << y << ") is the current mouse position" << std::endl;
}

//
// GLUT resize function
// 
void resize(int w, int h) {
	// Reset the coordinate system before modifying
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	
	// Set the viewport to be the entire window
	glViewport(0, 0, w, h);
	glGetIntegerv(GL_VIEWPORT, viewport);
}

int main(int argc, char *argv[])
{
	// window size parameters
	int w = 800; int h = 600;

	// glut initialization functions:
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB );
	glutInitWindowSize(w,h);
	glutInitWindowPosition(200,200);
	glutCreateWindow("CISC 829: Homework 1 Programming Assignment");
	initialize();

	points = (Point *)malloc(POINTSIZE*sizeof(Point));
	hull = (Point **)malloc(POINTSIZE*sizeof(Point));
	// display, onMouseButton, mouse_motion, onKeyPress, and resize are functions defined above
	glutDisplayFunc(display);
	glutMouseFunc(onMouseButton);
	glutMotionFunc( mouse_motion );
	glutPassiveMotionFunc( mouse_passive );
	glutKeyboardFunc(onKeyPress);
	glutReshapeFunc(resize);

	// start glutMainLoop -- infinite loop
	glutMainLoop();
}