Sign in to follow this  
  • entries
    132
  • comments
    99
  • views
    88599

Ennui

Sign in to follow this  
Driv3MeFar

134 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 warning

class 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"

template
MyQueue::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;
}
}

template
MyQueue::~MyQueue()
{
delete[] m_data;
}

template
T& 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];
}

template
void 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;
}

template
void 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;
}

template
bool MyQueue::Empty() const throw()
{
return (m_elements == 0);
}

template
bool MyQueue::Full() const throw()
{
return (m_elements == m_size);
}

template
unsigned MyQueue::Size() const throw()
{
return m_size;
}

template
unsigned 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.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now