#ifdef BSPTEST

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

#include "bsptree.h"

typedef unsigned char uchar;

struct State{
  uchar y,u,v;
  State *next;

  uchar val(int i)
    {return(((uchar*)this)[i]);}
  void set(uchar _y,uchar _u,uchar _v)
    {y=_y; u=_u; v=_v;}
};

typedef BSPTree<State,float,3> Tree;

// large prime p such that: 2(p-1 + 255) < 2^32
//                          p < 2^31 - 254
const uint32_t prime_base = 2147483353;
uint32_t signature = 0;

void AddToSig(uchar c)
{
  signature += c;
  signature = (signature + signature) % prime_base;
}

int main()
{
  int i,k;

  const int num = 1000000;
  const int queries = 16*64*64;

  State state[num],st,*s;
  double d;
  Tree tree;

  for(i=0; i<num; i++){
    state[i].y = rand() & 0xFF;
    state[i].u = rand() & 0xFF;
    state[i].v = rand() & 0xFF;
    state[i].next = NULL;
    tree.add(&state[i]);
  }

  printf("building..."); fflush(stdout);
  tree.build();
  printf("done.\n");

  for(i=0; i<16*64*64; i++){
    st.set(rand()&0xFF, rand()&0xFF, rand()&0xFF);

    tree.startQuery(st);
    k = 0;
    while(k<4 && (s = tree.getNextNearest(d))){
      // printf("%d (%3d %3d %3d) %f\n",i,s->y,s->u,s->v,d);
      AddToSig(s->y);
      AddToSig(s->u);
      AddToSig(s->v);

      k++;
    }
    tree.endQuery();

    if(i%100 == 0){
      printf("\r%2d%%",100*i/queries);
      fflush(stdout);
    }
  }
  printf("\r%2d%%\n",100*i/queries);

  printf("signature: %08x\n",signature);

  return(0);
}

#endif