Last Modified: Wed Mar 13 20:20:09 EST 2002
|
C M S C 2 1 4 C o m p u t e r S c i e n c e I I S p r i n g 2 0 0 2 |
Latest Posting: March 13, 2002 (NEW!)
(Errata: Fixed BNF for VERIFYS)
Originally Posted: February 28, 2002
2nd version Posted: March 10, 2002 (NEW!)
3rd version Posted: March 11, 2002 (NEW!)
(Added README section, link to Project 2 Proposal, and corrected the BNF,
which appears in red)
Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.
Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.
Hardcoding is considered a violation of academic integrity
Submit the following files.
Furthermore, you will need to submit the following files.
This is a file which has hardly been indented. Using the style guide, modify so it looks nice. Make sure the comments also look nice, based on the style guide. Several files starting with "Style" are now in posting account. Modify StyleExercise.cpp instead of StyleExercise.txt. The directions for how to modify are provided in a separate file.
If you didn't write documentation for MovieArrayList and MovieSortedList, you should now write the documentation for ArrayList and SortedList. If you did, it should be just renaming the classes and adding a method here or there, but otherwise, very little work.
The new documents will be called ArrayList.doc and SortedList.doc. (NEW) You should submit this as part of your tar file.
The print() method should print out:
<dqstring> " Earnings: " <digits>
It should NOT print a newline at the end. SortedList
and ArrayList will iterate through each element in their
list, and print the object using the print() method, followed
by a newline. For this project, you should
still print out "THERE ARE NO MOVIES IN THIS LIST", even though
this message only makes sense for Movie. In Project
3, this will be modified to something more reasonable.
MovieComparator is a so-called "function object". Basically, it is an object, but the entire purpose of the object is to hold a function. As such, it has no data members. Instead, it has an overloaded operator().
Put the code for compare inside the operator(). You have been provided a MovieComparator.h.
For example, suppose you wish to implement operator==().
This is how it would look:
bool Movie::operator==( const Movie & other ) const
{
MovieComparator comp;
if ( comp( *this, other ) == 0 )
return true;
else
return false;
}
Notice how comp is the name of the object, yet, it's
being called like a function (if we had overloaded the [] operator,
it would be easier to see this call).
Movie.h will have to #include "MovieComparator.h" and MovieComparator.h will have to #include "Movie.h". While this is a circular dependence, the function wrapper prevents infinitely including the files.
(NEW) Unfortunately, the circular depedence may prevent certain #include files from appearing, thus causing compiler errors saying certain files are missing. To solve this problem, read the FAQ. There is a question dealing with this.
There are several ways to implement update() in
MovieSortedList. To make sure everyone is consistent, you
should update a Movie object (NEW) as follows.
// Can assign to getData() since it returns a reference.
curr->getData() = movieIn; // curr points to Node that is updated
The reason you can do this is because
getData() returns a reference. The reference
is the actual memory location within the Node object that contains
the Movie. Had the function returned by value,
you could not do this (you would be assigning to a temporary).
bool remove( const Movie & movie ) ;
bool contains( const Movie & movie ) const;
(CORRECTION) contains() should be a
const method
This means that to call either remove() or update, instead of passing a string, you will create a Movie object with the string as the argument, then pass the Movie to these methods.
While this is awkward, to say the least, it has the advantage of making SortedList only have two template parameters, instead of three (once you convert this class to SortedList, that is).
bool locate( const Movie & movie, Node *&curr ) const;
So, instead of passing a string, you now pass in a Movie
object. Fortunately, one can compare movies using relational
operators. Make curr a reference parameter. Also,
convert this to a recursive function---may need to use helper
functions. Also, you may add a prev reference parameter if you
want. It shouldn't be necessary to do so, if you used one of the
locate methods mentioned in project 1 (forward predecessor, forward
successor, backward predecessor, backward successor).
This function will return true if the iterator lies between the endpoints of the MovieArrayList object. Recall that an iterator is basically a pointer. If it points to some valid element of the MovieArray, then it can erase.
A valid iterator points to a valid element in the MovieArrayList. Assume it points to element i. If you erase this element and the array has n elements, then elements from i + 1 to n - 1 are "shifted" left by 1, to index i up to n - 2.
Since erasing it causes the array to decrease in size, you must dynamically allocate a new array with a size that's one smaller than the current size, and copy the element appropriately.
It is possible that the iterator does not point to a valid array element, so you must check that the iterator points to a valid element in the array. Hint: use the fact that (CORRECTION) cfirst() and cend() determine the boundaries of the array, and that you can compare iterators in MovieArrayList.
If there is only one element erased, you can set the array pointer to NULL. Make sure to adjust the list size appropriately.
Add/modify the following methods to the PUBLIC section of MovieArrayList::Iterator.
Does the following subtraction: curr - other.curr where curr is the data member in iterator. This does pointer subtraction, and figures out the distance between two iterators.
Returns a Iterator where points to the element that is "offset" elements forward from "curr" of the current object. You can either make it "safe" (i.e., it never goes past cend()) or just let it advance. To implement, make a copy of the current iterator, and set curr in the copy to be curr + offset. This uses pointer arithmetic to move curr forward by offset in the copy. Returns the copy. The current iterator's curr should not be changed.
Returns a Iterator where points to the element that is "offset" elements backward from "curr" of the current object. You can either make it "safe" (i.e., it never goes past (CORRECTION) cbegin()) or just let it go out of bounds from the array (which isn't such a bad thing, really). To implement, make a copy of the current iterator, and set curr in the copy to be curr - offset. This uses pointer arithmetic to move curr backwards by offset in the copy. Returns the copy. The current iterator's curr should not be changed.
This Iterator constructor already exists. Add the default value of NULL in the header file.
Add/modify the following methods to the PUBLIC section of MovieArrayList::ConstIterator. (NEW) These methods are to emulate pointer arithmetic, since iterators behave like pointers. Pointer arithmetic is part of the C/C++ language.
Does the following subtraction: curr - other.curr where curr is the data member in iterator. This does pointer subtraction, and figures out the distance between two iterators. (NEW) This is useful when you need to determine the index of one iterator, given that you know the index of the other iterator, i.e., the same reason why pointer subtraction is normally useful.
Returns a ConstIterator where points to the element that is "offset" elements forward from "curr" of the current object. You can either make it "safe" (i.e., it never goes past cend()) or just let it advance. To implement, make a copy of the current iterator, and set curr in the copy to be curr + offset. This uses pointer arithmetic to move curr forward by offset in the copy. Returns the copy. The current iterator's curr should not be changed.
Returns a ConstIterator where points to the element that is "offset" elements backward from "curr" of the current object. You can either make it "safe" (i.e., it never goes past cfirst()) or just let it go out of bounds from the array (which isn't such a bad thing, really). To implement, make a copy of the current iterator, and set curr in the copy to be curr - offset. This uses pointer arithmetic to move curr backwards by offset in the copy. Returns the copy. The current iterator's curr should not be changed.
This ConstIterator constructor already exists. Add the default value of NULL in the header file.
Make sure to test all of this.
Task 4: Remove loops from MovieSortedList.
This is an exercise in recursion. To remove a loop will require
converting everything to recursion. There is background reading
about converting loops to recursion, and recursion in general.
It is located in the Tutorial section that can reached from
the main webpage. This should hopefully converting 5 or fewer
loops to recursive calls.
Writing recursive function calls will require you to write recursive helper functions. Functions are the basis of recursion, so your code should get smaller.
Note: this is merely an exercise to get you to learn recursion. In reality, you wouldn't opt to use recursion, unless it makes sense to do so, since recursion uses up to O(n) stack space where as iteration with loops often uses O(1). Nevertheless, the goal is to learn recursion. Just keep in mind that it may not always be space efficient.
(NEW) There is a new link on converting loops to recursion.
Task 5: Templatize MovieSortedList and MovieArrayList
Convert MovieSortedList to a template class called SortedList.
SortedList uses a two input template parameter:
template <class Data, class Comparator>
where Data is a class like Movie, and
Comparator is a comparator class like MovieComparator.
The comparator class is useful if Data happens to be a pointer type.
Convert MovieArrayList to a template class called ArrayList.
ArrayList uses a one input template parameter:
template <class Data>
where Data will be a class like Movie. It assumes
that the class has overloaded comparison operators.
Task 6: Write the sort214 function to sort ArrayList...
A header file will be provided to you called Algorithm.h.
You will implement sort214 method in Algorithm.cpp.
This function will take two parameters: two Iterators pointing
to the first element to start sorting, and one past the last element.
You may assume that they point to the same list.
You may use any sorting algorithm you wish. This may require looking up your 114 textbook or the current 214 textbook. The choices you have are: insertion sort, selection sort, bubble sort, and quicksort.
You will need to modify the algorithm in the following way. Normally, sorting algorithms assume you have an array. However, you can actually sort with pointers too, if you are careful.
If you have an algorithm for, say, bubble sort, convert it as
follows:
void bubblesort( int *first, int *end )
{
// code
}
where first points to the first element in the array
to be sorted, and end points to one past the last element
to be sorted. Once you have this version working, you should
be able to easily convert it to a version using iterators since
iterators are essentially pointers.
sort214 will be a template function.
You should also write a template function for
compare(). The compare() method should now be removed
from . You do NOT have to write a template
function for compare() (unless you want to). You use the
MovieComparator object instead to compare Movie objects.
(3/11) (CORRECTION) You should use the
MovieComparator object to compare Movies in SortedList,
but use relational operators to compare ArrayList<Movie>.
Task 7: Convert vector in the Movie class to ArrayList
In your Movie class, a vector of strings was used.
Instead, use an ArrayList of strings. Change this in
the header file, and make any needed changes in the .cpp file. There
should be few changes, and those that occur are only due to the
ArrayList having less functionality than a real vector class.
The purpose of this is to show that you can write a class that's very similar to an STL vector class (though the vector class is still perhaps more sophisticated
Run your test driver runTestDriver() to make sure it's still behaving correctly (thus, the reason for the test drivers).
Task 8: Convert Tester Classes
In MovieSortedListTester, MovieSortedList are used
used. It's part of SimpleMap and you see it being constructed
in constructOp(). Where you see MovieSortedList,
convert it to (CORRECTION)
SortedList<Movie, MovieComparator>.
Similarly, MovieArrayListTester uses MovieArrayList.
Instead of this, use ArrayList<Movie>.
Task 9: Add new commands to tester classes
There will be commands to add iterators to the input files. You
can do one of two things: either create tester classes that
specifically handle iterators, or add a new SimpleMap object
for storing maps of string objects to MovieSortedList::ConstIterator * (3/11 CORRECTION:
Iterator was changed to ConstIterator) objects. (PREVIOUS paragraph reworded to make it easier to
read)
The list of commands will appear in the next section.
(NEW) Task 10:
Modify runTestDriver()
for ArrayList and SortedList template classes.
Again, just to see if it works.
Here are additional commands for the categories
Movie
No additional commands for Movie.
However, there is a change to the MOVIE PRINT
command. In the MovieTester code, you will need to print out
the object by simply doing:
cout << (*this)[ varName ] << endl;
That's because Movie print() method now prints the proper
title of the movie in double quotes, three spaces, "Earnings: ", and
the earnings (but no newline). The newline will be taken care of when
printing the object (as above).
MovieSortedListTester
Here are the list of new commands. (BNF to be added later)
(NEW) cbegin() was replaced with cfirst(), to make it match with the header files..
This allows you to declare iterator (initialized to NULL). It allows you to assign one iterator to another iterator (both are const iterators). It allows you to assign to a beginning of a list, and to past the end of a list, and to the last element of a list.
The output for this should be:
SORTED CONST_ITERATOR DECLARE x
where x is the const iterator variable declared.
<new_sort_cmmd> := "SORTED" <seps> "CONST_ITERATOR"
<seps> DECLARE <seps> <var>
[ <empty> | <copy_sort> | <iter_sort> ]
<copy_sort> := <seps> "=" <seps> <var>
<iter_sort> := <seps> "=" <seps> <var> <seps> "." <seps>
[ "cfirst" | "clast" | "cend" ]
<seps> "(" <seps> ")"
The initial variable is a SortedList<Movie, MovieComparator>::ConstIterartor object. If a second variable appears, that's a SortedList<Movie, MovieComparator> object.
The output BNF is:
<sort_const_out> := "SORTED CONST_ITERATOR DECLARE " <var> <endl>
The iterator variable is printed.
For the RUN methods, you can make similar assignments as DECLARE. You can also move iterators forward or backward by a constant (which can be assumed to be non-negative). You must determine x is an iterator object. You can assume iterator variable names are distinct from other variable names.
(NEW) Notice that operator+=() and operator-=() have NOT been defined for SortedList. You must "implement" these operation using the operators that have been defined for SortedList. In this respect, the this does not perfectly match with the operations of the SortedList template class.
The output will be:
SORTED RUN x assign CONST_ITERATOR
(CORRECTION) RUN has been added to the output.
<new_sort_run_cmmd> := "SORTED" <seps> RUN <seps> <var> <seps>
[ <shift_run_sort> | <iter_run_sort> ]
<shift_run_sort> := [ "+=" <seps> <udigits> | "-=" <seps> <udigits> ]
<iter_run_sort> := "=" <seps> <var> <seps> "." <seps>
[ "cfirst" | "clast" | "cend" ]
<seps> "(" <seps> ")"
The first variable is the SortedList iterator variable and the
second variable, if it exists, is a SortedList object.
The output BNF is:
<sort_run_out> := "SORTED RUN " <var> " assign CONST_ITERATOR" <endl>
The variable is the ConstIterator variable that was just assigned.
Assume x and y are ConstIterator objects, this
will print the elements from x up to, but not including
y. It will be printed out in the format of a normal print.
(1) "Gone With The Wind" Earnings: 2000
(2) "Matrix" Earnings: 3000
If the ConstIterators point to the same element, then print
NO MOVIES IN THIS RANGE
The REV_PRINT assumes that x appears AFTER y, so
it will print the list in backwards starting at x, up to,
but not including y. (NEW) Thus, you will
set the iterator to point to x, then iterate backwards
using the -- operator, until you reach y, although
y will not be printed (since it is NULL).
(1) "Matrix" Earnings: 3000
(2) "Gone With The Wind" Earnings: 2000
Again, if they point to the same object, print
NO MOVIES IN THIS RANGE
<new_sort_print_cmmd> := "SORTED" <seps>
[ "PRINT" | "REV_PRINT" ]
<seps> <var> <seps> <var>
Both variables are ConstIterator objects.
The output should be:
<new_spout> := "SORTED " [ "PRINT " | "REV_PRINT " ]
<var> " " <var> <endl>
[ [ "(" <udigits> ") " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl> ]+ |
"NO MOVIES IN THIS RANGE" <endl> ]
<title> := <word> [<blank> <word>]* [", " <word>]?
The output should print "SORTED" followed by either "PRINT" or
"REV_PRINT", then the two ConstIterator variables, then a
newline, then the list of movies between the two ConstIterator,
or "NO MOVIES IN THIS RANGE" if the two ConstIterators happen
to point to the same location.
SORTED VERIFY x y <list> "Gone With The Wind" 2000 "Matrix" 3000 </list>(CORRECTION) The word "Earnings:" should not have appeared in the list.
This will check that the list of movies between x and all the way up to, but not including y is the same as the list afterwards.
<new_sverify> := "SORTED" <seps> "VERIFY" <seps> <var>
<seps> <var> "<list>" <seps>
[<dqstring> <seps> <digits> <seps>]*
"</list>"
This is quite similar to the VERIFY from project 1. The only difference
is that the variables are ConstIterator variables.
The output BNF is:
<new_sverifyout> := "SORTED VERIFY " <var> " " <var>
" CONST_ITERATOR "
[ "IS SUCCESSFUL" | "FAILS" ] <endl>
(NEW) The following is an explicit text for what the previous paragraph says.
The input BNF for should be obvious, so it won't be listed here. The variables are either iterator variables or they are ArrayList variables.
The output BNF is:
<sort_const_out> := [ "ARRAY CONST_ITERATOR DECLARE " <var> |
"ARRAY ITERATOR DECLARE " <var> ] <endl>
The iterator variable is printed.
Notice that operator+=() and operator-=() have NOT been defined for ArrayList.
Also, you may assume that the correct iterator types will be used. Thus, there won't be any assignments of ConstIterator to Iterator or vice versa (though, theoretically, a Iterator can be assigned to a ConstIterator object---it just won't be tested).
The input BNF is similar to that for SortedList, so use that BNF as a reference.
The output BNF is:
<arr_run_out> := [ "ARRAY RUN " <var> " assign CONST_ITERATOR" |
"ARRAY RUN " <var> " assign ITERATOR" ]
The variable is the iterator variable.
The input BNF is very similar to the SortedList version, so refer to that.
The output should be:
<new_apout> := "ARRAY " [ "PRINT " | "REV_PRINT " ]
<var> " " <var> <endl>
[ [ "(" <udigits> ") " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl> ]+ |
"NO MOVIES IN THIS RANGE" <endl> ]
<title> := <word> [<blank> <word>]* [", " <word>]?
The output should print "ARRAY" followed by
either "PRINT" or "REV_PRINT", then the two iterator variables, then a
newline, then the list of movies between the two iterators, or "NO
MOVIES IN THIS RANGE" if the two iterators happen to point to the same
location. (CORRECTION) Changed "SORTED" to "ARRAY"
ARRAY VERIFY x y <list> "Gone With The Wind" 2000 "Matrix" 3000 </list>(CORRECTION) The word "Earnings:" should not have appeared in the list.
This will check that the list of movies between x and all the way up to, but not including y is the same as the list afterwards.
<new_sverify> := "ARRAY" <seps> "VERIFY" <seps> <var>
<seps> <var> "<list>" <seps>
[<dqstring> <seps> <digits> <seps>]*
"</list>"
This is quite similar to the VERIFY from project 1. The only difference
is that the variables are ConstIterator objects (you can
assume we won't use Iterator variables, although you
can implement them for Iterator and ConstIterator
objects, if you want).
The output BNF is:
<new_averifyout> := "ARRAY VERIFY " <var> " " <var>
[ " CONST_ITERATOR " | " ITERATOR " ]
[ "IS SUCCESSFUL" | "FAILS" ] <endl>
This will call sort214 on x which is an ArrayList<Movie>. This should preserve the number of elements. Thus, there may be duplicates.
<sort_bnf> := "ARRAY" <seps> "SORT" <seps> <var>where the variable is an ArrayList object.
The output BNF is:
"ARRAY SORT " <var> <endl>
where the variable is an ArrayList object.
This will allow an (non-const) iterator (listed as x) to be "dereferenced" and (CLARIFICATION: 3/10) have a movie assigned to the movie pointed to by x.
<arr_deref> := "ARRAY" <seps> "RUN" <seps> "*" <seps>
<var> <seps> "=" <seps> <var>
where the first variable is an Iterator object and
the second is a Movie variable. (3/11) (CORRECTION)
The "=" sign was added to the BNF. Notice this must be
an Iterator object, not a ConstIterator object.
The output BNF is:
<arr_deref_out> := "ARRAY RUN * " <var> " = " <var> <endl>
where the first variable is an Iterator object and the
second is a Movie variable.
This will allow an (non-const) iterator (listed as x) to be "dereferenced" using the arrow operator, and the earnings set.
<arr_arrow> := "ARRAY" <seps> "VERIFY" <seps> <var>
<seps> "->" <seps> "setEarnings" <seps>
"(" <seps> <digits> <seps> ")"
where the first variable is an Iterator object.
The output BNF is:
<arr_arrow_out> := "ARRAY VERIFY " <var>
"->setEarnings( " <digits> " ) "
[ "IS SUCCESSFUL" | "FAILS" ] <endl>
where the first variable is an Iterator object and the
digits is the number.
ARRAY VERIFYS x
<list>
"Gone With The Wind"
"Matrix"
</list>
In this case, x is a MovieArrayList. This checks
for the titles of the movie only. There are no list of amounts
to check for.
<new_averifys> := "ARRAY" <seps> "VERIFYS"
<seps> <var> "<list>" <seps>
[<dqstring> <seps>]*
"</list>"
where the first variable is an ArrayList object. ((3/13) there was a second variable in VERIFYS which should
not have been there).
The output BNF is:
<new_averifyout> := "ARRAY VERIFYS " <var> " "
[ "IS SUCCESSFUL" | "FAILS" ] <endl>
where the variable is an ArrayList object. (Space add 3/10 after
variable name).
In a plain text file called Proposal.two.doc, begin to figure out what data members you will use. For more sophisticated classes, you will use SortedList and ArrayList template classes. Start to write out documentation similar to the ones you wrote in Project 1 for such classes. If you have more than four classes, you will only be required to write documentation for the four simplest classes (realize that if the documentation is complete now, then you may avoid work later on).
For the proposed classes, also write class headers. Each
class you write will start with a lowercase 'p. For example,
if you have a class you want to call "Calendar", then you would
actually write a class called "pCalendar". The purpose of this
is to make it easier to identify your proposed classes.
(3/11) (CORRECTION) Put all classes descriptions in the Proposal.two.doc file. That file will contain all the class descriptions. In project 3, you will begin to split them up into other .doc files
(CORRECTION) No longer have to do following part that is crossed out).
You should have a runTestDriver() method, which should
"print" out methods. Have "stub" functions, i.e., write out
the function names, and parameters, but leave the bodies empty.
If the function has to return something, return the simplest thing
that makes it work (for example, if it has an int return value,
return 0, if it has a bool, return true).
In runTestDriver(), you should have code that "tests" the various methods. Read the tutorial on "Writing Test Drivers" in the Tutorial section of the main webpage. You should have "output" for the various commands so that, in theory, you are printing out the actual result and the "predicted" result. If your test driver actually ran, a person looking at your output should see the actual and predicted result.
The goal of writing a test driver prior to coding is to get you to think about how the class ought to behave before you worry about how you want the class to be implemented. Thinking about it's behavior is a good way to think abstractly.
Of course, once you start to implement the object, you may realize that, for efficiency reasons, you may have to implement it a different way, but the goal is to concentrate on class behavior first, and to worry about the actual implementation details later on. After all, that's how the user of a class will think. They only see the abstraction you provide as a class writer.
Once you begin to implement the actual classes, you may discover that you make bigger changes. That's fine. The idea is for you to worry about design prior to coding, and writing test cases prior to coding is a step in that direction.
Here is the Project 4 Preview, Part 2 (POSTED)
Also, for ArrayList, it's a good idea to print a message indicating you've gone out-of-bounds, if the index is out-of-bounds. Notice that regular arrays won't tell you such things.
In order to successfully submit your project, it must pass
the primary input and produce the primary output. The primary
input will be sent to your project using input redirection.
p2 < primary.input
Your program MUST produce the executable p2, EXACTLY, when
the command "make" is run with no arguments. Thus, you must use
a makefile named exactly "Makefile".
Your program must use cxx with the options -w0 -std strict_ansi. Unfortunately, while we have aliased this for you, it doesn't always work with Makefile, so use the full name in your makefiles.
We will use "diff -bwi" to test your code. This ignores case, treats N blanks as 1 blank, treats N blank lines as 1 blank line. We will also strip all blank lines from your input when matching to ours. However, diff is sensitive to punctuation, number of dashes, etc. so you should attempt to make your output match ours as closely as possible otherwise you may not be able to submit your program. If this is the case (that your program does not submit) you must fix your code until the output it produces matches that of the primary output. Note: "hardcoding" output is a violation of the University's Code of Academic Integrity.
To submit your project you must first combine the following files (and only these files) into a single tar file using the Unix tar command:
You may name your tarfile anything you want, but p2.tar is the suggested name.
NOTE! You should make a backup copy of all your files BEFORE attempting to create your tarfile!!!! You have been warned.
After creating the tar file you should submit that one file using
the following command:
submit p2.tar 2
where p2.tar can be replaced by whichever tar file you
have created, and 2 refers to the current project,
|
See the class syllabus for policies concerning email Last Modified: Wed Mar 13 20:20:09 EST 2002 |
|
|
|
|
|