The usual iostream objects are a kind of iterator. The container in this case is a file. We attach the "iterator" to the file via the open() method. Did you know you could simultaneously open several streams to the same file? If the streams are reading (not writing) this is safe. If one stream is writing, problems may occur as the file changes while being read.
The get() method provides sequential access to the contents of the file, returning the next character with each call. We use the eof() method to detect if we have tried to read past the end of the file and peek() allows us to look at the next char in the file without moving past it. When we are finished with the contents, we close() the file, essentially detaching the iterator from the container.
Iterator classes are developed in conjunction with the container class they are related to. Their implementation is often dependent on the implementaion of the container class, so it is reasonable to give the iterator class access to the private members (implementation details) of the container class. This is usually accomplished through friendship.
____________________________________________________________________
____________________________________________________________________
Focus your attention on the printList function in the driver module. I am convinced that we should change the parameter to a reference to a const object. The reason is that printList should not have to change the List in any way; it is only to display the contents of the list. Try this now (don't forget to change the prototype as well). What error do you get when you build the project?
____________________________________________________________________
____________________________________________________________________
How can we access all the items in the container without modifying the contents? One answer: create an iterator class. This class will have the ability to access the list contents (in a read-only fashion even if the List object is constant) without affecting the List data members. Erase (or comment out) the lines in the body of the printList function - we will replace it with some new code in a few minutes.
Add the header file ListItr.h to the project. It is already found in the project folder. Uncomment the #include statement to Driver.cpp (just above the #include "List.h") for ListItr.h. Build the project. You will get several errors; unfortunately the errors generated by Visual Studio are not very informative. The cause of the error is that the compiler does not recognize what a List is. The ListItr class needs a List object in the constructor. Notice that there is no include for the List header file. Add it to ListItr.h.
Recompile. You should get no errors.
Add the file named ListItr.cpp to the project. It is already
in the project folder. Examine the contents of this file. We must implement
the constructor if we expect to invoke it! I started writing the constructor,
but did not have time to test it. Build the project! What error occurs
and why?
____________________________________________________________________
____________________________________________________________________
____________________________________________________________________
Add this statement to the class definition in List.h:
friend class ListItr;Why will this statement fix the errors encountered above?
____________________________________________________________________
Rebuild - there should be no compile errors! But, there will be a link error! What function must be implemented before we go any further? Hint - read the error message!
____________________________________________________________________
Implement it as a function stub - it does not need to do anything yet! Verify that
the project links successfully.
OK - we now have an iterator object. A List object contains a pointer to a dynamically allocated array of Word objects. Examine the ListItr constructor. When the constructor is finished, does the iterator object contain a copy of the array of Word objects from the original List or does it simply have a pointer to the same array?
____________________________________________________________________
Does the iterator know how many items are present in the original List? ______
The iterator's data member, current, is set to _______ indicating the iterator's current list position is 1.
Remember that this List has legal positions 1 through size+1. However, only positions 1 through size contain real information. Also remember that these position numbers are translated to subscripts 0 through size-1 to determine the location where each element is stored. In the ListItr class, implement the method next. This checks whether current+1 is a legal position. If it is illegal, it does nothing. If current+1 is legal, current is changed to this value.
The cast operator is used to determine if the ListItr's current member is a valid item or not (meaning current is at the end-of-list position). This might be used in code like this: if (!AnItr) cout << "no current value"; The cast should return false if current is illegal and true if the current item is valid. Implement the cast operator.
In printList, write some code to start at the first item of the list and loop through to the last item. Do this using only the ListItr methods (i.e. do not use a counter or the length() of the original List). Suggestion: Use itrL.next(); the cast operator should be useful to halt the loop.
Inside this loop, we want to print the current item specified by the ListItr object. Oops - we will need an access method to do this.
Add a public method to ListItr that will return a const ListElement & (we do not want a copy of the ListElement, just a reference to it). Name the method currValue(void). This should also be a const member function. Implement it in ListItr.cpp. This is a one-liner! Well - it would be if we could count on current being legal. If current is illegal, we want to end the program. This is a bit severe, but it points out the fact that the method was used illegally and the programmer needs to fix the application (not the iterator class). You can use the exit() function (found in stdlib.h) to do this.
Add the statement
cout << itrL.currValue().getWord();to the body of the loop. Test!
Assuming all went well, we have successfully used an iterator to access the contents of a constant List object. One more thing: should the Iterator destructor include the statement, delete[] items;?
Yes or No? _________ Explain!
____________________________________________________________________
____________________________________________________________________
|
|
The left table is in row-major order, the right in column-major order. We will produce our output in column-major order (as it is more difficult)!
Create an overloaded version of printList that takes a second argument: the number of columns desired for output. The prototype and function heading are already in the file. You will need to complete the body of the function. The following instructions should help a lot!
Now - a little math to determine the position of the words that should appear at the top of each column. Suppose the list contains n elements and we want k columns. If k divides n, all columns will contain n/k items. Otherwise, n/k+1 items will appear in each column (except the last). Devise a C++ statement to determine the correct value for max_elts_per_column given n and k. Remember that a%b==0 if b divides evenly into a.
max_elts_per_column = ___________________________________________________________;
Next we must determine the position of the word at the top of each column. Write the formula for the position of the word at the top of column i (where i is one of 0, 1, 2, ..., k-1). Remember the first word in the List is at position 1!
column_top[i] = 1 + _________________________________________//position in list of top word in col i
OK! Time to write some code. Declare the variable, max_elts_per_column, and the array of int's named column_top in the new printList function. The column_top array must be dynamically allocated since we do not know its size (k) until the function is called.
Write the code to determine max_elts_per_column and initialize the elements of the array according to the formulas above. To determine n, look in the List class for a public method.
Build the project and eliminate all compile errors.
We will need a ListItr object for each column. This will require an array of these objects, also dynamically allocated. Try this statement:
ListItr * columnItr = new ListItr[k];Build the project and record the error:
__________________________________________________________________________
This type of allocation requires a default constructor and ListItr does not have such a thing. Change the declaration to the following:
//an array of pointers to ListItr's ListItr ** columnItr = new ListItr *[k];Next, write a loop that creates k ListItr objects (dynamically) and stores their addresses in the columnItr array. You can use the ListItr conversion constructor in the loop. Build and eliminate all errors.
The next step is to get all the iterators pointing to the correct element. Try this loop-de-loop:
for (i=0; i<k; i++) while (--column_top[i]>0) columnItr[i]->next();Now add a loop to print the table:
for (i=0; i<max_elts_per_column; i++){
for (c=0; c<k; c++){
if (*(columnItr[c])){
cout << std::setw(70/k) << columnItr[c]->currValue().getWord();
columnItr[c]->next();
}
}
cout << endl; //get ready for next row
}
All that remains is to deallocate the storage we dynamically allocated
in printList. Do it!
Test! Try different numbers of columns. When everything works, you're almost done.
Look at the getWord method in WFile. This method is not declared as a constant method. Can it be? Try it. Make the method const in the header file and also change the definition of the function in WFile.cpp. What is the first error and what line causes it?
Error:_______________________________________________________________________
Line with error: _______________________________________________________________
Explain what variable is being changed on this line that requires the method to be non-const.
___________________________________________________________________________
Remove the const specifications and save all of your work.
Turn in printed copies ListItr.h, ListItr.cpp, and Driver.cpp stapled to your lab. Be sure your name appears in each file! Clean up!