Cannot Instantiate Abstract Class - How do i fix this to work properly?

Question

I'm attempting to make a Binary Search Tree database, where i can search through the dictionary entries. I'm trying to figure out how to fix this in my code, i was given a pre-requisite base class that is also a template abstract class, and it is used to derive the BST or BinarySearchTree class, however i'm having problems compiling in Visual Studio 2012, it keeps saying my functions
(for ex. int SearchableADT::loadFromFile(std::string) is abstract;)

Also, does this constructor look to be correct? I just want the constructor to set the head at NULL, but i don't know if i need to use the SearchableADT somewhere in the constructor.

Thank you for all the help!! I need it!

#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;

template <typename T>
class SearchableADT
{
public:
    virtual int loadFromFile(string filename)= 0;
    //virtual void clear(void) = 0;
    virtual void insertEntry(T value) = 0;
    virtual void deleteEntry(T value) = 0;
    virtual bool isThere(T value) = 0;
    virtual int numEntries(void) = 0;
};

template <typename T>
class BST : public SearchableADT<T>
{
public:
    BST():SearchableADT<T> {head = NULL;} //default constructor
    virtual int loadFromFile(string filename);
    //virtual void clear(void);
    virtual void insertEntry(T value);
    virtual void deleteEntry(T value);
    virtual bool isThere(T value);
    virtual int numEntries(void);
 private:
    struct t_node
    {
        string data;
        t_node* L; //left node
        t_node* R; //right node
    };
    t_node* head; // head of the whole BST
    t_node* cPTR; // current pointer
    t_node* pPTR; // parent pointer
    t_node* tPTR; //temporary pointer

};
template <typename T>
bool BST<T>::isThere(T value)
{
    bool found = false;

if(head == NULL)
{
    cout<<"Error: No data found in ADT\n";
    return found;
}

cPTR = head;
//loops through the tree until the entry is found
while(cPTR != NULL)
{
    if(cPTR->data == info)
    {
        found = true;
        break;
    }

    else
    {
        pPTR = cPTR;
        if(info > cPTR->data)
            cPTR = cPTR->R;
        else
            cPTR = cPTR->L;
    }
}
if(!found)
{
    cout<<"'"<<info<<"' was not found in the dictionary\n";
}
return found;
}//end of isThere() function

template <typename T2>
void BST<T2>::insertEntry(T2 info)
{
    t_node* t = new t_node;
    t->data = info;
    t->L    = NULL;
    t->R    = NULL;
    pPTR    = NULL;
    if(head->data == NULL)
        head = t;
    else
    {
        t_node* cPTR; //current pointer
        cPTR = head;

        //checks to see if the data just entered is
        //greater than the head 
        while(cPTR)
        {
            pPTR = cPTR;
            if( t->data > cPTR->data)
                cPTR = cPTR->R;
            else
                cPTR = cPTR->L;
        }

        //checks to see if the data just entered is
        // less than the parent data that was 
        // set equal to cPTR;
        if(t->data < pPTR->data)
        {
            pPTR->L = t;

        }
    else
    {
        pPTR->R = t;
    }
}
}//end of insertEntry() function

template <typename T2>

void BST<T2>::deleteEntry(T2 info)
{
    //i use this as an example of abstraction
    //after using this function the cPTR and pPTR are already pointing to the data needed to be found
    if(!isThere(info))
    {
        cout<<"The data: '"<<info<<"' could not be found in the ADT, sorry!\n";
        return;
    }

    //one has to account for all possibilities when deleting data
    //1.) - Removing just a leaf node (no children) **easy  
//2.) - Removing a leaf node with 1 child **medium
//3.) - Removing a leaf node with 2 children **hard

//case 1
if( cPTR->L == NULL && cPTR ->right == NULL)
{
    if(pPTR-> L == cPTR)
        pPTR->L = NULL;
    else
        pPTR->R = NULL;
    delete cPTR;
    return;
}//end of case 1

//case 2
else if((cPTR->L == NULL && cPTR->R != NULL) ||
   (cPTR->L != NULL && cPTR->R == NULL))
{
    //if the left data of cptr has data and the right data is NULL
    if(cPTR->L != NULL && cPTR->R == NULL)
    {
        if(pPTR->L == cPTR)
        {
            pPTR->L = cPTR->right;
            delete cPTR;
        }
        else
        {
            pPTR->R = cPTR->L;
            delete cPTR;
        }
    }

    else //right child present, and left child is NULL 
    {
        if(pPTR->L == cPTR)
        {
            pPTR->L = cPTR->right;
            delete cPTR;
        }
        else
        {
            pPTR->R = cPTR->R;
            delete cPTR;
        }
    }

    //case 3
    else if((cPTR->L != NULL && cPTR->R != NULL))
    {
        tPTR=cPTR->R;

        //if the right node doesn't have a right leaf or left leaf, delete that node
        if((tPTR->L == NULL && tPTR->R == NULL))
        {
            cPTR = tPTR;
            delete cPTR;
            cPTR->R = NULL;
        }
        else
        {
            if(tPTR->L != NULL)
            {
                t_node* secPTR;
                secPTR = tPTR->L;
                //cycle through left nodes until you find the lowest left node
                while(secPTR->L != NULL)
                {
                    secPTR = secPTR->L;
                }
                //because you're only setting the data equal to eachother the cPTR keeps its left and right nodes
                //therefore it correctly replaces the data without unwanted loss of other information
                cPTR->data = secPTR->data;
                delete secPTR;
                cPTR->L    = NULL;
            }
            else
            {
                cPTR->data = tPTR->data;
                cPTR->R    = tPTR->R;
                delete tPTR;
            }

        }
    }
}
}  //end of deleteEntry() function

template <typename T2>
int BST<T2>::numEntries()
{
    int num = 0;

    if(head->R == NULL && head-> L == NULL)
    {
        num++;
    }
    else
    {
        //note i learned that you could count the nodes like this via the web
        //i could redo this with recursion if you'd like
        num = count(head->L) + count (head->R) + 1;
    }
    return num;
}
template <typename T2>
int BST<T2>::loadFromFile(string filename)
{
    int count = 0;
    string tempdata;
    ifstream fin(filename);
    if(!fin)
    {
        cout<< "Error: Could no open file\n";
        count--;
    }
    while(fin)
    {
        fin>>tempdata;
        if(fin)
        {
            insertEntry(tempdata);
            count++;
        }
    }
    fin.close();
    return count;       
 }//end of loadFromFile() function


int main()
{
    char choice 'z';
    string tempdata,
           fileloc;

cout<<"Welcome to Jordin Ray's Spell Check Application\n"
    <<"Please pick a tree type\n"
    <<"'b' -Binary Search Tree\n"
    <<"'a' -AVL tree\n"
    <<"'h' -hash table\n";
cin>>choice;
cout<<"Please give the exact location of the file for download\n";
cin>>fileloc;
if(choice == 'b')
{
    SearchableADT<string> dictionary = new BST<string>;
    dictionary.loadFromFile(fileloc);
    char ch = 'z';
    while(ch != 'q')
    {
        string word = "";
        if(ch == 'e')
        {
            cout<<"Please enter the word you would like to search for\n";
            cin>>word;
            dictionary.isThere(word);
        }
        else if (ch == 'p')
        {
            cout<<"Please enter the partial word you would like to look for with a '?' where the missing letter is: \n"
                <<"Ex. - '?nd' will search for words in the dictionary that have those last two letters\n";
            //dictionary.partialIsThere(word);
        }
        else if (ch == 'c')
        {
            dictionary.clear();
        }
        else if (ch == 's')
        {
            int entries;
            entries = dictionary.numEntries();
            cout<<"\nThe amount of entries logged in the database is: "<<entries<<".\n";
        }
        cout<<"Would you like to:\n"
            <<"Clear the dictionary      - 'c'\n"
            <<"Check for an entry        - 'e'\n"
            <<"Check for a partial entry - 'p'\n"
            <<"Report Statistics         - 's'\n"
            <<"Quit                      - 'q'";
        cin>>ch;
    }//end of while loop
}
return 0;
}//end of main

Answer 1

I tried to compile your code with Clang++ on a Mac and your problems start much earlier than the template/inheritance mixing. Namely at line 23:

error: expected '('
    BST():SearchableADT<T> {head = NULL;} //default constructor

(solution: the base constructor needs argument list, add () )

and, after having fixed that comes the next at line 59:

error: use of undeclared identifier 'info'
    if(cPTR->data == info)

and I gave up at this stage. There are some other minor issues, e.g. there is no need in C++ to #include <cstring>: for all functions that expect C-style strings you can always use the c_str() method of std::string. Also const correctness should be observed: e.g. loadFromFile(string filename) should rather look like loadFromFile(const string& filename). Etc.

Now to the major problem. I don't see why you need that templated base class at all. The whole design would be much easier if you could avoid templates and just write a class storing strings.

BTW it is perfectly possible to have an abstract template base class from which concrete template classes are derived. Just make sure you provide concrete implementation for all pure virtual methods. Here is a made-up example that may help you getting started:

#include <string>
#include <iostream>

template<typename T>
class AbstractBase {
    public:

    virtual const T& func() const = 0;

};

template<typename T>
class Derived: public AbstractBase<T> {
    public:

    // stores x
    Derived(const T& x): AbstractBase<T>(), _x(x) {}

    // returns x
    const T& func() const { return _x; }

    private:
    T _x;
};

int main(int argc, char *argv[]) {
    Derived<std::string> d("foo");
    std::cout << d.func() << std::endl;
    return 0;
}

However, the template/inheritance mixing design problem will rear its ugly head later in cases where some of the to-be-implemented methods do not make sense for certain template parameters. The example above was "cheap" since func() just returns a value. What if I add a function twice() that returns 2 * _x ? Fine if _x is a number, but what about strings? Or vectors? You get the point... :-)