Thread: C++ Guided Design Programming Challenge

I'll start:

Code:

class CQueue
{
public:
     // other methods
     int       GetCount()			{ return count; }
     bool	IsEmpty();

private:
     // other vars
     int       count;
};

bool CQueue::IsEmpty()
{
	bool empty;

	if(count)
		empty = false;
	else
		empty = true;

	return empty;
}

As you can no doubt tell the count variable will be incremented per push and decremented per pop, for whatever reason the user might want to know how many objects are in the queue, so GetCount simply returns count, and IsEmpty() will return true if queue is empty (i.e. count is 0), count should be set to 0 in CQueue's constructor.

I took the easy ones, I hope that's what you're looking for.

Okay, good start, but an easier way to phrase it would be:

Code:

bool CQueue::IsEmpty()
{
 return count == 0;
}

How would you implement IsFull() then?

Well it depends how we're controlling the maximum, if it's just a variable then just return true if count == max, false otherwise.

Btw I didn't know you could return like that from IsEmpty(), that's cool.

Originally posted by HybridM
Btw I didn't know you could return like that from IsEmpty(), that's cool.

return (count == 0); would probably be easier to read. Basically (count == 0) can either be true or false which will then be returned by return bool;

Code:

class CQueue
{
  public:
    CQueue()			{ count= 0; count_max= 0; };

    // other methods
    int		GetCount()	{ return count; };
    bool	IsEmpty()	{ return (count == 0); };
    bool	IsFull()	{ return (count == count_max); };

  private:
    // other vars
    int	count;
    int	count_max; 	
};

Maybe add a non default constructor for limited size?

Okay, so what is the underlying data structure going to be, then?

How would you implement Pop(), provided it was implemented:

1) on a list?

2) on an array?

Actually, I think we have not decided about this yet. Maybe it's Cat's turn to say something

On a sidenote, my personal opinion is that push and pop are definetly the wrong names. This is not a stack where something can be pushed into and all previous elements will change their "position" in the stack (i.e. one rank up), where stuff get's pushed in and popped out at the same "side", this is a queue where data get's added to the end and taken from the beginning. (At least if I understood the excercise )

Try to push somebody at the end of a reallife queue. Could be funny. For a second or two...

OK, feel free to use something else, but this is how I implemented Pop in my queue, I called it "Serve()" as it fits the queue theme better.

Code:

int CQueue::Serve(bool Remove)
{
	int Value;
	Node *Temp;

	if(!IsEmpty())
	{
		Value = Front->GetData();
		if(Remove)
		{
			--count;
			Temp = Front;
			if(count)
			{
				Front = Front->Next;
			}
			delete Temp;
		}
	}
	else
		cout << "Unable to serve, queue is empty." << endl;

	return Value;
}

This may need some explanation, so here goes...
The Remove boolean is there so the user can choose whether they wish to peek at the front of the queue (not remove) or remove as well as get value.

A temporary Node is created so as to allow memory deallocation, value is assigned the data of the front node, so as to be returned, front is assigned to the node behind it, unless it is the last node in the queue. What used to be the front is then deleted through temp, and value is returned.

I think that's all

It would also be nice to have two (or more) different threads for this project: one for software engineers who just want to post the code and be done with everything, and one for those that want to learn something and maybe go at a slower pace.

On a sidenote, my personal opinion is that push and pop are definetly the wrong names.

Agreed.

I think a forum is a difficult medium to conduct something like this, someone should do a simple website where people can submit their ideas, perhaps cat (or someone else if cat doesn't have the time) could screen them and launch votes to decide which we go with. On the same page we could also keep an up to date version of the project so far.

It could be very cool, and could set cprogramming.com apart from the plethora of other boards.

Originally posted by HybridM
It could be very cool, and could set cprogramming.com apart from the plethora of other boards.

You mean like defining new standards, reaching out for new worlds ...errr..?

The topic was "C++ Guided Design Programming Challenge" and I think we should stick to that. If Cat's project is successful, it can still be extended.

You mean like defining new standards, reaching out for new worlds ...errr..?

Hmm..no.

What I meant was it would make the whole experience easier for everyone and overall more enjoyable. It was a suggestion for if this sort of thing becomes regular.

Good work, 7Stud. Some additional thoughts, too:

1) By default, the queue should have no maximum size. Allow this to be reversable, such that a user can set a limit, unset it, set it, ad infinitum.

2) Exceptions are for more serious errors than full/empty queues.
For these cases, either let the user crash, as happens with normal user errors (ie: out-of-bounds accesses, etc) OR simply have the ADT exhibit 'no-op' behaviour (ie: nothing happens at all).

Let's say the user tries to get_front(), but the queue is empty.
To implement the first sort of behaviour (crash 'n burn), just return a temporary object. Otherwise, the queue has a member of type T called 'dummy' that get's returned when that happens, and no harm is done.


>> Do we need a non-default destructor?

Absolutely, how else can we guarantee proper cleanup?

I'm down with the limitable infinite queue now. I was working on a static_queue, where the storage would be a compile-time constant array, but getting it to be faster than deque is going to be more work than I expected, and insuring proper alignment for placement new (without resorting to boost) is more awkward than I want to deal with right now. If you're interested in where I was going with this have a look at boost's optional class, very clever way to get the space for an object and delay constructing it until absolutely necessary.

As to the general issue of throwing, I look at this as a question of how bad would ignoring the issue be? The standard streams have all sorts of things that they want to tell you, no-one pays any attention to them. How many threads have we seen where the problem is that the file was never opened in the first place(it was in another directory etc..)? You shouldn't rely on exceptions as the normal way of discovering that a queue is full, but it might be a good way to encourage users to check first. It does add a lot of bloat, not just for the throw, but often checking the same thing twice, once before the call and in the method just before you do anything. I can also sympathize with the view that if you wanted this sort of safety you would be using Ada.

I've confused the matter enough, here's my candidate for a final interface.

Code:

template<class T>
class queue {
public:
    typedef T value_type;     // comes in handy
    typedef size_t size_type; // future-proofing, clarity
   
    queue();          // infinite
    queue(size_type); // limited

    bool limited() const;    // true iff limit exists.
    void unlimit();          // removes any limit.
    void limit(size_type);   // sets new maximum number of elements
    size_type limit() const; // maximum number of elements if limited,
                             // numeric_limits<size_type>.max() if unlimited
    size_type size() const;  // number of elements in queue
    bool empty() const;      // size() == 0
    bool full() const;       // limited() && size() == limit()

    bool append(const T &); // no-ops & returns false if full.
    void discard();         // removes oldest element.
    T & oldest();           // access oldest element, undefined if empty
};

I've gone with limit, as opposed to capacity, as capacity already has semantics in the stl, and our behavior is different. front also has semantics in stl, that matches our behavior here, but if we want to use front it should probably be just front (not get_front) to match the stl and discard_front should also probably be pop_front for the same reasons. However, we can't use push_back because we are very different from the stl here, so append is the logical choice. Once append is used it makes sense to define our own words for access and removal.

There is one more outstanding issue. What should happen if we limit a queue to have fewer elements than it already has? I think that we should probably remove the most recently added elements until we are under the new limit, the users can remove the oldest themselves.

good summary 7Stud, even if I did pick a lot of nits, I just like arguing these things.