|
|
c m s c 214
f a l l 2 0 0 1 |
No. You could do it and get it to work, but it makes more sense to use a pointer.
Basically, you have some sort of memory error. Just think of it as a core dump that doesn't produce a core dump. This makes it harder to find, but it has little to do with your quota, or really running out of memory (by, for example, allocating too much stuff).
Since you are creating 3 executables, it may be quite large
(up to several Megs), and therefore exceed your quota. If you
need some temporary space, do the following:
% cd /tmp
% mkdir FOO
% chmod 700 FOO
% cd FOO
% cp ~/P1/proj1.tar .
% submit proj1.tar 1 TEMP
% cp -R TEMP ~/P1/
The last line will copy the TEMP into your directory, so you
have a copy of what happened.
Yes, a player can pick up and drop objects, etc., even while not on any team.
Yes, if you can figure out how to use it. It's not necessary, however. There are other ways to do it.
The sum of the weights of all items carried by the player must be less than or equal to the strength of the player.
Also, the player always attempts to pick an item up of the given name with the smallest ID. If this is too heavy, the player does NOT attempt to pick up other items with the same name and a larger ID.
You could, but I wouldn't. Part of the reason for putting a vector in a class is to hide the fact that it is a vector. Once you create a "get" method, you will expose the fact that it is a vector, and be unable to change it later on.
By that, I mean, when you design a class, usually the user expects the interface stays unchanged, while private data members could change. Obviously, you could change the interface, and make the user deal with it, but that may not always be desirable.
Instead, you can opt for a different solution. If you need to find out if a user is on a team, add a method like whichTeam() which returns a string (or a pointer to a PlayerList) which is a valid team name if the player is on a team or "NONE" if not on a team (I won't use NONE as a team name).
This way, the user doesn't have to see the vector. Admittedly, the user does see the doubly linked list, so that's not hidden nearly as well as it should be.
Suppose you had the following method
void Foo::setPrice( float priceIn )
{
}
How would you implement this? Probably as "price = priceIn".
Normally, set functions simply copy the value to the data members,
possibly doing some error checking to see if the value is valid.
However, some folks are making this task more challenging than they have to, merely because next and prev are pointers. They do some dynamic allocation or something. This isn't really needed. Use the "set" methods when you want to assign to a data member, and "get" methods when you want t retrieve their values. This should even be the case for pointers.
Occasionally, you may have to break the rule, but not in this case.
The answer for this has to be yes. The reason is the following. Suppose you want to iterate across a list. You will need to stop. The only method that lets you know whether you should stop or not is inList(). If curr points to the last element of a list, inList() will claim it's still in the list. Thus, if you try to print, you will get an infinite loop. Not good!
You don't want it to say that it's not in the list when it points to the last element either, because if you do that, then you won't be able to print the last element (and it won't work if you attempt to print backwards).
This is a very good observation, in fact, it is the observation I wanted students to make, and to me, constitutes the "trickiest" thing (other than being careful how to pick up objects) in the project.
While you can maintain two objects, it really makes little sense to do so. Here's something to think about however. Look at the PlayerList and consider the add() method. Why does it pass a pointer and not a const reference? Perhaps that can give you some clue as to how to manage things with only one Player object.
Not precisely. If you do not write any constructor, the compiler creates a default constructor for you. It also creates an implicit copy constructor when you don't define your own copy constructor. If you define any constructor, the default constructor disappears, and you must define a default constructor.
Since no constructor was defined, a default one is defined. That version is very simple. It calls memberwise default constructors on each of the data members. There's only a vector, so it calls its default constructor which merely creates an vector of size 0. Since vectors define their own copy constructors, etc. and they do what's required, there's no need to write your own copy constructor.
No. A class should be a "black box" and should be implemented correctly. This means that it should take care of it's own dynamic allocation and deallocation, and if you're using it, you shouldn't have to be aware of it at all.
When you copy an object, it will copy the data members using the data member's copy constructor or assignment operator. Either way, that data member will take care of itself.
The only time the class has to worry about defining copy constructors, etc. is if there's dynamic allocation that it must handle itself. This means, there must be calls to "new" and "delete". This doesn't happen if the class doesn't contain pointers (unless you are doing something particularly unusual). Even then (as with iterators), having pointers doesn't imply the need write copy constructors, etc. (although it often does).
You are supposed to determine, for most classes, whether to write:
The issue at hand is "should I make a deep or shallow copy"? A "deep copy" is when you copy all the nodes, etc, so that each individual object has an entire copy of the dynamic memory. A "shallow copy" only copies pointers. (Hint: iterators only require shallow copies, while linked lists require deep copies).
You shouldn't say "it isn't necessary because we never call the copy constructor for the object in this assignment". Basically, the idea is to imagine you are writing the "class" for other people's use. Surely, they will want to copy the object (unless you expressly forbid it---which is rather uncommon).
Again, don't perceive yourself as a person who writes classes to get the project to work, but as a person who writes classes so other people can use them. This perspective helps to you to determine (1) is this method useful to a user, (2) should I implement this for their use?
Admittedly, you might discover all sorts of methods that would be useful to the user, but not important to the project, and would therefore be too time consuming to write. In that case, you wouldn't implement it. At the very least though, assume the user will want to copy/destroy the object, and want a correct implementation of the above. At that point, determine whether the built in constructor/destructor/assignment operator is good enough.
Yes, you will need to do so for Part 2. This is part of the thinking process. You may not be able to determine which methods you need right away, but as you implement the commands, you will see you amy need additional methods, etc. I would avoid adding such methods for Part 1, since you really don't need anything new. But definitely, you can use change/add methods for Part 2.
There is a restriction about returning the entire "treasure" vector for Player. The purpose of that is to hide the fact that there is a vector to the user. You may however, return back references, or pointers to individual Items in the treasure.
The first thing to do is not to panic. Even if were an error on my part (and it isn't this time), your best bet would be to read the error messages and determine where the error is occuring.
Some of you have realized the error occurs on the line where it calls sort. Read the STL tutorial (there's a link on the Project 1 webpage) and read the requirements for being able to sort.
It should be an easy matter of updating a different file so that the DungeonParser file works.
Recall that you should define all three:
Several students have defined the destructor, but not the copy constructor or assignment operator.
vectors need to copy and assign objects, and may call the destructor. If it does so, and the copy constructor/assignment operator is not defined, but the destructor is, then the linked list will disappear. So, write a copy constructor/assignment operator.
You are restricted to implement this project using material covered in class. Since we haven't talked about creating function or class templates, you can't create them in your project.
However, you can use more features of the STL vector, if you can find information. Don't use inheritance, binary search trees, etc. They will appear in future projects.
No. The money refers to "gold pieces". These are coins. Treasure, on the other hand, are not coins. They will be items such as swords, rings, etc.
Yes, it does. The player now has the item, and the room does not. Although there are no duplicate items (two items with the same names and ID), you should still check whether a Player (or room) has the item or not, and only add it when it does not (although this check will always show that a player does not have the item).
If a player drops the item, the room then has the item.
No. It stays the same. The strength represents how much a player can lift, not how much more they can lift.
Recall that AllRankingLists contains a vector of RankingList. Each of the RankingList has a school name. If any of the schools have the same name as the parameter passed in, return true, else return false.
Ask yourself, does it make any sense whatsoever to copy curr and prev? Draw a picture and you will see it does not make sense. Simply set them to NULL, and you should be OK.
Click on "From Charles" in the front webpage. Then, print the second day review. It goes over "copy()".
But basically, the copy is just a name of a function which will act exactly like the copy constructor. Its purpose is to allow the copy constructor to call it, and then to have the assignment operator call it as well.
Here's what's supposed to happen:
void copy( const Foo &foo )
{
init(); // some initialization
// copy foo to this, just as you would if it were a copy constructor
}
Foo::Foo( const Foo &foo )
{
copy( foo ); // calls copy defined above
}
Foo &Foo::operator=( const Foo &other )
{
if ( this != &other )
{
freeMem();
copy( foo ); // copy called here too
}
return *this;
}
The purpose of defining this copy is "code centralization", i.e.,
avoiding the copying of code.
The locate was explained in the first quiz worksheet. This worksheet was available in the posting account as well, and the TAs should have explained it during lab. Nevertheless, it seems like few people understood it, or studied it.
Here's a solution for a successor locate using "curr", "prev".
Note: "curr" and "prev" are local variables, not data members.
The restriction for "curr" and "prev" are as data members.
bool List::locate( Node *&curr, Node *&prev, int search )
{
prev = NULL;
curr = first;
while ( curr != NULL && search > curr->getKey() )
{
prev = curr;
curr = curr->getNext();
}
// added Sept. 21
return ( curr != NULL && curr->getKey() == search );
}
bool List::add( int val )
{
Node *curr, *prev; // local variables!
if ( ! locate( curr, prev, val ) )
{
// add more code
}
}
You can basically ignore those lines. Those lines are usually there when there is a circular dependence on class files (for example, class A depends on class B, and class B depends on A). You generally need a class declaration, otherwise, you run into compiler errors.
My motivation was twofold. The bad reason is that I wasn't ready to post the project when I said I was, and so I posted something that was simpler than what you had to implement.
However, there's a second reason. This is a large project. If I had given it in one part (as I originally planned), then most people would have tackled the project from the start (processing the input, etc). and wondered how all the parts fit together. It may have taken a long time before people started to code the doubly linked list.
One way to learn how to write a doubly linked list is to write a simple doubly linked list. Many people think it's a waste of time to do it, but in many respects, it's a very smart way to start. If you make a doubly linked list of Player, you will devote a lot of time to writing Player, and it may be difficult to separate problems with the doubly linked list, with problems in the Player class.
You should discover that it's very easy to implement a PlayerList class once you have developed a RankingList class. That's precisely the point. Making a "simple" class which you can test quickly, can often make writing harder versions of the class quicker too.
In fact, you should discover that a doubly linked list is a doubly linked list, regardless of what the list stores.
Yes it should be something else besides TEAM_H. That was the old name for PlayerList. You can change it if you want, but you aren't required to change it.
Iterators are meant to be used by the user to access the list, without letting the user "see" the Node class. Even though it would be nice to have implement locate() using iterators, this inability to access Node prevents it from being used.
If you want, you can create a InternalIterator class, to be used only by the RankingList or PlayerList class, but that might be too much work (although feel free to do so).
To answer the second question, you don't have to, but it might be nice, just to get some practice using iterators.
Technically, it's not possible. However, the point of having a sorted list with no repeats is that you should reject attempts to add new elements to the list, if they have a key that's equal to some key in the list.
With an item, there's never going to be the opportunity that two items have the same name and same ID. However, you should still CHECK that the Player does not have an item by the same name and ID.
Again, recall that we use an sorted list with no repeats as the basis for holding Items. We want all such lists check to see if they are already holding that item or not. Sorted lists should just check for this, as a matter of course, even if, as in the current situation, the check would end up false (meaning that there should be no way for a user to pick up two items with the same name and ID, since there won't be two items like that around).
The goal of a test driver is to test your class! You should test the following:
It's not wise to write all classes, then attempt to test it using the sample input files. You need to learn how to make sure a class works correctly, and you do that by writing test drivers (this is a sample main() that tests all of the methods).
I may provide a driver at some point, but you are still expected to write and submit one yourself.
In fact, for each class, you should ask yourself, "should I add:
Because I didn't want to make the output operator a friend function of the class. (I prefer not to use friend functions). So, the output operator will simply call the public print() method to do its work.
Basically the idea is to implement the public print() FIRST, and then have the output operator call the print() method. That way, it's easy to write the output operator.
It's added because you will place curr in the correct spot for either a predecessor or successor locate. If you didn't pass it by reference, then other methods that call locate wouldn't be able get the new value of curr. (This is often, why you pass things by reference).
Now, you might note, "didn't the project say not to create a "curr" or "prev" data member"? That's true. But you can create "curr" and "prev" local variables and pass them to locate().
Many students getting compiler errors trying to use getNext() and getPrev() which are non-const methods (you can't call non-const methods on the other object passed in, since it is a const object). However, it doesn't make sense to set next and prev to those addresses, since they are pointers to the "other" list. So, you can simply set them to NULL, and let the RankingList take care of setting the curr and prev.
Unfortunately, yes. There's one in the Iterator class for Int, and there's one in the in the RankingList. The one in RankingList should be named contains() instead of inList(). HOWEVER, I'll leave that one alone.
Since the inList method does not appear in PlayerList, a contains() methods has been added.
It's been longer than two weeks, actually. However, here's why it should go more quickly than you think. IntIterator.h, ConstIntIterator.h, ListIterator.h, ConstListIterator.h are essentially all the same files. They don't take more than 3 or 4 lines per method.
AllRankingLists and AllTeamsList are similar too. There are very few lines of code in both of these.
DungeonParser, Item, ReadTag have been implemented. There's basically only one method in PlayerInputParser and TeamInputParser. Int.h and IntNode.h should be easy. So should Node.h. PlayerList and RankingList are very nearly identical.
When it comes down to it, you have to work on about 4 "real" classes: RankingList, AllRankingLists, Player, CommandParser. It may take a while to understand what to do, but once you do, you can often write one class, and do cut and paste to create a similar class.
You can also use the sample output to help you determine what the output operator should print for Part 2.
Yes. We will test Part 1 using driver programs, and test Part 2 using input redirection. I will eventually provide a kind of driver program to compile Part 1 against, however, you should still write your own drivers.
No. There is a way to do it with only the methods you've been shown in the tutorial: push_back(), pop_back(), resize(), and sort(). Worse gets to worst, you can alwasy create a new vector and put in the elements you want, minus the element to remove. Yes, that's inefficient, and there are better ways, but if you can't think of how to do it, then that's one way.
That should have been deleted. But basically, it returns a string consisting of a person's first name, followed by a space, followed by their last name.
Suppose you have two Names, X and Y. Compare X's last name to Y's last name. If X's last name is less than Y's last name, then X is less than Y. If the last names are the same, then compare the first names. If X's first name is less than Y's first name, then X is less than Y. If X's first name is greater than Y, then X is greater than Y. Otherwise, they are equal.
Yes. It should be sorted by team name. Use the C++ string comparison operators (e.g. >, >=). In fact, all vectors should be sorted.
Pick something reasonable. Essentially, we'll test the printing by using iterators, instead of the output operator, but you should implement it so you can do debugging for yourself.
I will post how to do this soon. Hopefully, by the end of the week.
You have to submit BOTH parts by Sept. 26. Part 1 is considered moderately trivial. This means that if you only had to submit Part 1, it would be an EASY project. Part 2 is where most of the work is. You need to be coding Part 2 by the middle of the week, because there's some thinking involved.
IntNode *getNext(); const IntNode *getNext() const;Ask yourself: when should a method be "const"? The answer is: when it doesn't changes the data members of an object. However, there's one tricky case. What happens if you return a pointer or a reference to a data member? That data member hasn't been altered, but it may be altered in the future by the user who makes the call to the method.
So, the normal solution is to make get functions non-const (as in the first getNext() above). However, there are times when the object is "const". You may want to access data members of that object, even though you do not intend to modify those data members. In that case, you would be stuck, because you won't be allowed to call any non-const methods.
So, you offer the user a second version. In the second version, you return a const pointer, so the user can't modify the object (the user can only call const methods on the IntNode object since it only has a const pointer). Since the user can't modify the IntNode, the user can't modify the list either. Therefore you can safely make the getNext() method const.
That's why there are two versions of the method. Again, rule of thumb:
Whenever you are returning a pointer or reference to a data member, have two versions of the method: a non-const method and a const methodThe const method is only called when the object is const. Otherwise, the non-const method is called.
You need the const method if you are implementing a copy constructor. Recall that object being copied is const. So, you can only traverse down the list using const methods. If you didn't have the const getNext() method, then you couldn't traverse the list. Some of you may have removed the "const" from the parameter for just that reason. That will cause other problems as the copy constructor is typically defined as having a const reference parameter.
Several students have asked that the description be posted in the posting account. There are several reasons why this isn't being done. First, it's a pain to maintain two versions, one at the website, and one more in the posting account. The version on the website is constantly being updated, and making copies is a pain.
Second, you should really know how to save a copy of the description on your WAM account, and then either "ftp" that copy to your class account and print it from there. While this may be "annoying", it's a skill you should know on UNIX. This is your third semester taking a programming class, so if you haven't learned "ftp", you should do so now.
There is a tutorial (or will be soon) on how to do this using Netscape. Go to the main webpage, and click on Tutorial. Look for the "print project tutorial".
In CMSC 114, you may have used the following methods
for your singly linked list:
class SLL { // singly linked list
Node *first, *curr, *prev;
public:
void goFirst(); // sets curr to first
bool goNext(); // moves curr, if possible
bool inList(); // true, if curr in list
int &getCurrent() const; // get value at curr
There are several problems with this:
You might ask, why not simply use "Node *" (the pointer to the node), and let the user do what they want with it. The problem is deletion. If the user deletes this node, then the list is ruined. By hiding the pointer in a Iterator object, you can force the destructor to only destroy the object, but not the "Node *".
A typical use for an iterator is to print a list. For
example,
void print( ostream &out ) const
{
ConstIterator iter = list.constIterator();
for ( iter.goFirst(); iter.inList(); iter.goNext() )
out << " " << iter.getCurrent();
}
The reason for using a "ConstIterator" is because the method
is const. A ConstIterator won't modify the list (since
getCurrent() returns back something by value).
It should be sorted by school name. For example, if you
have three schools: "Monty", "Blair", "Rose", then, when printing
out the ranking list in order, it should look something like:
Blair: 2 -- 10 -- 14 -- 19
Monty: 3 -- 4
Rose: 5 -- 9 -- 11 -- 15
The length of each list isn't used to determine how
AllRankingLists is sorted.
Here's the idea. RankingList consists of a "school name"
and a doubly link list of IntNode. Visually, you can think
of it like:
+---------------------+
| +---------+ |
| school | Monty | | IntNode
| +---------+ | +---+ +----+ +----+
| first *-------|---->| 3 |--->| 10 |---->| 12 |--X
| | X--+---+<---+----+<--- +----+
| | |
| last *-------|---------------------------+
+---------------------+
first points to the first element of the list.
last points to the last element of the list. Each node
consists of a next and prev pointer. For example,
10's next pointer point to the node with 12, and 10's
prev pointer point to the node with 3. 12's next pointer is
NULL (which is not the null character!).
Also, each IntNode contains a pointer a dynamically allocated Int node.
Properties of the list:
You will need to implement this doubly linked list. Furthermore, you need a vector of such doubly linked lists for AllRankingLists.