Linked list question...
Author
i have a generic linked list template that has a struct defined for each node which, in turn, has a void pointer to point off to some data (whatever you want to include in the list). Each node is auto-generated an ID when it is added, which is the search indicator. NOTE: the structure for the node is outside of the template class definition.
My question is this -
Using this list in a tile based game, should i iterate through the entire list until a match is found on the void pointer's data? i have a feeling this will be too slow - if so, anyone have any recommendations as to how i should set this up (i.e. create another linked list type specific for this game)?
Lastly, can template functions be virtual?
Thanks!!!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 9:52:14 AM
Author
i don't mean to bugger on and on about this, but here is my header file for the template code:
Thanks!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:03:11 AM
#include <windows.h>#include <windowsx.h>#include <ddraw.h>#include <stdio.h>#include <fstream.h>#include <cmath>///////DECLARATIONS#ifndef __LINKEDLIST_H__#define __LINKEDLIST_H__struct LISTDATA_TYP{public: LISTDATA_TYP() {} ~LISTDATA_TYP() {} void *m_pData; int m_nNodeID; LISTDATA_TYP* m_pNextNode; LISTDATA_TYP* m_pPrevNode;};template <class T> class LinkedListTemplate{public: LinkedListTemplate(); ~LinkedListTemplate(); int InsertElementInList(void *pDataElement); int DeleteElementInList(long nID); void* GetElementFromList(long nSearchNodeID); protected: int AddNewNode(LISTDATA_TYP* pNewNode); int RemoveNode(LISTDATA_TYP* pDeleteNode); long SetNewListElementID(); LISTDATA_TYP* FindNodeInList(long nSearchNodeID); LISTDATA_TYP *m_pHeadNode; LISTDATA_TYP *m_pTailNode; LISTDATA_TYP *m_pCurrentNode; long m_iListElementIndex;};///////DEFINITIONS//Public functionstemplate <class T> LinkedListTemplate<T>::LinkedListTemplate() { m_pHeadNode=NULL; m_pTailNode=NULL; m_pCurrentNode=NULL; m_iListElementIndex = 0; }template <class T> LinkedListTemplate<T>::~LinkedListTemplate() { if(m_pHeadNode) { while(m_pHeadNode->m_pNextNode!=m_pTailNode) {RemoveNode(m_pHeadNode->m_pNextNode);} if(m_pHeadNode) {delete(m_pHeadNode);} if(m_pTailNode) {delete(m_pTailNode);} } };template <class T> int LinkedListTemplate<T>::InsertElementInList(void *pDataElement) { LISTDATA_TYP* pNewNode = new LISTDATA_TYP; pNewNode->m_pData = pDataElement; pNewNode->m_nNodeID = SetNewListElementID(); return AddNewNode(pNewNode); }template <class T> int LinkedListTemplate<T>::DeleteElementInList(long nID) { return(RemoveNode(FindNodeInList(nID))); }template <class T> void* LinkedListTemplate<T>::GetElementFromList(long nSearchNodeID) { return(FindNodeInList(nSearchNodeID)->m_pData); }//Protected functions:template <class T> long LinkedListTemplate<T>::SetNewListElementID() { m_iListElementIndex++; return m_iListElementIndex-1; }template <class T> int LinkedListTemplate<T>::AddNewNode(LISTDATA_TYP* pNewNode) { if(m_pHeadNode==NULL) //New List { m_pHeadNode = m_pTailNode = pNewNode; return(pNewNode->m_nNodeID); } else if ((m_pHeadNode!=NULL)&&(m_pHeadNode==m_pTailNode)) { //only one NODE exists in the list m_pHeadNode->m_pNextNode = pNewNode; pNewNode->m_pPrevNode = m_pHeadNode; m_pTailNode = pNewNode; return(pNewNode->m_nNodeID); } else { //2 or more NODEs in list m_pTailNode->m_pNextNode = pNewNode; pNewNode->m_pPrevNode = m_pTailNode; m_pTailNode = pNewNode; return(pNewNode->m_nNodeID); } }template <class T> int LinkedListTemplate<T>::RemoveNode(LISTDATA_TYP* pDeleteNode) { if(!m_pHeadNode) //does a list exist? { return(FALSE); } int nID = pDeleteNode->m_nNodeID; LISTDATA_TYP *pCurrNode = m_pHeadNode; LISTDATA_TYP *pPrevNode = m_pHeadNode; while(pCurrNode->m_nNodeID != nID && pCurrNode) { //Save position pPrevNode = pCurrNode; pCurrNode = pCurrNode->m_pNextNode; } //Find the NODE if(pCurrNode==NULL) { return(FALSE); //NODE not found } if(m_pHeadNode==m_pTailNode) { //One NODE in list delete(m_pHeadNode); m_pHeadNode = m_pTailNode = NULL; return(TRUE); } else if (pCurrNode == m_pHeadNode) { //Front of list //Move head to next NODE m_pHeadNode=m_pHeadNode->m_pNextNode; delete(pCurrNode); pCurrNode = NULL; return(nID); } else { //Node is in middle of list pPrevNode->m_pNextNode = pCurrNode->m_pNextNode; pPrevNode->m_pPrevNode = pCurrNode->m_pPrevNode; delete(pCurrNode); pCurrNode = NULL; return(nID); } }template <class T> LISTDATA_TYP* LinkedListTemplate<T>::FindNodeInList(long nSearchNodeID) { bool bFound = false; if(m_pCurrentNode==NULL) {m_pCurrentNode = m_pHeadNode;} while((m_pCurrentNode != NULL) && (!bFound)) { if(m_pCurrentNode->m_nNodeID == nSearchNodeID) {bFound=true;} else { if(m_pCurrentNode->m_nNodeID < nSearchNodeID) { int nIndexDiff = (nSearchNodeID - m_pCurrentNode->m_nNodeID); for(int i=0;i<nIndexDiff;i++) { m_pCurrentNode = m_pCurrentNode->m_pNextNode; } if(m_pCurrentNode->m_nNodeID==nSearchNodeID) {bFound=true;} } else { int nIndexDiff = (m_pCurrentNode->m_nNodeID - nSearchNodeID); for(int i=nIndexDiff;i>0;i--) { m_pCurrentNode = m_pCurrentNode->m_pPrevNode; } if(m_pCurrentNode->m_nNodeID==nSearchNodeID) {bFound=true;} } } } return m_pCurrentNode; }#endif//UNUSED CODE//Search list from head... slower than actually keeping a marker in the list and searching forward or backward//template <class T> // LISTDATA_TYP* LinkedListTemplate<T>::FindNodeInList(long nSearchNodeID)// {// bool bFound = false;// // LISTDATA_TYP* pCurrentNode = m_pHeadNode;// while((pCurrentNode != NULL) && (!bFound))// {// if(pCurrentNode->m_nNodeID == nSearchNodeID) {bFound=true;}// else// {// if(pCurrentNode->m_nNodeID < nSearchNodeID) // pCurrentNode = pCurrentNode->m_pNextNode;// else// pCurrentNode = pCurrentNode->m_pPrevNode;// }// }//// return pCurrentNode;// } Thanks!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:03:11 AM
Hi,
a linked list is fine for fast insertions, but it doesnt say anything about how fast it finds its entries. This depends on
1) if and how you sort your list
2) how you find elements (linear search or whatever)
If insertions should be fast, you should try to sort your list.
On what your list is sorted depends on the usage (e.g. rendering materials -> minimize state changes, texture changes etc.).
Once it is sorted you can either insert elements by e.g. a binary search (divide list in 2 parts, if new element is in upper part divide it again etc.), or, more tricky, let the user of your template insert the element and offer just a method as "insertBeforeLastElement". The user can then iterate through the list (draw all materials) and will decide to where the new element belongs and just insert it.
There''s a lot of literature on this, it''s worth the digging since your game speed will strongly relate on those data management..
- thomas
a linked list is fine for fast insertions, but it doesnt say anything about how fast it finds its entries. This depends on
1) if and how you sort your list
2) how you find elements (linear search or whatever)
If insertions should be fast, you should try to sort your list.
On what your list is sorted depends on the usage (e.g. rendering materials -> minimize state changes, texture changes etc.).
Once it is sorted you can either insert elements by e.g. a binary search (divide list in 2 parts, if new element is in upper part divide it again etc.), or, more tricky, let the user of your template insert the element and offer just a method as "insertBeforeLastElement". The user can then iterate through the list (draw all materials) and will decide to where the new element belongs and just insert it.
There''s a lot of literature on this, it''s worth the digging since your game speed will strongly relate on those data management..
- thomas
Author
quote:
Can template class members be virtual? Thanks!
i guess a better way to phrase this would be:
Can you derive classes from a template class? Any examples (just syntax... pseudo code would be fine)?
Perhaps this violates the need and use of a template...
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:46:55 AM
Hello,
Well, I am using something similar, I am using the STL std::deque thought, not something I wrote, I thought iterating one by one to search for one item would be a pain, so what I did is that I use a Binary search tree, since I do need to iterate each object in the deque to see if it should be drawn or not, the deque is an easy way to do it, however if I want to find an object it might take too much time.
anyway what I do is to have the BSTree keep references to the objects, the object class has in itself an ID, so the tree node struct looks like this:
when I push a new object in the node I imediatly insert a reference to it to the tree (IE Node->Object = (void *) &deque[deque.sixe()-1]
. then when you search the tree you use Node->Object->GetId();
so I use a deque to store objects, and a Binary search tree of references to search for objects.
hope, this will at least give you an idea.
Well, I am using something similar, I am using the STL std::deque thought, not something I wrote, I thought iterating one by one to search for one item would be a pain, so what I did is that I use a Binary search tree, since I do need to iterate each object in the deque to see if it should be drawn or not, the deque is an easy way to do it, however if I want to find an object it might take too much time.
anyway what I do is to have the BSTree keep references to the objects, the object class has in itself an ID, so the tree node struct looks like this:
struct Node{ void *Object; Node *left; Node *right;} when I push a new object in the node I imediatly insert a reference to it to the tree (IE Node->Object = (void *) &deque[deque.sixe()-1]
. then when you search the tree you use Node->Object->GetId();so I use a deque to store objects, and a Binary search tree of references to search for objects.
hope, this will at least give you an idea.
I don''t think so.
Templates are kind of inline functions; their methods are expanded like a macro by the compiler. But you can write a class implementing this template from which you can derive.
- thomas
Templates are kind of inline functions; their methods are expanded like a macro by the compiler. But you can write a class implementing this template from which you can derive.
- thomas
That''s a whole lot of code just for a linked list!
Why are you using void pointers? The whole point of templates is that you can get away from nastiness such as void pointers. And you don''t appear to actually use type ''T'' anywhere.
Apart from that, the code of your list isn''t really the issue. If you need to find things quickly, a list is not the best structure. You''re better going for some sort of sorted structure so you can perform some sort of logarithmic-time search on it.
Why are you using void pointers? The whole point of templates is that you can get away from nastiness such as void pointers. And you don''t appear to actually use type ''T'' anywhere.
Apart from that, the code of your list isn''t really the issue. If you need to find things quickly, a list is not the best structure. You''re better going for some sort of sorted structure so you can perform some sort of logarithmic-time search on it.
Author
Actually, the void* is outside of the template... it's only there in that one return value b/c of the data node structure (i can't seem to get the node code to work if i put the structure inside the template... that was initially what the T type was for).
i have some code that casts the void pointer to type T, but i didn't include it (rather just the void* return).
Additionally, i'm fairly new to this type of stuff
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 3, 2001 9:36:18 AM
i have some code that casts the void pointer to type T, but i didn't include it (rather just the void* return).
Additionally, i'm fairly new to this type of stuff
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 3, 2001 9:36:18 AM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement