A .doc file (which MUST be plain text---no Microsoft Word documents) should contain the same thing that was specified in Project 1: class invariants, a list of data members, a list of public methods (you don't need to list private methods, since they are almost always helper functions to public methods). The public methods should at least have the prototype and a brief description.

You should briefly describe the purpose of the class, its data members, and its methods. There should be enough information that someone else can see how to implement the class (and why).

You should include classes OTHER than ArrayList and SortedList. The classes you come up with MAY include ArrayList or SortedList as data members, but are certainly not required to have them as data members.

For example, a Name class will be important in Project 4. It doesn't require a SortedList or ArrayList data member. When writing the documentation, you might decide its data members should be two strings which contain the first and last name.

You might have a constructor which allows you to set the name. You might overload the comparison operators. You might have a print() method. When developing ideas for a class, think about what methods are sensible for a class, in general, rather than specifically for the problem at hand. Don't worry about how the class will be used for a solution to the problem.

Also, see the Project 2 Checklist (there's a link in Project 2 description).

You should also read the Background Reading from Project 1, for documentation of Stack. There's a small addition concerning the purpose of the class. This will make it easier for someone who reads the class documentation to understand what the class is about.

Yes, it was. The j index should start at 0, not at i. It should now be corrected.

One student noted that Input 6 fails when checking whether list1 contains m1. Recall that in Project 1, contains() takes strings as input. Thus, m5 was treated as the title of a movie, and since that title didn't exist, it "failed". (Clearly, when the input file was developed, I was thinking of Project 2 and not Project 1, but forgot to change the movie variable to the title). So, the output is actually correct, because "m5" is not the name of any movie. (In Project 2, this would be valid).

Another student wonders why .cpp files were included. This was meant as a short cut for compiling the code. If your code doesn't compile because of this shortcut, you can ask the head grader to recompile for your project.

No. You can call contains() and map() directly from the SimpleMap class. Also, note that getValue() was implemented incorrectly in SimpleMap. The return type is mistakenly written as First when it should have a return type Second. Fortunately, this function doesn't get used much and shouldn't affect your project.

They should take Movie variables, and no longer take strings as inputs. This should be a moderately easy change, but PLEASE MAKE THIS CHANGE!

A few students have noted that the project description says that the second iterator must come BEFORE the first iterator (or point to the same element). Technically, this is STILL true of iter and iter2. Recall that iter2 is cend() which is NULL for a SortedList. NULL is either the element past last (i.e., one past the last element) and therefore can be thought of as AFTER iter.

However, NULL is also previous to first. That is, it comes one BEFORE the first.

It's the second intepretation that's used. Basically, the idea is to write a loop from the first iterator to the second, and moving the iterator using operator-- until you reach the second. Notice that if you do that, the iterator will move backwards until it falls off the list and meets up with cend().

So, it's not incorrect to say cend() is BEFORE (in effect, it's BOTH before first and AFTER last).

The runTestDriver() will be postponed until the next project. The project proposal is basically going to be writing your own .doc files for classes you think you will need in Project 4.

This does not have to be a complete list of classes, although the documentation for each class should be as complete as you can make it. In particular, you should decide on public methods (first), then data members (second), and the private methods can wait, since these are almost always helper functions.

Start with a very simple class. For example, you may notice that you need to keep track of a person's name. Thus, a Name class seems like a good simple class. Decide what methods you need for the class. Write out the documentation for this in Proposal.two.doc and for at least one other class (which can be simple).

In Project 3, you will be asked to write a "critique" of other student's proposals. Mainly, you will be asked "does the class make sense to you?, could you implement the class given the description?, how might you change it to improve it? what other classes should other students use? This information may help you decide what to do with your own proposal.

You won't be held strictly accountable for the classes you write. As you think about the design further, you may realize that there are better classes, or better interfaces, and some of that may come from the critiques.

All commands that were used in Project 1 should continue to work in Project 2 (unless, otherwise specified). In particular, you must handle TWO versions of VERIFY with lists. From Project 1, it must handle a SortedList or ArrayList. In this project, it must, in addition, handle two iterators. For ArrayList, it must handle two Iterators or two ConstIterators when VERIFYing. For printing, it should use two ConstIterators. We won't check for two Iterators for printing.

Right now. While it's good to look it through just before you submit, you want to avoid surprises. By looking at it now, you can double check a few things, and fix things up before the deadline.

Use one file called Proposal.two.doc. This should describe at least two different classes you want to use for Project 4, up to four classes. It should include potential data members and methods. This is preliminary. You will not be forced to use exactly the same methods or data members. However, put some thought into it.

Go to project 2 description for link to checklist. Make sure to read it often, just in case.

Notify instructors of errors in primary.

You should use comparison operators in sort214, but MovieComparator when you instantiate SortedList. The project description has been updated to reflect this.

There are several ways to proceed. First, you could create new tester classes to handle iterators. This turns out to be rather painful, but is possible, and if you want to do it, you can.

The other way is to add the following data member to, say, MovieSortedListTester.h (a similar one would be added to the MovieArrayListTester.h).

SimpleMap<std::string, 
          SortedList<Movie, MovieComparator>::ConstIterator * >
     lookup2 ;

Now, if you are given a variable, how do you know if it's an Iterator or a ConstIterator or SortedList or what have you? SimpleMap supports a contains() function. You can pass it a string, and it returns true or false depending on whether it's in the map or not.

For example, if you have var, you can check whether it's in lookup or lookup2 by calling contains(), as in:

   if ( lookup2.contains( varName ) )
     // it's an iterator

The next question is: how do you retrieve the object? So far, you've used something like: (*this)[ varName ]. Unfortunately, you can't use operator[] for Iterators as well (unless you write a separate class to handle iterator testers). C++ does not permit two functions that have the same number of parameters, but differ only in the return type. Since operator[] already returns SortedList references, you can't also make it return SortedList Iterator references, as well.

There are several ways to solve it. You can overload some other operator besides operator[]. For example, you can overload operator(). However, you don't even have to do that! After all, operator overloading is just a nice convenience. You can just define a plain method, say getIter(), which returns an ConstIterator by reference. Here's an example:

 ConstIterator & getIter( std::string name ) ; // in .h file
 const ConstIterator & getIter( std::string name ) const ; // in .h file

Of course, in ArrayList, you will need to create a method to retrieve Iterator and another method to retrieve ConstIterator from the SimpleMap objects.

Once implemented, you can call it like:

    getIter( varName )->setEarnings( value ) ; // do this!!!

    // doesn't work, operator[] already used to return list/array objects
    (*this)[ varName ]->setEarnings( value ) ; 

If you don't want to write additional methods, you can use operator[] directly on the SimpleMap data member. By doing so, you will get a pointer back, not a reference. So, you can merely dereference this pointer. For example, you can do:

    (* lookup2[ varName ])->setEarnings( value ) ; // do this!!!

Finally, you could also map to strings to objects, rather than mapping them to pointers. The main advantage of using pointers is to guarantee a call to the correct constructor by using "new". However, the main disadvantage is handling dynamic memory allocation.

It's a little awkward, but for the time being, when printing out these lists, continue to print out "THERE ARE NO MOVIES IN THIS LIST" when the list is empty. In project 3, the word "MOVIES" will be replaced by "OBJECTS".

As far as the data member in Node, instead of calling it movie, you can call it data.

Yes, it should. In other words, when you are looking at positive and negative inputs, VERIFYS should contribute to that.

Yes. You should modify the MOVIE PRINT method to simply print the Movie object (using overloaded output operator) plus a newline. These changes also need to be made to print methods in MovieSortedListTester and MovieArrayListTester (they should simply call the print() methods to SortedList and ArrayList).

It's not necessary to do so. In fact, it's easier to declare additional SimpleMap data members in MovieSortedListTester and MovieArrayListTester classes to handle iterators. Look at constructOp() to see how to handle the declaration of iterators.

The "tricky" part is that operator[] has already been overloaded to handle SortedList and ArrayList objects. They can't also be used to handle iterator objects. So, there are several choices. First, you can overload some other operator (for example, operator()), or you can write a method like getIter() which behaves like operator[] (i.e., it has the same kind of parameters and return type), except it works with the SimpleMap with iterators, instead of SortedList or ArrayList.

The reason for not creating additional classes is to allow you access to the class, the iterator, and movies.

No. Yes. If you want.

The problem occurs because Movie depends on MovieComparator and MovieComparator depends on Movie. This is called a circular dependence, and can cause problems when compiling.

To get around the problem, change your header file as follows. In the Movie.h header file, place the following line:

class Movie;  // forward declaration

#include <iostream>
// rest of .h files included here

class Movie {
  // actual class declaration

class MovieComparator;  // forward declaration

#include <iostream>
// rest of .h files included here

class MovieComparator {
  // actual class declaration

A forward declaration basically tells the compiler that there is some class being declared, but it's declaration will appear later. The compiler tends to get confused if it sees an object, and hasn't yet seen either the class declaration (i.e., the header file for the class) or a forward declaration.

You only need to forward declare classes that have circular dependencies (i.e., class A depends on B and class B depends on A). If there is just a plain dependency (i.e., class A depends on B, but not vice versa), then there's no need to have a forward declaration.

A new version has been posted. Unfortunately, while cxx does not have problems with ArrayList<Data>, it does have problems with ArrayList<Data>::Iterator.

So, the new version uses two template parameters, one for the Data and one for the IteratorType, which should be instantiated to Movie and ArrayList<Movie>::Iterator, respectively.

The third parameter of sort214 is temp, and can be ignored. It's only there to keep cxx happy. Since it has a default value, you can just pass in the first two parameters and it should behave as the original one.

You don't have to, but if you want to you can. It's only required in Movie (not sure what other classes have a vector of strings...ah, the InputTokenizer). In fact, making this replacement everywhere will cause more bugs, which is good, because it will help you fix the ArrayList class. Realize that transform will no longer work, so you need to find a different way to convert to lowercase, if you used transform. You can write your own transform if you want. Put it in Algorithm.h and implement. However, do this only if you have extra time. We could even consider it for a small amount of extra credit.

No. Unfortunately, you can't check if an iterator is out of bounds (especially in an ArrayList). In order to do so, you would need access to cbegin() and cend(), etc. However, those iterators are declared in an OUTER class, while the iterator is in a NESTED class. Alas, OUTER classes have no special privileges accessing a NESTED class and NESTED classes have no special privileges accessing an outer class.

But, you might say "Isn't cbegin() a public method of the outer class?". Yes, that's true, but the question is: which object should cbegin() be called on? You might say "The list that the iterator is pointing to". While that's the obvious answer, ask yourself how the compiler knows what list it's pointing to, and where this list object is located in memory. It doesn't magically know this, and may be quite inefficient trying to locate the list.

There is a way for the nested object to know something about the outer object, and Java implements this. If the nested object can only be constructed by an instance of the outer object, then this information of "who constructed you" can be passed to the inner object. However, C++ doesn't do this. It's best to think of a nested and outer class being two separate classes, which is conveniently nested, but just for "convenience". It's more accurate to think of them as separate classes, in terms of accessing methods, etc.

Think about the following: when you write x + 3 does the value of x change? It doesn't. Even if x is a pointer, the value of x doesn't change. So what does x + 3 do? It creates a temporary value (this is what is meant by temporary in question 5). That's why you return copies. Those don't modify the original iterator.

No. The idea is to use other Comparator classes if you want to have a SortedList of Student or URL or whatever other class you wish to have a sorted list. You would write them as you did the Comparator class (have an overloaded operator() method returning int).

This will eventually be posted to the Checklist, but the files you need to submit are Movie.doc, SortedList.doc, and ArrayList.doc, plus documentation for your proposed classes. The proposed classes should all be titled something like: Date.proposed.doc where proposed in the second word. This will make it easier to locate the proposed documentation.

Fortunately, the changes to the main 3 doc files are minor, and you should be able to rename them from Project 1. For those who didn't write "doc" files, then you have more work to do.

Yes. It was fixed in the files, but the README.updates wasn't updated. It's now in the README.updates.

This is trickier than expected. When you pass something to a reference parameter, this is equivalent to passing a pointer. So, here's what you should think about. Can I take the address of the thing I'm passing? If the answer is no, you need to think of a different way to pass it.

Here's an example:

void foo( int & x );

One solution is to set y = y + 1 and pass in y. Since y has been declared, and is not a temporary, it will be fine.

Where's the trickiness? OK, suppose we're talking about pointers.

void foo( Node *& ptr );

The rule of thumb is this: am I passing a temporary to a reference? If you are, then you may get compiler errors. Now, as it turns out, you can pass temporaries to const reference parameters. The reason the compiler warns you about temporaries to reference parameters is because users expect non-const parameters to be modified, and to use them after the function call is done. However, temporary values typically disappear quickly, and so a compiler warning makes sense. On the other hand, if it's const, you don't intend to change it, and you probably don't need to use it after the call, so a temporary works out fine passed to a const parameter.

Yes. Normally, you compare data objects with locate(). For example, you might do something like:

   while ( curr->getData() > movieIn ) // uses overloaded >
     ...

// uses comp Comparator data member 
   while ( comp( curr->getData(), movieIn ) == 1 ) 
     ...

The second reason, which is actually more important, is that Comparator classes allow you to store pointers in SortedList. For example, if you had SortedList<Movie *, MoviePtrComparator>, you could have a comparator that would dereference the pointer, and compare the objects. On the other hand, if you didn't use the Comparator, and used the comparison operators, you would compare addresses, i.e.,

   while ( curr->getData() > dataIn ) // uses overloaded >
     ...

As it turns out, there's no need for a setData() method, so the project description is in error there. There's a more clever way. Notice that getData() returns by reference. That means you can assign to it. Here's an example:

     Node *curr; // assume it points to something useful
     curr->getData() = movieObj;  // copies movieObj into Node object
                                  // pointed by curr

The first few files have been posted. More files to come soon. Read README.updates in the posting account for more information.

It's coming soon! Basically, some missing "background" reading files, the BNF, and the files need to be posted. But you'll need to do some reading for now. Things should appear soon!