5.4 HOMEWORK

With a C++ class Pet defined as
```
     class Pet {         string name;         int age;     public:         Pet( string n, int a ) : name( n ), age( a ) {}     }; 
```
three out of the nine main's shown below do not compile. (The six others compile and run fine.) Identify the ones that do not compile and give reasons for why that is the case.
1. int main() { Pet pets [3]; }
2. int main() { Pet* pets [3]; }
3. int main() { vector<Pet> pets; }
4. int main() { vector<Pet> pets(3); }
5. int main() { vector<Pet*> pets; }
6. int main() { vector<Pet*> pets(3); }
7. int main() { list<Pet> pets(3); }
8. int main() { list<Pet> pets; }
9. int main() { list<Pet*> pets; }
Assume that all the needed library header files are included in the programs for the testing of the main's shown

The class X in the following program is supplied with a destructor in line (A). Whenever this destructor is invoked, it lets us know by printing out the message shown in the body of the destructor. In main, we first construct an empty vector in line (B) for holding objects of type X. We then construct three objects of type X in lines (C) through (E) and push them into the vector in lines (F) through (H). When this program is compiled and run, it produces the following output

     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 2     Destructor invoked for X object with p = 3     Destructor invoked for X object with p = 2     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 2     Destructor invoked for X object with p = 3

Explain this output. Explain especially why for object x1 the destructor is invoked four times, for object x2 three times, and for object x3 only two times. Here is the program:

 
 //VectorDest.cc #include <iostream> #include <vector> class X {     int p; public:     //constructor:     X( int q ) { p = q; }     //destructor:     ~X() {                                                                  //(A)        cout << "Destructor invoked for X object with p = " << p << endl; }     }; int main() {     vector<X> vec;                                                          //(B)     X x1( 1 );                                                              //(C)     X x2( 2 );                                                              //(D)     X x3( 3 );                                                              //(E)     vec.push_back( x1 );                                                    //(F)     vec.push_back( x2 );                                                    //(G)     vec.push_back( x3 );                                                    //(H)     return 0; }

The following program is a slight variation on the program of the previous problem. The class X is now supplied with an additional function, changeState () in line (A). In main we do the same thing as before, except that we also change the state of each of the three objects created before the program is allowed to run to completion. This program produces the following output:

     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 2     Destructor invoked for X object with p = 300     Destructor invoked for X object with p = 200     Destructor invoked for X object with p = 100     Destructor invoked for X object with p = 1     Destructor invoked for X object with p = 2     Destructor invoked for X object with p = 3

Explain this output. Explain especially the order in which the three objects created in main, x1, x2, and x3, are destroyed and the order in which the copies of the objects held by the vector are destroyed.

 
 //VectorDestOrder.cc #include <iostream> #include <vector> class X {     int p; public:           X( int q ) { p = q; }      void changeState( int pp ) { p = pp; }           //(A)      ~X(){ cout << "Destructor invoked for X object with p = "            << p << endl; } }; int main() {     vector<X> vec;     X x1( 1 );     X x2( 2 );     X x3( 3 );     vec.push_back( x1 );     vec.push_back( x2 );     vec.push_back( x3 );     x1.changeState(100);     x2.changeState(200);     x3.changeState(300);     return 0; }

What's wrong with the following program:

     #include <iostream>     #include <vector>     int main()     {         vector<string> wordVec;         vector<string>::iterator p = wordVec.begin();         wordVec.push_back("apples");         wordVec.push_back("oranges");         while ( p != wordVec.end() )             cout << *p++ << endl;     }

The goal of this Java homework is to get you to appreciate the fail-fast property of the iterator defined for a List. Say you are scanning a list, item by item, and as you do so you wish to remove some of the items from the list. Removal of items will cause structural modifications to the list. In general, such structural modifications to a list as it is being iterated through can cause the iterator to exhibit nondeterministic program behavior. To protect a program against such problems (which can also happen when one thread is iterating through a list while another thread is modifying the list), Java makes the list iterator fail-fast. What that means is that if a method detects that a list is being modified structurally as it is being iterated through, the method will throw a ConcurrentModificationException. This also applies to the other containers that support iterators in the Java Collections Framework.

Write a Java class PruneList that does the following:
1. The class should require two command line arguments for its invocation. That is, the class would be invoked by a command line like
```
     Java PruneList filename 30 
```
  where the first argument, filename, is the name of the file containing an arbitrary number of integers in one or multiple lines. The second argument, in this case 30, is a threshold value to be used for pruning the integer data.
2. Read the integers from the file named as described above into an ArrayList.
  
  Suggestion: You could construct a BufferedReader stream and invoke its readLine () method to pull into your program each line of the data file at a time. You could then deploy the StringTokenizer class as shown below to extract the individual integers and stuff them into an ArrayList as shown below:
```
     FileReader fr = new FileReader( args[0] );     BufferedReader br = new BufferedReader(fr);     ArrayList list = new ArrayList ();     String line;     while ((line = br.readLine ()) != null){         StringTokenizer st = new StringTokenizer(line);         while(st.hasMoreTokens ()) {             list.add(new Integer(st.nextToken()));         }     } 
```
3. Sort the ArrayList container by invoking Collections.sort. (Sorting is not essential to the main goal of this homework. This step is included only because it makes it easier to see the result and to verify that the program is working correctly.)
4. Iterate through the ArrayList and remove from the list all items whose value exceeds the threshold specified by the command line in (a) above.
5. Print out the ArrayList before and after the removal of the items.
There are potentially two different ways of removing the items that meet the condition mentioned in (d) above. You could invoke the method remove( int index ) defined directly for the ArrayList, or you could invoke the method remove() defined for the ListIterator class. However, the former will cause the ConcurrentModificationException to be thrown for reasons mentioned at the beginning of this homework problem. On the other hand, the latter approach will work just fine. Experiment with both approaches.
The goal of this homework^[22] is to get you to understand some of the subtleties involved in the use of the generic library remove_if function for removing elements from a C++ sequence container. This function removes all elements for which a certain predicate is true, but not really. What it does is that all such elements are taken out of their existing locations, the remaining elements shuffled toward the beginning of the container, and then the "removed" elements placed at the end of the container, in the same order in which they existed originally in the container. So the overall size of the container remains unchanged. At the same time, the function returns the iterator pointing to the beginning of the section of the container where the "removed" elements were placed. If desired, this iterator value can be used to actually erase the "removed" elements, shrinking the size of the container.

Write a C++ program to do the following:
1. Write a C++ program, PruneList.cc, that requires two command-line arguments, one for the file containing formatted integer data and the other for an integer value to be used as a threshold in the manner described below. There can be an arbitrary number of integers in the named data file, in an arbitrary number of lines.
2. Establish an input file stream to read all the integers in the named file into a vector<int> container.
3. Sort the vector using the generic library sort. (This step is not essential to the main goals of this homework. It is included merely because it makes it easier to see the results and to visually verify that the program is working correctly.)
4. Display on your terminal the items in the vector by using the copy function from the generic library in the following manner:
```
     copy( vec.begin(), vec.end(),                   ostream_iterator<int>( cout, " " ) ); 
```
  where vec is the vector<int> object into which you read all of the integers from the data file.
5. Your program should use remove_if to eliminate each item from the vector vec whose value exceeds the threshold supplied as the second command-line argument in (a) above. This function takes three arguments, the first and the second being the beginning and the ending iterator values for that part of the container where the removal operations are to be conducted. In our case, these arguments can simply be vec.begin() and vec.end(). The third argument supplies the decision criterion for the removal of elements. The simplest possible call to remove_if will look like
```
     remove_if( vec.begin(), vec.end(), 30 ); 
```
  This will cause all elements that equal the value 30 to be moved to the end of the container. Obviously, this call will not work for us since we want all elements that are equal to or greater than a threshold to be removed. This can be done by supplying a function object for the third argument. Here is a possible definition for such a function object:
```
 template<class Arg> struct ThresholdCheck                                : public unary_function<Arg, bool> {     int threshold;     //constructor:     ThresholdCheck( int thresh ) : threshold( thresh ) {};     bool operator() (const Arg& x) { return x >= threshold ?                                              true : false; } }; 
```
  The class ThresholdCheck, defined as a templatized struct, is derived from the base class unary_function defined in the functional header file. The two template parameters supplied to the base class are for the argument type needed by the overloading of the ‘()' operator and for the result type returned by this operator. In our case, the overload definition for the ‘()' operator defines a predicate for comparing each vector element against the threshold.
6. With the function object defined as above, you can now invoke remove_if in the following manner:
```
      vector<int>::iterator result =          remove_if( vec.begin(), vec.end(),                             ThresholdCheck<int>( 50 ) ); 
```
  if you want 50 to be the decision threshold for the removal of the vector elements.
7. As mentioned before, remove_if does not actually remove the elements from the container; it just moves to the end of the container. To get rid of these elements altogether (and to thus shrink the size of the container) you must invoke the erase() function on the vector using the iterator returned by remove_if:
```
      vec.erase( result, vec.end() ); 
```
8. Display the resulting vector.
Section 5.1.7 showed a C++ program that used a map container to efficiently construct a word histogram for a text file. Implied in that program was the fact that the container kept the <key, value> pairs of the histogram in a sorted ascending order by using the ‘<' operator defined for the string type. This comparison operator carries out a character-by-character comparison of two strings using their ASCII codes. This causes the histogram to create separate counts for the same two words if one has upper case letters in it.

The goal^[23] of this homework is to modify the earlier program to create a case-insensitive word histogram for a test file. This can be done by incorporating a user-defined comparison function object in the map declaration:
```
      map<string, int, Nocase> hist; 
```
where Nocase is a class that defines a user-defined comparison function for the keys through the overloading of the ‘()' operator.
Modify the Java class WordHistogram of Section 5.2.3 so that it displays the words in the decreasing order of the frequencies associated with the words.
This is a problem in the run-time resizing of C++ vectors. In what follows, we first provide the reader with an example from Stroustrup [54] that shows why you'd want to invoke the resize method on a vector at run time to increase its size (as opposed to just using the push_back operation to let the size grow one element at a time). This homework problem consists of writing code for the example presented.

Let's say we have a data source that is producing a stream of non-negative integers continuously. Our goal is to make a histogram of these integers and to keep this histogram continually updated as new integers arrive. To remind the reader about histogramming, suppose at some point in time the integers output by the stream were
```
     3 0 2 1 1 0 1 0 1 2 3 1 
```
our histogram would need to contain four bins. If we used an array to represent the histogram, we could declare the array as
```
     int hist [4] = {0}; 
```
For the integer stream shown above, the state of the histogram after that data was read would be
```
     hist[0] = 3;     hist[1] = 5;     hist[2] = 2;     hist[3] = 2; 
```
since we have three O's, five 1's, two 2's, and two 3's in the stream. So if i is the next integer read from the data stream, all we would need to do to update the histogram would be
```
     hist[i]++; 
```
This array based approach would work fine as long as we knew the largest integer that we expected the data stream to produce. If we don't know the largest integer, a vector based approach would be more suitable. For the vector based approach, we could declare our histogram initially as
```
     vector<int> hist (4); 
```
When an integer i is read from the data stream, we'd update the histogram just as before, but after we compare the integer with the size of the histogram:
```
     if ( i < hist.size() ) hist[i]++; 
```
But if it turns out that the histogram does not have a bin for the latest integer because the integer is too large, we could do the following:
```
     if ( i >= hist.size() ) {       hist.resize( i + i );       hist[i]++;     } 
```
where the invocation of the function resize would increase the size of the vector to twice what's needed for including the integer i in the histogram. [Of course, we could also have said just hist.resize( i + 1 ) or, for that matter, hist.resize( 10 * i ). The choice made with hist.resize( i + i ) may, depending on the properties of a specific data source, be a happy medium between the absolute minimum needed to accommodate the new integer and some upper wild guess for accommodating future integers. The choice made would hopefully reduce the overhead associated with vector resizing, in terms of memory allocation/deallocation and element copying.]

Write a C++ program that implements the above notions and constructs a dynamically expandable histogram from a stream of integers of arbitrary values.

^[22]This homework is best done after the reader has gone through the material in Chapters 12 and 13 because it uses notions related to template classes and function objects that are presented in those chapters.

^[23]This homework is best done after you have gone through Chapter 12 and learned the concept of a function object presented there.