Hi, zeus48-ga:
In implementing the template class Priorityqueue, I see one basic
point that we need to resolve, a difference (perhaps) in our
interpretation of the "ordering" of the queues' priorities.
The header file uses the word HIGHEST to denote 10, or the last of the
queue array entries. While one might interpret this to mean only
"highest index", my suspicion was that as this index is labelled
"priority" in terms of the class's interface for insertions, the most
likely possibility is that the higher the index, the higher the
priority.
Therefore the output from my program, running the test cases you
designed, differs from the output that you anticipated precisely in
that the call to get_front returns 11 rather than 23.
It is a minor point; the change to the code to order the priorities
oppositely would be trivial. We just need to agree on which direction
is correct (and, of course, whatever you think is by definition
correct, despite my "initiative").
Let's begin with the files, so you can copy them down for your own
testing. I can then do some comments, clarifications, etc.
>>>>>>>>>>>> BEGIN priorityqueue.h >>>>>>>>>>>>>>>
#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H
#include <stdlib.h>
#include <queue>
#include <iostream>
#include <assert.h>
using namespace std;
template <class Item>
class Priorityqueue
{
public:
enum {HIGHEST = 10};
Priorityqueue();
void insert (const Item& entry, unsigned int priority);
Item get_front();
size_t size() const;
bool is_empty() const;
private:
queue<Item> queues [HIGHEST + 1];
};
#include "priorityqueue.inc"
#endif
<<<<<<<<<<<<< END OF priorityqueue.h <<<<<<<<<<<<<<<<
>>>>>>>>>>>>> BEGIN priorityqueue.inc >>>>>>>>>>>>>>>
// definitions of template methods go here
// first, the "empty" constructor
template<class Item>
Priorityqueue<Item>::Priorityqueue()
: queues()
{
}
template<class Item>
void Priorityqueue<Item>::insert(
const Item& entry,
unsigned int priority)
{
// assume priority is valid
assert(priority <= HIGHEST);
/* insert copy of entry as last
element at given priority */
queues[priority].push(entry);
}
template<class Item>
Item Priorityqueue<Item>::get_front()
{
/* caller must ensure Priorityqueue
contains an Item, e.g. !empty ;
otherwise behavior is undefined */
Item entry;
int i;
for(i = HIGHEST; i >= 0; i--)
{
if( ! queues[i].empty() )
{
entry = queues[i].front();
queues[i].pop();
return entry;
}
}
// assume some queue was nonempty
assert( i >= 0 );
}
template<class Item>
size_t Priorityqueue<Item>::size() const
{
// total size from each queue
size_t n = 0;
for(int i = 0; i <= HIGHEST; i++)
{
n += queues[i].size();
}
return n;
}
template<class Item>
bool Priorityqueue<Item>::is_empty() const
{
// check for a nonempty queue
bool b = true;
for(int i = 0; i <= HIGHEST; i++)
{
if ( ! queues[i].empty() )
{
b = false;
break;
}
}
return b;
}
<<<<<<<<<<<<<<< END OF priorityqueue.inc <<<<<<<<<<<
>>>>>>>>>>>>>>> BEGIN zeusQueue.cpp >>>>>>>>>>>>>>>>
// Exclude rarely-used stuff from Windows headers
#define WIN32_LEAN_AND_MEAN
#include <stdio.h>
// #include <tchar.h>
#include "priorityqueue.h"
int main(int argc, char* argv[])
{
Priorityqueue<int> pqueue;
// with something like this hard coded
pqueue.insert (23,1);
pqueue.insert (36,2);
cout << pqueue.size() << '\n';
pqueue.insert (76,3);
pqueue.insert (11,4);
cout << pqueue.get_front() << '\n';
pqueue.insert (34,6);
pqueue.insert (67,5);
cout << pqueue.size() << '\n';
return 0;
}
<<<<<<<<<<<<<<< END OF zeusQueue.cpp <<<<<<<<<<<
Notes:
(1) I changed the name of the included file priorityqueue.tem to
priorityqueue.inc, because this is more consistent with the Visual
Studio IDE. The header file and this included/template file can both
be "added" as Header Files to the project you want to build there
(allowing VS to recognize what needs to be rebuilt if changes are made
in one place or the other).
(2) The output statements I implemented are rudimentary and can
easily be modified to match the text you used in the "sample output",
but I thought it would be more expeditious to give you this working
version so we can iron out more substantive issues quickly.
(3) The implementation is quite lean. I used asserts in the couple
of ways we discussed earlier, but made no further efforts to trap
incorrect assumptions. We could certainly add a test for
pqueue.empty() to the test program ahead of pqueue.get_front(). Also
note that the interface does not allow us to know _what_ priority an
entry was listed at prior to being "popped" from the top of the
priority queue. It was not possible in the amount of time to do a
thorough job of considering the design from the standpoint of memory
management, as one would assuredly want to do for production quality
code.
(4) I anticipate that you will have a lot of questions about the
program and how it works. Despite the brevity of the code, there are
actually a number of trenchant points about how the code is written.
But let's get the program compiled and working on your end and then
worry about that. I made the main program "simple" in the way one
would write a UNIX console program, and the way the #include <tchar.h>
line is commented out hints at this. Let me know if you have any
problems "recreating" the project from these text files; I can zip up
the entire VS directory and put it out on the 'Net if need be.
regards, mathtalk-ga |
Clarification of Answer by
mathtalk-ga
on
11 Dec 2002 19:49 PST
Yes, I got too tricky with the coding on get_front. The quick fix is
to add:
return entry;
to the bottom of the routine, just to make the compiler happy that
"if" we fall through to there, the routine has a return value. Of
course we should never get there, but the assert should be stated
differently, i.e. assert(false), to reflect that.
Congratulations on getting the program to work on your platform, and
let me know if I can be of assistance.
Thanks for rating my answer (and for the handsome tip!). After
working on it for so many hours, the feedback means a lot!
regards, mathtalk-ga
|
