#ifndef OCTSAMPLER
#define OCTSAMPLER

#include "PointSet.h"

#include <math.h>

class OctSampler;

class OctSamplerCell{
public:
  OctSampler* _tree;
  
  //center of the cell
  float _cx, _cy, _cz;
  
  int _level;
  OctSamplerCell** _sub_cell;
  
  //index of point-set included in the cell
  int _start, _end;
  
  OctSamplerCell(OctSampler* tree, float cx, float cy, float cz, int level, int start, int end){
    _tree = tree;
    
    _cx = cx;
    _cy = cy;
    _cz = cz;
    _level = level;
    
    _sub_cell = NULL;
    
    _start = start;
    _end = end;
  }
  
  ~OctSamplerCell(){
    if(_sub_cell != NULL){
      for(int i=0; i<8; i++)
        if(_sub_cell[i] != NULL)
          delete _sub_cell[i];
      delete[] _sub_cell;
    }
  }
  
  void split();
  int split1D(int s, int e, int index);
  
  void averagedLeafSize(double& total, int max_point);
  void countPoints(int& count, int target_level);
  void collectPoints(PointSet* qs, int& count, int target_level);
};

class OctSampler{
public:
  PointSet* _ps;
  OctSamplerCell* _root;
  float max[3], min[3];
  
  //half size of bounding box
  float _sx, _sy, _sz;
  
  OctSampler(PointSet* ps){
    _ps = ps;
    
    _ps->getBound(min, max, 1.0f);
    
    _sx = 0.5f*(max[0] - min[0]);
    _sy = 0.5f*(max[1] - min[1]);
    _sz = 0.5f*(max[2] - min[2]);
    
    float cx = 0.5f*(max[0]+min[0]);
    float cy = 0.5f*(max[1]+min[1]);
    float cz = 0.5f*(max[2]+min[2]);
    _root = new OctSamplerCell(this, cx, cy, cz, 0, 0, _ps->_pointN);
  }
  
  ~OctSampler(){
    delete _root;
  }
  
  float averagedLeafSize(int max_point){
    double total = 0.0;
    _root->averagedLeafSize(total, max_point);
    
    return (float)(total/_ps->_pointN);
  }
  
  PointSet* getPointSet(int level){
    int count = 0;
    _root->countPoints(count, level);
    PointSet* qs = new PointSet();
    qs->setPointSize(count);
    count = 0;
    _root->collectPoints(qs, count, level);
    return qs;
  }
  
  inline float sizeX(int level){
    return (float)(_sx*pow(2, -level));
  }
  
  inline float sizeY(int level){
    return (float)(_sy*pow(2, -level));
  }
  
  inline float sizeZ(int level){
    return (float)(_sz*pow(2, -level));
  }
};

#endif