Last Modified: Tue Feb 12 19:48:57 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 |
Last updated: February 21, 2002
Previously updated: February 18, 2002
Previously updated: February 12, 2002
Read the FAQ for updates/corrections. Items that have changed from the previous version will be marked in red to make it easier to spot changes.
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
Furthermore, you will be given a description which will be implemented as Project 4. You must write a description of all classes that you think you will need to solve that project. In addition to the the coding part of the project, you will spend the next 3 projects planning out classes, etc., needed for the fourth project.
Furthermore, you will need to submit the following files.
(CHANGE) You do not have to submit the test drivers (i.e., MovieDriver, MovieSortedListDriver, MovieArrayListDriver) as separate files. Instead, read the section at the end on "Test Drivers, Revisited" to see how you should submit your driver. (It will be part of the file you submit for each class you are testing).
(CLARIFICATION) The relational operators MUST call compare, which is NOT a member function.
This is a constructor. Given a string that looks like " Star Wars ", this will split the text up into individual words and store each word in an element of a vector. For example, for " Star Wars ", the vector would store { "Star", "Wars" }. Capitalization must be preserved.
A word will be defined as any sequence of non-whitespace, printable characters. You may assume that words are separated by blank spaces. There won't be any punctuation that you will ignore. If punctuation shows up, it's considered part of the word. Thus "The ; Show" is actually three words. To repeat, one or more blank spaces are delimiters (separators) for the words.
This should set earnings to earningsIn. If the earnings is negative, set it to 0.
The constructor has default values.
This returns a string which concatenates the words of the movie. For example, if the movie is { "Gone", "With", "The", "Wind" }, then the string returned is "Gone With The Wind". The title must maintain the same capitalization as the words read in. For example, if you read in { "stAR", "WARS" } then the string should be "stAR WARS". There should be a single blank separating each word (even if the original input had multiple blanks).
(ADDITION) Return a string without the double quotes (i.e., you shouldn't see double quotes printed, if you print it to the screen). There should be no newline at the end, either.
Returns true if the movie title begins with "a", "an", or "the". This is case-insensitive!!!! Call the isArticle() standalone function.
This returns a string which concatenates the words of the movie. If the movie contains an article (i.e., the words "A", "An", and "The") as its first word, then you print out all but the first word, then a comma, then one space and the first word.
For example, if the movie is { "an", "affair", "to", "remember" }, then the string returned is "affair to remember, an". Again, you should maintain the same capitalization as the string that was used in the contructor.
If the title does not BEGIN with an article, then you should return the string getTitle() would return.
(ADDITION) Return a string without the double quotes (i.e., you shouldn't see double quotes printed, if you print it to the screen). There should be no newline at the end, either.
Returns the earnings of the movie.
Sets earnings to earningsIn but only if earnings is non-negative. If earningsIn is non-negative, return true, and update earnings. If earningsIn is negative, return false, and don't change the earnings data member.
Returns the word referred to by "index". If index is out of bounds, return "ERROR". Indexing begins at 0. If the movie is { "an", "affair", "to", "remember" } and the index is 2, the function returns "to".
Returns the number of words in the title. For example, if the movie is { "an", "affair", "to", "remember" }, the function would return 4.
Prints the title of a movie in the order of getProperTitle(). Thus, if the title were { "an", "affair", "to", "remember" } then it would print "affair to remember, an" (WITHOUT the double quotes). This function MUST be used by the overloaded output operator to print the Movie objects.
(ADDITION) Should print to the stream, out. Should only print the string, with no double quotes, and not ending in a newline.
Described below.
Returns true if the word is "a", "an", or "the". Must be case INSENSITIVE. Thus "A", "AN", "ThE" would all return true.
The overloaded output operator. Must call print() method.
To be more specific, this is how we compare movies. Each movie stores a list of words that represents a movie's title. For example, "Gone", "With", "The", "Wind" would be stored as the first four elements of a Movie object. Each element stores one word.
Here's the pseudocode for compare:
For example, if you are comparing { "Gone, "With", "The", "Wind" } (which is the first movie) to { "Matrix" }, then because "Gone" < "Matrix", then the first movie is smaller than the second, and the function would return -1.
However, if at least one of the movies doesn't have word i, then do the following:
The algorithm isn't quite complete. Here are two complications that you must also handle.
As you write the code, you should write a static method for Movie called runTestDriver() (see "Test Driver, Revisited" below). These tests should print out messages to the screen, checking for assignment operator, copy constructor, and all the methods shown. Initially try to get the print functions to work, so you can test the other ones. Go to the Tutorial section, and read up on writing test drivers.
Note that the iterator will be implemented differently in MovieSortedList than in MovieArrayList. This points out the differences between iterating an array and a linked list.
Node should already be in the class, so you just need to implement the methods.
Some restrictions:
This is a description of what each method does:
Creates a doubly linked that's empty.
If there are no nodes with the same key as dataIn, this method creates a Node that stores a copy of the Movie object as a data member, and adds it to the list in the correct order. Must call locate().
Returns true if successfully added, or false if there is a movie with the same key is already in the list.
Removes the node from the doubly linked list with the same title. You must convert this to a vector of strings (use function you wrote in Movie.cpp). If a movie exists with the same title (using operator==), it should remove it from the list and return true. If not, it should return false and leave the list unchanged. Must call locate().
Returns true, if the list contains this title. Again, you may need to split the title up into a vector of strings to do the comparison. Must call locate().
Update the movie with the same title as this movie, i.e., copy over the movie. Returns true if the title exists in a movie in the list, and false, if it does not. Must call locate().
Returns the number of elements in the doubly linked list. Should do so efficiently (in Big O notation).
Removes all elements from the linked list. This requires deallocating memory and setting first and last appropriately.
2/24: Prototype updated to match the files posted
Print the titles of the movie. The movies should be printed as follows:
(ADDITION) You must now also print the
earnings. After the title, you should print 3 spaces, the
string "Earnings:", a space, the earnings, and a newline.
(1) "Gone With The Wind" Earnings: 2000
(2) "Matrix" Earnings: 1500
(3) "see the sea" Earnings: 3100
That is, they should begin with a few spaces, one left parenthesis,
the number (starting at 1), one close parenthesis, a blank space
a left quote, the proper title (see Movie), and a close quote.
Each line should end in a newline character.
If there are no movies, it should print:
THERE ARE NO MOVIES IN THIS LIST
This should end in a newline.
Returns a ConstIterator which points to first element of the linked list. If the linked list is empty, sets curr to NULL.
Returns an Iterator which points to NULL.
Returns an ConstIterator which points to the last element of the linked list. If the linked list is empty, curr points to NULL.
Four methods listed above (add(), remove(), contains(), update()) must call locate().
These methods will declare a LOCAL VARIABLE called curr. The locate() method may assume that curr is set to some reasonable value (or you can set it within the method). You should do either a predecessor or successor locate. If you feel a prev pointer is necessary, add that to the parameter list as a pointer REFERENCE (just like curr).
The method returns true if it finds the titleIn. This MAY require splitting up the title into a vector of strings to do the proper comparison (there may be other ways to do this too).
Constructor. Initializes the node to contain the movie passed in. If no movie is passed in, it uses the version produced by the default constructor of Movie() (which is what you see above). curr and prev initialized to NULL.
Returns next.
Returns next.
Returns prev.
Returns prev.
Sets next to nextIn.
Sets prev to prevIn.
Return movie.
Return movie.
Initializes curr to currIn. NULL is the default value, if no argument is sent.
Returns a pointer to the Movie object within the object pointed to by curr. Overloads the -> operator.
Returns a reference to the Movie object within the object pointed to by curr. Overloads the dereference operator.
Prefix increment. Advances curr forward by 1. Returns *this.
(CORRECTION) Postfix increment. Saves a copy of the iterator to temp. Moves curr forward by 1. Returns temp.
(ADDITION) Prefix decrement. Moves curr backward by 1. Returns *this.
Postfix decrement. Saves a copy of the iterator to temp. Moves curr backward by 1. Returns temp.
Returns true if two iterators point to the same Node. (NOT the same value, but the same memory location).
Return the negation of operator==.
Think about why it's not necessary to write a copy constructor, assignment operator, and destructor for this nested class.
As you write the code, you should write a static method for MovieSortedList called runTestDriver() (see "Test Drivers, Revisited" below). These tests should print out messages to the screen, checking for assignment operator, copy constructor, and all the methods shown. Initially try to get the print functions to work, so you can test the other ones. Go to the Tutorial section, and read up on writing test drivers.
Note: if you are pressed for time, you may wish to start working on MovieTester and MovieSortedListTester before working on this class. While we will test this class, it will not appear in the primary.
Note that the iterator will be implemented differently in MovieSortedList than in MovieArrayList. This points out the differences between iterating an array and a linked list.
Some restrictions:
This is a description of what each method does:
Creates an array list of 0 elements, with listSize initialized to 0.
Returns the element at index by reference. If index is out of bounds, the behavior is undefined (meaning, it is permissible for the program cause the operation to crash).
Returns the element at index by const reference. If index is out of bounds, the behavior is undefined (meaning, it is permissible for the operation cause the operation to crash). The const version of this operator allows access to elements of the array list when an MovieArrayList object is const.
Changes the size of the array to newSize. However, if newSize is negative, then it does nothing (and leaves the original size the same as before). The method returns false, in this case.
If the array increases in size, then the additional elements will be set to the default value (as created by the default constructor of Movie).
If the array changes in size, then return true.
If newSize and listSize are the same, then nothing should happen (it should just return false).
When resizing the array, you must deallocate the old array, and allocate a new one. This should be done "efficiently", meaning try to avoid allocating and deallocating more than you have to.
Adds dataIn element at the end of the array. Thus, there is one additional element added at the end of the list.
If the array list is not empty, it removes the last element of the array, creating an array list with one fewer element. It returns true in this case. If it is empty, it remains empty, and returns false.
Returns the number of elements in the array.
int changed to void on 2/24
Removes all items, and sets size to 0.
Returns an Iterator which points to first element of the array list (at index 0). Does this even if the array list is empty.
Returns an ConstIterator which points to first element of the array list (at index 0). Does this even if the array list is empty.
Returns an Iterator which points to one past the last element of the array list (figure out which index). (2/24) If array list is empty, the iterator returned should have curr set to NULL (assuming you represent an array of 0 elements by using a NULL pointer---if you don't, then you should return the pointer produced by creating an array of 0 elements, instead).
Returns a ConstIterator which points to one past the last element of the array list (figure out which index). (2/24) If array list is empty, the iterator returned should have curr set to NULL (assuming you represent an array of 0 elements by using a NULL pointer---if you don't, then you should return the pointer produced by creating an array of 0 elements, instead).
Prints the contents of the array list starting at index 0 up to index n - 1 (if the list contains n elements). The format is the same as the print method for MovieSortedList. If the list contains 0 elements, it should print the same message about having no movies in the list. The overloaded output operator should call this method.
Determine whether it is NECESSARY to write the copy constructor, assignment operator, and destructor. If so, write them. If it's unnecessary, meaning the implicit versions are correct, then don't implement. Note: when copying this object, a deep copy should be made.
Also, the relational operators will compare the pointers using relational operators (note: pointers can be compared). Don't worry if two iterators are pointing to elements in different lists. This would be hard to check for. Merely compare curr of one iterator to another.
Finally, the only unusual constructor is the constructor which takes an Iterator object. This allows an iterator to be saved to a const iterator.
The following are a list of all methods:
The only unusual method is: makeConstIterator. This method creates a ConstIterator with its curr matching the curr of the current iterator.
The following are a list of all methods in this nested class:
As you write the code, you should write a static method for MovieArrayList called runTestDriver() (see "Test Driver, Revisited" below). These tests should print out messages to the screen, checking for assignment operator, copy constructor, and all the methods shown. Initially try to get the print functions to work, so you can test the other ones.
Almost all of this class has been written. However, if any bugs remain, you will need to debug it. No bugs have been deliberately left in, however.
A description of the tester files appears in later sections below.
Task 5: Write MovieSortedListTester and
MovieArrayListTester
These classes should work with main() and handle a few
simple operations such as declaring an object, copying an object,
printing the size, determining if the list has the correct
items in it, in the correct order, declaring an iterator,
moving it around and printing it. Write the MovieSortedListTester
first since that's the only required by the primary input. The
MovieArrayListTester will be checked only in secondary inputs,
and is not required for a successful submission.
See section about testers below.
Task 6: Finish main.cpp and test, test, test!
Yeah, what the task said...
There's not much to add to it, so you should be able to use the file as is (uncommenting sections as needed).
In the following link, you will read a description of what will be required in project 4. At this point, the description is sketchy. Your goal is to determine what classes you think will be necessary for this class, and hopefully, some methods that you may need. By that point, you will use some version of the MovieSortedList and MovieArrayList (which will then store other things besides movies.
In a plain text file called Proposal.doc, describe the names of the classes you think you will need. Explain what each class will do. If you think you can write the data members and methods, you can do that, too.
Here is the Project 4 Preview
Within each class is a SimpleMap data member, which maps a string to a pointer to an object. The string is the variable name, and the pointer is the object associated with the variable name. Whenever you want to assign a pointer to a variable name, you can call the map function.
For example, if you look at the MovieTester code, you
can see calls like:
Movie *ptr = new Movie(); // creates a new Movie object
map( str, ptr ); // maps the string to the new object
operator[] has been overloaded so you can access the object
in a "convenient form". If you are in the MovieTester
class, you access the object as:
(*this)[ varName ]
For example, to call setEarnings()
(*this)[ varName ].setEarnings( value );
Things becomes a little tougher in MovieSortedListTester.
You can use the same technique to access a MovieSortedList
object. However, you will also need to access Movie objects.
Those can be accessed by using operator[] on the movieLookup
object, as in:
Movie & m = movieLookup[ varName ];
Notice that this creates an "associative" array, where the index
is a string (the variable name) instead of an int.
Read the MovieTester code to get a better idea of what's going on.
The only class that's not partly implemented for you is MovieArrayListTester. Use MovieSortedListTester to guide you on how to implement the class. In particular, use a SimpleMap to map a string to MovieArrayList pointer objects. A good way to start is to copy the code for MovieSortedListTester, and change the name to MovieArrayListTester and make appropriate changes.
In this project, the tokenizer will split based on blank spaces, which will be blanks, newlines, and tabs (though no tabs should appear).
The tokenizer will read until a "keyword" (in this case </cmmd>. It tokenizes up to, but not including the keyword. The keyword is removed from the input.
Spaces are placed so that each "word" is considered a token. Spaces appear as described by the BNF below, and roughly correspond to how a compiler would break up words in a program (except the spaces are there for making it easier to break up to tokens).
If you write your own test files, you need to be careful to follow the spacing convention, otherwise, you may not get the correct answer.
The first token (at index 0), will always be the keyword MOVIE, SORTED, or ARRAY. The rest of the words in the command will be indexed up to, but not including, the ending </cmmd> keyword, and should work, even if the command spans more than one line.
The tokenizer has one very useful feature. When it sees a double quote, it reads up to the next double quote. It disposes of both quotes, but saves everything in between as one string.
For example, if you see:
SORTED VERIFY x . contains ( "gone with the wind" ) </cmmd>
This will contain 8 tokens: { "SORTED", "VERIFY",
"x", ".", "contains", "(", "gone with the wind", ")" },
indexed from 0 to 7. All the tokens will be saved as
elements of a vector of string elements.
To that effect, this project's goal is to write an automated test driver. In effect, it is a very simplistic interpreter for C++. It will allow you to declare methods, call methods, and determine whether a boolean function is true or false.
Note: some of the non-terminals appear in the EBNF Tutorial. Go to the Tutorial section of the main webpage, and click on it.
<start> := "<cmmdlist>" <multicmmd> <seps> "</cmmdlist>"
<multicmmd> := [[ <seps> <command> ]]*
<command> := "<cmmd>" <seps>
[[ <moviecmmd> | <srtdcmmd> | <arraycmmd> ]]
"</cmmd>"
<moviecmmd> := "MOVIE" <seps> [[ <moviedecl> | <moviepr> |
<movierun> | <movieverify> ]] <seps>
<moviedecl> := "DECLARE" <seps> <var>
[[ <seps> ( <mcopy> | <mconst> ) ]]?
<mcopy> := "=" <seps> <var>
<mconst> := "(" <seps> "string" <seps> "=" <seps> <dqstring>
[[ <seps> "," <seps> "int" <seps> "=" <seps> <digits> ]]?
<seps> ")"
<moviepr> := "PRINT" <seps> <var>
<movierun> := "RUN" <seps> <var> <seps> "=" <seps> <var>
<movieverify> := "VERIFY" <seps> <operator> <seps> <var> <seps> <var> |
"VERIFY" <seps> <operator> <movieget> <movieget> |
"VERIFY" <seps> <var> <seps> "." <seps> "setEarnings"
<seps> "(" <seps> <digits> <seps> ")"
<movieget> := <seps> <var> <seps> "." <seps> "getEarnings" <seps>
"(" <seps> ")"
<operator> := "==" | "!=" | "<" | "<=" | ">" | ">="
<movieverify> := "VERIFY" <seps> <operator>
( <seps> <var> <seps> <var> |
<seps> <var> <seps> "." <seps> "getEarnings"
<seps> "(" <seps> ")" <seps> <var> <seps> "."
<seps> "getEarnings" <seps> "(" <seps> ")" )
<movierun> := "RUN" <seps> [ <movieassign> | <movieset> ]
<movieassign> := <var> <seps> "=" <seps> <var>
<movieset> := <var> <seps> "." <seps> "setEarnings" <seps>
<lparen> <digits> <rparen>
<mconst> := <lparen> <seps> <param> [ <seps> "," <seps> <param> ]+
<seps> <rparen>
<param> := ( "string" <seps> "=" <seps> <dqstring> |
"int" <seps> "=" <seps> <digits> )
Note: because of the width of the screen, some of these rules take one or more lines. Do NOT assume that this means there is a newline at the end of the line.
The input (see input file) is written using a format that's like HTML. In fact, it's written in a more generalized form called XML. This format is becoming increasingly popular way to record information in a standard way. In XML, you can create your own tags, or use tags developed by someone for their data.
In this case, you have a list of commands (called a command list). Each command starts with <cmmd> and ends in </cmmd>. Each command begins with one of three words: MOVIE, SORTED, ARRAY. A command that starts with MOVIE will handle primarily Movie objects. A command that starts with SORTED will primarily handle MovieSortedList and Movie. Finally, a command that starts with ARRAY will primarily handle MovieArrayList and Movie.
MOVIE commands can be broken down into four types: DECLARE, RUN, VERIFY, PRINT.
DECLARE allows you to declare a variable. You may assume:
You can declare a variable three ways.
DECLARE MOVIE xIn this case, x will be initialized with the default constructor.
DECLARE MOVIE x = yIn this case, you call the copy constructor.
DECLARE MOVIE x ( string = "hey there" )which uses the Movie constructor with the first value (e.g., "hey there") and the default constructor for the second value.
DECLARE MOVIE x ( string = "hey there" , int = 2300 )In this case, you call the constructor with both arguments.
You may assume that the copy constructor assigns to a valid variable (i.e., it's been declared earlier). You may assume the values have correct syntax for the constructors taking 1 or 2 arguments. Again, look at the input file for a better understanding.
RUN operations are methods that don't return true or false. Currently, there's only one such method that is supported: the assignment statement.
MOVIE RUN y = x
VERIFY operations fall into several categories. They
are either methods that return true or false, as in setEarnings().
MOVIE VERIFY y . setEarnings ( 2000 )
Or they compare two movie variables using the relational operators you
defined.
MOVIE VERIFY == x y
n
You must handle all 6 relational operators. Or you can
compare the earnings of movies, using all 6 relational operators.
MOVIE VERIFY == y . getEarnings ( ) x . getEarnings ( )
Finally, there is PRINT, which allows you to print a movie variable.
MOVIE PRINT x
Most of the methods are implemented in MovieTester. You just need to complete the implementation for the remainder of the relational operators. Only == and != has been implemented for you.
<srtdcmmd> := "SORTED" <seps> [[ <srtddecl> | <srtdpr> |
<srtdrun> | <srtdverify> ]] <seps>
<srtddecl> := "DECLARE" <seps> <var>
[[ <seps> "=" <seps> <var> ]]?
<srtdpr> := "PRINT" <seps> <var>
<srtdrun> := "RUN" <seps> <var> <seps>
[[ <srtdassign> | <srtdclear> ]]
<srtdassign> := "=" <seps> <var>
<srtdclear> := "." <seps> "clear" <seps> "(" <seps> ")"
<srtdverify> := "VERIFY" <seps> <var> <seps> [[ <svmethod> | <svlist> ]]
<svmethod> := "." <seps>
[[ <srtdcontain> | <srtdremove> |
<srtdupdate> | <srtdadd> ]]
<srtdadd> := "add" <seps> "(" <seps> <var> <seps> ")"
<srtdupdate> := "update" <seps> "(" <seps> <var> <seps> ")"
<srtdremove> := "remove" <seps> "(" <seps> <dqsrting> <seps> ")"
<srtdcontain> := "contains" <seps> "(" <seps> <dqsrting> <seps> ")"
<svlist> := "<list>"
[[ <seps> <dqstring> <seps> <digits> ]]*
<seps> "</list>"
<svmethod> := <var> <seps> "." <seps>
[[ <srtdcontain> | <srtdremove> |
<srtdupdate> | <srtdadd> ]]
<srtdassign> := <var> <seps> "=" <seps> <var>
<srtdclear> := <var> <seps> "." <seps> "clear"
<seps> "(" <seps> ")"
<srtdadd> := <var> <seps> "." <seps> "add"
<seps> "(" <seps>
<var> <seps> ")"
<srtdupdate> := <var> <seps> "." <seps> "update"
<seps> "(" <seps>
<var> <seps> ")"
<srtdremove> := <var> <seps> "." <seps> "remove"
<seps> "(" <seps> <dqsrting> <seps> ")"
<srtdupdate> := <var> <seps> "." <seps> "update"
<seps> "(" <seps> <dqsrting> <seps> ")"
For a MovieSortedList, there are only two ways to declare:
SORTED DECLARE x
SORTED DECLARE x = y
SORTED RUN x = y
SORTED RUN x . clear ( )
In addition, there is a verify list, which verifies the list
elements. Here's an example:
<cmmd> SORTED VERIFY mList
<list>
"BATMAN" 3000
" Go Go" 1000
" RUN THERE" 2000
</list>
</cmmd>
It will be SORTED, followed by VERIFY, followed by
a valid variable name, followed by <list>, followed
by 0 or more occurrences of a movie in double quotes,
followed by the earnings.
The ordering is important. You must determine if mList contains BATMAN, Go Go, RUN THERE, in exactly that order, with the earnings 3000, 1000, 2000 for each movie. If mList contains fewer or more movies, or the earnings are different, or the order is different, then it fails to verify. Again, recall that movies are case-insentive, and two movies are equivalent based on the definition used by compare.
<arrcmmd> := "ARRAY" <seps> [[ <arrdecl> | <arrpr> |
<arrrun> | <arrverify> ]] <seps>
<arrdecl> := "DECLARE" <seps> <var>
[[ <seps> "=" <seps> <var> ]]?
<arrpr> := "PRINT" <seps> <var>
<arrrun> := "RUN" <seps> <var> <seps>
[[ <arrassign> | <arrclear> | <arrpush> ]]
<arrassign> := [[ <arrpassign> | <arrmassign> ]]
<arrpassign> := "=" <seps> <var>
<arrmassign> := "[" <seps> <udigits> <seps> "]" <seps> "=" <seps>
[[ <var> |
<var> <seps> "[" <seps> <udigits> <seps> "]" ]]
<arrclear> := "." <seps> "clear" <seps> "(" <seps> ")"
<arrpush> := "." <seps> "pushBack" <seps>
"(" <seps> <var> <seps> ")"
<arrverify> := "VERIFY" <seps> <var> <seps> [[ <avmethod> | <avlist> ]]
<avmethod> := "." <seps> [[ <arrresize> | <arrpop> ]]
<arrresize> := "resize" <seps> "(" <seps> <digits> <seps> ")"
<arrpop> := "popBack" <seps> "(" <seps> ")"
<avlist> := "<list>"
[[ <seps> <dqstring> <seps> <digits> ]]*
<seps> "</list>"
<arrpassign> := <var> <seps> "=" <seps> <var>
<arrmassign> := <var> <seps> "[" <seps> <udigits>
<seps> "]" <seps> "="
( <var> | <var> <seps> "[" <seps>
<udigits> <seps> "]"
<arrclear> := <var> <seps> "." <seps> "clear"
<seps> "(" <seps> ")"
<arrpush> := <var> <seps> "." <seps> "pushBack"
<seps> "(" <seps>
<var> <seps> ")"
<avmethod> := <var> <seps> "." <seps>
( <arrresize> | <arrpop> )
<arrresize> := <var> <seps> "." <seps> "resize"
<seps> "(" <digits> ")"
<arrpop> := <var> <seps> "." <seps> "popBack"
<seps> "(" <seps> ")"
The DECLARE and PRINT operations are the same as in MovieSortedList.
RUN operations can be an assignment statement (as before), a call
to clear() as before, or a call to a pushBack() where pushBack takes
a movie variable as argument. It can also call an assignment statement.
Either you can assign one MovieArrayList variable to another, or
you can use the operator[] to access a movie object in a MovieArrayList
object and set it to either a previously declared Movie variable
or to a movie object in the some MovieArrayList object.
Here are some possibilities:
ARRAY RUN x = y
ARRAY RUN x [ 1 ] = movie1
ARRAY RUN x [ 1 ] = y [ 0 ]
where x and y are MovieArrayList objects and
movie1 is a Movie object. You may assume all such
objects have been declared using a DECLARE operation.
The VERIFY operations apply to methods resize() which takes
an int value for a parameter (possibly, invalid) and pop() which
has no parameters. And, just as in the MovieSortedList BNF,
you can check to see if a movie array contains certain movies and
earnings:
<cmmd> ARRAY VERIFY aList
<list>
"BATMAN" 3000
" Go Go" 1000
" RUN THERE" 2000
</list>
</cmmd>
Again, the order matters. In order for this array list to verify,
you must have 3 elements, with "BATMAN"," Go Go", and " RUN THERE"
in that order, plus the three earnings in that order. It is possible
for a movie to be called "NONE", and show up multiple times (because
of the resize() operation), so keep that in mind.
<output> := <line>
[[ ["Input: " <digits> <endl> <out> <line>]+ |
"EMPTY COMMAND LIST" <endl> <line> ]]
<endl>
<stats>
<line> ::== "----*----*----*----*----*----*----*----*" <endl>
<output> := <line>
[[ [ "Input: " <digits> <endl> <out>
----*----*----*----*----*----*----*----*" <endl> ]+ |
"EMPTY COMMAND LIST" <endl> <line> ]]
<endl>
<stats>
<stats> := "Inputs verified: " [[ "NONE" |
<udigits> [", " <udigits>]* ]] <endl>
"Total positive inputs: " <udigits> <endl>
"Inputs not verified: " [[ "NONE" |
<udigits> [", " <udigits>]* ]] <endl>
"Total negative inputs: " <udigits> <endl>
"Total inputs checked: " <udigits> <endl>
<stats> := "Inputs verified: " [[ "NONE" | <udigits> [" ," <udigits>]+ ]] <endl>
"Total positive inputs: " <udigits> <endl>
"Inputs not verified: " ( "NONE" | <udigits> [ " ," <udigits> ]+ ) <endl>
"Total positive inputs: " <udigits> <endl> <endl>
"Total inputs checked: " <udigits> <endl>
There is a leading line, plus "Input: " and the input number.
The input number starts at 1, and continues up. Thus, if there
are n commands, the inputs are numbered 1 to n.
The output of each command is separated by a line.
If there are no commands, print "EMPTY COMMAND LIST" followed by a newline, followed by the fancy line.
After the list are statistics that print the results of commands with the word VERIFY appearing as the second word.
<mdeclareout> := "MOVIE DECLARE " <var> <endl>where the variable name is printed.
The output for RUN for a movie should be:
<mrunout> := "MOVIE RUN " <var> " assign" <endl>
where the variable name is printed, and "assign" is
printed if it's an assignment statement or "setEarnings"
is printed if that method is called.
<mrunout> := "MOVIE RUN " <var> " " ( "assign" | "setEarnings" ) <endl>
The output for PRINT should be:
======>(UPDATED BNF) (on Feb 19). No longer
prints "Title:".
<mprintout> := "MOVIE PRINT " <var> <endl>
<dquote> <title> <dquote>
" Earnings: " <udigits> <endl>
<title> := <word> [<blank> <word>]* [", " <word>]?
It should print the variable name. On the second
line, there should be the "Title: ", then a double quote,
then the proper title, then a double quote, then 3 spaces,
then "Earnings: ", then the earnings and a newline.
The output for VERIFY should be:
(NEW BNF)
<mverifyout> := "MOVIE VERIFY " <var> " " [[ <mverifyout> |
<mverifyoutset> ]]
<mverifyoutset> := "setEarnings " [[ "IS SUCCESSFUL" | "FAILS" ]] <endl>
<mverifyoutop> := <var> " " <op> " " [[ "IS SUCCESSFUL" | "FAILS" ]] <endl>
<op> := "==" | "!=" | "<" | "<=" | ">" | ">="
It should print out "IS SUCCESSFUL" if the comparison returns
true, and FAILS, if it returns false.
<mverifyoutset> := "MOVIE VERIFY " <var>
"setEarnings " [[ "IS SUCCESSFUL" | "FAILS" ]] <endl>
<mverifyoutop> := "MOVIE VERIFY " <var> " " <var> " "
<op> " " [[ "IS SUCCESSFUL" | "FAILS" ]] <endl>
(NEW) The first var is the name of the first variable, and the second var is the name of the second variable, when using relational operators. For setEarnings(), it's the name of the variable which setEarnings() is being applied to.
<sdeclareout> := "SORTED DECLARE " <var> <endl>where the variable name is printed.
The output for RUN for a MovieSortedList should be:
<srunout> := "SORTED RUN " <var> " " [[ "assign" | "clear" ]] <endl>
where the variable name is printed, and "assign" is
printed if it's an assignment statement or "clear"
is printed if that method is called.
The output for PRINT should be:
<sprintout> := "SORTED PRINT " <var> <endl>
[[ ["(" <udigits> ") " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl>]+ |
"THERE ARE NO MOVIES IN THIS LIST" <endl> ]]
<title> := <word> [<blank> <word>]* [", " <word>]?
This should print out "SORTED PRINT ", followed by the name of
the variable being printed, then a new line, then a list of
movies, as shown in the print() method of MovieSortedList,
or "THERE ARE NO MOVIES IN THIS LIST", if there are 0 movies in
the list.
<sprintout> ::== "SORTED PRINT " <var> <endl>
( [ <lparen> <udigits> <rparen>
" " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl> ] +
"THERE ARE NO MOVIES IN THIS LIST" <endl>
The output for VERIFY should be:
(NEW BNF)
<sverifyout> := "SORTED VERIFY " <var> <smethod> [[ "IS SUCCESSFUL" |
"FAILS" ]] <endl>
<smethod> := " add " | " remove " | " contains " | " update " | " LIST "
It should print out "IS SUCCESSFUL" if the method call returns
true, and FAILS, if it returns false. <smethod> refers to the
method that's being tested (e.g., add, remove, etc), except for
"LIST", which is when you check if the movie contains the list shown
between <list> and </list> (see sample input).
(NEW)
Now prints out variable name before the method.
<adeclareout> := "ARRAY DECLARE " <var> <endl>where the variable name is printed.
The output for RUN for a movie should be:
<arunout> := "ARRAY RUN " <var> [[ " assign" | " assign MOVIE" | " pushBack" |
" clear" ]] <endl>
where the variable name is printed.
<mrunout> := "ARRAY RUN " <var> " "
( "assign" | "assign MOVIE" | "setEarnings" ) <endl>
The output for PRINT should be:
<aprintout> := "ARRAY PRINT " <var> <endl>
[[ ["(" <udigits> ") " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl>]+ |
"THERE ARE NO MOVIES IN THIS LIST" <endl> ]]
<title> := <word> [<blank> <word>]* [", " <word>]?
This is the same format as for SORTED PRINT.
<aprintout> ::== "ARRAY PRINT " <var> <endl>
( [ <lparen> <udigits> <rparen>
" " <dquote> <title> <dquote>
" Earnings: " <udigits> <endl> ] +
"THERE ARE NO MOVIES IN THIS LIST" <endl>
The output for VERIFY should be:
(NEW BNF)
<averifyout> := "ARRAY VERIFY " <var> <amethod> [[ "IS SUCCESSFUL" |
"FAILS" ]] <endl>
<amethod> := " popBack " | " resize " | " LIST "
It should print out "IS SUCCESSFUL" if the method call returns
true, and FAILS, if it returns false. <smethod> refers to the
method that's being tested (e.g., pop, resize), except for "LIST",
which is when you check if the movie contains the list shown between
<list> and </list> (see sample input).
(NEW)
Now prints out variable name before the method.
A style guide will be posted. In the meanwhile, read the background reading on documentation, and follow the style guide given in Project 0.
In addition, to the documentation specifications, here are several style rules to follow.
for (int i=0;i<n;i++)
func(arg1,arg2,i);
write it as:
for (int i=0; i<n; i++)
func(arg1, arg2, i);
Notice the single space after each comma and semicolon.
for (int i=0; i<n; i++)
if (i!=3)
func(arg1, arg2, i);
You would write:
for (int i = 0; i < n; i++)
if (i != 3)
func(arg1, arg2, i);
In the README, indicate which classes you implemented the copy
constructor, assignment operator, and destructor. For example:
Implemented copy constructor, assignment operator, and destructor
for following classes
------------------------------------------------------------------
Foo
Didn't implement it for
-----------------------
Bar
Briefly explain why you implemented or didn't implement
for the classes listed.
Second, indicate which kind of "locate()" method you used. These are the four choices. If you picked something else, describe the algorithm.
How I implemented locate() -------------------------- // fill in stuff hereFinally, write the pseudocde for your "add" method. Indicate the running time for ad
Pseudocode for add ------------------ // fill in stuff hereMake sure you label the README file so we know who you are, which section, etc.
Initially, you were told to create separate files for test drivers. However, this makes it inconvenient for compiling. So, instead, create a static method called EXACTLY runTestDriver() which takes no arguments. Add this to the PUBLIC section of your class declaration (in the .h file), as in:
public:
static void runTestDriver();
All the code you used to test your class should go into
this method in the corresponding .cpp file. If your
file used helper methods, e.g., testDriverCheckCopy(), then
those should be static methods. However, these methods should
start with the word "testDriver", so we can tell they are
methods used by your test driver. Thus:
static void testDriverCheckCopy(); // checks copy cons
This can be placed in public or private section
of your class header file (preferably, private).
For this project, it will be optional to have verify methods. These are used to test preconditions, postconditions, and class invariants.
This is how you would use it, if you wanted to. First,
declare a private variable called "checkContract" and
have methods that will set it to true or false (setCheckContract(),
which takes a bool argument). Then, in you might have code that
looks like:
void pop()
{
if ( checkContract )
if ( popPrecond() && stackClassInvariant() )
cout << "POP PRECONDITION SUCCESSFUL" << endl;
else
cout << "POP PRECONDITION FAILS" << endl;
// code
if ( checkContract )
if ( popPostcond() && stackClassInvariant() )
cout << "POP POSTCONDITION SUCCESSFUL" << endl;
else
cout << "POP POSTCONDITION FAILS" << endl;
}
where popPrecond(), popPostcond(), stackClassInvariant()
are boolean methods which return true or false, and check for whether
code is implemented correctly.
You could cause the program to exit if the condition fails, forcing the programmer to fix it as errors occur.
The checkContract variable, when true, is used to check the preconditions, postcondition, and class invariants. However, such checking is often "expensive" (meaning, slow). So, it's handy to have a way to turn it off.
Again, this is optional, and should only be done when the project is completed. However, it's usually best to think of these invariants AS you develop the class, and put the code as methods are being developed. Doing it after the fact tends to defeat the purpose (although if the tests fail, you know you haven't tested enough).
Also, for MovieArrayList, 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.
p1 < primary.input
Your program MUST produce the executable p1, EXACTLY, when
the command "make" is run with no arguments. Thus, you must use
a makefile named exactly "Makefile".
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 p1.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 p1.tar 1
where p1.tar can be replaced by whichever tar file you
have created, and 1 refers to the current project,
|
See the class syllabus for policies concerning email Last Modified: Tue Feb 12 19:48:57 EST 2002 |
|
|
|
|
|