#include       <iostream>
#include       <iomanip>
#include       <vector>

using namespace std;

#include        "point.h"
#include        "tree.h"
        
// prototypes
int     main(int argc, char **argv);
                
int main(int argc, char **argv)
{       
        Point                                   *ptp = NULL;
        std::vector<Point*>                     pts;
        std::vector<Point*>::iterator           pit;
        kdTree<Point,Point*,PointAxisCompare>   kdtree;

        Point                                   query(276,335);
        Point                                   *nearest;
        double                                  radius(0.0);

        int                                     k=3;
        std::vector<Point*>                     knearest;

        double                                  x1=100, y1=-100;
        double                                  x2=400, y2=150;
        Point                                   min,max;
        std::vector<Point*>                     range;

  // read points in from file
  while(std::cin >> (ptp = new Point(0.0,0.0))) pts.push_back(ptp);

  // build kd-tree
  kdtree.insert(pts,Point(-640,-480),Point(640,480));

  // print kd-tree (in-order traversal)
  std::cout << "kd-tree (in-order): " << std::endl << kdtree;

  // nearest-neighbor
  kdtree.nn(query,nearest,radius);
  std::cout << "Point nearest to " << query << " is " << nearest << std::endl;

  // k nearest-neighbors
  kdtree.knn(query,knearest,radius,k);
  std::cout << k << " points nearest to " << query << " are " << std::endl;
  for(pit=knearest.begin(); pit!=knearest.end(); pit++)
    std::cout << *pit << std::endl;

  // range query points may be disorganized, i.e., user may have started out
  // at bottom-right, top-right, whatever; sort out into minx, maxx, miny, maxy
  // bounding box s.t. top-left is (minx,miny)
  min[0] = x1 < x2 ? x1 : x2;  max[0] = x1 > x2 ? x1 : x2;
  min[1] = y1 < y2 ? y1 : y2;  max[1] = y1 > y2 ? y1 : y2;
  kdtree.range(min,max,range);
  std::cout << " points in range " << min << "," << max << " are " << std::endl;
  for(pit=range.begin(); pit!=range.end(); pit++)
    std::cout << *pit << std::endl;

  // clean up (proper deletion)
  kdtree.clear();
  for(pit=pts.begin(); pit!=pts.end(); pit=pts.erase(pit))
    if(*pit) delete *pit;
}