Game Development Community

Adding a map class (similar to stl)

by Michael Perry · in Torque Game Engine · 02/13/2007 (11:17 am) · 2 replies

Hey all. As most of us know, stl (standard template library) does not play well with TGE. This isn't much of a problem if you take advantage of the built in container classes, such as LList, or you use a resource to force stl into the engine.

I'd like to avoid the forced method, and attempt to add a new container which I find useful, but isn't in stock TGE: map.

If you need a quick primer, a map works like this:
map<int, char*> errorList;

map[0] = "No Error";
map[1] = "Out of memory";
map[2] = "Unknown error";

cout << map[0] << '\n';

In the template list, the first type defines what key you use for indexing the map, and the second type defines the type of data accessed via []. It's basically a linked list that appears to have non-structure linking...in other words, my code could flow like this:

map<int, char*> errorList;

map[0] = "No Error";
map[48] = "Out of memory";
map[96 = "Unknown error";

cout << map[48] << '\n';

As you can see, this allows storing of values that do not appear to have a linear progression.

While there is a lot more functionality commonly found in your average stl container, I'd like to at least get the basics working first. A lot of the code I have written so far is heavily based off of LList, and I'm (hopefully) at the end where [] access functionality will be in place:

// A single link in the list
// F = KEY, T = DATA 
template <class F, class T> class MapNode
{
public:
	MapNode<T, F> *   Next;
	MapNode<T, F> *   Prev;
	F *            Data;
        T               key;          [b]///< new code[/b]
	MapNode()
	{
		Next = NULL;
		Prev = NULL;
		Data = NULL;
	}
};

The only addition here is the key field, which is used for jumping straight to the entry in the list. My next post will have the actual CMap class.
NextNext Thread
PrevPrevious Thread
More from Torque Game Engine


Employee Michael Perry
ZombieShortbus
#1
02/13/2007 (11:17 am) 
template <class F, class T> class CMap
{
protected:
	MapNode< F,T > *first_entry;
	MapNode< F,T > *last_entry;
	int cnt;

public:
	CMap(){reset();}
	~CMap(){};
	void reset(){first_entry = last_entry = NULL; cnt = 0;}
	T *first(void) const
	{
		if( first_entry ){
			return first_entry->Data;
		}
		else
		{
			return NULL;
		}
	}
	T *last(void) const
	{
		if( last_entry )
		{
			return last_entry->Data;
		}
		else
		{
			return NULL;
		}
	}
	T *next( T* current )
	{
		if( current == NULL )
		{
			return first();
		}

		MapNode<F,T> *next = findNode( current )->Next;
		if( next )
		{
			return next->Data;
		}
		else
		{
			return NULL;
		}
	}
	T *prev( T *current )
	{
		if( current == NULL )
		{
			return last();
		}

		MapNode<F,T> *prev = findNode( current )->Prev;
		if( prev )
		{
			return prev->Data;
		}
		else
		{
			return NULL;
		}
	}
	T *link(F key, T *entry, T *next = NULL)
	{
		MapNode<F,T> *prevNode = NULL;
		MapNode<F,T> *nextNode = findNode( key );
		MapNode<F,T> *newNode = new MapNode<F,T>;

		newNode->Data = entry;
		newNode->key = key;

		if( nextNode == NULL)
		{
			prevNode = last_entry;
			last_entry = newNode;
		}
		else
		{
			prevNode = nextNode->Prev;
			nextNode->Prev = newNode;
		}

		if( prevNode == NULL )
		{
			first_entry = newNode;
		}
		else
		{
			prevNode->Next = newNode;
		}

		newNode->Next = nextNode;
		newNode->Prev = prevNode;

		++cnt;

		return entry;
	}
	T *link(F key, T &entry, T *next = NULL)
	{
		T *newEntry = new T;
		*newEntry = entry;
		
		return link( key, newEntry, next );
	}
	void unlink(F key)
	{
		MapNode<T> *entryNode = findNode( key );
		if( !entryNode ) return;


		if( entryNode->Prev == NULL )
		{
			first_entry = entryNode->Next;
		}
		else
		{
			entryNode->Prev->Next = entryNode->Next;
		}

		if( entryNode->Next == NULL )
		{
			last_entry = entryNode->Prev;
		}
		else
		{
			entryNode->Next->Prev = entryNode->Prev;
		}

		delete entryNode;

		--cnt;
	}
	T * alloc( F key, T *next = NULL )
	{
		T *entry = new T;

		if( entry == NULL )
		{
			return NULL;
		}

		return link( key, entry, next );
	}
	void free(F key)
	{
		unlink(key);
		delete findNode(key);
	}
	void free(void)
	{
		MapNode<F,T> *node = NULL;

		while( (node = iterate( node ) )!=NULL )
		{
			MapNode<F,T> *nodeToKill = node;
			node = node->Prev;
			free( nodeToKill->Data );
		}
	}
	MapNode<F,T> *findNode( F key )
	{
		MapNode<F,T> *it = NULL;
		while( (it = iterate( it ) )!=NULL )
		{
			if( it->Data == key )
			{
				return it;
			}
		}
		return NULL;
	}
	MapNode<F,T> *iterate( MapNode<F,T> *entry = NULL )
	{
		if( entry == NULL ) return first_entry;
		return entry->Next;
	}
	T operator = (T value)
	{
		return value;
	}
	T operator [](F key)
	{
		MapNode<F,T>* entry = findNode(key);
		if (entry == NULL)
		{
			link(key, NULL, NULL);
		}
		return entry->Data;
	}
};

Employee Michael Perry
ZombieShortbus
#2
02/13/2007 (11:18 am)
Problems seem to be stemming up with the last 4 functions, which are findNode, iterate, operator=, and operator[]

As of right now I have a compiler error: left operand must be l-value, when I attempt the following:

CMap<int, char*> list;
	
list[0] = "test";

Any insight or recommendations would be highly appreciated, and as always, thanks in advance...


*EDIT*-Oh and I realize the operator= function is way way way off, that was the last revision of code I made while bombarding the compiler with different solutions. That is more or less where I am stuck at.