• entries
132
99
• views
88774

# Ennui

152 views

So, I'm at home for the holidays, and since my dev machine is a desktop, I am without a suitable developement platform. This, combined with the fact that I can't drink heavily whilst at the parents house, has made me really bored.

I did bring my PS2 home with me and have been playing some Dragon Quest VIII (which is incredible), but I do miss programming.

Solution? Visual C++ 2005 Express Edition!

At first I was going to throw together some snazzy shader demos, eg parallax mapping, but my moms PC sadly uses an onboard graphics chip, so thats out of the question. With little else to do, I decided to make a data structure. Everyone loves data structures, right?

I settled on making my own queue via a circular array. Not nearly as robust as a std::queue, or as thoroughly tested. I wrote up some unit tests which all passed and stopped with that, but I'm sure there are still bugs in there somewhere.

Code:
MyQueue.h
#ifndef MYQUEUE_H#define MYQUEUE_H//@todo: only do this if using visual studio... #ifdef MSVS or something like that#pragma warning(disable:4290) //disable throw spec ignored warningclass MyQueueException;template class MyQueue{public:	MyQueue(unsigned size);	~MyQueue();	T& Front() const throw(MyQueueException);	void Pop() throw(MyQueueException);	void Push(T item) throw(MyQueueException);	bool Empty() const throw();	bool Full() const throw();	unsigned Size() const throw();	unsigned Elements() const throw();private:	T* m_data;	unsigned m_size;	unsigned m_head, m_tail;	unsigned m_elements;};#include "MyQueue.cpp"#endif

MyQueue.cpp
#include #include "MyQueue.h"#include "MyQueueExceptions.h"templateMyQueue::MyQueue(unsigned size) : m_size(size), m_head(0), m_tail(0), m_elements(0){	try	{		m_data = new T[size]; //@bug: new really shouldnt be called from a c-tor...	}	catch (std::bad_alloc) //@bug: this can't really recover gracefully from a bad_alloc, so maybe just let it propagate?	{		m_data = NULL;		m_size = 0;	}}templateMyQueue::~MyQueue(){	delete[] m_data;}templateT& MyQueue::Front() const throw(MyQueueException){	if (Empty())	{		throw MyQueueException(MyQueueException::E_QUEUE_EMPTY, "Front(): Trying to read front of empty queue");	}	assert(m_head < m_size);	return m_data[m_head];}templatevoid MyQueue::Pop() throw(MyQueueException){	if (Empty())	{		throw MyQueueException(MyQueueException::E_QUEUE_EMPTY, "Pop(): Trying to pop from empty queue");	}	m_head = (m_head + 1) % m_size;	--m_elements;}templatevoid MyQueue::Push(T item) throw(MyQueueException){	if(Full())	{		throw MyQueueException(MyQueueException::E_QUEUE_FULL, "Push(): Trying to push onto full queue");	}	assert(m_tail < m_size);	m_data[m_tail] = item;	m_tail = (m_tail + 1) % m_size;	++m_elements;}templatebool MyQueue::Empty() const throw(){	return (m_elements == 0);}templatebool MyQueue::Full() const throw(){	return (m_elements == m_size);}templateunsigned MyQueue::Size() const throw(){	return m_size;}templateunsigned MyQueue::Elements() const throw(){	return m_elements;}

MyQueueExceptions.h
#ifndef MYQUEUE_EXCEPTIONS_H#define MYQUEUE_EXCEPTIONS_H#include class MyQueueException : public std::exception{public:	enum MYQUEUE_EXCEPTION 	{		E_QUEUE_FULL,		E_QUEUE_EMPTY	};		MyQueueException(int e_code, std::string e_what) : m_code(e_code), m_what(e_what) {}	virtual ~MyQueueException() {}	virtual int code() const { return m_code; }	virtual const char* what() const { return m_what.c_str(); }private:	int m_code;	std::string m_what;};

main.cpp (herein lie unit tests of dubious quality)
#include #include #include #include #include "MyQueue.h"#include "MyQueueExceptions.h"void intTest();void ptrTest();int main(){	intTest();	ptrTest();	}void intTest(){	MyQueue<int> queue(10);	for(int i = 0; i < 11; ++i)	{		try		{			std::cout<			queue.Push(i);		}		catch (MyQueueException &e)		{			std::cout<", "<		}	}	for(int i = 0; i < 11; ++i)	{		try		{			std::cout<			queue.Pop();		}		catch (MyQueueException &e)		{			std::cout<", "<		}	}	for(int i = 0; i < 10; ++i)	{		try		{			queue.Push(i);		}		catch (MyQueueException &e)		{			std::cout<", "<		}	}	queue.Pop();	queue.Pop();	std::cout<	queue.Push(10);	queue.Push(11);	try	{		queue.Push(12);	}	catch (MyQueueException &e)	{		std::cout<", "<	}	std::cout<	for(int i = 0; i < 11; ++i)	{		try		{			std::cout<			queue.Pop();		}		catch (MyQueueException &e)		{			std::cout<", "<		}	}}class testclass{public:	std::string m_str;	testclass(std::string str) : m_str(str) {}};void ptrTest(){	std::vector strs;	strs.push_back("this");	strs.push_back("is");	strs.push_back("a");	strs.push_back("test");	strs.push_back("foo");	strs.push_back("bar");	MyQueue q(4);	for(unsigned i = 0; i < q.Size(); ++i)	{		try		{			q.Push(new testclass(strs));		}		catch (MyQueueException &e)		{			std::cout<		}	}		std::cout<	unsigned numElements = q.Elements();	for(unsigned i = 0; i < numElements; ++i)	{		try		{			testclass *tmp = q.Front();			std::cout<m_str<			delete tmp;			q.Pop();		}		catch (MyQueueException &e)		{			std::cout<", "<		}	}	std::cout<}

A few things of note:
I used a raw array to hold the data in the queue. Normally I would have gone with a std::vector, but at that point, it would really be better to use a std::queue to begin with. I also make shallow copies of the data, should they be pointers. The end user is responsible for cleaning up his or her own memory, and not invalidating pointers being held in the queue.

The thing I like about circular arrays is the constant insertion and removal times for items. You'll notice that there is no need to delete or NULL out anything being removed from the queue, you just keep circling round the array overwritting old data as needed. Also, being of fixed size has some advantages. I'll probably use this in my networking library to store reliable UDP messages until I get confirmation that they were received, and should I fill the queue, I can just assume the person on the other end disconnected. The only problem with this plan is that in my net library I need to get at all members of the queue without poping them off one at a time (I want them to remain in the queue). If I do end up using this in my net lib, I'll need to either add iterators or an operator[] overload. I'll likely add both next week for lack of anything better to do.

Comments/Suggestions/Ideas welcome (on this and other projects for me to do while at home).

Edit: Oh, and Merry Christmas.

There are no comments to display.