20ECES228001  Data Structures  Fall 2007 


Due: October 5, 2007
Submit source code implementing the extended pqueue class and solution to
the powers problem to xxxxx@email.uc.edu
Rationale:
You will exercise your understanding of the implementation of ordered lists called Priority Queues using arrays. You will use a Stack ADT to solve a fundamental computational problem: finding positive integer X raised to the power Y where Y is a positive integer. 
Homework Problems:

A PQueue object is a container for any type of object having
some defineable notion of "value". A user of the PQueue
class defines a value function and passes it as an argument to the
PQueue constructor upon object creation. The value function
takes a pointer to an object as input. Its output is a long
representing the value of input object.
Objects may be inserted into a PQueue container using the method void insert(void *object);Objects may be removed from a PQueue container using the method void *remove(); // Return value is a pointer to the removed objectWhen remove() is invoked, the object of lowest value in the container is removed and returned. The final method available in this class is the following bool empty();which returns true if and only if the container is empty. Example: The following sample hw2a.cc file: #include <iostream> #include "pqueue.h" using namespace std; long val (void *object) { return (long)*(int*)object; } int main () { PQueue *lst = new PQueue(val); lst>insert(new int(34)); lst>insert(new int(12)); lst>insert(new int(9)); lst>insert(new int(22)); lst>insert(new int(55)); lst>insert(new int(2)); lst>insert(new int(3)); lst>insert(new int(16)); cout << *(int*)(lst>remove()) << " " << *(int*)(lst>remove()) << " " << *(int*)(lst>remove()) << "\n"; }outputs the numbers 2, 3, 9 when linked to pqueue.o. 
Implementation details of PQueue:
A PQueue container has one array: objects of type
void*[], each element of which is a pointer to a contained
object. The arrangement of objects in objects after
insertion and removal operations has the following properties: 1) all
contained objects are pointed to by elements objects[0] to
objects[n1] where n is the number of contained
objects and n < size; 2) for any i from
0 to n1, if 2*i+1 < n then
valfn(objects[i] < valfn(objects[2*i+1]) and if
2*i+2 < n then valfn(objects[i]) <
valfn(objects[2*i+2]).
For example, the following array values satisfy the above (the number
on the extreme left is valfn(objects[0])):
5 23 13 25 67 14 15 33 78 70 16 
Build, say hw2a.cc as above. Be sure to include
pqueue.h. Compile using the following:
g++ Wall c pqueue.cc g++ Wall c hw2a.cc g++ Wall hw2a.o pqueue.o o hw2athen run hw2a. 
Given a positive number X and a positive integer Y,
compute X raised to the Y power in a very small amount
of time (log(Y) multiplications maximum).
Example: 8 raised to the power 5 is 32768. Method:
input: A positive number X and a positive integer Y 1. Create stack S. 2. While Y is greater than 1 do the following: 2a. Push Y mod 2 onto S. 2b. Y := Y div 2. 3. P := X. 4. While S is not empty do the following: 4a. P := P*P. 4b. Pop S and put the result in Z. 4b. If Z=1 then P := P*X. 5. Return P. 
Services provided by the Stack class:
// Example of a display function with prototype matching the type // that is understood by the Stack class void displayfunc (void *object) { cout << *(int*)object << " "; } ... Stack *stack = new Stack(displayfunc); // Creates a new stack object Stack *stack = new Stack(NULL); // Also possible  no display expected ... stack>push(new int(10)); // Push an object onto the stack (example) ... int *a = (int*)stack>pop(); // Pop and return an object (example) ... int *b = (int*)stack>peek(); // Only look at the top stack object (example) ... if (!stack>empty())... // Test whether the stack is empty 
Services provided by Big Integer functions:
All big integers are merely character strings of arbitrary length
where each character is an ascii counterpart to a digit from 09.
Negative numbers are not implemented (OK, so they should be called big
nonnegative integers). The following are examples of their use as
provided by the functions in bigint.cc:
char *n = toBigInt(6754); // turns the int 6754 into a string "6754" ... char *m = addBigInt(n,"654"); // adds two big integers ... char *p = multiplyBigInt(m, n); // multiplies two big integers 
Using bigint.cc and stacker.cc:
Create a file called power.cc and add a Power class
to that file. The class has only the null constructor and one method
of two arguments with the following protoype:
char *pow (int x, int y);The homework assignment is to code this method to return x raised to the power y. Create power.h accordingly. The following file, named hw2b.cc, shows how to use the Power class: #include <iostream> #include "power.h" using namespace std; int main (int argc, char **argv) { if (argc != 3) { cerr << "Usage: " << argv[0] << "When invoked with the command line hw2b 453 23 the result is 453**23 = 12310016818803551465696882268112889772096056731865941383954477 To compile use the following: g++ Wall c hw2b.cc g++ Wall c stacker.cc g++ Wall c bigint.cc g++ Wall c power.cc g++ Wall hw2b.o stacker.o bigint.o power.o o hw2b 