// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Test program for KDtree // This code could be greatly improved. Right now, the coordinate (key) // is part of the CityRec, which is the element field of the node. // I'm completely ignoring the Key field. The coodinate array should // become some sort of specialiation for the key field. // This data structure should also be integrated with the dictionary ADT, // (though it will be at least a little different because of the // regionsearch command). #include "book.h" class CityRec { private: string myname; int mypos[2]; public: // Constructor CityRec(int x, int y, string inname) { mypos[0] = x; mypos[1] = y; myname = inname; } ~CityRec() {delete &myname; } string name() { return myname; } int* coord() { return mypos; } }; // Overload << operator to print City records ostream& operator << (ostream& s, CityRec* p) { return s << p->name() << ", " << (p->coord())[0] << ", " << (p->coord())[1]; } #include "binnode.h" #include "KDtree.h" int main(int argc, char** argv) { CityRec *getCity = NULL; CityRec *getCity2 = NULL; int coord[2]; KD* tree = new KD(2); tree->insert(new CityRec(10, 20, "Acity")); tree->print(); coord[0] = 10; coord[1] = 20; tree->remove(coord, getCity2); cout << getCity2 << endl; tree->print(); // Insert records for the book example tree->insert(new CityRec(40, 45, "A")); tree->insert(new CityRec(70, 10, "C")); tree->insert(new CityRec(69, 50, "D")); tree->insert(new CityRec(15, 70, "B")); tree->insert(new CityRec(80, 90, "F")); tree->insert(new CityRec(55, 80, "E")); tree->print(); cout << endl << "Do a regionsearch: 80, 90, 0\n"; coord[0] = 80; coord[1] = 90; tree->regionsearch(coord, 0); cout << endl << "Do a regionsearch: 25, 65, 25\n"; coord[0] = 25; coord[1] = 65; tree->regionsearch(coord, 25); cout << endl << "Now for delete tests" << endl; tree->insert(new CityRec(56, 20, "G")); tree->insert(new CityRec(57, 25, "H")); tree->print(); coord[0] = 40; coord[1] = 45; tree->remove(coord, getCity); tree->print(); return 0; }