how do I create a template structure of template nodes?

[Chazzmundo]

My problem is that I need a container (i.e. vector<>, deque<>, list<> etc) which holds something of a template type.

The only problem is that I need to be able to iterate through it so I have extended upon what one of my lecturers has wrote but it does not quite work.

Basically it is meant to be a ListOfT which holds NodeOfT. So in effect it is a container of an unspecific class.


I am doing this to make a bullet register for a ship in an Asteroids game.


Could someone please pass on an example of how you could create a container of type T which contains Nodes of type T.

Thank you for your help.

[hanst99]

template<typename T>
class Node;

template<typename T>
class NodeList
{
private:
 vector<Node<T> > nodeVector;
}

[D80DSL3A]

That's probably not going to be very useful Hanst, except to your post count that is...

@Chazzmundo: How fancy need it be? Will a simple unsorted template type link list do?

[hanst99]

I don't really care about my post count, it's not like I get paid for this. And he hasn't asked for a class, he asked how to create a container of T that holds Nodes of T. I did show him, so I don't really see your problem here.

[Chazzmundo]

Well here is my NodeOfT.h

#ifndef NODE_OF_T
#define NODE_OF_T
//this class implements a node which can hold T data

template <typename T>
class NodeOfT	
{
private:
	T data;
	NodeOfT<T>* prev;
	NodeOfT<T>* next;

public:
	//creates a node containing the null T
	//pointing to null for next and prev
	NodeOfT()
	{
		data='\0';
		prev=0;
		next=0;
	}

	//creates a NodeOfT containing T c
	//pointing to null for next and prev
	NodeOfT(T c)
	{
		data = c;
		prev = 0;
		next = 0;
	}
	
	//creates NodeOfT containing T c, pointing to *next and *prev
	NodeOfT(T c, NodeOfT* p,NodeOfT* n)
	{
		data = c;
		prev = p;
		next = n;
	}
	
	//sets the T
	void setT(T c)
	{
		data = c;
	}

	//sets the next pointer
	void setNextPtr(NodeOfT* pN)
	{
		next=pN;
	}
	//sets the prev pointer
	void setPrevPtr(NodeOfT* pN)
	{
		prev = pN;
	}

	//gets the T
	T getData()
	{
		return data;
	}

	//gets the next pointer
	NodeOfT*  getNextPtr(void)
	{
		return next;
	}
	//gets the prev pointer
	NodeOfT* getPrevPtr(void)
	{
		return prev;
	}
};
#endif 

and this is my ListOfT.h (a bit long sorry)

#ifndef LIST_OF_T
#define LIST_OF_T
#include "NodeOfT.h"
#include <iostream>

//this class is to implement a list of T - from the user point of view it 
//should look like a list of T - not a list of nodes of T - there is subtle
//difference.

//we also have the notion of a current element - this is basically a built in iterator
//which some people think lists should have

template <typename T>
class ListOfT
{
private:
	NodeOfT<T>* first; //first in the list
	NodeOfT<T>* last;   //last in the list -could be the same as the first
	NodeOfT<T>* current; //the current node - sort of iterator
						//the only way that current can be null is if the list is empty
	int numberOfNodes; //how many nodes there are

public:
	//create an empty list
	ListOfT()
	{
		numberOfNodes=0;
		first=0;last=0;current=0;
	}



	//This class will need a destructor but I have not written it
	~ListOfT()
	{

	}
	
	//create a list with head c
	ListOfT(T c)
	{
		//since the list will have only one element it must be first,last and current
		NodeOfT* p=new NodeOfT(c);
		numberOfNodes=1;
		first=p;last=p;current=p;
	}

	//function to insert T after current
	//if current is null then list must be empty so behave appropriately
	void insertAfter(T c)
	{
		if(current==0) //the list is empty - so inserting is the same as creating a list of length 1
		{
			NodeOfT* p=new NodeOfT(c);
			numberOfNodes=1;
			first=p;last=p;current=p;p->setNextPtr(0);
		}
		else 
		{
			//we create a node containing the T
			NodeOfT* p=new NodeOfT(c);
			//the next value of the new node is the same as the next of the current
			p->setNextPtr(current->getNextPtr());
			//the next pointer on the current node is set to point to the new node
			current->setNextPtr(p);
			//the pointer on p is set to point back to current
			p->setPrevPtr(current);
			//the prev pointer on the next node to p needs to point back to p
			//but only if the next pointer of p is not null
			if(p->getNextPtr()!=0) (p->getNextPtr())->setPrevPtr(p);
			else last=p;
			currentForward();
			numberOfNodes++;
		}
	}

	//function to insert T before current
	//if current is null then list must be empty so behave appropriately
	void insertBefore(T c)//supply
	{
		if(current==0) //the list is empty - so inserting is the same as creating a list of length 1
		{
			NodeOfT* p=new NodeOfT(c);
			numberOfNodes=1;
			first=p;last=p;current=p;p->setPrevPtr(0);
		}
		else 
		{
			//we create a node containing the T
			NodeOfT* p=new NodeOfT(c);
			//the prev value of the new node is the same as the prev of the current
			p->setPrevPtr(current->getPrevPtr());
			//the next pointer on the current node is set to point to the new node
			current->setPrevPtr(p);
			//the pointer on p is set to point forwards to current
			p->setNextPtr(current);


			//the prev pointer on the prev node to p needs to point forwards to p
			//but only if the prev pointer of p is not null
			if(p->getPrevPtr()!=0) (p->getPrevPtr())->setNextPtr(p);
			else first=p;
			currentForward();
			numberOfNodes++;
		}
	}


	//function to erase current node - current gets set to prev
	//provided prev not null, otherwise gets set to next if next not null,
	//otherwise gets set to null
	void eraseCurrent()
	{
		if (current->getPrevPtr() != 0)
		{
			current = current->getPrevPtr();
		}
		else if (current->getNextPtr() != 0)
		{
			current = current->getNextPtr();
		}
		else 
		{
			current = 0;
		}

		delete current;
	}

	//lists all the Ts in the list to the console
	void itemize()
	{
		NodeOfT* p=first;
		while(p!=0)
		{
			std::cout<<p->getT();
			p = p->getNextPtr();
		}
		std::cout<<std::endl;
	}

	//tells us if the list is empty
	bool empty() 
	{
		if (numberOfNodes == 0) 
			return true; 
		else return false;
	}

	//returns the current T
	//if current node is null this will cause problems
	T getCurrent()
	{
		return current->getT();
	}

	//tells us if current can be moved to next
	bool currentForwardable() 
	{
		if (current->getNextPtr() == 0) 
			return false; 
		else return true;
	}

	//tells us if current can be moved to prev
	bool currentBackable() 
	{
		if (current->getPrevPtr() == 0) 
			return false; 
		else return true;
	}

	//move the iterator
	void currentForward() 
	{
		if (currentForwardable() ) 
			current = current->getNextPtr();
	}

	void currentBack() 
	{
		if (currentBackable() ) 
			current = current->getPrevPtr();
	}

	//returns the number of Ts in the list
	int size() 
	{
		return numberOfNodes;
	}


	T getPrevious()
	{
		T x;
		
		if (currentBackable()) 
		{
			currentBack();
			x = getCurrent();
			currentForward();
		}
		else 
		{
			x = '\0';
		}
		
		return x;
	}

	T getNext()
	{
		T x;
		
		if (currentForwardable()) 
		{
			currentForward();
			x = getCurrent();
			currentBack();
		}
		else 
		{
			x = '\0';
		}
		
		return x;
	}

	void setToFirst()
	{
		current = first;
	}

	void setToLast()
	{
		current = last;
	}


};
#endif 

Is this a correct way of implementing a list of a template type?

[hanst99]

Well, two tips for this one:
1)

a correct way

if it does what you want it to, sure.
2) A much easier method would have been to just use the builtin list class, unless it was your homework to write a list implementation or something:
http://cplusplus.com/reference/stl/list/

[Chazzmundo]

I am required to write it myself unfortunately.

EDIT:
I managed to sort it. The problem was that things such as this
NodeOfT* p=new NodeOfT(c);

should be: NodeOfT<T>* p=new NodeOfT<T>(c);

Silly mistake. Thank you for the help anyways :)

[D80DSL3A]

Does your eraseCurrent() work ok?
It looks like you adjust current (so it's pointing to a node you don't want to delete) and then delete it without linking across it first. This leaves the nodes before and after it with pointers to the deleted node because they were not changed.

[Chazzmundo]

it did have a minor problem that I found since my last post. I edited to the following:

void eraseCurrent()
	{
		if(current!=0)//list is not empty
		{
			if(current->getPrevPtr()!=0)//current has a previous
			{
				current->getPrevPtr()->setNextPtr(current->getNextPtr());//currents previous has its next set to currents next
				if(current->getNextPtr()!=0) current->getNextPtr()->setPrevPtr(current->getPrevPtr());//current next has its previous set to currents prev
				else last=current->getPrevPtr();//current was last so last needs re-setting
				NodeOfT<T>* tmp=current;//remember what current was
				current=current->getPrevPtr();//make prev current
				delete tmp;//cleanup heap
				tmp=0;//not really necessary but tidiness is a habit.
			}
			else if(current->getNextPtr()!=0)//current has no previous but does have a next
			{
				current->getNextPtr()->setPrevPtr(0);//needs to point to null
				first=current->getNextPtr();//current was first as well = so first needs resetting
				NodeOfT<T>* tmp=current;//remember what current was
				current=current->getNextPtr();//make next current
				delete tmp;//clean up
				tmp=0;//not really necessary but tidiness is a habit.
			}
			else //current has no previous and no next - so is the only node
			{
				delete current;
				current=0;
				first=0;
				last=0;
			}
			//we have definitely deleted something
			NumberOfNodes--;
		}
	}

[D80DSL3A]

That looks WAY better!

[Chazzmundo]

EDIT: SOLVED PLEASE DO NOT RESPOND

I am adding to this rather than creating a new thread as it relevant to this.

So my problem is that I have successfully implemented my own container (a list) of a template type T (in this case it is a class Bullet), and I am able to access the nodes within this list but for some reason I am unable to edit the data :s

So at the moment, I have a ListOfT<Bullet> bulletRegister; in my Ship.h. When the fire() function is called, it does the following:

void Ship::fire() //fire a new bullet to the screen
{
	canShoot = 0; //reset fire counter
	cout<<"Shot has been fired!"<<endl;

	//add bullet to register
	Bullet b(xPos,yPos,xSpeed, ySpeed, true);
	cout<<b.getXSpeed()<<"\t"<<b.getYSpeed()<<endl; //debug
	bulletRegister.insertAfter(b);
}

Every time the game loop is run, the following is run:

void Ship::calculatePosition()
{
	...

	//check through bullet register and update/delete where approriate
	if (bulletRegister.size() != 0)
	{
		//cout<<"Size: "<<bulletRegister.size()<<endl;
		bulletRegister.setToFirst(); //sets the list iterator to the first element
		while(bulletRegister.currentForwardable()) //while there is a next object in the list
		{
			//check whether to update
			checkBullet();		
			
			bulletRegister.currentForward(); //move iterator one node forward
		}
		checkBullet(); //check for this last bullet in register
	}
}

So the above loops through the nodes in the list and calls the checkBullet function:

//check if current bullet in list needs to be deleted
void Ship::checkBullet()
{
	bulletRegister.getCurrent().updatePosition();
	
        //the following three lines are debug to prove it does not update the position
        cout<<"prev: "<<bulletRegister.getCurrent().getXpos();
	bulletRegister.getCurrent().setXpos(bulletRegister.getCurrent().getXpos()+5);
	cout<<"  after altering: "<<bulletRegister.getCurrent().getXpos()<<endl;


	//cout<<"Now checking: "<<bulletRegister.getCurrent().getTime()<<endl;
	if (bulletRegister.getCurrent().shouldDelete())
	{
		bulletRegister.eraseCurrent();
		cout<<"deleted\n";
	}
}

Now bulletRegister.getCurrent().updatePosition(); should update the bullets position and time (and it does within the actual call) but as soon as control returns to the caller function (checkBullet() ), it does not seem to register that the data was changed.

To prove this further I manually altered the x position of the bullet and cout'ed the bullets position before and after. As you can see in the code there should be a difference of +5 in the after cout. There is not :(

I do not understand why this is not updating, I must be accessing the correct Bullet datatype because it cout's the correct position and speed of the bullet (before altering) but it is not actually altering the data itself.

Any ideas?

EDIT: SOLVED PLEASE DO NOT RESPOND
I solved by making a copy of each of the bullets variables, storing into a Bullet b object and using the list.setCurrent(b). Not the best and most practical way to do it but it works.