Note that this assignment was modified today in class, and the description below includes that modification.  You should turn in one program -- the correctly debugged, templated version of Assignment29.zip which we worked on in class today.  Good luck.

DK

Question 1:  Study the code in Assignment29.zip to prepare for a quiz later this week on Tree-based Priority Queues.

Question 2a:  Debug the code in Assignment29.zip.  Turn in the debugged code as part of your submission for Question 2b below.

Question 2b:

The Priority Queue which you created in Assignment 28 only worked for apstring's.  Our choices for making it work for other types (such as integers, char's, arbitrary classes, etc) are somewhat limited.  We could turn off type checking altogether by storing the value as a void*, but this is clumsy (due to all the casting required) and, worse, quite dangerous (since you could cast, say, an integer* through a void* and into, say, an apstring*, and you can imagine the havoc which will ensue when you dereference that supposed apstring* -- can you say "CRASH"?).  Bad idea.  So we could make PriorityQueue an abstract class and subclass it for each type, as in IntegerPriorityQueue and ApstringPriorityQueue. While this works, it is still clumsy, and it does not work for arbitrary classes which we have not see.  Huh?  Say you did it this way, then shipped your work as a library which someone else used, only they create a class called Lemur (don't ask) and they want a PriorityQueue of Lemurs.  They can't do it.  Bummer.  So custom subclasses is another bad idea.  What, then, might be the answer...?

Enter TEMPLATES.  By templating your PriorityQueue class, it can be used over arbitrary types, even Lemurs.  So while templates are a bit arcane to deal with, they do elegantly solve a nagging problem.  They also appear on the AP exam.  Two good reasons to learn about them!

So here we shall do just that.  Your task is to rewrite your PriorityQueue class from last assignment the code in Assignment29.zip so that it now is template-based.  If you are unsure of how to do this, study the template-based AP classes (such as apstack, apqueue, apvector, apmatrix).  They are good examples of how to make a template-based C++ class.

As for testing your program, it should work just as on Assignment 28 except first you should input one character:  "i" means integer and "s" means apstring.  If the input is "s", then create a PriorityQueue<apstring> and match the output from Assignment 28 precisely.  If the input is "i", create a PriorityQueue<int> and match the output from Assignment 28 except that instead of strings the values will themselves be integers.  Note that you must share code for the two cases (string or integer) as much as possible.

Good luck.

DK