// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// Test program for KDtree: This is primarily a syntax checker

#include <iostream>
using namespace std;

#include "book.h"

#include "binnode.ht"

bool InCircle(int* c1, int* c2, int dim, int radius)
  { return true; }

class CityRec {
private:
  int pos[2];
public:
    int* coord() { return pos; }
};

void printout(CityRec& e) {};


template <class Elem> class KD {
private:
  BinNode<Elem>* root;
  int D; // Dimension of the key
  // True iff two coords are equal
    bool EqualCoord(int*, int*) const {}
  bool findhelp(BinNode<Elem>*, int*, Elem&, int) const;
  BinNode<Elem>* findmin(BinNode<Elem>*, int, int) const;
  void regionhelp(BinNode<Elem>*, int*, int, int) const;
public:
  KD(int Din) { root = NULL; D = Din; }  // Constructor
  bool remove(int* coord, Elem& e)
    { findmin(root, 0, 0); }
  bool find(Elem& e, int* coord) const
    { return findhelp(root, coord, e, 0); }
  void regionsearch(int* coord, int radius) const
    { regionhelp(root, coord, radius, 0); }
};
  
template <class Elem> bool KD<Elem>::
findhelp(BinNode<Elem>* root, int* coord,
         Elem& e, int discrim) const {
  // Member coord of a node is an integer array storing
  // the node's coordinates.
  if (root == NULL) return false;     // Empty tree
  int* currcoord;
  currcoord = (root->val()).coord();
  if (EqualCoord(currcoord, coord)) { // Found it
    e = root->val();
    return true;
  }
  if (currcoord[discrim] < coord[discrim])
    return findhelp(root->left(),coord,e,(discrim+1)%D);
  else
    return findhelp(root->right(),coord,e,(discrim+1)%D);
}

template <class Elem> void KD<Elem>::
regionhelp(BinNode<Elem>* root, int* coord,
           int rad, int discrim) const {
  // Check if record at root is in circle
  if (InCircle((root->val()).coord(), coord, D, rad))
    printout(root->val());  // Do what is appropriate
  int* currcoord = (root->val()).coord();
  if (currcoord[discrim] > (coord[discrim] - rad))
    regionhelp(root->left(), coord, rad, (discrim+1)%D);
  if (currcoord[discrim] < (coord[discrim] + rad))
    regionhelp(root->right(), coord, rad, (discrim+1)%D);
}

template <class Elem> BinNode<Elem>* KD<Elem>::
findmin(BinNode<Elem>* root,
          int discrim, int currdis) const {
  // discrim: discriminator key used for minimum search;
  // currdis: current level (mod D);
  BinNode<Elem> *temp1, *temp2;
  int *coord, *t1coord, *t2coord;
  if (root == NULL) return NULL;
  coord = (root->val()).coord();
  temp1 = findmin(root->left(), discrim, (currdis+1)%D);
  if (temp1 != NULL) t1coord = (temp1->val()).coord();
  if (discrim != currdis) { // If not at descrim's level,
                            // we must search both subtrees
    temp2 = findmin(root->right(),discrim,(currdis+1)%D);
    if (temp2 != NULL) t2coord = (temp2->val()).coord();
    if ((temp1 == NULL) || ((temp2 != NULL) &&
         (t2coord[discrim] < t1coord[discrim])))
      temp1 = temp2; // Right side has smaller key value
  } // Now, temp1 has the smallest value in children
  if ((temp1 == NULL) || (coord[discrim]<t1coord[discrim]))      
    return root;
  else return temp1;
}

int main(int argc, char** argv) {
  CityRec dum;
  int dumc[2] = {10, 20};
  KD<CityRec>* tree = new KD<CityRec>(2);
  tree->find(dum, dumc);
  tree->regionsearch(dumc, 10);
  tree->remove(dumc, dum);
  return(0);
}