HW2a - Subclassing the PQueue class

Subclass PQExt of class PQueue Steps to take:

Determine what the PQueue class is doing. It provides a container for objects of any kind. How are the objects stored? Actually the objects are not stored in the container - only pointers to the objects are stored.
Come up with ideas for determining the maximum object. One idea is to run through all the stored objects, checking the value of each, and output a pointer to the object of highest value. Evaluate this idea: it takes O(n) time. Can this be improved? Consider when the maximum value object changes. Certainly when an object is removed, the maximum value object does not change unless the container becomes empty in which case there is no such object. When an object is inserted, the maximum value object changes if the inserted object has value greater than the current maximum value object. Under no other circumstances does the maximum value object change. These ideas suggest the following solution: maintain a variable, call it themax, which is a pointer to container objects. The value of that variable will be the address of the current maximum value object. When findmax is invoked, the value of themax will be returned - this takes O(1) time which is much faster than the first idea. The only question is how to update themax according to the discussion earlier.
Here are some ideas. On a call to remove, themax can be set to NULL if the container is empty. On a call to insert(theobject), themax should be set to point to theobject if the value of themax's object is less than the value of theobject's object. Actually it is unnecessary to modify remove - just add a test for an empty container in insert - if the container is empty then certainly theobject will be the new themax.
Write code.
- themax: We need to declare this variable. It is a pointer to a container object. Hence
```
       void *themax;
```
- findmax: What is the input to findmax? nothing. What is the output of findmax? a pointer to a container object. All pointers to container objects are of type void* so we start with:
```
        void *findmax() {
        ....
        }
```
  Now we need to fill in the ..... We would like to just say
```
        return themax;
```
  but we are required to return a -1 if the container is empty. So we need to add a test like this one:
```
        if (themax == NULL) ...
```
  But this is a little awkward because it requires changing the remove method. So we might want to change this to
```
        if (empty()) ...
```
  So what is ...? Well, the output needs to be of type void* but the value we need to output is -1. So we need to cast the -1 as a void* like this:
```
        return (void*)-1;
```
  The only problem with this is that hw2a.cc as provided is not compatible because it does this: *(int*)lst->findmax(). So we use
```
        return (void*)new int(-1); instead.
```
- insert: When an object is inserted it must be checked against the existing themax to see which is larger. If the container is empty themax gets to point to theobject. So the test is
```
        if (empty() || valfn(themax) < valfn(theobject)) ...
```
  What is ...? Well, all we need to do is have themax point to theobject. Here is how to do it:
```
        themax = theobject;
```
- Other considerations: For this problem int objects are stored. The value of an int object is the same as its priority (this homework is a very simple example - usually the priority is a complicated function of the contained objects). Thus, we need to write a value function that returns long and takes a void* as input. Here is an example:
```
        long val(void *object) { return (long)*(int*)object;  }
```
  The object is a pointer to void so it needs to be cast to (int*). Then that pointer needs to be dereferenced to get the value of the object: thus *(int*)object. Then that needs to be cast to long to return a type as specified by the prototype: thus, (long)*(int*)object. The val function becomes an argument to the constructor of the PQExt class:
```
        PQExt *pqe = new PQExt(val);
```
  which means a constructor for the PQExt class has to be written. This will do:
```
        PQExt::PQExt (long (*v)(void*)) : PQueue(v, NULL) { }
```
  It is important for you to struggle with this and master it.