#include "shadeop.h"
#include "alloca.h"
#include <math.h>
#include <sys/stat.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>


typedef struct Particle {
   float pos[3];     // The particle's position
   short plane;      // Splitting plane
} Particle;


// Structure used to locate the nearest particle
typedef struct NearestParticles {
   int max;
   int found;
   int gotHeap;
   float pos[3];
   float *dist2;
   const Particle** index;
} NearestParticles;

// Balanced particle map
typedef struct BalancedParticleMap {
   int storedParticles;
   Particle* particles;
   int halfStoredParticles;
} BalancedParticleMap;

// Flat particle map.  Used to build Kd-tree
typedef struct ParticleMap {
   int storedParticles;
   Particle* particles;
   int halfStoredParticles;
   int maxParticles;
   float boundingBoxMin[3];
   float boundingBoxMax[3];
} ParticleMap;

ParticleMap* CreateParticleMap(int maxParticles);
void StoreParticle(ParticleMap* map, const float pos[3]);
void LocateParticles(BalancedParticleMap* map, NearestParticles* const np, const int index);
BalancedParticleMap* BalanceParticleMap(ParticleMap* map);
float DensityEstimate(BalancedParticleMap* map, const float pos[3], const float maxDistance, const int count);
void DestroyParticleMap(BalancedParticleMap* map);
void SaveParticleMap(BalancedParticleMap* bmap, char* filename);
BalancedParticleMap* LoadParticleMap(char* filename);