I have a data structure that uses a template class such that it can store any data type - ints, floats, strings, etc.
Because the data will be organized, I need a way to compare two values. Usually I can use > or <, but in the case of strings that will not work because using the >/< operators on a string won't tell me which comes first alphabetically. For that, I need to use the compare() function.
However since the data structure is a template class, I can't tell it to use the compare() function because it won't recognize the compare() function for anything BUT a string.
As a work-around, I tried writing two compare functions:
template (class t)
int BinaryTree<T>::compareVals(T v1, T v2);
and
template (class t)
int BinaryTree<T>::compareVals(string v1, string v2);
So that in the case of the value being a string type, the program would use the method with the compare() function in it.
However trying to do that, I am getting a compiler error basically telling me I can't overload the function.
So I'm out of ideas. How can I make this template class correctly compare and sort strings as well as numbers?
Thank you very much for your input!
Here is the entire class, for reference:
#ifndef binarytree_class
#define binarytree_class
#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::string;
using std::vector;
template <class T>
class BinaryTree{
public:
struct TreeNode{
TreeNode * leftChild,
* rightChild;
T key;
vector<T> data;
int size;
};
BinaryTree();
~BinaryTree();
bool isEmpty();
int getSize();
void add(T key, T data);
void remove(T key);
int getHeight();
bool keyExists(T key);
int getKeyHeight(T key);
void displayAll();
private:
int size;
TreeNode * root;
TreeNode * findParent(TreeNode * start, TreeNode * child); //finds the parent node of child in subtree starting at root start
TreeNode * findNode(TreeNode * node, T input); //find node with data input in subtree at root node
TreeNode * findMin(TreeNode * node);
void removeNode(TreeNode * node); //Small part of algorithm (case: 2 children) borrowed from tech-faq.com/binary-tree-deleting-a-node.html
void displaySubTree(TreeNode * node); //displays subtree starting at node
void sortAdd(TreeNode * eNode, TreeNode * nNode); //adds a new node nNode to subtree starting at root eNode
void destroySubTree(TreeNode * node); //destroys subtree starting at node.
void display(TreeNode * node, string indent, bool last); //Algorithm borrowed from http://stackoverflow.com/questions/1649027/how-do-i-print-out-a-tree-structure
char leftOrRight(TreeNode * eNode, TreeNode * nNode); //compares keys in existing node vs new node and returns L or R
int calcHeight(TreeNode * node, int depth); //calculates the height from node. Algorithm borrowed from wiki.answers.com
int compareVals(T v1, T v2);
int compareVals(string v1, string v2);
};
template <class T>
BinaryTree<T>::BinaryTree<T>() : size(0){}
template <class T>
bool BinaryTree<T>::isEmpty(){
return (!size);
}
template <class T>
int BinaryTree<T>::compareVals(T v1, T v2){
int result;
v1 <= v2? result = -1 : result = 1;
return result;
}
template <class T>
int BinaryTree<T>::compareVals(string v1, string v2){
int result;
result = v1.compare(v2);
if(result >= 0)
result = -1;
else
result = 1;
return result;
}
template <class T>
int BinaryTree<T>::getSize(){
return size;
}
template <class T>
void BinaryTree<T>::add(T key, T data){
bool done = false;
TreeNode * temp;
if(keyExists(key)){
temp = findNode(root,key);
temp->size++;
temp->data.push_back(key);
}
else{
temp = new TreeNode;
temp->leftChild = 0;
temp->rightChild = 0;
temp->key = key;
temp->size = 0;
temp->data.push_back(data);
if(isEmpty())
root = temp;
else
sortAdd(root, temp);
size++;
}
}
template <class T>
void BinaryTree<T>::sortAdd(TreeNode * eNode, TreeNode * nNode){
if(leftOrRight(eNode, nNode) == 'L'){
if(eNode->leftChild == 0)
eNode->leftChild = nNode;
else
sortAdd(eNode->leftChild,nNode);
} else {
if(eNode->rightChild == 0)
eNode->rightChild = nNode;
else
sortAdd(eNode->rightChild,nNode);
}
}
template <class T>
char BinaryTree<T>::leftOrRight(TreeNode * eNode, TreeNode * nNode){
char result;
if(compareVals(nNode->key, eNode->key) == -1)
result = 'L';
else
result = 'R';
return result;
}
template <class T>
void BinaryTree<T>::displayAll(){
display(root,"",true);
}
template <class T>
void BinaryTree<T>::display(TreeNode * node, string indent, bool last){
if(!isEmpty()){
cout << indent;
if(last){
cout << "\\-";
indent += " ";
} else {
cout << "|-";
indent += "| ";
}
cout << node->key << "\n";
if(node->leftChild != 0)
display(node->leftChild, indent, false);
if(node->rightChild != 0)
display(node->rightChild, indent, true);
} else
cout << "TREE IS EMPTY" << "\n\n";
}
template <class T>
int BinaryTree<T>::getHeight(){
if(!root)
cout << "ERROR: getHeight() root is NULL!" << "\n";
int result;
if(isEmpty())
result = 0;
else
result = calcHeight(root, 1);
return result;
}
template <class T>
int BinaryTree<T>::getKeyHeight(T key){
int result = -1;
if(!keyExists(key))
cout << "ERROR: Trying to get height of nonexistant key " << key << "\n";
else{
TreeNode * temp = findNode(root, key);
result = getHeight() - calcHeight(temp,1);
}
return result;
}
template <class T>
int BinaryTree<T>::calcHeight(TreeNode * node, int depth){ //Algorithm borrowed from wiki.answers.com
int leftDepth,
rightDepth,
result;
if(node->leftChild)
leftDepth = calcHeight(node->leftChild, depth+1);
else
leftDepth = depth;
if(node->rightChild)
rightDepth = calcHeight(node->rightChild, depth+1);
else
rightDepth = depth;
if(leftDepth > rightDepth)
result = leftDepth;
else
result = rightDepth;
return result;
}
template <class T>
void BinaryTree<T>::remove(T input){
if(!keyExists(input))
cout << "ERR: trying to remove nonexistant key " << input << "\n";
else{
TreeNode * temp = findNode(root,input);
removeNode(temp);
}
}
template <class T>
bool BinaryTree<T>::keyExists(T key){
bool result;
if(isEmpty())
result = false;
else{
if(findNode(root,key) != 0)
result = true;
else
result = false;
}
return result;
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findNode(TreeNode * node, T input){
TreeNode * result = 0; //Returns 0 if none found
if(node->key == input)
result = node;
else{
if(node->leftChild != 0)
result = findNode(node->leftChild, input);
if(result == 0 && node->rightChild != 0)
result = findNode(node->rightChild, input);
}
return result;
}
template <class T>
void BinaryTree<T>::removeNode(TreeNode * node){
TreeNode * parent = 0;
if(node != root)
parent = findParent(root,node);
if(node->leftChild && node->rightChild){ //Case: both children (algorithm borrowed from tech-faq.com)
TreeNode * temp = findMin(node->rightChild);
string tkey = temp->key;
removeNode(temp);
node->key = tkey;
} else {
if(parent){
if(!(node->leftChild) && !(node->rightChild)){ //case: no children & not root
if(parent->leftChild == node)
parent->leftChild = 0;
else
parent->rightChild = 0;
}
if(!(node->leftChild) && node->rightChild){ //case: right child only & not root
if(parent->leftChild == node)
parent->leftChild = node->rightChild;
else
parent->rightChild = node->rightChild;
}
if(node->leftChild && !(node->rightChild)){ //case: left child only & not root
if(parent->leftChild == node)
parent->leftChild = node->leftChild;
else
parent->rightChild = node->leftChild;
}
delete node;
size--;
}
else{
if(node->leftChild) //case: left child only & root
root = node->leftChild;
else //case: right child only & root
root = node->rightChild;
delete node; //case: no children & root intrinsically covered
size--;
}
}
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findMin(TreeNode * node){
TreeNode * result;
if(node->leftChild == 0)
result = node;
else
result = findMin(node->leftChild);
return result;
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findParent(TreeNode * start, TreeNode * child){
TreeNode * result = 0;
if(start->leftChild){
if(start->leftChild->key == child->key)
result = start;
else
result = findParent(start->leftChild, child);
}
if(start->rightChild && result == 0){
if(start->rightChild->key == child->key)
result = start;
else
result = findParent(start->rightChild, child);
}
return result;
}
template <class T>
void BinaryTree<T>::destroySubTree(TreeNode * node){
TreeNode * parent = 0;
if(node != root)
parent = findParent(root,node);
if(node->leftChild)
destroySubTree(node->leftChild);
if(node->rightChild)
destroySubTree(node->rightChild);
if(parent){
if(parent->leftChild == node)
parent->leftChild = 0;
else
parent->rightChild = 0;
}
size--;
delete node;
}
template <class T>
BinaryTree<T>::~BinaryTree<T>(){
if(!isEmpty())
destroySubTree(root);
}
#endif
