#include<iostream>
#include<fstream>
#include<string>
#include "math.h"
using namespace std;
class City {
//friend ifstream& operator>>(ifstream& file, City& acity){file>>acity.x_coordinate; file>>acity.y_coordinate;return file;}
friend ifstream& operator>>(basic_istream<char>& file, City& acity)
{
return (ifstream&)(file >> acity.x_coordinate >> acity.y_coordinate);
}
friend ostream& operator<<(ostream& os, City& acity)
{
return (ostream&)(os << " x = " << acity.x_coordinate << " y = " << acity.y_coordinate);
}
//friend ostream& operator<<(ostream& os, City& acity){
//os << " x = ";os << acity.x_coordinate;os<< " y = ";os << acity.y_coordinate;return os;}
private:
int x_coordinate;
int y_coordinate;
public:
City()
{
x_coordinate = 0;
y_coordinate = 0;
}
City(string name, int x, int y): x_coordinate(x), y_coordinate(y) {}
City(const City& acity)
{ x_coordinate = acity.x_coordinate;
y_coordinate = acity.y_coordinate;
}
virtual ~City() {};
bool operator==(const City& right)
{
return x_coordinate == right.y_coordinate;
}
bool operator!=(const City& right)
{
return !(x_coordinate == right.y_coordinate);
}
bool distanceWithin(int distance)
{
return sqrt(x_coordinate * x_coordinate + y_coordinate * y_coordinate) < distance; }
int distanceQuared()
{
return x_coordinate * x_coordinate + y_coordinate * y_coordinate;
}
};
const City NULL_("NULL", -1, -1);
template <typename Key, typename E> class Dictionary {
private:
void operator =(const Dictionary&) {}
Dictionary(const Dictionary&) {}
public:
Dictionary() {}
// Default constructor virtual ~Dictionary() {}
// Base destructor
// Reinitialize dictionary
virtual void clear() = 0;
// Insert a record
// k: The key for the record being inserted.
// e: The record being inserted.
virtual void insert(const Key& k, const E& e) = 0;
// Remove and return a record.
// k: The key of the record to be removed.
// Return: A maching record. If multiple records match
// "k", remove an arbitrary one. Return NULL if no record
// with key "k" exists. virtual E remove(const Key& k) = 0;
// Remove and return an arbitrary record from dictionary.
// Return: The record removed, or NULL if none exists.
virtual E removeAny() = 0;
// Return: A record matching "k" (NULL if none exists).
// If multiple records match, return an arbitrary one.
// k: The key of the record to find
virtual E find(const Key& k) const = 0; // Return the number of records in the dictionary.
virtual int size() = 0; };
template <typename E> class BinNode {
public:
virtual ~BinNode() {} // Base destructor // Return the node's value
virtual E& element() = 0; // Set the node's value
virtual void setElement(const E&) = 0; // Return the node's left child
virtual BinNode* left() const = 0; // Set the node's left child
virtual void setLeft(BinNode*) = 0; // Return the node's right child
virtual BinNode* right() const = 0; // Set the node's right child
virtual void setRight(BinNode*) = 0; // Return true if the node is a leaf, false otherwise
virtual bool isLeaf() = 0; }; // Simple binary tree node implementation
template <typename Key, typename E> class BSTNode : public BinNode<E> {
friend ifstream& operator>>(ifstream& file, BSTNode& node)
{
file >> node.k;
file >> node.it;
return file;
}
friend ostream& operator<<(ostream& os, BSTNode& node)
{
return os << node.k << node.it;
}
private:
Key k;
// The node's key
E it;
// The node's value
BSTNode* lc;
// Pointer to left child
BSTNode* rc;
// Pointer to right child
public:
// Two constructors -- with and without initial values
BSTNode() { lc = rc = NULL; }
BSTNode(Key K, E e, BSTNode* l = NULL, BSTNode* r = NULL)
{
k = K;
it = e;
lc = l;
rc = r;
}
~BSTNode() {}
// Destructor
// Functions to set and return the value and key
E& element()
{
return it;
}
void setElement(const E& e)
{
it = e;
}
Key& key()
{
return k;
}
void setKey(const Key& K)
{
k = K;
}
// Functions to set and return the children
inline BSTNode* left() const {
return lc; }
void setLeft(BinNode<E>* b)
{
lc = (BSTNode*)b;
}
inline BSTNode* right() const
{
return rc;
}
void setRight(BinNode<E>* b)
{
rc = (BSTNode*)b;
} // Return true if it is a leaf, false otherwise
bool isLeaf()
{
return (lc == NULL) && (rc == NULL);
}
bool operator==(const BSTNode& right)
{
return *this == right;
}
bool operator!=(const BSTNode& right)
{
return (*this != right);
}
};
template <typename Key, typename E> class BST :public Dictionary<Key, E> {
private: BSTNode<Key, E>* root;
// Root of the BST
int nodecount;
// Number of nodes in the BST
// Private "helper" functions
void clearhelp(BSTNode<Key, E>*);
BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*,
const Key&, const E&);
BSTNode<Key, E>* deletemin(BSTNode<Key, E>*);
BSTNode<Key, E>* getmin(BSTNode<Key, E>*);
BSTNode<Key, E>* removehelp(BSTNode<Key, E>*, const Key&);
E findhelp(BSTNode<Key, E>*, const Key&) const;
void printhelp(BSTNode<Key, E
