Member Avatar for badllama

Okay, I’ve got a noob question. It’s been awhile since I coded so I thought I’d start off at the beginning and create a template list and tree. Back in the old days I left the nodes open, but I wanted to keep the data private this time. My first thought was to make the node class a friend of the list. For example:

template <class T>
class node
{
	friend class list;
public:
	node() { prev = NULL; next = NULL; };
	T get() { return this->key; };
private:
	T key;
	static int count;
	node <T> *prev;
	node <T> *next;
};

Gives me a bunch of errors: “class template has already been declared as a non-class template”, “multiple template parameter lists are not allowed”. It looks as though the compiler is ignoring the “friend” part of things and seeing queue as a definition. Yet every online example I’ve found follows this format.

So, okay, there’s no real reason the node needs to be its own class. Instead I make it a nested class within list, which will be the only class that needs to see the node anyway. That works… mostly… Except when the user says “remove node with key of ‘strawberry’” I want the removeNode method to call a findSpecNode(key) method that returns the address of the node. I could do that in the removeNode method but I’d rather farm it out to its own method.

template <class LISTDATA>
listNode<LISTDATA> *list<LISTDATA>::findSpecNode (LISTDATA ToFind)
{
	listNode *tempNode = NULL;
	if (this->start != NULL)
	{
		tempNode = this->start;
		while (tempNode->next != NULL && tempNode->key != ToFind)
			tempNode = tempNode->next;
		if (tempNode->key != ToFind)
			throw exceptions ("Error (list.findSpecNode): Could not find node in list");
	}
	else
	{
		throw exceptions("Error (list.findSpecNode): could not find node, list empty");
	}
	return tempNode;
}

That isn’t working either. I’m getting the following error messages. I’ve looked them up, but I they aren’t relevant. Also, if I make that method void instead of listNode<LISTDATA>* it compiles fine. So I’m guessing the whole problem is the compiler not recognizing a return type of <T>*?

//All errors are from this line:
listNode<LISTDATA> *list<LISTDATA>::findSpecNode (LISTDATA ToFind)

error C2143: syntax error : missing ';' before '<'
eerror C4430: missing type specifier - int assumed. Note: C++ does not support default-int
error C2988: unrecognizable template declaration/definition
error C2059: syntax error : '<'
error C2065: 'LISTDATA' : undeclared identifier

There’s got to be something I’m not understanding about this whole thing; something I can’t remember or wasn’t taught to begin with. I can do a workaround, put a global cursor in or something, but I guess I got “globals are bad, make everything modular” drilled into my head a bit too much back in school Besides, I’d rather know why than how. Can anyone steer me in the right direction here? Why doesn’t friend work? Why doesn’t return <T>* work?

Oh, C++ using Microsoft Visual Studio 2008. Thank you very muchly.

  • 3 Contributors
  • 7 Replies
  • 227 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by Valaraukar
Member Avatar for Valaraukar

Could you attach (using the advanced editor) the files that you are working with so that I can have a poke around?

Member Avatar for mrnutty

Is listNode a even template class? I ask because of this contradiction statements :

listNode<LISTDATA>*

vs

listNode *tempNode = NULL
Edited by mrnutty because: n/a
Member Avatar for badllama

firstPerson: listNode, in that incarnation, is a template class within list which contains prev and next pointers and data of type LISTDATA.

template <class LISTDATA>
	class list
	{
	private:
		template <class LISTDATA>
		class listNode
		{
		public:
			listNode () { prev = NULL; next = NULL; };
			~listNode () { };
			LISTDATA key;
			listNode *prev;
			listNode *next;
		};
		// SO ON AND SO FORTH
	};

As I understand it that is correct for a method header that returns the address of a class which contains <T>, but a declaration inside the method doesn't require that. However, I'm obviously having some problems with syntax there so clearly there's something I'm not understanding.

Member Avatar for badllama

caged_fire. Ahhh, that's how you attach files. Ha. Done. Some of it's going to be pretty messy, apologies.

#include <string>
#include <iostream>

#ifndef EXCEPTIONS_H
#define EXCEPTIONS_H

	class exceptions
	{
	public:
		exceptions (std::string Message) { this->errorMsg = Message; }
		void print () const;
	private:
		std::string errorMsg;
	};

	void exceptions::print() const
	{
		std::cerr << errorMsg;
		std::cerr << std::endl << std::endl;
	}

#endif
#include <iostream>
#include "exceptions.h"

#ifndef LIST_H
#define LIST_H

	// ----------------- LIST CLASS -------------------

	template <class LISTDATA>
	class list
	{
	private:
		template <class LISTDATA>
		class listNode
		{
		public:
			listNode () { prev = NULL; next = NULL; };
			~listNode () { };
			LISTDATA key;
			listNode *prev;
			listNode *next;
		};
	public:
		list ();
		~list ();
		void add (const LISTDATA Value);
		void remove (const LISTDATA Value);
		void remove ();
		void push (const LISTDATA Value);
		LISTDATA pop ( );
		void enqueue (const LISTDATA Value);
		LISTDATA dequeue ();
		int size () { return this->numberOfNodes; };
		LISTDATA operator [] (const int stop);
		void print();
	private:
		listNode <LISTDATA> *start;
		listNode <LISTDATA> *end;
		int numberOfNodes;
	private:
		void addToStart (const LISTDATA Key);
		void addToEnd (const LISTDATA Key);
		void addInOrder (const LISTDATA Key);
		LISTDATA removeFromStart ();
		LISTDATA removeFromEnd ();
		LISTDATA removeNode (const LISTDATA Value);
		void findSpecNode (LISTDATA Key);
	};

	// ---------- LIST CONSTRUCTOR DESTRUCTOR ----------

	template <class LISTDATA>
	list<LISTDATA>::list()
	{
		this->start = NULL;
		this->end = NULL;
		this->numberOfNodes = 0;
	}

	template <class LISTDATA>
	list<LISTDATA>::~list()
	{
		LISTDATA tempData;
		while (this->end != NULL)
		{
			tempData = this->removeFromEnd();
		}
	}

	// ---------------- ADD AND REMOVE ----------------------

	template <class LISTDATA>
	void list<LISTDATA>::add(LISTDATA Value)
	{
		this->addToEnd(Value);
	}

	template <class LISTDATA>
	void list<LISTDATA>::remove(const LISTDATA Value)
	{
		this->removeNode (Value);
	}

	template <class LISTDATA>
	void list<LISTDATA>::remove()
	{
		LISTDATA tempData;
		tempData = this->removeFromEnd();
	}

	template <class LISTDATA>
	void list<LISTDATA>::push(const LISTDATA Key)
	{
		this->addToEnd();
	}

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::pop()
	{
		LISTDATA tempData;
		tempData = this->removeFromEnd();
		return tempData;
	}

	template <class LISTDATA>
	void list<LISTDATA>::enqueue(const LISTDATA Value)
	{
		this->addToEnd(Value);
	}

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::dequeue()
	{
		LISTDATA tempData;
		tempData = this->removeFromStart();
		return tempData;
	}

	// ------------------- ADD TO --------------------------

	template <class LISTDATA>
	void list<LISTDATA>::addToStart(const LISTDATA Value)
	{
		listNode <LISTDATA> *tempNode = new listNode <LISTDATA>;
		tempNode->key = Value;
		if (this->start == NULL)
		{
			this->start = tempNode;
			this->end = tempNode;
		}
		else
		{
			this->start->prev = tempNode;
			tempNode->next = this->start;
			this->start = tempNode;
		}
		this->numberOfNodes++;
	}

	template <class LISTDATA>
	void list<LISTDATA>::addToEnd(const LISTDATA Value)
	{
		listNode <LISTDATA> *tempNode = new listNode <LISTDATA>;
		tempNode->key = Value;
		if (this->end == NULL)
		{
			this->start = tempNode;
			this->end = tempNode;
		}
		else
		{
			this->end->next = tempNode;
			tempNode->prev = this->end;
			this->end = tempNode;
		}
		this->numberOfNodes++;
	}

	template <class LISTDATA>
	void list<LISTDATA>::addInOrder(const LISTDATA Value)
	{
		listNode <LISTDATA> *tempPrev;
		listNode <LISTDATA> *tempNext;
		listNode <LISTDATA> *tempNode;
		listNode <LISTDATA> *addNode = new listNode <LISTDATA>;

		addNode->key = Value;
		if (this->start == NULL)
		{
			this->addToStart(Value);
		}
		else if (Value < this->start->key)
		{
			this->addToStart(Value);
		}
		else if (Value > this->end->key)
		{
			this->addToEnd(Value);
		}
		else
		{
			tempNode = this->start;
			while (Value < tempNode->key)
			{
				tempNode = tempNode->next;
			}
			tempPrev = tempNode->prev;
			tempPrev->next = addNode;
			addNode->prev = tempPrev;
			addNode->next = tempNode;
			tempNode->prev = addNode;
		}
		this->numberOfNodes++;
	}

	// ---------------- REMOVE FROM ------------------------

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::removeFromStart()
	{
		listNode <LISTDATA> *tempNode;
		LISTDATA tempData;
		if (this->start != NULL)
		{
			tempNode = this->start;
			if (tempNode->next == NULL)
			{
				this->start = NULL;
				this->end = NULL;
			}
			else
			{
				this->start = tempNode->next;
				this->start->prev = NULL;
			}
			tempData = tempNode->key;
			delete tempNode;
			this->numberOfNodes--;
		}
		else
		{
			throw exceptions("Error (list.removeFromStart): Attempt to delete from an empty list");
		}
		return tempData;
	}

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::removeFromEnd()
	{
		listNode <LISTDATA> *tempNode;
		LISTDATA tempData;
		if (this->start != NULL)
		{
			tempNode = this->end;
			if (tempNode->prev == NULL)
			{
				this->start = NULL;
				this->end = NULL;
			}
			else
			{
				this->end = tempNode->prev;
				this->end->next = NULL;
			}
			tempData = tempNode->key;
			delete tempNode;
			this->numberOfNodes--;
		}
		else
		{
			throw exceptions("Error (list.removeFromEnd): Attempt to delete from an empty list");
		}
		return tempData;
	}

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::removeNode (const LISTDATA Value)
	{
		listNode <LISTDATA> *tempNode;
		listNode <LISTDATA> *tempPrev;
		listNode <LISTDATA> *tempNext;
		LISTDATA tempData;
		tempNode = this->findSpecNode(Value);
		// PROBLEM HERE!!!

		if (tempNode != NULL)
		{
			if (tempNode == this->start) { tempData = this->removeFromStart(); }
			else if (tempNode == this->end) { tempData = this->removeFromEnd(); }
			else
			{
				tempData = tempNode->key;
				tempPrev = tempNode->prev;
				tempNext = tempNode->next;
				if (tempPrev != NULL) { tempPrev->next = tempNext; }
				if (tempNext != NULL) { tempNext->prev = tempPrev; }
				delete tempNode;
				this->numberOfNodes--;
			}
		}
		else
		{
			throw exceptions("Error (list.removeNode): Could not find node to delete");
		}
		return tempData;
	}

	// ------------------ FIND NODE ------------------------

	template <class LISTDATA>
	listNode *list<LISTDATA>::findSpecNode (LISTDATA ToFind)
	{
		listNode *tempNode = NULL;
		if (this->start != NULL)
		{
			tempNode = this->start;
			while (tempNode->next != NULL && tempNode->key != ToFind)
				tempNode = tempNode->next;
			if (tempNode->key != ToFind)
				throw exceptions ("Error (list.findSpecNode): Could not find node in list");
		}
		else
		{
			throw exceptions("Error (list.findSpecNode): could not find node, list empty");
		}
		return tempNode;
	}

	// ---------------- LIST ACCESS ------------------------

	template <class LISTDATA>
	LISTDATA list<LISTDATA>::operator [](const int stop)
	{
		listNode <LISTDATA> *tempNode;
		tempNode = this->start;
		if (stop < this->numberOfNodes)
		{
			for (int i=0; i<stop; i++)
			{
				tempNode = tempNode->next;
			}
		}
		else
		{
			throw exceptions("Error (list.[]): Range out of bounds");
		}
		return tempNode->key;
	}

	template <class LISTDATA>
	void list<LISTDATA>::print()
	{
		listNode <LISTDATA> *tempNode;
		tempNode = this->start;
		int i = 0;
		if (tempNode == NULL)
		{
			std::cout << "The list is empty " << std::endl;
		}
		else
		{
			std::cout << "Printing list!" << std::endl;
			std::cout << "There is a total of " << this->size();
			this->size() == 1 ? std::cout << " node." : std::cout << " nodes.";
			std::cout << std::endl;
			tempNode = this->start;
			while (tempNode->next != NULL)
			{
				std::cout << "Printing node number " << i << ": " << tempNode->key << std::endl;
				tempNode = tempNode->next;
				i++;
			}
			std::cout << "Printing node number " << i << ": " << tempNode->key << std::endl;
		}
	}


#endif

/* **************************************************************
** LIST CLASS EXCEPTIONS
** Error (list.removeFromStart): Attempt to delete from an empty list
** Error (list.removeFromEnd): Attempt to delete from an empty list
** Error (list.removeNode): Could not find node to delete
** Error (list.findSpecNode): Could not find node in list
** Error (list.findSpecNode): could not find node, list empty
** ERROR (list.[]): Range out of bounds
** *************************************************************/

/* **************************************************************
** LIST CLASS ADDING CLASS EXAMPLE

	class testClass
	{
	public:
		testClass () { };
		testClass (const testClass &setData);
		~testClass () { };
		void set(int Value1, std::string Value2);
		// TESTED AGAINST KEY, OPTIONAL VALUE, CHANGE AS NEEDED
		bool operator < (const testClass test2) { return this->Key < test2.Key; };
		bool operator <= (const testClass test2) { return this->Key <= test2.Key; };
		bool operator > (const testClass test2) { return this->Key > test2.Key; };
		bool operator >= (const testClass test2) { return this->Key >= test2.Key; };
		bool operator == (const testClass test2) { return this->Key == test2.Key; };
		bool operator != (const testClass test2) { return this->Key != test2.Key; };
	private:
		int Key;			// EXAMPLE VALUE ONLY, OPTIONAL
		std::string Name;	// EXAMPLE VALUE ONLY, OPTIONAL
	};

**   
** *************************************************************/
#include <iostream>
#include <stdlib.h>

#include "exceptions.h"
#include "testClass.h"
#include "list.h"

int main ()
{
	int i;

	list <int> l;
	l.print();
	int testArray[10] = {12, 67, 19, 27, 123, 65, 108, 79, 2, 82};
	for (i=0; i<10; i++) { l.add(testArray[i]); }
	l.print();
	std::cout << "Removing node" << std::endl;
	l.remove();
	l.print();
	try
	{
	std::cout << "Removing node 19" << std::endl;
	l.remove(19);
	l.print();
	}
	catch (const cm::exceptions& ListError)
	{
		ListError.print();
		return 1;
	}
	std::cout << "Ending primitive data types test " << std::endl << std::endl;
	std::cout << "Beginning custom class test" << std::endl << std::endl;

	cm::list <txtAdv::testClass> cl;
	int testArray2[5] = {101, 102, 103, 201, 202};
	std::string testArray3[5] = {"Living Room", "Dining Room", "Kitchen", "Corner Store", "Arcade"};
	txtAdv::testClass DataClass;
	for (i=0; i<5; i++)
	{
		DataClass.set(testArray2[i], testArray3[i]);
		cl.add(DataClass);
	}
	for (i=0; i<cl.size(); i++)
	{
		cl[i].print();
	}
	/*
	try { cl[5].print(); }
	catch ( const cm::exceptions& ListError2)
	{
		ListError2.print();
		return 1;
	}
	*/
	std::cout << cl[0].getNo();
	if (cl[0] < cl[2]) { std::cout << " < "; } else { std::cout << " not < "; }
	std::cout << cl[2].getNo() << std::endl;

	std::cout << cl[2].getNo();
	if (cl[2] < cl[0]) { std::cout << " < "; } else { std::cout << " not < "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << cl[0].getNo();
	if (cl[0] <= cl[0]) { std::cout << " <= "; } else { std::cout << " not <= "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << cl[0].getNo();
	if (cl[0] > cl[2]) { std::cout << " > "; } else { std::cout << " not > "; }
	std::cout << cl[2].getNo() << std::endl;

	std::cout << cl[2].getNo();
	if (cl[2] > cl[0]) { std::cout << " > "; } else { std::cout << " not > "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << cl[0].getNo();
	if (cl[0] >= cl[0]) { std::cout << " >= "; } else { std::cout << " not >= "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << cl[0].getNo();
	if (cl[0] == cl[2]) { std::cout << " == "; } else { std::cout << " not == "; }
	std::cout << cl[2].getNo() << std::endl;

	std::cout << cl[2].getNo();
	if (cl[2] == cl[2]) { std::cout << " == "; } else { std::cout << " not == "; }
	std::cout << cl[2].getNo() << std::endl;

	std::cout << cl[0].getNo();
	if (cl[0] != cl[0]) { std::cout << " != "; } else { std::cout << " not != "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << cl[4].getNo();
	if (cl[4] != cl[0]) { std::cout << " != "; } else { std::cout << " not != "; }
	std::cout << cl[0].getNo() << std::endl;

	std::cout << "Removing 102 Dining Room" << std::endl;
	DataClass.set(102, "Dining Room");
	cl.remove(DataClass);
	std::cout << "Removing last node" << std::endl;
	cl.remove();
	for (i=0; i<cl.size(); i++)
	{
		cl[i].print();
	}

	return 0;
}
#include <string>
#include "list.h"

#ifndef TESTCLASS_H
#define TESTCLASS_H

		class testClass
		{
		public:
			testClass () { };
			testClass (const testClass &setData);
			~testClass () { };
			void set(int Value1, std::string Value2);
			//operator < (testClass test1, testClass test2);
			bool operator < (const testClass test2) { return this->squareNo < test2.squareNo; };
			bool operator <= (const testClass test2) { return this->squareNo <= test2.squareNo; };
			bool operator > (const testClass test2) { return this->squareNo > test2.squareNo; };
			bool operator >= (const testClass test2) { return this->squareNo >= test2.squareNo; };
			bool operator == (const testClass test2) { return this->squareNo == test2.squareNo; };
			bool operator != (const testClass test2) { return this->squareNo != test2.squareNo; };
			void print();
			int getNo() { return this->squareNo; };
		private:
			int squareNo;
			std::string squareName;
		};

		testClass::testClass (const testClass &setData)
		{
			this->squareNo = setData.squareNo;
			this->squareName = setData.squareName;
		}

		void testClass::set(int Value1, std::string Value2)
		{
			this->squareNo = Value1;
			this->squareName = Value2;
		}

		void testClass::print()
		{
			std::cout << "Square number " << this->squareNo << " is " << this->squareName << "." << std::endl;
		}

#endif
Member Avatar for Valaraukar

The problems all seem to be with your "findSpecNode" function. If you adapt your code to return the index of the node that you are searching for (and not a pointer to a 'non-concrete type') then it seems to compile fine :)

Also the function declaration didn't actually match your implementation. You had declared it as void but you were then implementing it to return a pointer to a listNode. Anyway as I said, if you return the index of the node you are searching for and not a pointer to the node itself, then it seems to be problem solved.

Member Avatar for badllama

caged_fire: Ha. Yeah, I'd changed the declaration to void to see if it would compile without returning the pointer. Apparently I forgot to change it back. Brain not good right now. Okay, so I'll need to do a workaround for this, or maybe just incorporate findSpecNode into removeNode since that's the only method I use it in. Thanks for the look over.

Member Avatar for Valaraukar

No problem :) Let me know how you get on. If you need any more help then I'll have a another look at your code and perhaps look into building a complete working solution so that I can post up a bit of code

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.