#include <GL/gl.h>

#include <GL/glu.h>

#include <glut.h>

#include <stdio.h>

#include <stdlib.h>

#include <sys/types.h>

#include <time.h>

#include <math.h>

#include <vector>

#include <map>

#include <set>



//#include "Omnidroid11Constants.h"



using namespace std;



#define WINDOW_WIDTH 640

#define WINDOW_HEIGHT 480

#define SCALE 0.01f



#define NUM_PARTICLES 10000

#define PARTICLE_DELAY 1

#define FIGHT_DISTANCE  8*150.0f*150.0f*150.0f





#define RADIANS(x) (3.14159f/180.0f*(x))

#define DSINF(x) sinf(RADIANS(x))

#define DCOSF(x) cosf(RADIANS(x))

#define EPSILON  0.000000000000000000000000001



#define KEY_UP        0

#define KEY_DOWN      1

#define KEY_LEFT      2

#define KEY_RIGHT     3

#define KEY_FORWARD   4

#define KEY_BACKWARD  5

#define MAX_KEY       6



typedef map<int, map<int, float> > ssfMap;

typedef map<int, float> sfMap;



float K_MEANS_RADIUS = 1000.0f;



int g_keys[MAX_KEY];



float g_eye[] = {0.0f, 20.0f, 0.0f};

float g_xrot = 0.0f;

float g_yrot = 135.0f;

float g_xpos = 0.0f;



static bool g_displayPoints = false;

static int g_displayLocations = 0;



static int lineBase = 0; //draws a sequence of 100 consecutive points



static int g_maxDist = 0;



#define ASSERT(x) \

    if(!(x)) { printf("assertion '%s' (%d) failed\n", #x, __LINE__); abort(); }



#define LERP(t, a, b) \

    ((a) + (t)*((b) - (a)))



#define MAX(a, b) \

    (((a) > (b)) ? (a) : (b))



#define MIN(a, b) \

    (((a) < (b)) ? (a) : (b))



#define LENGTH_SQR(x, y, z) \

    (((x) * (x)) + ((y) * (y))+ ((z) * (z)))



enum Value {

    NORMAL,

    GOOD,

    BAD

};



struct SPoint {

    short x, y, z;



    SPoint(short nx, short ny, short nz):

	x(nx),

	y(ny),

	z(nz)

    {

    }

};



struct DataPoint {

    short x, y, z;

    int location;

    time_t t;



    short health;

    char healthChange;

    char weapon;

    char ammo;

    char frag;

    char fired;





    DataPoint() :

	location(-1)

    {

    }

};



struct Location {

    SPoint point;

    size_t importance;

    size_t importance2;

    ssfMap neighbors;

    //map<int, float> itemPoints;

    ssfMap itemPoints;



    explicit Location(const SPoint &p):

	point(p),

	importance(0),

	importance2(0)

    {

    }

};



struct Particle {

    int current;

    int previous;



    explicit Particle(int cur):

	current(cur),

	previous(-1)

    {

    }	

};



//possible more interesting points near:

//quake.4926.1084466356.log:

//1178, 2638, 3270, 3683, 3710, 3993, 4247, 4627, 5028

//quake.4926.1084467536.log:

//709

int CURRENT_POSITION = 1<<30; //we initialize these properly later

int OPPONENT_POSITION = 1<<30;

int CURRENT_START_INTERVAL = 0;

int OPPONENT_START_INTERVAL = 0;



vector<Location> g_locations;

vector<DataPoint> g_points;

vector<DataPoint> g_opponentPoints;

set<int> g_spawnPoints;

set<int> g_itemPoints;

set<int> g_spawnLocations;

set<int> g_itemLocations;

vector<Particle> g_particles;



static void initParticles();

static void updateParticles();

static void resampleParticles();



static void

displayBox(float r, float g, float b)

{

    static const float x0 = -0.5f;

    static const float y0 = -0.5f;

    static const float z0 = -0.5f;

    static const float x1 = 0.5f;

    static const float y1 = 0.5f;

    static const float z1 = 0.5f;



    float pt0[] = {x0, y0, z0};

    float pt1[] = {x0, y0, z1};

    float pt2[] = {x0, y1, z0};

    float pt3[] = {x0, y1, z1};

    float pt4[] = {x1, y0, z0};

    float pt5[] = {x1, y0, z1};

    float pt6[] = {x1, y1, z0};

    float pt7[] = {x1, y1, z1};



    glBegin(GL_QUADS);



    glColor3f(r/2,g/2, b/2);

    glVertex3fv(pt0);

    glVertex3fv(pt1);

    glColor3f(r,g, b);

    glVertex3fv(pt3);

    glVertex3fv(pt2);



    glColor3f(r/2,g/2, b/2);

    glVertex3fv(pt1);

    glVertex3fv(pt5);

    glColor3f(r,g, b);

    glVertex3fv(pt7);

    glVertex3fv(pt3);



    glColor3f(r/2,g/2, b/2);

    glVertex3fv(pt5);

    glVertex3fv(pt4);

    glColor3f(r,g, b);

    glVertex3fv(pt6);

    glVertex3fv(pt7);



    glColor3f(r/2,g/2, b/2);

    glVertex3fv(pt4);

    glVertex3fv(pt0);

    glColor3f(r,g, b);

    glVertex3fv(pt2);

    glVertex3fv(pt6);



    glVertex3fv(pt3);

    glVertex3fv(pt7);

    glVertex3fv(pt6);

    glVertex3fv(pt2);



    glEnd();

}



static void

displayTetra(float r, float g, float b)

{

    static GLfloat vertexArray[] = {0.0f, -1.0f, 0.0f,

				    1.0f,  1.0f, 0.0f,

				    -0.5f, 1.0f, 0.87f,

				    -0.5f, 1.0f, -0.87f};

    

    GLfloat colorArray[] = {0.0f, 0.0f, 0.0f,

			    r, g, b,

			    r, g, b,

			    r, g, b};

    

    static GLubyte indices[] = {

			       0, 1, 2,

			       0, 2, 3,

			       0, 3, 1,

			       1, 3, 2,

    };



    glVertexPointer(3, GL_FLOAT, 3*sizeof(GLfloat), vertexArray);

    glColorPointer(3, GL_FLOAT, 3*sizeof(GLfloat), colorArray);



    glEnableClientState(GL_VERTEX_ARRAY);

    glEnableClientState(GL_COLOR_ARRAY);



    glDrawElements(GL_TRIANGLES, 12, GL_UNSIGNED_BYTE, indices);



    glDisableClientState(GL_COLOR_ARRAY);

    glDisableClientState(GL_VERTEX_ARRAY);

}



static void

keyboard(unsigned char key, int x, int y)

{

    switch(key) {

    case 'l':

	g_displayLocations = (g_displayLocations + 1) % 3;

	break;

    case 'p':

	g_displayPoints = ! g_displayPoints;

	lineBase = rand()%(g_points.size()-250);

	break;

    case 'i':

	g_keys[KEY_FORWARD] = 1;

	break;

    case 'k':

	g_keys[KEY_BACKWARD] = 1;

	break;

    case 'w':

	g_keys[KEY_UP] = 1;

	break;

    case 's':

	g_keys[KEY_DOWN] = 1;

	break;

    case 'a':

	g_keys[KEY_LEFT] = 1;

	break;

    case 'd':

	g_keys[KEY_RIGHT] = 1;

	break;

    }

}



static void

keyboardUp(unsigned char key, int x, int y)

{

    switch(key) {

    case 'i':

	g_keys[KEY_FORWARD] = 0;

	break;

    case 'k':

	g_keys[KEY_BACKWARD] = 0;

	break;

    case 'w':

	g_keys[KEY_UP] = 0;

	break;

    case 's':

	g_keys[KEY_DOWN] = 0;

	break;

    case 'a':

	g_keys[KEY_LEFT] = 0;

	break;

    case 'd':

	g_keys[KEY_RIGHT] = 0;

	break;

    }

}





static void

display()

{  

    glClearColor(0.0f, 1.0f, 1.0f, 1.0f);

    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);



    glMatrixMode(GL_PROJECTION);

    glLoadIdentity();

    gluPerspective(60.0, ((float)WINDOW_WIDTH)/WINDOW_HEIGHT, 1.0f, 1000.0f);

    gluLookAt(0.0f, 0.0f, 0.0f,

	      0.0f, 0.0f, -1.0f,

	      0.0f, 1.0f, 0.0f);

    glRotatef(g_xrot, 1.0f, 0.0f, 0.0f);

    glRotatef(g_yrot, 0.0f, 1.0f, 0.0f);

    glTranslatef(-g_eye[0], -g_eye[1], -g_eye[2]);



    glMatrixMode(GL_MODELVIEW);

    glLoadIdentity();



    if(g_displayPoints) {

	for(size_t ii = 0; ii < g_points.size(); ++ ii) {

	    const DataPoint &p = g_points[ii];

	    

	    glPushMatrix();

	    

	    glTranslatef(p.x*SCALE, p.y*SCALE, p.z*SCALE);



	    if(p.healthChange == -1)

		displayTetra(0.0f, 0.0f, 0.0f);

	    else if(p.frag != 0)

		displayTetra(1.0f, 1.0f, 1.0f);

	    else if(p.healthChange == 2)

		displayTetra(1.0f, 0.0f, 0.0f);

		/*

	    else if(p.healthChange == 1)

		displayTetra(0.0f, 1.0f, 0.0f);

	    else if(p.ammo != -1)

		displayTetra(0.0f, 1.0f, 1.0f);

	    else if(p.weapon != -1)

		displayTetra(0.0f, 0.0f, 1.0f);

		*/

	    else if(p.fired != 0)

		displayTetra(1.0f, 1.0f, 0.0f);

            else if(ii >= lineBase && ii < lineBase+250)

		displayTetra(0.5f, 0.5f, 0.5f);

		/*

	    else 

		displayTetra(0.5f, 0.5f, 0.5f);

		*/

	    

	    glPopMatrix();

	}

	

	/*

	  glColor3f(1.0f, 1.0f, 0.0f);

	  glBegin(GL_LINES);

	  for(size_t ii = 0; ii < g_points.size(); ++ ii) {

	  const DataPoint &p = g_points[ii];

	  

	  const SPoint &l = g_locations[p.location].point;

	  glVertex3f(p.x*SCALE, p.y*SCALE, p.z*SCALE);

	  glVertex3f(l.x*SCALE, l.y*SCALE, l.z*SCALE);

	  }

	  glEnd();

	*/

    }



    if(1 == 1) {

        const DataPoint &p = g_points[CURRENT_POSITION];

        glPushMatrix();

	glTranslatef(p.x*SCALE, p.y*SCALE, p.z*SCALE);

	    if(p.healthChange == -1)

		displayTetra(0.0f, 0.0f, 0.0f);

	    else if(p.frag != 0)

		displayTetra(1.0f, 1.0f, 1.0f);

	    else if(p.healthChange == 2)

		displayTetra(1.0f, 0.0f, 0.0f);

	    else if(p.healthChange == 1)

		displayTetra(0.0f, 1.0f, 0.0f);

	    else if(p.ammo != -1)

		displayTetra(0.0f, 1.0f, 1.0f);

	    else if(p.weapon != -1)

		displayTetra(0.0f, 0.0f, 1.0f);

	    else if(p.fired != 0)

		displayTetra(1.0f, 1.0f, 0.0f);

	    else 

		displayTetra(1.0f, 1.0f, 1.0f);

	glPopMatrix();



        const DataPoint &q = g_opponentPoints[OPPONENT_POSITION];

        glPushMatrix();

	glTranslatef(q.x*SCALE, q.y*SCALE, q.z*SCALE);

	displayTetra(0.0f, 0.0f, 0.0f);

	glPopMatrix();

    }



    if(g_displayLocations != 2) {



	for(size_t ii = 0; ii < g_locations.size(); ++ ii) {

	    g_locations[ii].importance = 0;

	}



	for(size_t ii = 0; ii < g_particles.size(); ++ ii) {

	    g_locations[g_particles[ii].current].importance += 1;

	}



	if(g_displayLocations == 0)

	    glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);



	for(size_t ii = 0; ii < g_locations.size(); ++ ii) {

	    const SPoint &l = g_locations[ii].point;

	    size_t imp = g_locations[ii].importance;

	    

	    glPushMatrix();

	    

	    glTranslatef(l.x*SCALE, l.y*SCALE, l.z*SCALE);

	    //glScalef(5.0f, 5.0f, 5.0f);

	    glScalef(imp/20.0f, imp/20.0f, imp/20.0f);

	    //glScalef(sqrtf(imp)/5.0f, sqrtf(imp)/5.0f, sqrtf(imp)/5.0f);

	    if(g_spawnLocations.find(ii) != g_spawnLocations.end())

	        displayBox(0.3f, 0.7f, 0.3f);

	    else if(g_itemLocations.find(ii) != g_itemLocations.end())

	        displayBox(1.0f, 1.0f, 1.0f);

	    else

	        displayBox(0.3f, 0.3f, 0.7f);

	    

	    glPopMatrix();

	}



        //Find the closes location and check its probability

        int currPosIndex = 0;

        double dist = LENGTH_SQR(

	        g_locations[0].point.x - g_points[CURRENT_POSITION].x,

                g_locations[0].point.y - g_points[CURRENT_POSITION].y,

                g_locations[0].point.z - g_points[CURRENT_POSITION].z);

        for(int ii = 0; ii < g_locations.size(); ii++) {

            double d2 = LENGTH_SQR(

	       g_locations[ii].point.x - g_points[CURRENT_POSITION].x,

               g_locations[ii].point.y - g_points[CURRENT_POSITION].y,

               g_locations[ii].point.z - g_points[CURRENT_POSITION].z);

            if(d2 < dist) {

	        dist = d2;

	        currPosIndex = ii;

	    }

        }



/*

        int maxTarget = 0;

	float maxProb = -1.0;

	for(map<int, float>::const_iterator ii = g_locations[currPosIndex].itemPoints.begin(); ii != g_locations[currPosIndex].itemPoints.end(); ii++)

	{

	    if(maxProb < ii->second)

	    {

	        maxTarget = ii->first;

	        maxProb = ii->second;

	    }

	}

	for(map<int, float>::const_iterator ii = g_locations[currPosIndex].itemPoints.begin(); ii != g_locations[currPosIndex].itemPoints.end(); ii++)

	{

//printf("MAX PROB=%f   %d   curr=%d  %d\n", maxProb, maxTarget, currPosIndex, g_locations.size());

	    const SPoint &l = g_locations[ii->first].point;

	    glPushMatrix();

	    glTranslatef(l.x*SCALE, l.y*SCALE, l.z*SCALE);

	    //glScalef(5.0f, 5.0f, 5.0f);

	    glScalef(ii->second*50.0f, ii->second*50.0f, ii->second*50.0f);

	    //glScalef(sqrtf(imp)/5.0f, sqrtf(imp)/5.0f, sqrtf(imp)/5.0f);

	    if(ii->second == maxProb)

	        displayBox(1.0f, 0.0f, 0.0f);

	    else

	        displayBox(0.5f, 0.0f, 0.0f);

	    glPopMatrix();

	}

*/



	glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);

	

	glColor3f(1.0f, 0.0f, 1.0f);

	glBegin(GL_LINES);

	for(size_t ii = 0; ii < g_locations.size(); ++ ii) {

	    const SPoint &l = g_locations[ii].point;

	    

	    for(ssfMap::const_iterator jj =

		    g_locations[ii].neighbors.begin();

		jj != g_locations[ii].neighbors.end(); ++ jj) {



		for(sfMap::const_iterator kk = jj->second.begin();

		    kk != jj->second.end(); ++kk) {

		    const SPoint &nl = g_locations[kk->first].point;

		    glVertex3f(l.x*SCALE, l.y*SCALE, l.z*SCALE);

		    glVertex3f(nl.x*SCALE, nl.y*SCALE, nl.z*SCALE);

		}

	    }

	}

	glEnd();	    

    }



    glutSwapBuffers();

    glutPostRedisplay();





    if(g_keys[KEY_FORWARD]) {

	float fwd[] = {0.0f, 0.0f, -2.0f};

	float fwd2[] = {0.0f, 0.0f, 0.0f};

	

	fwd2[0] = 1*fwd[0] + 0*fwd[1] + 0*fwd[2];

	fwd2[1] = 0*fwd[0] + DCOSF(g_xrot)*fwd[1] + DSINF(g_xrot)*fwd[2];

	fwd2[2] = 0*fwd[0] - DSINF(g_xrot)*fwd[1] + DCOSF(g_xrot)*fwd[2];



	fwd[0] = DCOSF(g_yrot)*fwd2[0] + 0*fwd2[1] - DSINF(g_yrot)*fwd2[2];

	fwd[1] = 0*fwd2[0] + 1*fwd2[1] + 0*fwd2[2];

	fwd[2] = DSINF(g_yrot)*fwd2[0] + 0*fwd2[1] + DCOSF(g_yrot)*fwd2[2];



	g_eye[0] += fwd[0];

	g_eye[1] += fwd[1];

	g_eye[2] += fwd[2];

    }

    if(g_keys[KEY_BACKWARD]) {

	float fwd[] = {0.0f, 0.0f, 2.0f};

	float fwd2[] = {0.0f, 0.0f, 0.0f};

	

	fwd2[0] = 1*fwd[0] + 0*fwd[1] + 0*fwd[2];

	fwd2[1] = 0*fwd[0] + DCOSF(g_xrot)*fwd[1] + DSINF(g_xrot)*fwd[2];

	fwd2[2] = 0*fwd[0] - DSINF(g_xrot)*fwd[1] + DCOSF(g_xrot)*fwd[2];



	fwd[0] = DCOSF(g_yrot)*fwd2[0] + 0*fwd2[1] - DSINF(g_yrot)*fwd2[2];

	fwd[1] = 0*fwd2[0] + 1*fwd2[1] + 0*fwd2[2];

	fwd[2] = DSINF(g_yrot)*fwd2[0] + 0*fwd2[1] + DCOSF(g_yrot)*fwd2[2];



	g_eye[0] += fwd[0];

	g_eye[1] += fwd[1];

	g_eye[2] += fwd[2];

    }

    if(g_keys[KEY_UP]) {

	g_xrot += 1.5f;

    } 

    if(g_keys[KEY_DOWN]) {

	g_xrot -= 1.5f;

    } 

    if(g_keys[KEY_LEFT]) {

	g_yrot -= 1.5f;

    }

    if(g_keys[KEY_RIGHT]) {

	g_yrot += 1.5f;

    }



    static int frames = 0;

    static unsigned long prevTime = 0;

    unsigned long curTime = (unsigned long)time(NULL);

    ++ frames;

    if(curTime != prevTime) {

	prevTime = curTime;

	//printf("%d\n", frames);

	frames = 0;

    }

}



static void

timer(int id)

{

    updateParticles();

    resampleParticles();

    glutTimerFunc(PARTICLE_DELAY, timer, id);

}



static void

getNeighbors(const SPoint &mean, float radius,

	     const vector<SPoint> &points,

	     vector<SPoint> *out)

{

    out->clear();



    float radSqr = radius * radius;



    for(size_t ii = 0; ii < points.size(); ++ ii) {

	const SPoint &p = points[ii];

	float xDist = mean.x - p.x;

	float yDist = mean.y - p.y;

	float zDist = mean.z - p.z;



	if(LENGTH_SQR(xDist, yDist, zDist) < radSqr) {

	    out->push_back(SPoint(p.x, p.y, p.z));

	}

    }

}



static SPoint

averageNeighbors(const vector<SPoint> &points)

{

    int sumx = 0;

    int sumy = 0;

    int sumz = 0;

    int size = points.size();



    for(size_t ii = 0; ii < points.size(); ++ ii) {

	const SPoint &p = points[ii];



	//printf("[%d %d %d]\n", p.x, p.y, p.z);

	sumx += p.x;

	sumy += p.y;

	sumz += p.z;

    }



    return SPoint(sumx / size,

		  sumy / size,

		  sumz / size);

}



static void

removeNeighbors(vector<SPoint> *pool, const SPoint &toRemove)

{

    for(vector<SPoint>::iterator jj = pool->begin();

	jj != pool->end(); ++ jj) {

	

	if(toRemove.x == jj->x &&

	   toRemove.y == jj->y &&

	   toRemove.z == jj->z) {

	    pool->erase(jj);

	    break;

	}

    }

}



static void

removeNeighbors(vector<SPoint> *pool, const vector<SPoint> &toRemove)

{

    for(vector<SPoint>::const_iterator ii = toRemove.begin();

	ii != toRemove.end(); ++ ii) {

	for(vector<SPoint>::iterator jj = pool->begin();

	    jj != pool->end(); ++ jj) {

	    

	    if(ii->x == jj->x &&

	       ii->y == jj->y &&

	       ii->z == jj->z) {

		pool->erase(jj);

		break;

	    }

	}

    }

}



static void

doKMeans(const vector<DataPoint> &points, float radius)

{

    vector<SPoint> pool;

    vector<SPoint> neighbors;



    for(size_t ii = 0; ii < points.size(); ++ ii) {

	const DataPoint &p = points[ii];

	pool.push_back(SPoint(p.x, p.y, p.z));

    }



    //printf("%zu\n", pool.size());





    SPoint mean(pool[0].x, pool[0].y, pool[0].z);

    

    while(pool.size() > 0) {

	getNeighbors(mean, radius, pool, &neighbors);

	

	if(neighbors.size() == 0) {

	    g_locations.push_back(Location(mean));

	    removeNeighbors(&pool, mean);

	    mean = SPoint(pool[0].x, pool[0].y, pool[0].z);

	    continue;

	}

	

	SPoint newMean = averageNeighbors(neighbors);

	

	//printf("%d %d %d -> ", mean.x, mean.y, mean.z);

	//printf("%d %d %d\n", newMean.x, newMean.y, newMean.z);

	

	if(LENGTH_SQR(mean.x - newMean.x,

		      mean.y - newMean.y,

		      mean.z - newMean.z) < 100) {

	    g_locations.push_back(Location(mean));

	    removeNeighbors(&pool, neighbors);

	    mean = SPoint(pool[0].x, pool[0].y, pool[0].z);

	    continue;

	}



	mean = newMean;

    }



    //printf("%zu %zu\n", pool.size(), neighbors.size());

}



static void

buildConnectivity(vector<Location> & locations)

{

    for(size_t ii = 0; ii < g_points.size(); ++ ii) {

	DataPoint &p = g_points[ii];



	int closestLocation = 0;

	float closestDist =

	    LENGTH_SQR(p.x - locations[closestLocation].point.x,

		       p.y - locations[closestLocation].point.y,

		       p.z - locations[closestLocation].point.z);

	

	for(size_t jj = 1; jj < locations.size(); ++ jj) {

	    float curDist =

		LENGTH_SQR(p.x - locations[jj].point.x,

			   p.y - locations[jj].point.y,

			   p.z - locations[jj].point.z);

	    if(curDist < closestDist) {

		closestLocation = jj;

		closestDist = curDist;

	    }

	}

	

	p.location = closestLocation;

    }



    for(size_t ii = 0; ii < g_points.size() - 1; ++ ii) {

	++ locations[g_points[ii].location].importance;

	if(g_spawnPoints.find(ii) != g_spawnPoints.end()) {

	    g_spawnLocations.insert(g_points[ii].location);

	}

	if(g_itemPoints.find(ii) != g_itemPoints.end()) {

	    g_itemLocations.insert(g_points[ii].location);

	}

    }



    int from = -1;

    int itemTargetStart = 0;

    int targetPrev = -1;

    for(size_t ii = 0; ii < g_points.size() - 1; ++ ii) {

	const DataPoint &p0 = g_points[ii];

	const DataPoint &p1 = g_points[ii + 1];

	int loc0 = p0.location;

	int loc1 = p1.location;



        /* If we didn't die, update the neighbors */

        if(p0.healthChange != -1) {

	    locations[loc0].neighbors[from][loc1] += 1;

	    //locations[loc1].neighbors[loc0] += 1;



	    if(loc0 != loc1) 

	        from = loc0;

	}

	else {

	    itemTargetStart = ii;

	    targetPrev = -1;

	    from = -1;

	}



	if(g_itemLocations.find(loc1) != g_itemLocations.end()) {

	    if(loc0 == loc1) {

	        itemTargetStart = loc0;

		targetPrev = loc0;

	        continue;

	    }

	    while(itemTargetStart < ii) {

		if(g_points[itemTargetStart].location 

		   != g_points[itemTargetStart+1].location) {

	           g_locations[g_points[itemTargetStart].location]

		                        .itemPoints[targetPrev][loc1] += 1;

		   targetPrev = g_points[itemTargetStart].location;

		}

		itemTargetStart++;

	    }

	}

    }



    for(size_t ii = 0; ii < locations.size(); ++ ii) {

        for(ssfMap::const_iterator kk = locations[ii].neighbors.begin();

	    kk != locations[ii].neighbors.end(); ++kk) {



	    float sum = 0;

	    for(sfMap::const_iterator jj =

		    kk->second.begin();

	            jj != kk->second.end(); ++ jj) {

	        sum += jj->second;

	    }

    

	    for(map<int, float>::const_iterator jj =

		    kk->second.begin();

	            jj != kk->second.end(); ++ jj) {

	        locations[ii].neighbors[kk->first][jj->first] /= sum;

	    }

	}

	    for(ssfMap::const_iterator jj =

		    locations[ii].itemPoints.begin();

	        jj != locations[ii].itemPoints.end(); ++ jj) {

                float sum = 0.0;

		for(sfMap::const_iterator kk = jj->second.begin();

		    kk != jj->second.end(); kk++) {

	            sum += kk->second;

		}

		for(sfMap::const_iterator kk = jj->second.begin();

		    kk != jj->second.end(); kk++) {

		    locations[ii].itemPoints[jj->first][kk->first] /= sum;

//printf("Set item points[%d].ip[%d][%d] = %f\n", ii, jj->first, kk->first, kk->second);

		}

	    }

    

    /*

	    for(map<int, float>::const_iterator jj =

		    locations[ii].itemPoints.begin();

	        jj != locations[ii].itemPoints.end(); ++ jj) {

	        locations[ii].itemPoints[jj->first] /= sum;

	    }

    */

    }



    printf("Total number of item locations: %d %f\n", g_itemLocations.size(), 1.0/g_itemLocations.size());



}



/* Writes an ascii file describing the connectivity and importance graphs */

static bool 

saveGraph(const char *fileName)

{

    FILE *graphFile = NULL;

    graphFile = fopen(fileName, "w");



    if(!graphFile) return false;



    fprintf(graphFile, "%zu\n", g_spawnLocations.size());

    

    for(set<int>::const_iterator ii = g_spawnLocations.begin();

	ii != g_spawnLocations.end(); ++ ii) {

	fprintf(graphFile, "%d\n", *ii);

    }



    fprintf(graphFile, "%zu\n", g_itemLocations.size());

    

    for(set<int>::const_iterator ii = g_itemLocations.begin();

	ii != g_itemLocations.end(); ++ ii) {

	fprintf(graphFile, "%d\n", *ii);

    }





    for(size_t ii = 0; ii < g_locations.size(); ++ ii) {

        if( 0 > fprintf(graphFile, "%d %d %d %d %zu %zu\n", 

			g_locations[ii].point.x,

			g_locations[ii].point.y,

			g_locations[ii].point.z,

			g_locations[ii].importance,

			g_locations[ii].neighbors.size(),

			g_locations[ii].itemPoints.size()))

	{

	    fclose(graphFile);

	    return false;

	}

	for(ssfMap::const_iterator jj =

		g_locations[ii].neighbors.begin();

	    jj != g_locations[ii].neighbors.end(); ++ jj) {

	    fprintf(graphFile, "%d %d\n", jj->first, jj->second.size());

	    for(sfMap::const_iterator kk = jj->second.begin();

	        kk != jj->second.end(); kk++) {

	    fprintf(graphFile,"%d %f\n", (*kk).first, (*kk).second);

	    }

	}

	for(ssfMap::const_iterator jj = 

	        g_locations[ii].itemPoints.begin();

		jj!= g_locations[ii].itemPoints.end(); ++jj) {

	    fprintf(graphFile, "%d %d\n", jj->first, jj->second.size());

	    for(sfMap::const_iterator kk = jj->second.begin();

	        kk != jj->second.end(); kk++) {

	    fprintf(graphFile,"%d %f\n", (*kk).first, (*kk).second);

	    }

	}

    }



    fclose(graphFile);

    return true;

}



/* Writes an ascii file describing the connectivity and importance graphs */

static bool 

loadGraph(const char *fileName)

{

    FILE *graphFile = NULL;

    graphFile = fopen(fileName, "r");

    

    if(!graphFile) return false;



    int numSpawnLocations;

    fscanf(graphFile, "%d\n", &numSpawnLocations);



    for(int ii = 0; ii < numSpawnLocations; ++ ii) {

	int id;

	fscanf(graphFile, "%d\n", &id);	

	g_spawnLocations.insert(id);

    }



    int numItemLocations;

    fscanf(graphFile, "%d\n", &numItemLocations);



    for(int ii = 0; ii < numItemLocations; ++ ii) {

	int id;

	fscanf(graphFile, "%d\n", &id);	

	g_itemLocations.insert(id);

    }







    Location toAdd(SPoint(0, 0, 0));

    int numNeighbors;

    int numItemPoints;



    while(!feof(graphFile)) {

	fscanf(graphFile, "%d %d %d %d %d %d\n",

	       &toAdd.point.x, &toAdd.point.y, &toAdd.point.z,

	       &toAdd.importance, &numNeighbors, &numItemPoints);



	if(feof(graphFile))

	    break;



	for(int ii = 0; ii < numNeighbors; ++ ii) {

	    int prevId, count;

	    fscanf(graphFile, "%d %d\n", &prevId, &count);

	    for(int jj = 0; jj < count; jj++)

	    {

	        int id;

	        float prob;

	        fscanf(graphFile, "%d %f\n", &id, &prob);

	        toAdd.neighbors[prevId][id] = prob;

//if(g_locations.size() == 0)

//printf("setting 0: %d/%d  %d/%d  %d %d %f\n", ii, numNeighbors, jj, count, id, prevId, prob);

	    }

	}



	for(int ii = 0; ii < numItemPoints; ++ ii) {

	    int prevId, count;

	    fscanf(graphFile, "%d %d\n", &prevId, &count);

	    for(int jj = 0; jj < count; jj++)

	    {

	        int id;

	        float prob;

	        fscanf(graphFile, "%d %f\n", &id, &prob);

	        toAdd.itemPoints[prevId][id] = prob;

//if(g_locations.size() == 0)

//printf("setting 0: %d/%d  %d/%d  %d %d %f\n", ii, numNeighbors, jj, count, id, prevId, prob);

	    }

	}

	g_locations.push_back(toAdd);

	toAdd.neighbors.clear();

	toAdd.itemPoints.clear();

    }



    fclose(graphFile);

    return true;

}



static bool

loadLogFile(const char *fileName, vector<DataPoint> & points)

{

    int startRecord = -1;

    int endRecord = 1<<30;

    int currentRecord = -1;



    FILE *configFile = NULL;

    configFile = fopen("kldiv.cfg", "r");

    if(configFile != NULL) {

        fscanf(configFile, "%d %d", &startRecord, &endRecord);

        fclose(configFile);

    }

    printf("Using records: [%d, %d]\n", startRecord, endRecord);



    

    FILE *logFile = NULL;

    logFile = fopen(fileName, "r");



    if(!logFile)

	return false;



    g_spawnPoints.insert(0);



    short x, y, z;

    time_t currtime;

    short currhealth;

    char healthChange, weap, ammo, frag, fired;

    int wasDeadFlag = 0;

    while(!feof(logFile)) {

	fread(&x, sizeof(short), 1, logFile);

	if(feof(logFile))

	    break;

	fread(&z, sizeof(short), 1, logFile);

	fread(&y, sizeof(short), 1, logFile);

	fread(&currtime, sizeof(time_t), 1, logFile);

	fread(&currhealth, sizeof(short), 1, logFile);

	fread(&healthChange, sizeof(char), 1, logFile);

	fread(&weap, sizeof(char), 1, logFile);

	fread(&ammo, sizeof(char), 1, logFile);

	fread(&frag, sizeof(char), 1, logFile);

	fread(&fired, sizeof(char), 1, logFile);





	//printf("%d: %d %d %d\n", goodness, x, y, z);



	if(wasDeadFlag != 0 && healthChange == ((char)0xFF))

	    continue;

        

	if(wasDeadFlag != 0 && healthChange != ((char)0xFF))

	   g_spawnPoints.insert(points.size());



        if(healthChange == 1 || weap != -1 || ammo != -1 )

	    g_itemPoints.insert(points.size());



        if(points.size() > 0 && wasDeadFlag == 0 && 

	       LENGTH_SQR(x-points[points.size()-1].x, 

	                  y-points[points.size()-1].y, 

			  z-points[points.size()-1].z) > g_maxDist)

	{

	    g_maxDist = LENGTH_SQR(x-points[points.size()-1].x,

	                          y-points[points.size()-1].y,

				  z-points[points.size()-1].z);

	}



        if(healthChange == ((char)0xFF))

	    wasDeadFlag = 1;

	else

	    wasDeadFlag = 0;



	DataPoint p;

	p.x = x;

	p.y = y;

	p.z = z;

	p.t = currtime;



	p.health = currhealth;

	p.healthChange = healthChange;

	p.weapon = weap;

	p.ammo = ammo;

	p.frag = frag;

	p.fired = fired;





/*

        if(p.healthChange != 0) printf("healthChange:%d\n", (int)p.healthChange);

	if(p.weapon != -1) printf("weapon:%d\n", (int)p.weapon);

	if(p.ammo != -1) printf("ammo:%d\n", (int)p.ammo);

	if(p.frag != 0) printf("frag:%d\n", (int)p.frag);

	if(p.fired != 0) printf("fired:%d\n", (int)p.fired);

*/



        /*

	if(goodness == 0)

	    p.value = NORMAL;

	else if(goodness > 0)

	    p.value = GOOD;

	if(goodness < 0)

	    p.value = BAD;

        */



	{

	}



	currentRecord++;

	if(startRecord >= 0 && currentRecord >= startRecord && currentRecord <= endRecord)

	    points.push_back(p);

	else if(startRecord < 0 && (currentRecord < -startRecord || currentRecord > -endRecord))

	{

	    //if(currentRecord + 1 >= -startRecord) p.healthChange = -1;

	    points.push_back(p);

	}

	else

	{

	    //printf("Skipping %d\n", currentRecord);

	}



    }



    fclose(logFile);



    printf("Maximum distance: %d\n", g_maxDist);

    printf("Number of points: %d\n", points.size());

    printf("Delta time: %d - %d = %d   avg:%f\n", points[points.size()-1].t, points[0].t, points[points.size()-1].t - points[0].t, (points[points.size()-1].t - points[0].t)/(double)points.size());



    return true;

}



static float

frand(float lo, float hi)

{

    return lo + ((rand() % RAND_MAX) / (float)RAND_MAX) * (hi - lo);

}



static void

initParticles()

{

    g_particles.clear();

    if(g_spawnLocations.size() == 0)

	return;



    vector<int> tempSpawnLocations(g_spawnLocations.begin(),

				   g_spawnLocations.end());



    g_particles.clear();

    for(int ii = 0; ii < NUM_PARTICLES; ++ ii) {

	int spawnIndex = rand() % tempSpawnLocations.size();

	

	g_particles.push_back(Particle(tempSpawnLocations[spawnIndex]));

    }

}



static void

updateParticles()

{



    CURRENT_POSITION++;

    OPPONENT_POSITION++;



    if(g_points[CURRENT_POSITION].t < g_opponentPoints[OPPONENT_POSITION].t) {

        for(;

            CURRENT_POSITION < g_points.size();

            CURRENT_POSITION++) {

            if(g_points[CURRENT_POSITION].t >= g_opponentPoints[OPPONENT_POSITION].t)

                break;

        }

    }

    else if(g_points[CURRENT_POSITION].t > g_opponentPoints[OPPONENT_POSITION].t)

    {

        for(;

            OPPONENT_POSITION < g_opponentPoints.size();

            OPPONENT_POSITION++) {

            if(g_opponentPoints[OPPONENT_POSITION].t >= g_points[CURRENT_POSITION].t)

                break;

        }

    }



    if(CURRENT_POSITION >= g_points.size() 

       || OPPONENT_POSITION >= g_opponentPoints.size())

    {

        CURRENT_POSITION = CURRENT_START_INTERVAL;

	OPPONENT_POSITION = OPPONENT_START_INTERVAL;

	initParticles();

	return;

    }





    vector<int> tempSpawnLocations(g_spawnLocations.begin(),

				   g_spawnLocations.end());



    for(int ii = 0; ii < g_particles.size(); ++ ii) {

        int prevCurrent = g_particles[ii].current;



	ASSERT(g_particles[ii].current < g_locations.size());

	ASSERT(g_particles[ii].previous == -1 || g_particles[ii].previous < g_locations.size());



	Location &loc = g_locations[g_particles[ii].current];

	float rand = frand(0.0f, 1.0f);

	int nextIndex = -1;



/*

	if(loc.neighbors.size() == 0)

	    continue;

*/

        int prevLoc = g_particles[ii].previous;



	for(sfMap::const_iterator jj = loc.neighbors[prevLoc].begin();

	    jj != loc.neighbors[prevLoc].end(); ++ jj) {



	    nextIndex = jj->first;

	    if(rand < jj->second)// && nextIndex != g_particles[ii].previous)

		break;

            rand -= jj->second;

	}



	if(loc.neighbors[prevLoc].size() == 0 || (loc.neighbors[prevLoc].size()==1 && loc.neighbors[prevLoc].begin()->first == ii)) {

	    if(frand(0.0f, 1.0f) > 0.6f || nextIndex == -1) {

	        //nextIndex = tempSpawnLocations[(int)frand(0.0f, tempSpawnLocations.size()-0.000001f)];

		g_particles[ii].current = tempSpawnLocations[(int)frand(0.0f, tempSpawnLocations.size()-0.000001f)];

		g_particles[ii].previous = -1;

		continue;

	    }

	}



	ASSERT(nextIndex != -1);

	

	g_particles[ii].current = nextIndex;



        if(g_particles[ii].current != prevCurrent)

	    g_particles[ii].previous = prevCurrent;

    }



    //Find the closes location and check its probability

    int opponentPosIndex = 0;

    double dist = LENGTH_SQR(

               g_locations[0].point.x - g_opponentPoints[OPPONENT_POSITION].x,

               g_locations[0].point.y - g_opponentPoints[OPPONENT_POSITION].y,

               g_locations[0].point.z - g_opponentPoints[OPPONENT_POSITION].z);

    for(int ii = 0; ii < g_locations.size(); ii++) {

        double d2 = LENGTH_SQR(

	       g_locations[ii].point.x - g_opponentPoints[OPPONENT_POSITION].x,

               g_locations[ii].point.y - g_opponentPoints[OPPONENT_POSITION].y,

               g_locations[ii].point.z - g_opponentPoints[OPPONENT_POSITION].z);

        if(d2 < dist) {

	    dist = d2;

	    opponentPosIndex = ii;

	}

    }



    double count = 0.0;

    for(int ii = 0; ii < g_particles.size(); ii++)

    {

        if(g_particles[ii].current == opponentPosIndex) count+=1.0;

    }



    for(size_t ii = 0; ii < g_locations.size(); ++ ii) {

            g_locations[ii].importance2 = 0;

    }



    for(size_t ii = 0; ii < g_particles.size(); ++ ii) {

           g_locations[g_particles[ii].current].importance2 += 1;

    }



    int maxImportance = 0;

    for(size_t i = 0; i < g_locations.size(); i++) {

        if(g_locations[i].importance2 > maxImportance)

            maxImportance = g_locations[i].importance2;

    }



    int isMax = 0;

    if(maxImportance == g_locations[opponentPosIndex].importance2)

        isMax = 1;

    //printf("Prediction accuracy = %f    %d\n", count/((double)g_particles.size()), isMax);



}



static void 

resampleParticles()

{

    if(g_points[CURRENT_POSITION].frag || g_opponentPoints[OPPONENT_POSITION].healthChange == -1) {

        fprintf(stderr, "Fragged at %d\n", CURRENT_POSITION);

        initParticles();

	return;

    }

    if(g_points[CURRENT_POSITION].fired 

       || g_points[CURRENT_POSITION].healthChange == -1

       || g_points[CURRENT_POSITION].healthChange == 2) {



       vector<Particle> tmpParticles;

       SPoint *nextpoint;

fprintf(stderr, "had indication! %d %d %d %d    %d\n", CURRENT_POSITION, g_points[CURRENT_POSITION].x, g_points[CURRENT_POSITION].y, g_points[CURRENT_POSITION].z, g_points[CURRENT_POSITION].t-g_opponentPoints[OPPONENT_POSITION].t);



       for(int ii = 0; ii < g_particles.size(); ++ii) {

           nextpoint = &g_locations[g_particles[ii].current].point;



//fprintf(stderr, "%d %d %d\n", nextpoint->x, nextpoint->y, nextpoint->z);

//fprintf(stderr, "%f\n", LENGTH_SQR(g_points[CURRENT_POSITION].x-nextpoint->x, g_points[CURRENT_POSITION].y-nextpoint->y, g_points[CURRENT_POSITION].z-nextpoint->z)+0.0f);



           if(LENGTH_SQR(g_points[CURRENT_POSITION].x-nextpoint->x,

                         g_points[CURRENT_POSITION].y-nextpoint->y,

                         g_points[CURRENT_POSITION].z-nextpoint->z) 

			     < FIGHT_DISTANCE) {

                tmpParticles.push_back(Particle(g_particles[ii].current));

		tmpParticles[tmpParticles.size() - 1].previous = g_particles[ii].previous;

	    }

       }



       if(tmpParticles.size() == 0) return;

       for(int ii = 0; ii < g_particles.size(); ++ii) {

           int index = rand()%tmpParticles.size();

           g_particles[ii].current = tmpParticles[index].current;

           g_particles[ii].previous = tmpParticles[index].previous;

       }



       tmpParticles.clear();

       return;

    }

    return;

}



/* requires the model loaded from a graph and the points loaded and

   filtered.

*/

static double

computeItemStatistics()

{

    int startPos = -1;

    int prevLoc = -1;

    /* reset the locations, since we loaded a different model */

    for(size_t ii = 0; ii < g_points.size(); ++ ii) {

	DataPoint &p = g_points[ii];



	int closestLocation = 0;

	float closestDist =

	    LENGTH_SQR(p.x - g_locations[closestLocation].point.x,

		       p.y - g_locations[closestLocation].point.y,

		       p.z - g_locations[closestLocation].point.z);

	

	for(size_t jj = 1; jj < g_locations.size(); ++ jj) {

	    float curDist =

		LENGTH_SQR(p.x - g_locations[jj].point.x,

			   p.y - g_locations[jj].point.y,

			   p.z - g_locations[jj].point.z);

	    if(curDist < closestDist) {

		closestLocation = jj;

		closestDist = curDist;

	    }

	}

	

	p.location = closestLocation;



	if(ii > 0 && startPos == -1 && p.location != g_points[ii-1].location) {

	    startPos = ii;

	    prevLoc = g_points[ii-1].location;

	}

    }



    double sum = 0.0;

    int count = 0;

    for(size_t ii = startPos; ii < g_points.size()-1; ++ii) {

        if(g_points[ii].healthChange == -1) {

	    startPos = ii+1;

	    prevLoc = -1;

	}

        else if(g_itemLocations.find(g_points[ii].location) != g_itemLocations.end())

	{

//printf("WENT TO ITEM LOCATION: %d    %d\n", g_points[ii].location, startPos);

	    if(ii > 0 && g_points[ii].location == g_points[ii-1].location) {

	        startPos = ii;

		prevLoc = g_points[ii].location;

	        continue;

	    }

            while(startPos < ii) {

		if(g_points[startPos].location != g_points[startPos+1].location)

		{

//printf("Found transition: loc[%d].ip[%d][%d] = %f\n", g_points[startPos].location, prevLoc, g_points[ii].location, g_locations[g_points[startPos].location].itemPoints[prevLoc][g_points[ii].location]);

float maxProbability = 0.0;

                    for(sfMap::const_iterator kk = g_locations[g_points[startPos].location].itemPoints[prevLoc].begin();

		        kk != g_locations[g_points[startPos].location].itemPoints[prevLoc].end(); ++kk) {

			    if(kk->second > maxProbability)

			        maxProbability = kk->second;

			}

			if(maxProbability != 0 && maxProbability == g_locations[g_points[startPos].location] .itemPoints[prevLoc][g_points[ii].location] )

			    sum += 1.0;

		    //sum += g_locations[g_points[startPos].location]

		                   //.itemPoints[prevLoc][g_points[ii].location];

		    count++;

		    prevLoc = g_points[startPos].location;

		}

		startPos++;

	    }

	}

    }



printf("Total accuracy was: %f    %f\n", sum/count, 1.0/g_itemLocations.size());

exit(0);

    return sum/count;

}



static double 

computeKLDivergence()

{

    vector<Location> newLocations;

    for(int ii = 0; ii < g_locations.size(); ii++)

    {

        newLocations.push_back(Location(g_locations[ii].point));

    }



    buildConnectivity(newLocations);

    

    double divergence = 0.0;

    for(int ii = 0; ii < g_locations.size(); ii++)

    {

      for(ssfMap::const_iterator kk = g_locations[ii].neighbors.begin();

          kk != g_locations[ii].neighbors.end(); ++kk) {

        for(map<int, float>::const_iterator jj =

                    g_locations[ii].neighbors[kk->first].begin();

                jj != g_locations[ii].neighbors[kk->first].end(); ++ jj) {

 

            if(jj->second == 0.0f) continue;



            //XXX@@@what do we do in this case?????

	    if(newLocations[ii].neighbors[kk->first][jj->first] == 0.0f)

	        continue;





	    divergence += newLocations[ii].neighbors[kk->first][jj->first] *

	                  log(newLocations[ii].neighbors[kk->first][jj->first]/jj->second);

//printf("newLoc[%d].nbrs[%d] = %f     g_loc=%f     %f\n", ii, jj->first, newLocations[ii].neighbors[jj->first], jj->second, divergence);

	}

	}

    }



    printf("KL-Divergence was: %f\n", divergence);



    for(ssfMap::const_iterator ii = g_locations[0].neighbors.begin();

        ii != g_locations[0].neighbors.end(); ++ii) {



	for(sfMap::const_iterator jj = ii->second.begin();

	    jj != ii->second.end(); ++jj) {

printf("%f    %f    %d %d\n", g_locations[0].neighbors[ii->first][jj->first],

newLocations[0].neighbors[ii->first][jj->first], g_locations[0].neighbors[ii->first].size(), newLocations[0].neighbors[ii->first].size());

        }

    }



    //I don't think the way of computing the divergence above is fair, since 

    //it hides terms when there is no transition probability.  So let's look 

    //at how closely their predictions match each other over a series of

    //250 update steps, using a full MM.



    if(newLocations.size() != g_locations.size())

    {

        fprintf(stderr, "GAAAAAAAAAAAAAAAAAAAH! %d %d\n", newLocations.size(), g_locations.size());

	exit(12);

    }



    double* probNewLoc = (double*)malloc(newLocations.size()*sizeof(double));

    double* probGLoc = (double*)malloc(g_locations.size()*sizeof(double));

    double* tmpNL = (double*)malloc(g_locations.size()*sizeof(double));

    double* tmpGL = (double*)malloc(g_locations.size()*sizeof(double));

    map<int, map<int, double> > gLocPriors; //stores how much came from each position

    map<int, map<int, double> > newLocPriors; //stores how much came from each position

    map<int, map<int, double> > tmpgLocPriors; //stores how much came from each position

    map<int, map<int, double> > tmpnewLocPriors; //stores how much came from each position



    //initialize the probability models to be the same.

    for(int ii = 0; ii < newLocations.size(); ii++)

    {

        if(g_spawnLocations.find(ii) != g_spawnLocations.end())

	{

	    probNewLoc[ii] = 1.0/g_spawnLocations.size();

	    probGLoc[ii] = 1.0/g_spawnLocations.size();

	    newLocPriors[ii][-1] = 1.0/g_spawnLocations.size();

	    gLocPriors[ii][-1] = 1.0/g_spawnLocations.size();

	}

	else

	{

            probNewLoc[ii] = 0.0;

            probGLoc[ii] = 0.0;

	}

    }



    //250 is about the amt of time needed to completely cover the map

    //i.e. if the opponent starts at an unknown spawn point, then

    //within 250 datapoints (X sec) they could be anywhere on the map

    //measuring divergence after this shouldn't affect much

    for(int iter = 0; iter < 1000; iter++)

    {

        //update both model's probabilities in parallel

	tmpgLocPriors.clear();

	tmpnewLocPriors.clear();

	for(int i = 0; i < g_locations.size(); i++)

	{

	    tmpNL[i] = probNewLoc[i];

	    tmpGL[i] = probGLoc[i];



	    probNewLoc[i] = 0.000000000000000000000000001;

	    probGLoc[i] = 0.000000000000000000000000001;

	    for(map<int, double>::const_iterator jj = gLocPriors[i].begin();

	        jj != gLocPriors[i].end(); ++jj){

		tmpgLocPriors[i][jj->first] = jj->second;

	    }

	    for(map<int, double>::const_iterator jj = newLocPriors[i].begin();

	        jj != newLocPriors[i].end(); ++jj){

		tmpnewLocPriors[i][jj->first] = jj->second;

	    }



	}

	gLocPriors.clear();

        newLocPriors.clear();

	for(int ii = 0; ii < g_locations.size(); ii++)

	{

	    //model 1 updates

	    for(ssfMap::const_iterator jj =

                    newLocations[ii].neighbors.begin();

                    jj != newLocations[ii].neighbors.end(); ++ jj) {

		for(sfMap::const_iterator kk = jj->second.begin();

		    kk != jj->second.end(); ++kk) {

		    //if(tmpnewLocPriors[ii][jj->first] <= 0) tmpnewLocPriors[ii][jj->first] = EPSILON;

                    double asdf = tmpNL[ii]*kk->second*tmpnewLocPriors[ii][jj->first];

		    //probNewLoc[ii] -= asdf;

                    probNewLoc[kk->first] += asdf;

		    newLocPriors[kk->first][ii] += asdf;

		}

            }

	    //model 2 updates

	    for(ssfMap::const_iterator jj =

                    g_locations[ii].neighbors.begin();

                jj != g_locations[ii].neighbors.end(); ++ jj) {

		for(sfMap::const_iterator kk = jj->second.begin();

		    kk != jj->second.end(); ++kk) {

		    //if(tmpgLocPriors[ii][jj->first] <= 0) tmpgLocPriors[ii][jj->first] = EPSILON;

                    double asdf = tmpGL[ii]*kk->second*tmpgLocPriors[ii][jj->first];

		    //probGLoc[ii] -= asdf;

                    probGLoc[kk->first] += asdf;

		    gLocPriors[kk->first][ii] += asdf;

		}

            }

	}



        //must renormalize everything to ensure sum of probs = 1,

	//otherwise bad things (tm) happen

	double sum1 = 0.0;

	double sum2 = 0.0;

	for(int ii = 0; ii < g_locations.size(); ii++)

	{

	    sum1 += probNewLoc[ii];

	    sum2 += probGLoc[ii];

	}

	for(int ii = 0; ii < g_locations.size(); ii++)

	{

	    probNewLoc[ii] = probNewLoc[ii]/sum1;

	    probGLoc[ii] = probGLoc[ii]/sum2;

	    

	    double sumPriors = 0.0;

	    for(map<int, double>::const_iterator jj = newLocPriors[ii].begin();

	        jj != newLocPriors[ii].end(); ++jj) {

		sumPriors += jj->second;

	    }

	    for(map<int, double>::const_iterator jj = newLocPriors[ii].begin();

	        jj != newLocPriors[ii].end(); ++jj) {

		if(sumPriors != 0.0)

		newLocPriors[ii][jj->first] = jj->second/sumPriors;

	    }



	    sumPriors = 0.0;

	    for(map<int, double>::const_iterator jj = gLocPriors[ii].begin();

	        jj != gLocPriors[ii].end(); ++jj) {

		sumPriors += jj->second;

	    }

	    for(map<int, double>::const_iterator jj = gLocPriors[ii].begin();

	        jj != gLocPriors[ii].end(); ++jj) {

		if(sumPriors != 0.0)

		gLocPriors[ii][jj->first] = jj->second/sumPriors;

	    }

	}



	//finally, recompute the divergence of the two models

	divergence = 0.0;

	for(int ii = 0; ii < g_locations.size(); ii++)

	{

	    //is this fair? 

	    //if(probGLoc[ii] == 0) continue;



	    divergence += probNewLoc[ii] * log(((double)probNewLoc[ii])/probGLoc[ii])/log(2);  //divide by log2 b/c i think that's how KL is supposed to be

	    // Don't want it this way

	    //is this fair? 

	    //if(probNewLoc[ii] == 0) continue;



	    //divergence += probGLoc[ii] * log(((double)probGLoc[ii])/probNewLoc[ii])/log(2);  //divide by log2 b/c i think that's how KL is supposed to be

	}

	printf("%d's divergence was %f\n", iter, divergence);

    }



exit(0);

    return divergence;

}



static void

loadOpponent(const char *fileName)

{

    if(!loadLogFile(fileName, g_opponentPoints)) {

        printf("error opening opponent log file\n");

	exit(-1);

    }



    //find out where they sync up

    if(g_points[0].t < g_opponentPoints[0].t) {

        OPPONENT_START_INTERVAL = 0;

        for(CURRENT_START_INTERVAL = 0; 

	    CURRENT_START_INTERVAL < g_points.size(); 

	    CURRENT_START_INTERVAL++) {

	    if(g_points[CURRENT_START_INTERVAL].t >= g_opponentPoints[0].t)

	        break;

	}

    }

    else

    {

        CURRENT_START_INTERVAL = 0;

	for(OPPONENT_START_INTERVAL = 0;

	    OPPONENT_START_INTERVAL < g_opponentPoints.size();

	    OPPONENT_START_INTERVAL++) {

	    if(g_opponentPoints[OPPONENT_START_INTERVAL].t >= g_points[0].t)

	        break;

	}

    }



    printf("Start time differential: %d\n", g_points[CURRENT_START_INTERVAL].t-g_opponentPoints[OPPONENT_START_INTERVAL].t);

}





int

main(int argc, char *argv[])

{

    if(argc != 3 && argc != 4) {

	printf("usage: go logfile opponentFile [-o<graphOutFile>|-k<klDivergenceGraph>|-i<itemPredictionGraph>]\n");

	exit(-1);

    }



    K_MEANS_RADIUS = 500.0f;

    //fscanf(stdin, "%f\n", &K_MEANS_RADIUS);

    printf("Using radius of %f\n", K_MEANS_RADIUS);



    const char *fileName = argv[1];

    bool readingLog = false;



    if(strstr(fileName, ".log")) {

	readingLog = true;

	printf("Reading log...\n");

	if(!loadLogFile(fileName, g_points)) {

	    printf("error opening log file\n");

	    exit(0);

	}

    } else if(strstr(fileName, ".graph")) {

	printf("Reading graph...\n");

	if(!loadGraph(fileName)) {

	    printf("error opening graph file\n");

	    exit(0);

	}

    } else {

	printf("unknown file extension\n");

	exit(0);

    }



    if(readingLog) {

	printf("Finding locations...\n");

	doKMeans(g_points, K_MEANS_RADIUS);

	

	printf("Building connectivity...\n");

        buildConnectivity(g_locations);

//printf("Computing Item Stats...\n");

//computeItemStatistics();

	//exit(0);



	loadOpponent(argv[2]);

	

	if(argc == 4 && argv[3][1] == 'o') {

	    printf("Saving graph file to %s...\n", argv[3]+2);

	    saveGraph(argv[3]+2);

	}

	else if(argc == 4 && argv[3][1] == 'i') {

	    printf("Loading item model graph %s...\n", argv[3]+2);

	    g_locations.clear();

	    if(!loadGraph(argv[3]+2))

	    {

	        printf("error opening graph file %s\n", argv[3]+2);

		exit(0);

	    }

	    printf("Computing Item Stats...\n");

	    computeItemStatistics();

	    exit(0);

	}

	else if(argc == 4 && argv[3][1] == 'k') {

	    printf("Loading kl-divergence graph %s...\n", argv[3]+2);

            g_locations.clear();

	    if(!loadGraph(argv[3]+2))

	    {

	        printf("error opening graph file %s\n", argv[3]+2);

		exit(0);

	    }

	    printf("Computing kl-divergence %s...\n", argv[3]+2);

	    computeKLDivergence();

	}

	else {

	    if(argc == 4)

	    printf("Unrecognized option %c%c for second parameter...ignoring\n",

	           argv[3][0], argv[3][1]);

	}



    }



//if(0 == 0) exit(0);



    srand(time(0));

    initParticles();



    printf("Done!\n");



    int ii;

    for(ii = 0; ii < MAX_KEY; ++ ii)

	g_keys[ii] = 0;



    glutInit(&argc, argv);

    glutInitDisplayMode(GLUT_DOUBLE | GLUT_DEPTH);

    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);

    glutCreateWindow("Quake 2 Data Viewer");



    glHint(GL_POLYGON_SMOOTH_HINT, GL_FASTEST);

    glEnable(GL_CULL_FACE);

    glEnable(GL_DEPTH_TEST);



    glutKeyboardFunc(keyboard);

    glutKeyboardUpFunc(keyboardUp);

    glutDisplayFunc(display);

    glutTimerFunc(PARTICLE_DELAY, timer, -1);



    glutMainLoop();

}