I am getting an error saying, expected unqualified-id before "template" I can't figure out why I am getting this error. Any ideas?
Thanks daiel
code below:
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <sstream>
//#include "comparable.h"
using namespace std;
//
enum cmp_t
{
MIN_CMP = -1,
EQ_CMP = 0,
MAX_CMP = 1
}
template <class KeyType>
class Comparable
{
private:
KeyType myKey;
public:
Comparable(KeyType key) : myKey(key0{};
cmp_t Compare(KeyType Key) const
{
return(Key == myKey) ? EQ_CMP :((Key < myKey) ? MIN_CMP : MAX_CMP);
}
KeyType Key() const { return myKey; }
void Print() const
{
cout << myKey;
}
};
//
inline static int
MIN (int a, int b)
{
return (a < b) ? a:b;
}
inline static int
MAX (int a, int b)
{
return (a > b) ? a:b;
}
enum balance_t
{
LEFT_HEAVY = -1,
BALANCED = 0,
RIGHT_HEAVY = 1
}
enum height_effect_t
{
HEIGHT_UNCHANGED = 0,
HEIGHT_CHANGED = 0
}
inline static int
LEFT_INBALANCE(short bal)
{
return (bal < LEFT_HEAVY);
}
inline static int
RIGHT_INBALANCE(short bal)
{
return(bal > RIGHT_HEAVY);
}
template <class KeyType>
AVLNode<KeyType>::AVLNode(comparable <KeyType> *item):myData(item), myBal(0))
{
Reset();
}
template <class KeyType>
AVLNode<KeyType>~AVLNode(void)
{
if(myTree) delete mySubTree;
if(myTree)delete mySubTree;
}
template<class KeyType>
int AVLNode <KeyType>::RotateOnce(AVLNode <KeyType> * & root, dir_t dir)
{
dir_t otherdir = oposite(dir);
AVLNode<KeyType> * oldRoot = root;
int heightChange = (root -> mySubTree[otherdir]-> myBal == 0);
?HEIGHT_NOCHANGE;
:HEIGHT_CHANGE;
root = oldRoot -> mySubTree[otherdir];
oldRoot -> mySubTree[otherdir] = root -> mySubTree[dir];
root -> mySubTree[dir] = oldRoot;
oldRoot -> myBal = -((dir == LEFT))? --(root -> myBal): ++(root -> myBal));
return heightChange;
}
template<class KeyType>
int AVLNode <KeyType>::RotateTwice(AVLNode <KeyType> * & root, dir_t dir)
{
dir_t otherdir = opposite(dir);
AVLNode <KeyType> * oldRoot = root;
AVLNode <KeyType> * oldOtherDirSubTree = root -> mySubTree[otherdir];
root = oldRoot -> mySubTree(otherdir) -> mySubTree[dir];
oldRoot -> mySubTree[otherdir] = root -> mySubTee[dir];
root -> mySubtee[dir] = oldRoot;
oldOtherDirSubTree -> mySbutree[dir] = root -> mySubTee[otherdir];
root -> mySubTree[otherdir] = oldOtherDirSubTree;
root -> mySubTree -> myBal = -MAX(root -> myBal, 0);
root -> mySubTree -> myBal = -MIN(root -> myBal, 0);
root -> myBal = 0;
return HEIGHT_CHANGE;
}
template<class KeyType>
int AVLNode <KeyType>::ReBalance(AVLNode <KeyType> * & root)
{
int heightChange = HEIGHT_NOCHANGE;
if(LEFT_INBALANCE (root -> myBal))
{
if( root -> mySubTree -> myBal == RIGHT_HEAVY )
{
//RL
heightChange = RotateTwice (root, RIGHT);
}
else
{
heightChange = RotateOnce(root, RIGHT);
}
else if (RIGHT_INBALANCE(root -> myBal))
{
if(root -> mySubTree-> myBal == LEFT_HEAVY)
{
//left right rotation
heightCHange = RotateTwince(root, LEFT);
}
else
{
heightChange = RotateOnce(root, LEFT);
}
}
return heightChange;
}
template <class KeyType>
cmp_t AVLNode <KeyType>::Compare(KeyType Key, cmp_t cmp) const
{
switch(cmp)
{
case EQ_CMP:
return mydate -> compare(Key);
Case MIN_cmp:
return (mySubTree)==NULL ? EQ_CMP:MIN_CMP
case MAX_cmp:
return(mySubTree==NULL) ? EQ_CMP:MAX_cmp
}
}
templae <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
cmp_t result;
while(root && (results = root -> comare(Key, cmp))
{
root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];
}
}
//not sure if this function is correct
templae <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Delete(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
cmp_t result;
while(root && (results = root -> comare(Key, cmp))
{
root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];
}
}
templae <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Insert(comparable<KeyType> *item, AVLNode <KeyType> * & root)
{
int change;
return Insert(item, root, change)
}
templae <class KeyType>
comparabe <KeyType> AVLNode<KeyType>::Insert(comparable<KeyType> *item,
AVLNode<KeyType> *&root, int &change)
{
if(root == NULL)
{
root = new AVLNode<KeyType>(item),
Change = HEIGHT_CHANGE,
return NULL
}
Comparable<KeyType> * found = NULL
int increase = 0;
cmt_t result = root -> compare (item -> Key())
dir_t dir = (result == MIN_CMP) ? LEFT:RIGHT
if(reult != EQ_CMP)
{
found = Insert(item, root -> mySubTree[dir], change)
if(found) reurn found;
increase = result *change
}
else
{
increase = HEIHT_NOCHANGE
return root -> myData;
root -> myBal += increase;
change = (increase && root -> myBal)?(1-Rebaance(root)): HEIGHT_NOCHANGE;
return NULL;
}
}
enum dir_t
{
LEFT = 0;
RIGHT = 1;
}
//AVL NODE
template<class KeyType>
class AVLNode
{
public:
enum {MAX_SUBTREE = 2;}
static dir_t opposite(dir_t dir)
{
return dir_t( 1 - int( dir ) )
}
AVLNode(comparable <KeyType> * item = null)
virtual ~AVLNode(void);
comparable <KeyType> * Data() const {return myDate};
KeyType Key() const
{
return myData -> Key();
}
//balance vector
static Bal ( void ) const
{
return myBal;
}
AVLNode * SubTree(dir_t dir) const { return mySubTree[dir]; }
//searching
static comparable <KeyType> *search
(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp = EQ_CMP);
//insert
static comparable <KeyType>
*Insert(comparable <KeyType> *item, AVLNode <KeyType> *&root);
static comparable <KeyType> *
Delete (KeyType Key, AVLNode <KeyType> *&root, cmp_t cmp = EQ_CMP)
{
int Height() const;
int check() const;
}
Private:
comparable <KeyType> *myDate;
AVLNode <KeyType> *mySubTree[MAX_SUBTREE];
short myBal;
void Reset(void)
{
myBal = 0;
mySubTree = mySubTree = NULL
}
static comparable<KeyType> *
insert (comparable<KeyType> * item, AVLNode<KeyType> * & root, int & change);
static comparable<KeyType>
Delete(KeyType Key, AVLNode<KeyType> *&root, int &change, cmp_t cmp = EQ_CMP);
static int RotateOnce(AVLNode<KeyType> *&root, dir_t dir);
static int rotateTwice(AVLNode<KeyType> *&root, dir_t dir);
static int ReBalance(AVLNode<KeyType> *&root);
cmp_t compare(KeyType> Key, cmp_t, cmp = EQ_CMP) const;
Private:
AVLNode(const AVLNode<KeyType> &);
AVLNode & operator = (const AVLNode<KeyType> &);
}
template <class KeyType>
class AVLTree
{
private:
AVLTree(const AVLTree<KeyType> &)
AVLTree & operator = (const AVLTree<KeyType> &);
AVLNode<KeyType> * myRoot;
Public:
AVLNode():myRoot(NULL){}
~AVLNode()
{
if(myRoot)
delete myRoot;
}
comparable<kyeType> *search(KeyType Key, cmp_t cmp=EQ_CMP
{
return AVLNode<KeyType>::search(Key, myRoot, cmp);
}
comparable<KeyType>::*insert(comparable<KeyType> *item)
{
return AVLNode<KeyType>::insert(item, myRoot);
}
comparable<KeyType> *Delete(KeyType Key, cmp_t, cmp = EQ_CMP)
{
return AVLNode<KeyType>::Delete(Key, myRoot, cmp);
}
void DumpTree() const;
int isEmpty()
{
return myRoot == NULL;
}
}
template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
cmp_t result;
while (root && (result = root->Compare(Key, cmp))) {
root = root->mySubTree[(result < 0) ? LEFT : RIGHT];
}
return (root) ? root->myData : NULL;
}
template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Delete(KeyType Key, AVLNode<KeyType> * & root, cmp_t cmp)
{
int change;
return Delete(Key, root, change, cmp);
}
template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Delete(KeyType Key,
AVLNode<KeyType> * & root,
int & change,
cmp_t cmp)
{
// See if the tree is empty
if (root == NULL) {
// Key not found
change = HEIGHT_NOCHANGE;
return NULL;
}
// Initialize
Comparable<KeyType> * found = NULL;
int decrease = 0;
// Compare items and determine which direction to search
cmp_t result = root->Compare(Key, cmp);
dir_t dir = (result == MIN_CMP) ? LEFT : RIGHT;
if (result != EQ_CMP) {
// Delete from "dir" subtree
found = Delete(Key, root->mySubTree[dir], change, cmp);
if (! found) return found; // not found - can't delete
decrease = result * change; // set balance factor decrement
} else { // Found Key at this node
found = root->myData; // set return value
// ---------------------------------------------------------------------
// At this point we know "result" is zero and "root" points to
// the node that we need to delete. There are three cases:
//
// 1) The node is a leaf. Remove it and return.
//
// 2) The node is a branch (has only 1 child). Make "root"
// (the pointer to this node) point to the child.
//
// 3) The node has two children. We swap items with the successor
// of "root" (the smallest item in its right subtree) and delete
// the successor from the right subtree of "root". The
// identifier "decrease" should be reset if the subtree height
// decreased due to the deletion of the successor of "root".
// ---------------------------------------------------------------------
if ((root->mySubTree == NULL) &&
(root->mySubTree == NULL)) {
// We have a leaf -- remove it
delete root;
root = NULL;
change = HEIGHT_CHANGE; // height changed from 1 to 0
return found;
} else if ((root->mySubTree == NULL) ||
(root->mySubTree == NULL)) {
// We have one child -- only child becomes new root
AVLNode<KeyType> * toDelete = root;
root = root->mySubTree[(root->mySubTree) ? RIGHT : LEFT];
change = HEIGHT_CHANGE; // We just shortened the subtree
// Null-out the subtree pointers so we dont recursively delete
toDelete->mySubTree = toDelete->mySubTree = NULL;
delete toDelete;
return found;
} else {
// We have two children -- find successor and replace our current
// data item with that of the successor
root->myData = Delete(Key, root->mySubTree,
decrease, MIN_CMP);
}
}
root->myBal -= decrease; // update balance factor
// ------------------------------------------------------------------------
// Rebalance if necessary -- the height of current tree changes if one
// of two things happens: (1) a rotation was performed which changed
// the height of the subtree (2) the subtree height decreased and now
// matches the height of its other subtree (so the current tree now
// has a zero balance when it previously did not).
// ------------------------------------------------------------------------
//change = (decrease) ? ((root->myBal) ? balance(root) : HEIGHT_CHANGE)
// : HEIGHT_NOCHANGE ;
if (decrease) {
if (root -> myBal) {
change = ReBalance(root); // rebalance and see if height changed
} else {
change = HEIGHT_CHANGE; // balanced because subtree decreased
}
} else {
change = HEIGHT_NOCHANGE;
}
return found;
}
static inline void
Indent( int len) {
for (int i = 0; i < len; i++) {
cout << ' ';
}
}
enum TraversalOrder { LTREE, Key, RTREE };
template <class KeyType>
static void
Dump(
TraversalOrder order,
const AVLNode<KeyType> * node,
int level=0)
{
unsigned len = (level * 5) + 1;
if ((order == LTREE) && (node->Subtree(LEFT) == NULL)) {
Indent( len);
cout << " **NULL**" << endl;
}
if (order == Key) {
Indent( len);
cout << node->Key() << ":" << node->Bal() << endl;
}
if ((order == RTREE) && (node->Subtree(RIGHT) == NULL)) {
Indent( len);
cout << " **NULL**" << endl;
}
}
template <class KeyType>
static void
Dump(const AVLNode<KeyType> * node, int level=0)
{
if (node == NULL) {
cout << "***EMPTY TREE***" << endl;
} else {
Dump( RTREE, node, level);
if (node->Subtree(RIGHT) != NULL) {
Dump( node->Subtree(RIGHT), level+1);
}
Dump( Key, node, level);
if (node->Subtree(LEFT) != NULL) {
Dump( node->Subtree(LEFT), level+1);
}
Dump(LTREE, node, level);
}// if non-empty tree
}
template <class KeyType>
void
AvlTree<KeyType>::DumpTree() const {
Dump(myRoot);
}
// Sample main code
main()
{
char stop;
AvlTree<long> tree;
Comparable<long> * found = NULL;
long inputValue;
Comparable<long> *myarray[25];
int numVoters;
ifstream inputFile;
inputFile.open("testvals.txt");
if (!inputFile)
cout<<"Error on opening file"<<endl;
numVoters = 0;
while (!inputFile.eof()&& numVoters < 25)
{
inputFile>>inputValue;
myarray[numVoters] = new Comparable<long>(inputValue);
numVoters++;
}
cout<<" Initial Input"<<endl;
for (int i = 0; i<numVoters; i++)
{
cout<<myarray[i]->Key()<<endl;
}
int i;
for (i = 0 ; i < numVoters ; i++) {
cout << "+++ inserting Key #" << i+1 << ": " << myarray[i]->Key() << endl;
found = tree.Insert(myarray[i]);
if (found) {
cout << "\t(already in tree)\n";
}
}
tree.DumpTree();
cin >> stop;
system("PAUSE");
return EXIT_SUCCESS;
}
