// FILE: CityDb.cpp
// CLASS IMPLEMENTED: city_db (see CityDb.h for documentation)
// INVARIANT of the ADT:
// ????
//
// Documentation for functions client don't have to know:
// these are basically tree traversal functions that the city_db member
// functions wrap around, so the user doesn't have to muck around with the
// implementation details of the city_db object (they don't care that it's a
// binary search tree, and they shouldn't need to pass pointers to the
// functions, so the member functions take the input from the user and call
// these helper functions with an extra argument: the root_ptr of the
// city_db class' storage BST.)
//
// void bst_remove_max(binary_tree_node<city_record>*& root_ptr,
// city_record& removed)
// Precondition: root_ptr is a root pointer of a non-empty
// binary search tree.
// Postcondition: The city record with the largest city code
// in the binary search tree has been removed, and root_ptr
// now points to the root of the new (smaller) binary search
// tree. The reference parameter, removed, has been set to a
// copy of the removed city record.
//
// void bst_remove(binary_tree_node<city_record>*& root_ptr,
// const city_record& target)
// Precondition: root_ptr is a root pointer of a binary search
// tree (or may be 0 for the empty tree)
// Postcondition: If target was in the tree, then one copy of
// target has been removed, and root_ptr now points to the
// root of the new (smaller) binary search tree. Otherwise,
// if target was not in the tree, then the tree is unchanged.
//
//
// void printCodeOrderRecur(binary_tree_node<city_record>* rootPtr)
// Precondition: rootPtr is a root pointer of a binary search tree.
// Postcondition: the tree is output to the screen in code order
// (which is smallest-largest, as evidenced by the provided output,
// input01.out, from the instructor.)
//
// void printCodeOrderRecur(int x,int y, int distance,
// binary_tree_node<city_record>* rootPtr)
// this is an overloaded version of the above function.
// Precondition: rootPtr is a root pointer of a binary search tree.
// Postcondition: all items in the binary search tree under rootPtr
// that are within the given distance of the x and y parameters
// are output to the screen, in the same format as the above function.
//
// binary_tree_node<city_record>* searchRecur(int CityCode,
// binary_tree_node<city_record>* rootPtr)
// Precondition: rootPtr is a root pointer of a binary search tree.
// Postcondition: if CityCode is in the binary search tree specified by
// rootPtr, a pointer to that node is returned. otherwise, a null pointer
// is returned.
//
// binary_tree_node<city_record>* searchRecur(int x, int y,
// binary_tree_node<city_record>* rootPtr)
// Precondition: rootPtr is a root pointer of a binary search tree.
// Postcondition: if a city_record with the given x,y coordinates
// is in the binary search tree specified by rootPtr, a pointer to that
// node is returned. otherwise, a null pointer is returned.
//
// void insertRecur(city_record cr,
// binary_tree_node<city_record>* rootPtr)
// Precondition: rootPtr is a pointer to a binary search tree with
// at least one element.
// Postcondition: the tree specified by rootPtr now has one more node,
// and the storage rule of the BST is maintained.
//
// for other function documentation please refer to CityDB.h
// include relevant header files here
#include "CityDb.h"
#include "BinTree.h"
#include "CityRecord.h"
#include <iostream>
#include <cmath>
namespace cs3358Spring2007Assign08
{
// NONMEMBER FUNCTIONS
void bst_remove_max(binary_tree_node<city_record>*& root_ptr,
city_record& removed)
{
// we traverse the root_ptr, taking all rights until we find the
// largest value.
if (root_ptr == 0)
return;
binary_tree_node<city_record>* cursor = root_ptr;
while (cursor->right() != 0 && cursor->right()->right() != 0)
cursor = cursor->right();
// two cases: cursor -> right points to the node we need to remove,
// or cursor -> right points to null.
// If its right points to null, that means cursor is
// still root_ptr. In that case, we just set root_ptr to be the
// left subtree and remove the note that is cursor.
// in the other case, we leave root the same, but we
// delete cursor -> right and then set cursor -> right to the left
// subtree of cursor -> right.
if (cursor->right() == 0)
{
root_ptr = cursor->left();// will work for null lefts as well.
removed = cursor->data();
delete cursor;
}
else
{
// cursor -> right is what we want to remove, and we know it's the max
// value (so it may have left subtrees under it but it doesn't have
// right subtrees.)
binary_tree_node<city_record>* temp = cursor->right()->left();
removed = cursor->right()->data();
// we don't care if cursor -> right -> left is 0 or not.
delete cursor->right();
cursor->set_right(temp);
}
}
void bst_remove(binary_tree_node<city_record>*& root_ptr,
const city_record& target)
{
if (root_ptr == 0)
return;
if (root_ptr->data() == target)
{
// we need to change root pointer here!
binary_tree_node<city_record>* left = root_ptr->left();
city_record new_root = city_record();
bst_remove_max(left,new_root);// get rid of city code.
if (left != 0)// I.E. it found something
{
root_ptr->set_left(left);
root_ptr->set_data(new_root);
}
else
{
//there was no left subtree so root_ptr just gets to be...
// the right subtree.
//and we need to delete the current item, so we'll use left
// to temporarily store that address (since we don't need the
// value in left anymore)
left = root_ptr;
root_ptr = root_ptr->right();
delete left;
}
return;
}
else if (root_ptr->data() > target)
bst_remove(root_ptr->left(), target);
else
bst_remove(root_ptr->right(), target);
}
void printCodeOrderRecur(binary_tree_node<city_record>* rootPtr)
{
if (rootPtr == 0)
return;
printCodeOrderRecur(rootPtr->left());
city_record cr = rootPtr->data();
std::cout << cr.get_code() << " (" << cr.get_x() << ", "
<< cr.get_y() << ")" << std::endl;
printCodeOrderRecur(rootPtr->right());
}
void printCodeOrderRecur(int x,int y, int distance,
binary_tree_node<city_record>* rootPtr)
{
if (rootPtr == 0)
return;
city_record cr = rootPtr->data();
int x2 = cr.get_x(), y2 = cr.get_y();
float dist = sqrt(pow(float(x2 - x),2) + pow(float(y2 - y),2));
printCodeOrderRecur(x, y, distance, rootPtr->left());
if (dist <= distance)
std::cout << cr.get_code() << " (" << cr.get_x() << ", "
<< cr.get_y() << ")" << std::endl;
printCodeOrderRecur(x,y,distance, rootPtr->right());
}
binary_tree_node<city_record>* searchRecur(int CityCode,
binary_tree_node<city_record>* rootPtr)
{
if (rootPtr == 0) return 0;
if (rootPtr->data().get_code() == CityCode)
return rootPtr;
binary_tree_node<city_record>* temp = searchRecur(CityCode,
rootPtr->left());
if (temp != 0)
return temp;
temp = searchRecur(CityCode, rootPtr->right());
if (temp != 0)
return temp;
return 0;
}
binary_tree_node<city_record>* searchRecur(int x, int y,
binary_tree_node<city_record>* rootPtr)
{
if (rootPtr == 0) return 0;
if (rootPtr->data().get_x() == x && rootPtr->data().get_y() == y)
return rootPtr;
binary_tree_node<city_record>* temp = searchRecur(x,y,
rootPtr->left());
if (temp != 0)
return temp;
temp = searchRecur(x,y, rootPtr->right());
if (temp != 0)
return temp;
return 0;
}
void insertRecur(city_record cr,
binary_tree_node<city_record>* rootPtr)
{
assert(rootPtr != 0); //this should never happen.
if (cr.get_code() <= rootPtr->data().get_code())
{
if (rootPtr->left() == 0)
{
rootPtr->set_left(new binary_tree_node<city_record>(cr));
//rootPtr.left.data = cr;
}
else
insertRecur(cr,rootPtr->left());
}
else
{
if (rootPtr->right() == 0)
{
rootPtr->set_right(new binary_tree_node<city_record>(cr));
}
else
insertRecur(cr,rootPtr->right());
}
}
// Member Functions
bool city_db::remove(int CityCode)
{
binary_tree_node<city_record>* result = searchRecur(CityCode,root_ptr);
if (result != 0) // we found something to remove.
{
bst_remove(root_ptr,result->data());
return true;
}
return false;
}
bool city_db::remove(int x, int y)
{
binary_tree_node<city_record>* result = searchRecur(x, y, root_ptr);
if (result != 0) // we found something to remove.
{
bst_remove(root_ptr,result->data());
return true;
}
return false;
}
void city_db::insert(city_record cr)
{
if (root_ptr == 0) // no items, we can do this insert ourselves.
root_ptr = new binary_tree_node<city_record>(cr);
else
{
// don't let them insert a non-unique city code.
if (searchRecur(cr.get_code(), root_ptr))
return;
insertRecur(cr,root_ptr);
}
}
bool city_db::search(int CityCode, city_record& record)
{
binary_tree_node<city_record>* temp = searchRecur(CityCode,root_ptr);
if(temp != 0)
{
record = temp->data();
return true;
}
else
return false;
}
bool city_db::search(int x, int y, city_record& record)
{
binary_tree_node<city_record>* temp = searchRecur(x,y,root_ptr);
if(temp != 0)
{
record = temp->data();
return true;
}
else
return false;
}
bool city_db::empty()
{
return (root_ptr == 0);
}
void city_db::printTree()
{
print(root_ptr, 0);
}
void city_db::printCodeOrder()
{
printCodeOrderRecur(root_ptr);
}
void city_db::printCodeOrder(int x, int y, int dist)
{
printCodeOrderRecur(x,y,dist,root_ptr);
}
}