Part I
Take either the posted solution to assignment 4 or your own solution and modify it so that, when a walk is performed, stored values are returned in ascending numerical order. With this change, your “set” becomes a “sequence” (data values are ordered). Change the class name to “IntSequence”, and call your files “IntSequence.h” and “IntSequence.cpp”. Now that order matters, retrieving the “ith” data value makes sense. Add a member method called “getValue”. It should accept the value of “i” and return the corresponding value. Among other things, this method provides an alternative way of walking through the values in a sequence. The two code snippets below are essentially equivalent.
Snippet #1:
for (valueObtained = sequence.startWalk(value);
valueObtained;
valueObtained = sequence.continueWalk(value)) {
cout << value << "\n";
}
Snippet #2:
for (i = 0; i < sequence.size(); i++) {
cout << sequence.getValue(i) << "\n";
}
Have method “getValue” throw an “out_of_range” exception if the value of “i” is unreasonable.
Two basic approaches are possible. One possibility is to keep the data sorted at all times (i.e. to modify “add” and “remove” so that they always leave the data in its proper order). The other possibility is to keep the data in any old order and to sort it only when necessary (i.e. when a walk is started, or “getValue” is called). You are to use the first approach.
Once you have modified methods “add” and “remove” so that they leave data values in their proper order, and added method “getValue”, you should have a functioning sequence class. Nothing else has to be changed. Your class will not, however, be as efficient as it might be. Consider method “valueExists”, for example. If we know that the data is sorted, we can, at the very least, stop searching when we come across a value that is bigger than the value that we are looking for. And, if we really want to do things properly, we can replace the sequential search with a bisection search.
Methods “operator==”, “intersect”, and “unionWith” can also be made more efficient. While you welcome to make as many improvements as you wish, you are only required to modify method “unionWith” (everything else can be left “as is”). Use the algorithm given below in pseudo-code form. “A” and “B” represent the two input sequences. Initially the output sequence is empty.
start off at the beginning of A and at the beginning of B
while (not at the end of either set) do
if (next value in A == next value in B) then
add next value in A to the end of the output sequence
advance to the next value in A and the next value in B
else if (next value in A < next value in B) then
add next value in A to the end of the output sequence
advance to the next value in A
else
add next value in B to the end of the output sequence
advance to the next value in B
endif
endwhile
while not at the end of A do
add next value in A to the end of the output sequence
advance to next value in A
endwhile
while not at the end of B do
add next value in B to the end of the output sequence
advance to next value in B
endwhile
The algorithm implements a “merge”. Merges of one form or another are common in data processing, and being exposed to the basic idea will certainly do you no harm.
Note that your improved method will be much longer than the original. This isn’t what counts. The important thing is that your new method will do its job in much less time.
Part II
One of the beauties of working with “String2002” objects (instead of working with character arrays) is that overflow is not an issue. This is because String2002 objects automatically increase their capacity as required. Modify your “sequence” class so that it behaves in the same way. You will have to use dynamically allocated array, which in turn requires a destructor, an “operator=” method, and a copy constructor. On the bright side, because overflow is no longer possible, you can forget about throwing “overflow_error” exceptions. Also the destructor, “operator=”, and the copy constructor will be very similar indeed to those in the notes.
The basic idea is pretty straightforward. Whenever it becomes necessary, the capacity of an object should be increased by replacing the original array with a larger one. He basic steps are as follows:
If we’re going to the trouble of expanding an object, it makes sense to increase its capacity by more than one. If an object has just had a value added to it, it is likely that further values will soon be added, and we don’t want to have to increase the capacity each and every time a value is added. Define a constant called “CAPACITY_STEP” and, when the capacity of a sequence needs to be increased, increase the capacity by this amount. Note that, for testing purposes, both the initial capacity of sequences and CAPACITY_STEP should be small. You may find it useful to have a private member function that, if a sequence is full, increases its capacity by CAPACITY_STEP.
Assignment is something of a special case in that there is no need to preserve original data values and, if the capacity of a sequence needs to be increased, there is an obvious choice. If the sequence being assigned to lacks sufficient capacity, its capacity should be made equal to the number of values in the other sequence. Otherwise its capacity should not be changed.
Notes
A test program has been supplied. Apart from name changes, it differs from the test program for assignment #4 only in that provision is made for testing method “getValue”.
Do not submit your Part I solution. Submit only in your final solution (parts I and II together), i.e. your final files “IntSequence.h” and “IntSequence.cpp”. Your solution must use dynamically allocated arrays.
Updated: Tuesday, February 3rd, 2009.