/*

   Simple DirectMedia Layer

   Copyright (C) 1997-2013 Sam Lantinga <slouken@libsdl.org>

   This software is provided 'as-is', without any express or implied

   warranty.  In no event will the authors be held liable for any damages

   arising from the use of this software.

   Permission is granted to anyone to use this software for any purpose,

   including commercial applications, and to alter it and redistribute it

   freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you must not

   claim that you wrote the original software. If you use this software

   in a product, an acknowledgment in the product documentation would be

   appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and must not be

   misrepresented as being the original software.

   3. This notice may not be removed or altered from any source distribution.

 */

 #include "SDL_config.h"

 /* General mouse handling code for SDL */

 #include "SDL_events.h"

 #include "SDL_events_c.h"

 #include "SDL_gesture_c.h"

 #include <memory.h>

 #include <string.h>

 #include <stdio.h>

 #include <math.h>

 //TODO: Replace with malloc

 #define MAXPATHSIZE 1024

 #define DOLLARNPOINTS 64

 #define DOLLARSIZE 256

 #define ENABLE_DOLLAR

 #define PHI 0.618033989

 typedef struct {

     float x,y;

 } SDL_FloatPoint;

 typedef struct {

     float length;

     int numPoints;

     SDL_FloatPoint p[MAXPATHSIZE];

 } SDL_DollarPath;

 typedef struct {

     SDL_FloatPoint path[DOLLARNPOINTS];

     unsigned long hash;

 } SDL_DollarTemplate;

 typedef struct {

     SDL_TouchID id;

     SDL_FloatPoint res;

     SDL_FloatPoint centroid;

     SDL_DollarPath dollarPath;

     Uint16 numDownFingers;

     int numDollarTemplates;

     SDL_DollarTemplate *dollarTemplate;

     SDL_bool recording;

 } SDL_GestureTouch;

 SDL_GestureTouch *SDL_gestureTouch;

 int SDL_numGestureTouches = 0;

 SDL_bool recordAll;

 #if 0

 static void PrintPath(SDL_FloatPoint *path)

 {

     int i;

     printf("Path:");

     for (i=0; i<DOLLARNPOINTS; i++) {

         printf(" (%f,%f)",path[i].x,path[i].y);

     }

     printf("\n");

 }

 #endif

 int SDL_RecordGesture(SDL_TouchID touchId)

 {

     int i;

     if (touchId < 0) recordAll = SDL_TRUE;

     for (i = 0; i < SDL_numGestureTouches; i++) {

         if ((touchId < 0) || (SDL_gestureTouch[i].id == touchId)) {

             SDL_gestureTouch[i].recording = SDL_TRUE;

             if (touchId >= 0)

                 return 1;

         }

     }

     return (touchId < 0);

 }

 static unsigned long SDL_HashDollar(SDL_FloatPoint* points)

 {

     unsigned long hash = 5381;

     int i;

     for (i = 0; i < DOLLARNPOINTS; i++) {

         hash = ((hash<<5) + hash) + (unsigned long)points[i].x;

         hash = ((hash<<5) + hash) + (unsigned long)points[i].y;

     }

     return hash;

 }

 static int SaveTemplate(SDL_DollarTemplate *templ, SDL_RWops * src)

 {

     if (src == NULL) return 0;

     //No Longer storing the Hash, rehash on load

     //if(SDL_RWops.write(src,&(templ->hash),sizeof(templ->hash),1) != 1) return 0;

     if (SDL_RWwrite(src,templ->path,

                     sizeof(templ->path[0]),DOLLARNPOINTS) != DOLLARNPOINTS)

         return 0;

     return 1;

 }

 int SDL_SaveAllDollarTemplates(SDL_RWops *src)

 {

     int i,j,rtrn = 0;

     for (i = 0; i < SDL_numGestureTouches; i++) {

         SDL_GestureTouch* touch = &SDL_gestureTouch[i];

         for (j = 0; j < touch->numDollarTemplates; j++) {

             rtrn += SaveTemplate(&touch->dollarTemplate[i],src);

         }

     }

     return rtrn;

 }

 int SDL_SaveDollarTemplate(SDL_GestureID gestureId, SDL_RWops *src)

 {

     int i,j;

     for (i = 0; i < SDL_numGestureTouches; i++) {

         SDL_GestureTouch* touch = &SDL_gestureTouch[i];

         for (j = 0; j < touch->numDollarTemplates; j++) {

             if (touch->dollarTemplate[i].hash == gestureId) {

                 return SaveTemplate(&touch->dollarTemplate[i],src);

             }

         }

     }

     SDL_SetError("Unknown gestureId");

     return -1;

 }

 //path is an already sampled set of points

 //Returns the index of the gesture on success, or -1

 static int SDL_AddDollarGesture_one(SDL_GestureTouch* inTouch, SDL_FloatPoint* path)

 {

     SDL_DollarTemplate* dollarTemplate;

     SDL_DollarTemplate *templ;

     int index;

     index = inTouch->numDollarTemplates;

     dollarTemplate =

         (SDL_DollarTemplate *)SDL_realloc(inTouch->dollarTemplate,

                                           (index + 1) *

                                           sizeof(SDL_DollarTemplate));

     if (!dollarTemplate) {

         SDL_OutOfMemory();

         return -1;

     }

     inTouch->dollarTemplate = dollarTemplate;

     templ = &inTouch->dollarTemplate[index];

     SDL_memcpy(templ->path, path, DOLLARNPOINTS*sizeof(SDL_FloatPoint));

     templ->hash = SDL_HashDollar(templ->path);

     inTouch->numDollarTemplates++;

     return index;

 }

 static int SDL_AddDollarGesture(SDL_GestureTouch* inTouch, SDL_FloatPoint* path)

 {

     int index = -1;

     int i = 0;

     if (inTouch == NULL) {

         if (SDL_numGestureTouches == 0) return -1;

         for (i = 0; i < SDL_numGestureTouches; i++) {

             inTouch = &SDL_gestureTouch[i];

             index = SDL_AddDollarGesture_one(inTouch, path);

             if (index < 0)

                 return -1;

         }

         // Use the index of the last one added.

         return index;

     } else {

         return SDL_AddDollarGesture_one(inTouch, path);

     }

     return -1;

 }

 int SDL_LoadDollarTemplates(SDL_TouchID touchId, SDL_RWops *src)

 {

     int i,loaded = 0;

     SDL_GestureTouch *touch = NULL;

     if (src == NULL) return 0;

     if (touchId >= 0) {

         for (i = 0; i < SDL_numGestureTouches; i++)

             if (SDL_gestureTouch[i].id == touchId)

                 touch = &SDL_gestureTouch[i];

         if (touch == NULL) return -1;

     }

     while (1) {

         SDL_DollarTemplate templ;

         if (SDL_RWread(src,templ.path,sizeof(templ.path[0]),DOLLARNPOINTS) <

            DOLLARNPOINTS) break;

         if (touchId >= 0) {

             //printf("Adding loaded gesture to 1 touch\n");

             if (SDL_AddDollarGesture(touch, templ.path) >= 0)

                 loaded++;

         }

         else {

             //printf("Adding to: %i touches\n",SDL_numGestureTouches);

             for (i = 0; i < SDL_numGestureTouches; i++) {

                 touch = &SDL_gestureTouch[i];

                 //printf("Adding loaded gesture to + touches\n");

                 //TODO: What if this fails?

                 SDL_AddDollarGesture(touch,templ.path);

             }

             loaded++;

         }

     }

     return loaded;

 }

 static float dollarDifference(SDL_FloatPoint* points,SDL_FloatPoint* templ,float ang)

 {

     //  SDL_FloatPoint p[DOLLARNPOINTS];

     float dist = 0;

     SDL_FloatPoint p;

     int i;

     for (i = 0; i < DOLLARNPOINTS; i++) {

         p.x = (float)(points[i].x * SDL_cos(ang) - points[i].y * SDL_sin(ang));

         p.y = (float)(points[i].x * SDL_sin(ang) + points[i].y * SDL_cos(ang));

         dist += (float)(SDL_sqrt((p.x-templ[i].x)*(p.x-templ[i].x)+

                                  (p.y-templ[i].y)*(p.y-templ[i].y)));

     }

     return dist/DOLLARNPOINTS;

 }

 static float bestDollarDifference(SDL_FloatPoint* points,SDL_FloatPoint* templ)

 {

     //------------BEGIN DOLLAR BLACKBOX----------------//

     //-TRANSLATED DIRECTLY FROM PSUDEO-CODE AVAILABLE AT-//

     //-"http://depts.washington.edu/aimgroup/proj/dollar/"-//

     double ta = -M_PI/4;

     double tb = M_PI/4;

     double dt = M_PI/90;

     float x1 = (float)(PHI*ta + (1-PHI)*tb);

     float f1 = dollarDifference(points,templ,x1);

     float x2 = (float)((1-PHI)*ta + PHI*tb);

     float f2 = dollarDifference(points,templ,x2);

     while (SDL_fabs(ta-tb) > dt) {

         if (f1 < f2) {

             tb = x2;

             x2 = x1;

             f2 = f1;

             x1 = (float)(PHI*ta + (1-PHI)*tb);

             f1 = dollarDifference(points,templ,x1);

         }

         else {

             ta = x1;

             x1 = x2;

             f1 = f2;

             x2 = (float)((1-PHI)*ta + PHI*tb);

             f2 = dollarDifference(points,templ,x2);

         }

     }

     /*

       if (f1 <= f2)

           printf("Min angle (x1): %f\n",x1);

       else if (f1 >  f2)

           printf("Min angle (x2): %f\n",x2);

     */

     return SDL_min(f1,f2);

 }

 //DollarPath contains raw points, plus (possibly) the calculated length

 static int dollarNormalize(const SDL_DollarPath *path,SDL_FloatPoint *points)

 {

     int i;

     float interval;

     float dist;

     int numPoints = 0;

     SDL_FloatPoint centroid;

     float xmin,xmax,ymin,ymax;

     float ang;

     float w,h;

     float length = path->length;

     //Calculate length if it hasn't already been done

     if (length <= 0) {

         for (i=1;i < path->numPoints; i++) {

             float dx = path->p[i  ].x - path->p[i-1].x;

             float dy = path->p[i  ].y - path->p[i-1].y;

             length += (float)(SDL_sqrt(dx*dx+dy*dy));

         }

     }

     //Resample

     interval = length/(DOLLARNPOINTS - 1);

     dist = interval;

     centroid.x = 0;centroid.y = 0;

     //printf("(%f,%f)\n",path->p[path->numPoints-1].x,path->p[path->numPoints-1].y);

     for (i = 1; i < path->numPoints; i++) {

         float d = (float)(SDL_sqrt((path->p[i-1].x-path->p[i].x)*(path->p[i-1].x-path->p[i].x)+

                                    (path->p[i-1].y-path->p[i].y)*(path->p[i-1].y-path->p[i].y)));

         //printf("d = %f dist = %f/%f\n",d,dist,interval);

         while (dist + d > interval) {

             points[numPoints].x = path->p[i-1].x +

                 ((interval-dist)/d)*(path->p[i].x-path->p[i-1].x);

             points[numPoints].y = path->p[i-1].y +

                 ((interval-dist)/d)*(path->p[i].y-path->p[i-1].y);

             centroid.x += points[numPoints].x;

             centroid.y += points[numPoints].y;

             numPoints++;

             dist -= interval;

         }

         dist += d;

     }

     if (numPoints < DOLLARNPOINTS-1) {

         SDL_SetError("ERROR: NumPoints = %i\n",numPoints);

         return 0;

     }

     //copy the last point

     points[DOLLARNPOINTS-1] = path->p[path->numPoints-1];

     numPoints = DOLLARNPOINTS;

     centroid.x /= numPoints;

     centroid.y /= numPoints;

     //printf("Centroid (%f,%f)",centroid.x,centroid.y);

     //Rotate Points so point 0 is left of centroid and solve for the bounding box

     xmin = centroid.x;

     xmax = centroid.x;

     ymin = centroid.y;

     ymax = centroid.y;

     ang = (float)(SDL_atan2(centroid.y - points[0].y,

                             centroid.x - points[0].x));

     for (i = 0; i<numPoints; i++) {

         float px = points[i].x;

         float py = points[i].y;

         points[i].x = (float)((px - centroid.x)*SDL_cos(ang) -

                               (py - centroid.y)*SDL_sin(ang) + centroid.x);

         points[i].y = (float)((px - centroid.x)*SDL_sin(ang) +

                               (py - centroid.y)*SDL_cos(ang) + centroid.y);

         if (points[i].x < xmin) xmin = points[i].x;

         if (points[i].x > xmax) xmax = points[i].x;

         if (points[i].y < ymin) ymin = points[i].y;

         if (points[i].y > ymax) ymax = points[i].y;

     }

     //Scale points to DOLLARSIZE, and translate to the origin

     w = xmax-xmin;

     h = ymax-ymin;

     for (i=0; i<numPoints; i++) {

         points[i].x = (points[i].x - centroid.x)*DOLLARSIZE/w;

         points[i].y = (points[i].y - centroid.y)*DOLLARSIZE/h;

     }

     return numPoints;

 }

 static float dollarRecognize(const SDL_DollarPath *path,int *bestTempl,SDL_GestureTouch* touch)

 {

     SDL_FloatPoint points[DOLLARNPOINTS];

     int i;

     float bestDiff = 10000;

     dollarNormalize(path,points);

     //PrintPath(points);

     *bestTempl = -1;

     for (i = 0; i < touch->numDollarTemplates; i++) {

         float diff = bestDollarDifference(points,touch->dollarTemplate[i].path);

         if (diff < bestDiff) {bestDiff = diff; *bestTempl = i;}

     }

     return bestDiff;

 }

 int SDL_GestureAddTouch(SDL_Touch* touch)

 {

     SDL_GestureTouch *gestureTouch = (SDL_GestureTouch *)SDL_realloc(SDL_gestureTouch,

                                                                      (SDL_numGestureTouches + 1) *

                                                                      sizeof(SDL_GestureTouch));

     if (!gestureTouch) {

         SDL_OutOfMemory();

         return -1;

     }

     SDL_gestureTouch = gestureTouch;

     SDL_gestureTouch[SDL_numGestureTouches].res.x = touch->xres;

     SDL_gestureTouch[SDL_numGestureTouches].res.y = touch->yres;

     SDL_gestureTouch[SDL_numGestureTouches].numDownFingers = 0;

     SDL_gestureTouch[SDL_numGestureTouches].res.x = touch->xres;

     SDL_gestureTouch[SDL_numGestureTouches].id = touch->id;

     SDL_gestureTouch[SDL_numGestureTouches].numDollarTemplates = 0;

     SDL_gestureTouch[SDL_numGestureTouches].recording = SDL_FALSE;

     SDL_numGestureTouches++;

     return 0;

 }

 static SDL_GestureTouch * SDL_GetGestureTouch(SDL_TouchID id)

 {

     int i;

     for (i = 0; i < SDL_numGestureTouches; i++) {

         //printf("%i ?= %i\n",SDL_gestureTouch[i].id,id);

         if (SDL_gestureTouch[i].id == id)

             return &SDL_gestureTouch[i];

     }

     return NULL;

 }

 int SDL_SendGestureMulti(SDL_GestureTouch* touch,float dTheta,float dDist)

 {

     SDL_Event event;

     event.mgesture.type = SDL_MULTIGESTURE;

     event.mgesture.touchId = touch->id;

     event.mgesture.x = touch->centroid.x;

     event.mgesture.y = touch->centroid.y;

     event.mgesture.dTheta = dTheta;

     event.mgesture.dDist = dDist;

     event.mgesture.numFingers = touch->numDownFingers;

     return SDL_PushEvent(&event) > 0;

 }

 static int SDL_SendGestureDollar(SDL_GestureTouch* touch,

                           SDL_GestureID gestureId,float error)

 {

     SDL_Event event;

     event.dgesture.type = SDL_DOLLARGESTURE;

     event.dgesture.touchId = touch->id;

     /*

     //TODO: Add this to give location of gesture?

     event.mgesture.x = touch->centroid.x;

     event.mgesture.y = touch->centroid.y;

     */

     event.dgesture.gestureId = gestureId;

     event.dgesture.error = error;

     //A finger came up to trigger this event.

     event.dgesture.numFingers = touch->numDownFingers + 1;

     return SDL_PushEvent(&event) > 0;

 }

 static int SDL_SendDollarRecord(SDL_GestureTouch* touch,SDL_GestureID gestureId)

 {

     SDL_Event event;

     event.dgesture.type = SDL_DOLLARRECORD;

     event.dgesture.touchId = touch->id;

     event.dgesture.gestureId = gestureId;

     return SDL_PushEvent(&event) > 0;

 }

 void SDL_GestureProcessEvent(SDL_Event* event)

 {

     float x,y;

     SDL_FloatPoint path[DOLLARNPOINTS];

     int index;

     int i;

     float pathDx, pathDy;

     SDL_FloatPoint lastP;

     SDL_FloatPoint lastCentroid;

     float lDist;

     float Dist;

     float dtheta;

     float dDist;

     if (event->type == SDL_FINGERMOTION ||

         event->type == SDL_FINGERDOWN ||

         event->type == SDL_FINGERUP) {

         SDL_GestureTouch* inTouch = SDL_GetGestureTouch(event->tfinger.touchId);

         //Shouldn't be possible

         if (inTouch == NULL) return;

         //printf("@ (%i,%i) with res: (%i,%i)\n",(int)event->tfinger.x,

         //           (int)event->tfinger.y,

         //   (int)inTouch->res.x,(int)inTouch->res.y);

         x = ((float)event->tfinger.x)/(float)inTouch->res.x;

         y = ((float)event->tfinger.y)/(float)inTouch->res.y;

         //Finger Up

         if (event->type == SDL_FINGERUP) {

             inTouch->numDownFingers--;

 #ifdef ENABLE_DOLLAR

             if (inTouch->recording) {

                 inTouch->recording = SDL_FALSE;

                 dollarNormalize(&inTouch->dollarPath,path);

                 //PrintPath(path);

                 if (recordAll) {

                     index = SDL_AddDollarGesture(NULL,path);

                     for (i = 0; i < SDL_numGestureTouches; i++)

                         SDL_gestureTouch[i].recording = SDL_FALSE;

                 }

                 else {

                     index = SDL_AddDollarGesture(inTouch,path);

                 }

                 if (index >= 0) {

                     SDL_SendDollarRecord(inTouch,inTouch->dollarTemplate[index].hash);

                 }

                 else {

                     SDL_SendDollarRecord(inTouch,-1);

                 }

             }

             else {

                 int bestTempl;

                 float error;

                 error = dollarRecognize(&inTouch->dollarPath,

                                         &bestTempl,inTouch);

                 if (bestTempl >= 0){

                     //Send Event

                     unsigned long gestureId = inTouch->dollarTemplate[bestTempl].hash;

                     SDL_SendGestureDollar(inTouch,gestureId,error);

                     //printf ("%s\n",);("Dollar error: %f\n",error);

                 }

             }

 #endif

             //inTouch->gestureLast[j] = inTouch->gestureLast[inTouch->numDownFingers];

             if (inTouch->numDownFingers > 0) {

                 inTouch->centroid.x = (inTouch->centroid.x*(inTouch->numDownFingers+1)-

                                        x)/inTouch->numDownFingers;

                 inTouch->centroid.y = (inTouch->centroid.y*(inTouch->numDownFingers+1)-

                                        y)/inTouch->numDownFingers;

             }

         }

         else if (event->type == SDL_FINGERMOTION) {

             float dx = ((float)event->tfinger.dx)/(float)inTouch->res.x;

             float dy = ((float)event->tfinger.dy)/(float)inTouch->res.y;

             //printf("dx,dy: (%f,%f)\n",dx,dy);

 #ifdef ENABLE_DOLLAR

             SDL_DollarPath* path = &inTouch->dollarPath;

             if (path->numPoints < MAXPATHSIZE) {

                 path->p[path->numPoints].x = inTouch->centroid.x;

                 path->p[path->numPoints].y = inTouch->centroid.y;

                 pathDx =

                     (path->p[path->numPoints].x-path->p[path->numPoints-1].x);

                 pathDy =

                     (path->p[path->numPoints].y-path->p[path->numPoints-1].y);

                 path->length += (float)SDL_sqrt(pathDx*pathDx + pathDy*pathDy);

                 path->numPoints++;

             }

 #endif

             lastP.x = x - dx;

             lastP.y = y - dy;

             lastCentroid = inTouch->centroid;

             inTouch->centroid.x += dx/inTouch->numDownFingers;

             inTouch->centroid.y += dy/inTouch->numDownFingers;

             //printf("Centrid : (%f,%f)\n",inTouch->centroid.x,inTouch->centroid.y);

             if (inTouch->numDownFingers > 1) {

                 SDL_FloatPoint lv; //Vector from centroid to last x,y position

                 SDL_FloatPoint v; //Vector from centroid to current x,y position

                 //lv = inTouch->gestureLast[j].cv;

                 lv.x = lastP.x - lastCentroid.x;

                 lv.y = lastP.y - lastCentroid.y;

                 lDist = (float)SDL_sqrt(lv.x*lv.x + lv.y*lv.y);

                 //printf("lDist = %f\n",lDist);

                 v.x = x - inTouch->centroid.x;

                 v.y = y - inTouch->centroid.y;

                 //inTouch->gestureLast[j].cv = v;

                 Dist = (float)SDL_sqrt(v.x*v.x+v.y*v.y);

                 // SDL_cos(dTheta) = (v . lv)/(|v| * |lv|)

                 //Normalize Vectors to simplify angle calculation

                 lv.x/=lDist;

                 lv.y/=lDist;

                 v.x/=Dist;

                 v.y/=Dist;

                 dtheta = (float)SDL_atan2(lv.x*v.y - lv.y*v.x,lv.x*v.x + lv.y*v.y);

                 dDist = (Dist - lDist);

                 if (lDist == 0) {dDist = 0;dtheta = 0;} //To avoid impossible values

                 //inTouch->gestureLast[j].dDist = dDist;

                 //inTouch->gestureLast[j].dtheta = dtheta;

                 //printf("dDist = %f, dTheta = %f\n",dDist,dtheta);

                 //gdtheta = gdtheta*.9 + dtheta*.1;

                 //gdDist  =  gdDist*.9 +  dDist*.1

                 //knob.r += dDist/numDownFingers;

                 //knob.ang += dtheta;

                 //printf("thetaSum = %f, distSum = %f\n",gdtheta,gdDist);

                 //printf("id: %i dTheta = %f, dDist = %f\n",j,dtheta,dDist);

                 SDL_SendGestureMulti(inTouch,dtheta,dDist);

             }

             else {

                 //inTouch->gestureLast[j].dDist = 0;

                 //inTouch->gestureLast[j].dtheta = 0;

                 //inTouch->gestureLast[j].cv.x = 0;

                 //inTouch->gestureLast[j].cv.y = 0;

             }

             //inTouch->gestureLast[j].f.p.x = x;

             //inTouch->gestureLast[j].f.p.y = y;

             //break;

             //pressure?

         }

         if (event->type == SDL_FINGERDOWN) {

             inTouch->numDownFingers++;

             inTouch->centroid.x = (inTouch->centroid.x*(inTouch->numDownFingers - 1)+

                                    x)/inTouch->numDownFingers;

             inTouch->centroid.y = (inTouch->centroid.y*(inTouch->numDownFingers - 1)+

                                    y)/inTouch->numDownFingers;

             //printf("Finger Down: (%f,%f). Centroid: (%f,%f\n",x,y,

             //     inTouch->centroid.x,inTouch->centroid.y);

 #ifdef ENABLE_DOLLAR

             inTouch->dollarPath.length = 0;

             inTouch->dollarPath.p[0].x = x;

             inTouch->dollarPath.p[0].y = y;

             inTouch->dollarPath.numPoints = 1;

 #endif

         }

     }

 }

 /* vi: set ts=4 sw=4 expandtab: */