-
What to do?
-
If you're done with the two template classes, and need some
guidance:
-
Purpose
-
The purpose of the Project 2:
- To learn how to modify existing code, and test thoroughly,
as such changes are being made.
- To write a sorted, doubly linked list class as a template class.
- To write a unsorted, dynamic array class as a template class.
(Basically, you are implementing a version of vector).
- To write iterators, nodes as nested classes inside the list class.
- To write iterators for the vector class.
- To write a template function that sorts the vector class
- To write a template function that removes duplicates
- To write comments based on CMSC 214 Style Specifications.
- To extend the features of the MUD.
-
Checklist
-
A link to a checklist will be provided. You should read the
checklist several times, but especially before submitting your
project.
-
Style Guide
-
A style guide will be created soon.
-
FAQ
-
We will provide corrections and announcements, as well as
"frequently asked questions" on the Project 2
FAQ page.
-
Project Overview
-
You will create two kinds of template class: a list class, which
will be implemented using a doubly linked list, and a
vector class, which will be implemented using a dynamic array.
The program you write will support additional commands
and more sophisticated inputs.
As with Project 1, this project will be released in parts.
This is the current, expected way to develop your project.
- You will be provided Movie.h, Movie.cpp,
and MovieSortedList.h.
- Implement MovieSortedList.cpp. This is NOT a template
class.
- You will be provided a minimal SortedList.h,
which will be a template class version of MovieSortedList.h,
where Movie will be replaced by Data and string
(which is the movie's title), will be replaced Key. Both
Data and Key are template type parameters.
- Implement SortedList.cpp, a template class,
by converting MovieSortedList.cpp to a template.
(One reason to write a non-template class and convert it, is that
it's easier to debug non-template classes).
- You will be provided MovieArrayList.h. Implement
MovieArrayList.cpp. This is NOT a template class.
- You will be provided with a minimal ArrayList.h,
a template class. This is similar to a "vector" class in STL.
- You will implement ArrayList.cpp, a template class,
by converting MovieArrayList.cpp into a template class.
- You will be provided a new Parser header files. This will
combine four parsers together: DungeonParser, PlayerInputParser,
TeamInputParser, and RobotInputParser (if there had been
a RobotInputParser, which there wasn't). This will be
in a file called Parser.h.
- CommandParser will be about the same, except, you
should add vector<Robot> (eventually to be changed to
ArrayList<Robot>) as a new data member.
- Before adding any new commands, you should make sure the original
commands still work. Since you will be modifying original code, it's
helpful to make those changes one at a time, and test, test, test.
NOTE: It's a good idea to test the SortedList and
ArrayList classes thoroughly, before incorporating it into
your other classes. Don't implement new commands until the changes
have been made. You implement one set of changes first (for example,
incorporate SortedList into your code first, then debug, then
ArrayList, then debug).
-
Files Provided
-
Files That Aren't Needed in Project 2
You shouldn't need the following files:
- Any of the files in Part 1.
- PlayerList.cpp or PlayerList.h. These
two files will be replaced by Team.cpp and Team.h
- PlayerInputParser.cpp, PlayerInputParser.h,
TeamInputParser.cpp, TeamInputParser.h,
DungeonParser.cpp, DuneongParser.h. Instead,
most of the functions will be moved into the file
Parser.cpp, Parser.h.
- Any Node or Iterator classes. They will
now be part of the SortedList and ArrayList
classes.
You will need the code in these files, but they will be reorganized
into other classes.
Files You Still Need from Project 1
- Player class.
- Name class.
- Item class.
- Room class.
- AllTeamsList class.
- CommandParser class.
- ReadTag file.
Files Provided
- Movie class.
- MovieSortedListDriver.cpp file.
- MovieSortedList.h file.
- MovieArrayList.h file.
- SortedList.h file.
- ArrayList.h file.
- Parser.h file.
- main.cpp file.
Files You Write
-
Background Reading
-
Background readings will be provided. The main topic will
be nested classes.
Nested classes
Read about nested classes here.
Operator++/--
Read about operator++/-- lists here.
-
Useful BNF
-
This uses extended BNF. See "background readings above".
<lower> ::== "a" | "b" | "c" | "d" | "e" | "f" |
"g" | "h" | "i" | "j" | "k" |
"l" | "m" | "n" | "o" | "p" |
"q" | "r" | "s" | "t" | "u" |
"v" | "w" | "x" | "y" | "z"
<upper> ::== "A" | "B" | "C" | "D" | "E" | "F" |
"G" | "H" | "I" | "J" | "K" |
"L" | "M" | "N" | "O" | "P" |
"Q" | "R" | "S" | "T" | "U" |
"V" | "W" | "X" | "Y" | "Z"
<alpha> ::== <lower> | <upper>
<digit> ::== "0" | "1" | "2" | "3" | "4" |
"5" | "6" | "7" | "8" | "9"
<digits> ::== [ <digit> ]+
<empty> ::==
<endl> ::== "\n"
<left> ::== "<"
<right> ::== ">"
<tag> ::== <left> <word> <right>
<under> ::== "_"
<blank> ::== " "
<blanks> ::== [ <blank> ]+
<mblanks> ::== [ <blank> ]+
<sep> ::== <blank> | <endl>
<seps> ::== [ <blank> ]+
<mseps> ::== [ <blank> ]*
<word> ::== <alpha> [ <alpha> | <digit> | <under> ]*
-
Input File BNF
-
The input file looks the same, except there is an additional
section for information about robots. See primary input for
an example.
<list_of_robots> ::== <left> "rlist" <right> <seps>
[ <onerobot> <seps> ]+
<left> "/rlist" <right>
<onerobot> ::== <left> "robot" <right> <seps>
<onename> <seps> <onestrength> <seps>
<listofitems>
<left> "/robot" <right>
<listofitems> ::== <left> "itemlist" <right> <seps>
( <empty> | [ <oneitem> [ <seps> <oneitem> ]+ ] )
<left> "/itemlist" <right>
Notice that <listofitems> has been redefined so the
list of items may be empty. This definition supercedes the definition
in Project 1, which assumed there was at least one item in every room.
Use Project 1 BNF for any non-terminals that are not explained here
(e.g. <onename>).
-
Input File Format
-
See primary input.
-
Commands/Output File BNF
-
The list of commands are the same as before, but now they apply to
robots. Here are the modification of the commands, as they apply to
robots.
Note:
<robotname> ::== <firstname> <blank> <lastname>
- JOIN_TEAM
JOIN_TEAM <seps> <robotname> <seps> <teamname>
Robots can't join teams. Therefore, you should print:
<join_team_out> ::== "[JOIN_TEAM] Robot (" <robotname> ") can't join a team"
<endl> <endl>
- WHICH_TEAM
WHICH_TEAM <seps> <robotname>
Since a robot can't be on any team, then print:
<which_team_rob_out> ::== "[WHICH_TEAM] "
"Robot (" <robotname> ") is not on any team"
- GOTO_ROOM
GOTO_ROOM <seps> <robotname> <seps> <roomname>
Like a player, a robot can go to any room.
<rob_goto_room_out> ::== "[GOTO_ROOM] "
( <rob_goto_room_switch> | <rob_goto_room_first> |
<rob_goto_room_stay> ) <endl> <endl>
<rob_goto_room_switch> ::== "Robot (" <robotname> ") leaves room ("
<roomname> ") and enters room ("
<roomname> ")"
<rob_goto_room_first> ::== "Robot (" <robotname> ") enters room ("
<roomname> ")"
<rob_goto_room_stay> ::== "Robot (" <robotname> ") is already in room ("
<roomname> ")"
- DISP_ROOM
DISP_ROOM <seps> <roomname>
Display the contents of the room. This includes the items
in the room as well as the people in the room. You may assume
the room name is valid. This will now include robots.
<disp_room_out> ::== "[DISP_ROOM]" <endl>
<list_of_items_out> <endl> <endl>
<list_of_players_out> <endl> <endl>
<list_of_robots_out> <endl> <endl>
<list_of_items_out> ::== "List of items in room: (" <roomname>
")" <endl>
"----*----*----*----*----*----*" <endl>
( <no_items> | <item_list_out> )
<no_items> ::== " NO ITEMS IN ROOM"
<item_list_out> ::== <one_item_out> [ <endl> <one_item_out> ]+
<one_item_out> ::== "(" <digit> ") Name: " <word>
" Id: " <digit>{4,4}
" Weight: " <digits> " Cost: " <digits>
<list_of_players_out> ::== "List of players in room: (" <roomname>
")" <endl>
"----*----*----*----*----*----*" <endl>
( <no_players> | <player_list_out> )
<no_players> ::== " NO PLAYERS IN ROOM"
<player_list_out> ::== <one_player_out> [ <endl> <one_player_out> ]+
<one_player_out> ::== " (" <digit> ") " <lastname> ", " <firstname>
<list_of_robots_out> ::== "List of robots in room: (" <roomname>
")" <endl>
"----*----*----*----*----*----*" <endl>
( <no_robots> | <robot_list_out> )
<no_robots> ::== " NO ROBOTS IN ROOM"
<robot_list_out> ::== <one_robot_out> [ <endl> <one_robot_out> ]+
<one_robot_out> ::== " (" <digit> ") " <lastname> ", " <firstname>
- LIST_TEAM_MEMBERS
LIST_TEAM_MEMBERS <seps> <teamname>
Since robots can't appear on any team, this command remains
the same as Project 1 (except the dashes have now been replaced
by the ones shown above).
- LIST_TEAM_MEMBERS_REV
LIST_TEAM_MEMBERS_REV <seps> <teamname>
Since robots can't appear on any team, this command remains
the same as Project 1 (except the dashes have now been replaced
by the ones shown above).
- ADD_GOLD
ADD_GOLD <seps> <teamname> <seps> <digits>
Since robots can't appear on any team, this command remains
the same as Project 1 (except the dashes have now been replaced
by the ones shown above).
- PICKUP
PICKUP <seps> <robotname> <seps> <itemname>
Unlike players, robots can pick up any item. Their strength
has nothing to do with their ability to lift items.
<rob_pickup_out> ::== "[PICKUP] "
( <rob_pickup_not_in_room> | <rob_pickup_no_item> |
<rob_pickup_success> )
<endl> <endl>
<rob_pickup_not_in_room> ::== "Robot (" <robotname>
") is not in any room"
<rob_pickup_no_item> ::== "Robot (" <robotname> ") " could not pick up ("
<itemname> "): (" <itemname> ") not in room"
<rob_pickup_success> ::== "Robot (" <robotname> ") " successfully pick up ("
<itemname> ":id " <digits>{4,4}
") from room (" <roomname> ")"
- DROP
DROP <seps> <robotname> <seps> <itemname>
This command is similar to that for players.
<rob_drop_out> ::== "[DROP] " ( <rob_drop_not_carry> | <rob_drop_success> )
<endl> <endl>
<rob_drop_not_carry> ::== "Robot (" <playername> ") is not carrying ("
<itemname> ")"
<rob_drop_success> ::== "Robot (" <playername> ") " dropped ("
<itemname> ":id " <digits>{4,4}
") in room (" <roomname> ")"
- DISP_TREASURE
DISP_TREASURE <seps> <robotname>
In addition to being able to display treasure for a team
or player, you can now display the treasure held by a robot.
<disp_treasure_out> ::== "[DISP_TREASURE]" <endl> <disp_treasure>
<endl> <endl>
<disp_robot> ::== " Treasure for robot (" <robotname> ")" <endl>
" ----*----*----*----*----*----*" <endl>
( <robot_treasure> | <robot_notreasure> ) <endl>
" ----*----*----*----*----*----*" <endl>
<robot_notreasure> ::== " NO TREASURE"
<robot_treasure> ::== " " <one_item_out> [ " " <endl> <one_item_out> ]+
- INVALID
<word> [ <seps> <word> ]+
Any other command is considered invalid. Such a command
may contain one or more invalid words. You must ignore these
so that the next command can be read properly.
-
Updates of BNF
-
Whenever the output says to print "MEMBERS", print "PLAYERS"
instead.
- DISP_ROOM if there are no players, it should say
"NO PLAYERS IN ROOM".
- LIST_TEAM_MEMBERS should say "NO PLAYERS ON THIS TEAM"
- LIST_TEAM_MEMBERS_REV should say "NO PLAYERS ON THIS TEAM"
- DISP_TREASURE should say "THIS TEAM HAS NO PLAYERS"
-
No STL
-
In this project, you won't use any STL. If you do, you
will lose 100 points. The only exception is strings. You
can use strings, since they technically part of STL. (Avoid
using vectors, algorithms, etc).
-
Assumptions
-
- The only new assumption is that robots can't join any team.
- Of course, just as last time, if there are no relevant error messages,
you can assume that the error won't occur. However, this doesn't
mean you shouldn't produce error messages of your own (which indicate
when something has gone wrong). You should do that for debugging
purposes.
-
Description of Files
-
Movie.h/Movie.cpp
These files have been provided to you. Movie is a very
simple class. The most important feature of this class (which allows
it to be stored in a SortedList class) is the
getKey() method. getKey() returns a key, which is
used to sort the Movie when it is placed in a
SortedList or MovieSortedList object.
Having a getKey() method isn't absolutely necessary
(although we use it in Project 2). In fact, in ArrayList and
MovieArrayList, you will be sorting using
operator< and operator== on Movie
objects, just as STL does. As you will notice, Movie does
not yet define those operators. You should define those operators in
Movie.
MovieSortedList.h
This stores a doubly linked list of MovieSortedList::Node
objects. Each of these objects contains a Movie object
stored by value. You should be able to conver your code for
Node, PlayerList, Iterator and
ConstIterator and place them into MovieSortedList.
You will notice that Node, ConstIterator,
and Iterator are now nested classes, and are not in
their own files.
Node nested class
Most of these operators should be familiar to you now, so they
won't be explained. However there are a few key changes.
- Movie, the object being stored in the Node
nested class, is now stored by value. It is not stored as a pointer.
Therefore, there is no need to dynamically allocate a Movie
object.
- The getKey() method is used to return the title
of the Movie. The key is what the movie is sorted
on, if one chooses to sort movies. This becomes important
when developing a template class. There will need to be some
method (in this case, getKey()) that one can use to sort.
Iterator nested class
There have been bigger changes to the iterator class to make
it look closer to the STL iterator classes. Let's look
at these changes.
- The Iterator class now stores a single pointer,
instead of three pointers. It points to the current object.
- Instead of using goNext and goPrev, you
will replace these with operator++ and operator--,
respectively. These operators come in prefix/postfix variations.
You must determine the prototypes for prefix/postfix (these
should be covered in a reasonable textbook on C++) versions of
these operators.
- operator++ should move the pointer forward as long
as it is pointing to a valid Node object (the only invalid
one will be NULL). It should return itself as a reference.
- operator-- should move the pointer backward as long
as it is pointing to a valid Node object (the only invalid
one will be NULL). It should return itself as a reference.
- operator== determines whether two iterators are
pointing to the same Node object. Returns true
if so.
- operator!= determines whether two iterators are
pointing to the same Node object. Returns false
if so.
- Instead of getCurrent(), you use the dereferencing
operator * to access the Movie reference.
This is treating the iterator as if it were a pointer (which it
isn't---but it does contain a pointer).
The ConstIterator nested class is similar, except it
provides two versions of the operator* operator.
You will also notice it's not necessary to implement copy
constructors, assignment operators, nor destructors since the
iterator classes do not perform any deep copies.
MovieSortedList main class
Most of the methods are the same as before. However, there
are a few new methods. In particular, the methods that return
constructors have changed.
- first() returns an Iterator that points to the
first node in the doubly linked list.
- cfirst() returns a ConstIterator that
points to the first node in the doubly linked list.
- last() returns an Iterator that points to the
last node in the doubly linked list.
- clast() returns a ConstIterator that
points to the last node in the doubly linked list.
- end() returns an Iterator that points to
the "node" (there is none) after the last node. This is called
the "one past the end" iterator, and really is just an iterator
with a pointer to NULL.
- cend() returns a ConstIterator that points to
the "node" (there is none) after the last node. This is called
the "one past the end" iterator, and really is just an iterator
with a pointer to NULL.
Again, it's not quite like the STL iterators (alas!). For example,
in an STL iterator, you would be able to create a regular iterator
and save it to a const iterator. As set up now, that's not quite possible.
This is why there are two versions of the iterators.
MovieArrayList.h
A MovieArrayList object attempts to emulate a specific
vector. You will templatize this class to create a ArrayList
class which is similar to the STL vector (not quite!).
You must observe the following restrictions:
- the number of elements in the dynamic array must be
exactly the number of elements being used. Thus, if
the user expect 10 elements, it must have 10 elements.
- The exception is when the listSize is 0.
Then, arr can be NULL, or it can be an array of
size 0 (which still must be allocated/deallocated). It's
usually easier to make it NULL.
There is no Node nested class for MovieArrayList.
Iterator nested class
curr will hold the address of the current array element.
For example, if the iterator is pointing to element 2 of the
array list, then curr equals & arr[ 2 ].
You can use pointer arithmetic to move the pointer forward
by "n" elements or backward by "n" elements.
- operator* will return a reference to the Movie
which curr is pointing to. It's OK if this causes
a core dump, if curr is not pointing to an element in
the array.
- operator-> will return a curr.
Yes, as it turns out, you can overload this operator. This
must be a new change to C++, which allows the use of "smart
pointers" (iterators are considered smart pointers).
- operator++ and operator-- behave as
expected, moving the pointer forward by one and backward by one.
The postfix versions should behave by creating a temporary copy
of the iterator, then moving the pointer in the original, then
returning the copy (thus, they return iterators by value).
- operator+ and operator- attempt to emulate
pointer arithmetic. Merely return curr plus (or minus)
the offset. It uses "real" pointer arithmetic, to implement this.
- operator<, operator<=,
operator>, operator>=,
operator==;, operator!= compare the location
of iterators. For example, operator< returns true
if an iterator points to a position with a smaller index
in an array than another iterator. This is easy to implement.
Just compare the addresses. If the curr from "this" object
is smaller than the address from the "other" object, return true.
Do similar for other operators.
The ConstIterator methods are similar to the
Iterator methods except fewer methods are offered.
For example, there's only const versions of operator*
and operator->.
MovieArrayList main class
- operator[] allows random access. You don't
have to check for valid indexes (if the index is invalid, it
can core dump). It returns the object stored at the index
passed in as the parameter. There's a const and non-const
version of this operator.
- resize causes the dynamic array to be resized.
If the new size is the same as old one, or if the new size
is negative, then don't change the array at all. However,
if the new size is different and non-negative (possibly 0),
then you can resize it. You will need to create a new
dynamic array, and copy over the elements. If the array
size increases, then the new elements must be constructed
using the default Movie object (fortunately, it does this
automatically). You must copy the corresponding elements of the
old array to the new array, and then delete the old array.
- pushBack adds one element at the back. The
size increases by one. Note: you will need to create a new
dynamic array with an increased size.
- popBack removes the element at the back, if the
size is positive. (Do nothing if the size is 0). The
size decreases by one. Note: you will need to create a new
dynamic array with an decreased size.
- erase removes the element pointed to by the
iterator. This will be the toughest method to implement.
It requires using nearly all the features of the iterator
(such as comparison operators). You can't make Iterator
a friend to accomplish this task.
- size returns the number of elements in the array.
- clear makes the size of the array 0, possibly
deleting the dynamic array (depending on your implementation).
- first returns an iterator that points to the
first element of the dynamic array.
- cfirst returns an const iterator that points to the
first element of the dynamic array.
- end returns an iterator that points to one past
the last element of the array (this can be done, by taking the
address of arr[ listSize ]).
- cend returns an const iterator that points to the
one past the last element of the array.
-
Special Methods
-
For each class you write, you must determine whether to write
the following methods:
- copy constructor
- destructor
- operator=
Recall that all three methods should be written as a group
or not at all. You should use these methods if the class
allocates dynamic memory via "new" and deallocates via "delete".
If it is NOT necessary to implement these methods, then do
NOT implement. By necessary, this means the class would behave
incorrectly (especially, if, say, only the destructor were
defined).
If you do choose to write these three methods, you should
write the following helper methods.
- init() behaves like default constructor
- freeMem() behaves like destructor
- copy() behaves like copy constructor
and use these methods to help implement the default
constructor, destructor, operator=, and copy constructor.
-
Requirements/Restrictions
-
The following requirements/restrictions should be observed.
- The program should compile with g++ with the -Wall
option. You may use cxx to test, but make sure it runs with
g++ as well.
- You should comment code. You will be given instructions
on how to do this later on.
- You should use namespaces. In particular, in your .h files (ONLY),
all of objects should
- You should use namespaces. In particular, in your .cpp files,
you should write "using namespace std".
- Hardcoded outputs will be severely penalized.
- Write helper functions. You will gain more credit if you do.
They should be clearly labelled as helper functions.
-
How to Submit Your Project
-
As with Project 1
submit p2.tar 2 SUBMIT
You can name the tar whatever you want. However, you should
wait until a primary input and output have been posted. (If you
submit before that, then if your project does not pass the
primary input/output, you will receive a poor grade on the project,
most likely a zero).
-
Academic Integrity Statement
-
Any evidence of unauthorized use of computer accounts or cooperation on
projects will be submitted to the Student Honor Council, which could result
in an XF for the course, suspension, or expulsion from the University.
Projects are to be written INDIVIDUALLY. For academic honesty
purposes, projects are to be considered comparable to a take-home exam. Any
cooperation or exchange of ideas which would be prohibited on an exam is
prohibited on a project assignment, and WILL BE REPORTED to the Honor Council.
VIOLATIONS OF ACADEMIC HONESTY INCLUDE:
- failing to do all or any of the work on a project by yourself,
other than assistance from the instructional staff.
- using any ideas or any part of another student's project, or
copying any other individual's work in any way.
- giving any parts or ideas from your project, including test data, to
another student.
- having programs on an open account or on a PC that other students
can access.
- transferring any part of a project to or from another student or
individual by any means, electronic or otherwise.
- publishing any of your code publicly (e.g., via a webpage)
which other students can access, even if the project is already due.
IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY
STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT
TO THEIR INSTRUCTOR.