C++ : Is it possible to mix templates with Inheritance??

[Concrete Geist]

This is a problem that has been plaguing me all weekend. I am trying to create a Linked List class (as practice), but I've encountered many problems. I have four objects, a Headnode that starts the list, Middlenodes, that hold the data, and Tailnodes that end the list. all of these inherit from a Node class. Using polymor
phism, abstraction and inheritance; this is theoretically very cool. But it's just not working like i'd hoped.

Below is my nightmarish code that produces several dozen errors. Some of the errors are too weird for me to understand. For example, it thinks that my constructors are declared as void. :eek:

The code itself is supposed to go inside a header file, the errors occured when I made a simple driver program that instantiated the Headnode with a float as the type.



#ifndef _HAVE_LINKED_LIST_H_
#define _HAVE_LINKED_LIST_H_

// Type for deciding termination method of data nodes
typedef enum {
REMOVE_SINGLE,
REMOVE_ALL
} ll_term_t;

// IDFLAG type
typedef unsigned short IDFLAG_t;

template<typename _data>class Node;
template<typename _data>class Headnode;
template<typename _data>class Internalnode;
template<typename _data>class Tailnode;

template<class _data>
class Node
{
public:
Node(){}
virtual ~Node(){}

virtual Node *append_node(_data *thedata)=0;
virtual Node *add_node(_data *thedata, IDFLAG_t id)=0;
virtual IDFLAG_t get_object_id()const =0;
virtual void _increment_onward(IDFLAG_t)=0;
bool remove_node( IDFLAG_t ID_FLAG );
Node *get_next()const { return next; }

protected:
Node *next;
};

template<typename _data>
bool Node<_data>::remove_node(IDFLAG_t ID_FLAG)
{
Node *temp = next->get_next();
if(!(temp)) // if we found the tailnode
return false;
if(next->get_object_id() == ID_FLAG) { // we found what we're looking for!
delete next;
next = temp; // patch the hole
return true; // report success
} else { // Not yet found, but there is still room to search. Keep on lookin'
temp = NULL;
return next->remove_node(ID_FLAG); // continue recursively
}
}

template<class _data>
class Headnode : public Node
{
public:
Headnode();
~Headnode();

Node *append_node(_data *thedata);
Node *add_node(_data *thedata, IDFLAG_t id);
static unsigned short size() { return (internal_count + 1); }

private:
const Tailnode *const tail_ptr<_data>;
static unsigned short internal_count;
static ll_term_t TERM_TYPE;
};

template<class _data>
unsigned short Headnode<_data>::internal_count(0);
template<class _data>
ll_term_t Headnode<_data>::TERM_TYPE(TERM_SINGLE);

template<class _data>
Headnode<_data>::Headnode()
{
next = new Tailnode<_data>;
tail_ptr = next;
}

template<class _data>
Headnode<_data>::~Headnode()
{
// If I'm being destroyed, then all others are to be destroyed as well.
TERM_TYPE = TERM_ALL;
delete next;
}

template<class _data>
Node *Headnode<_data>::append_node(_data *thedata)
{
next = next->append_node(thedata);
return this; // appease the compiler
}

template<class _data>
Node *Headnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
if(next->get_object_id() == id) { // wants to put it on the front end.
Node *temp = (!(next->get_next())) ? tail_ptr : next->get_next(); // get_next() is inline
next = new internalnode(thedata, temp);
next->_increment_onward(id + 1);
} else {
next = next->add_node(thedata, id);
}

return this; // appease the compiler
}

template<class _data>
class Internalnode : public Node
{
public:
Internalnode(_data *thedata, Node *link_to);
~Internalnode();

Node *add_node(_data *thedata, IDFLAG_t id);
Node *append_node(_data *thedata);
IDFLAG_t get_object_id()const { return id; }
void _increment_onward(IDFLAG_t first); /* this function fixes the id vars in all the internalnodes
after an insertion has be done. */
private:
IDFLAG_t id;
_data *DATA;
};

template<class _data>
Internalnode<_data>::Internalnode(_data *thedata, Node *link_to)
{
id = internal_count++;
DATA = thedata;
next = link_to;
}

template<class _data>
Internalnode<_data>::~Internalnode()
{
// self-destruction chain reaction
if( TERM_TYPE == TERM_ALL )
delete next;
}

template<class _data>
Node *Internalnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
// then somewhere in the middle is where it wants to be put.
if(next->get_object_id() == id) { // wants to put it on the front end.
Node *temp = (!(next->get_next())) ? tail_ptr : next->get_next(); // get_next() is inline
next = new internalnode(thedata, temp);
if(next->get_next())
next->_increment_onward(id + 1);
} else {
next = next->add_node(thedata, id);
}

return this;
}

template<class _data>
Node *Internalnode<_data>::append_node(_data *thedata)
{
next = next->append_node(thedata);
return this;
}

template<class _data>
void Internalnode<_data>::_increment_onward(IDFLAG_t first)
{
id = first;
if(!(next->get_next())) { // end condition
internal_count++;
return;
}

next->_increment_onward(id + 1); // continue recursively
}

template<class _data>
class Tailnode : public Node
{
public:
Tailnode():next(NULL){}
~Tailnode(){}

Node *append_node(_data *thedata);
Node *add_node(_data *thedata, IDFLAG_t id);
bool remove_node(IDFLAG_t id) { return false; }
};

template<class _data>
Node *Tailnode<_data>::append_node(_data *thedata)
{
return new Internalnode<_data>(thedata, this)
}

template<class _data>
Node *Tailnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
return append_node(thedata);
}

#endif /* _HAVE_LINKED_LIST_H_ */



I'll put the errors in another post, this text box is getting glitchy.

[Concrete Geist]

Linked_List.h:54: parse error before `{'
Linked_List.h:57: destructors must be member functions
Linked_List.h:57: `void Headnode ()' redeclared as different kind of
symbol
Linked_List.h:14: previous declaration of `template <class _data> class
Headnode'
Linked_List.h:14: previous non-function declaration `template <class
_data> class Headnode'
Linked_List.h:57: conflicts with function declaration `void Headnode
()'
Linked_List.h:59: syntax error before `*'
Linked_List.h:60: syntax error before `*'
Linked_List.h: In function `short unsigned int size ()':
Linked_List.h:61: `internal_count' undeclared (first use this function)
Linked_List.h:61: (Each undeclared identifier is reported only once for
each function it appears in.)
Linked_List.h: At top level:
Linked_List.h:63: parse error before `private'
Linked_List.h:65: `short unsigned int internal_count' used prior to
declaration
Linked_List.h:67: parse error before `}'
Linked_List.h:70: confused by earlier errors, bailing out

Is it my code? Or is it simply that what I'm attempting can't be done?

[truls]

This compiles fine. Crashed when I try to run it though, but you can debug that ;-)

T.

---------------------------------

#ifndef _HAVE_LINKED_LIST_H_
#define _HAVE_LINKED_LIST_H_
// Type for deciding termination method of data nodes
typedef enum {
REMOVE_SINGLE,
REMOVE_ALL
} ll_term_t;
// IDFLAG type

typedef unsigned short IDFLAG_t;

template<class _data>
class Node
{
public:
Node(){}
virtual ~Node(){}
virtual Node<_data> *append_node(_data *thedata)=0;
virtual Node<_data> *add_node(_data *thedata, IDFLAG_t id)=0;
virtual IDFLAG_t get_object_id()const =0;
virtual void _increment_onward(IDFLAG_t)=0;
bool remove_node( IDFLAG_t ID_FLAG );
Node<_data> *get_next()const { return next; }
protected:
Node<_data> *next;
static unsigned short internal_count;
static ll_term_t TERM_TYPE;
};

template<class _data>
unsigned short Node<_data>::internal_count;

template<class _data>
ll_term_t Node<_data>::TERM_TYPE;

template<class _data>
bool Node<_data>::remove_node(IDFLAG_t ID_FLAG)
{
Node<class _data> *temp = next->get_next();
if(!(temp)) // if we found the tailnode
return false;
if(next->get_object_id() == ID_FLAG) { // we found what we're looking for!
delete next;
next = temp; // patch the hole
return true; // report success
} else { // Not yet found, but there is still room to search. Keep on lookin'
temp = NULL;
return next->remove_node(ID_FLAG); // continue recursively
}
}

template<class _data> class Tailnode;

template<class _data>
class Headnode : public Node<_data>
{
public:
Headnode();
~Headnode();
Node<_data> *append_node(_data *thedata);
Node<_data> *add_node(_data *thedata, IDFLAG_t id);
IDFLAG_t get_object_id()const { return 3; };
void _increment_onward(IDFLAG_t) {};
static unsigned short size() { return (internal_count + 1); }
private:
Tailnode<_data> * tail_ptr;
static unsigned short internal_count;
static ll_term_t TERM_TYPE;
};
template<class _data>
unsigned short Headnode<_data>::internal_count=0;

template<class _data>
ll_term_t Headnode<_data>::TERM_TYPE = REMOVE_SINGLE;

template<class _data>
Headnode<_data>::Headnode()
{
tail_ptr = new Tailnode<_data>;
}
template<class _data>
Headnode<_data>::~Headnode()
{
// If I'm being destroyed, then all others are to be destroyed as well.
TERM_TYPE = REMOVE_ALL;
delete next;
}
template<class _data>
Node<_data> *Headnode<_data>::append_node(_data *thedata)
{
next = next->append_node(thedata);
return this; // appease the compiler
}
template<class _data>
Node<_data> *Headnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
if(next->get_object_id() == id) { // wants to put it on the front end.
Node<_data> *temp = (!(next->get_next())) ? tail_ptr : next->get_next(); // get_next() is inline
next = new Internalnode<_data>(thedata, temp);
next->_increment_onward(id + 1);
} else {
next = next->add_node(thedata, id);
}
return this; // appease the compiler
}

template<class _data>
class Internalnode : public Node<_data>
{
public:
Internalnode(_data *thedata, Node<_data> *link_to);
~Internalnode();
Node<_data> *add_node(_data *thedata, IDFLAG_t id);
Node<_data> *append_node(_data *thedata);
IDFLAG_t get_object_id()const { return id; }
void _increment_onward(IDFLAG_t first); /* this function fixes the id vars in all the internalnodes
after an insertion has be done. */
private:
Tailnode<_data> * tail_ptr;
IDFLAG_t id;
_data *DATA;
};

template<class _data>
Internalnode<_data>::Internalnode(_data *thedata, Node<_data> *link_to)
{
id = internal_count++; // moved definition to base class
DATA = thedata;
next = link_to;
}

template<class _data>
Internalnode<_data>::~Internalnode()
{
// self-destruction chain reaction
if( TERM_TYPE == REMOVE_ALL )
delete next;
}

template<class _data>
Node<_data> *Internalnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
// then somewhere in the middle is where it wants to be put.
if(next->get_object_id() == id) { // wants to put it on the front end.
Node<_data> *temp = (!(next->get_next())) ? tail_ptr : next->get_next(); // get_next() is inline
next = new Internalnode(thedata, temp);
if(next->get_next())
next->_increment_onward(id + 1);
} else {
next = next->add_node(thedata, id);
}
return this;
}

template<class _data>
Node<_data> *Internalnode<_data>::append_node(_data *thedata)
{
next = next->append_node(thedata);
return this;
}

template<class _data>
void Internalnode<_data>::_increment_onward(IDFLAG_t first)
{
id = first;
if(!(next->get_next())) { // end condition
internal_count++;
return;
}
next->_increment_onward(id + 1); // continue recursively
}

template<class _data>
class Tailnode : public Node<_data>
{
public:
Tailnode(){ next = NULL; }
~Tailnode(){}
Node<_data> *append_node(_data *thedata);
Node<_data> *add_node(_data *thedata, IDFLAG_t id);
IDFLAG_t get_object_id()const { return 3; };
void _increment_onward(IDFLAG_t) {};
bool remove_node(IDFLAG_t id) { return false; }
};

template<class _data>
Node<_data> *Tailnode<_data>::append_node(_data *thedata)
{
return new Internalnode<_data>(thedata, this);
}

template<class _data>
Node<_data> *Tailnode<_data>::add_node(_data *thedata, IDFLAG_t id)
{
return append_node(thedata);
}
#endif /* _HAVE_LINKED_LIST_H_ */

[Concrete Geist]

I'm very new to templates, so this was a nightmare for me. Could you tell me what I did wrong?

[Stuka]

Since you're using templates, you need to put all of your methods inside your class definition, not separately from them in the same file. This has to do with compiler limitations, and not language problems - in theory, what you did should work, but due to the fact that the compiler can't figure out how to handle template class member functions that are declared outside the class definition, you've gotta put 'em in there. I think that's your biggest issue.

[truls]

diff the files and find out :D

Node is a template, so every time you refer to node as a data entity you should use Node<_data>. Just see what I removed or added and go from there.

I used Visual Studio though (work), I assume you're using gcc and I'll try to get it to work in that tomorrow sometimes. Just got adsl installed, and I'm not done setting thing up yet.

T.

[Concrete Geist]

Originally posted by Stuka:
<STRONG>Since you're using templates, you need to put all of your methods inside your class definition, not separately from them in the same file. </STRONG>

I'm a little confused by that. By that do you mean override every pure virtual function?

Truls, your code needed a little modification, but it works. I'm beginning to understand, thanks a lot. :)

[Concrete Geist]

bump

[Energon]

Originally posted by Concrete Geist:
<STRONG>I'm a little confused by that. By that do you mean override every pure virtual function?
</STRONG>

Nope, he means just what it says. You define your functions in the same header you declare them in, and you keep them in the class declaration instead of seperating them out. You should never ever see something like this in a template class:

template&lt;typename _data&gt;
bool Node&lt;_data&gt;::remove_node(IDFLAG_t ID_FLAG) {

You've moved the function defenition outside the class declaration, and that confuses compilers to no end atm.

[Concrete Geist]

So that means that a general node declaration would look like this:


template&lt;typename _data&gt;
class Node
{
public:
Node(){}
~Node(){}

friend class Linked_List;

// pure virtual functions
virtual Node&lt;_data&gt; *add_node(_data thedata, ID_FLAG_T id_point)=0;
virtual Node&lt;_data&gt; *append_node(_data thedata)=0;
virtual void _increment_onward(ID_FLAG_T x)=0;

// inherited methods
Node&lt;_data&gt; *get_next()const { return next; }

bool remove_node(ID_FLAG_T id_point)
{
Node&lt;class _data&gt; *temp = next-&gt;get_next();
if(!(temp)) // if we found the tailnode
return false;
if(next-&gt;get_object_id() == id_point) { // we found what we're looking for!
delete next;
next = temp; // patch the hole
return true; // report success
} else { // Not yet found, but there is still room to search. Keep on lookin'
temp = NULL;
return next-&gt;remove_node(id_point); // continue recursively
}
}

protected:
Node&lt;_data&gt; *next;
};

[Energon]

You got it.