Last Modified: March 30, 2004
|
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 4 |
Think of these iterators just like those for vectors. ++ moves the iterator to the next largest value and -- moves to the next smallest value. Neither of these values will ALWAYS be found at getRight() (for ++) and getLeft() (for --). Draw the BST containing 5,3,1,4, and 7. From 4, if one does ++ you get to the root (5).
For equality and inequality, we test the iterators to see if they are pointing to the same node. For the other relational operators, we test the contents of the node to see how, for example, ["SW",1] compares to ["NE",2].
That is the file that your Bst * tree (in the private section of BstIterator.h) is reading to build the tree.
Yes, you heard correctly. In a moment of weakness, I gave away the store including a 2 (more) days extention on this project. It is due Saturday, April 17, at 11PM. Last late day is Monday, April 19, at 11PM. After that it is worth only 10 points.
Please remember that the submission process is slow on the due date night because of heavy use of the server. So try not to submit real close to 11PM or you may miss the deadline. Also, if you have everything working except the Iterator, submit it early then work on the iterator. If you don't get the iterator working, you still have the project in on time. It is not worth it to submit late with the iterator working (-15 + 7 = -8 points).
You still have to do all of the things you did to build the tree like strip out the blanks, run it through converter() and build the tree after you've read the tree data.
Your board MUST hold strings. DO NOT simply write "R" and "S" when you encounter an 8 or 9. This will result in a severe deduction of points.
Let's say you templatize on string, Pair and Mpair. Your template
has 3 different generic types so when you declare a Board object, you need
to state what each is. (You also have to be careful you are getting the
order correct.) So in this case, your Board object in main.cpp would look
like:
Board<string,Pair,Mpair>
Yes, this is a change to my main, but it is necessary and you are also changing the catch clauses at the bottom of main. We will run your project on your main. However, a word of caution. Don't make other changes to main like calling other functions in there.
Yes, that is because you have each file including the other before
it is defined. You need a forward declaration. So at the top
of Bst.h before you #include "BstIterator.h" put
template<class T>
class BstIterator;
And at the top of BstIterator.h before you #include "Bst.h"
put
template<class T>
class Bst;
Yes, you can remove begin() and end() from the Robot.h. Then you also don't need to #include "BstIterator.h" in there. Or you can leave all of the above in Robot.h and just don't implement it.
That would be okay since you still will have to dynamic_cast to get the base class versions of certain functions.
If you are using the BaseRobot pointers as stated in the previous FAQ, you will be doing a lot more dynamic casting but it should still work fine.
You need to call reader() from the Bst class in your BstIterator constructor and the parameter is "testbst2.txt", a file already in the posting account.
So to make this easy, BstIterator's constructor has a call to tree.reader("testbst2.txt"). You still need to convert and strip these entries, but now you have the root to the tree and the whole "kit and caboodle". You will notice that this file looks very much like a "moves.dat" or a "moves2.dat"
First, BstIterator will be extra credit - 7 points so you have the potential to get 107 on this project.
Secondly,we will ALL use the following in the BstIterator
class:
Bst<T> * tree;
I will change this in the BstIterator.h file. BUT since this is extra credit now, you are on your own with no hints from me to complete the BstIterator class.
Think of the BstIterator class as a class that should be able to work with any BST as long as you have a way to get to the first element, the last element and the root. Then write it like that.
In other words, forget about the game and fitting it in there. This can be thought of as a stand alone class.
I guess you and I are looking at this in different ways. I am looking at it as in "how am I going to test this" and you are looking at it in terms of "how can I get this to work in my code".
So from the testing point of view, which is completely
different from your game point of view, I need an iterator to walk
through a BST. And this is exactly the manner in which you should test
your iterator class. Make a BST (let's call it "tree") and make a
BstIterator (let's call it "it") and you can set:
it = tree.getRoot();
or
it = tree.begin();
or
it = tree.end();
By the way, I am also using a couple of extra functions to walk
the iterator and I have made them private in my code (you can do this
too if you need some extra functions).
void findNext(T key, Node<T> * curr, Node<T> *& succ);
void findPrevious(T key, Node<T> * curr, Node<T> *& prev);
If you are doing <, >, <= or >=, you should compare the contents of what your iterator is pointing to because less than, etc. makes no sense when memory is dynamically allocated to build your tree.
However, if you are doing = = or !=, you need to compare iterators to see if they are both pointing to the same node or not.
Robot and Stalker objects have been removed from Board.h and have been replaced by 2 BaseRobot pointers. I called them "rr" amd "wc" to coincide with my previous names for these objects.
They are initialized in the Board constructor. For
example, the Robot's BaseRobot pointer might look like the
following:
rr = new Robot<S>();
Okay, you will have to implement the default constructor only in order to get Bst to compile.
It turns out that it is easier to put a BstIterator into a BST
than the other way around. Now that I have had time to check this, we
are changing it in this fashion. In Bst.h:
private:
Node<T> * root;
BstIterator<T> it;
BstIterator.h remains unchanged from the first version posted.
Since board previously had a Robot and Stalker as data members, and we are now using inheritance and virtual methods, using pointers is better than using objects. You no longer have objects of Robot and Stalker in Board. Now you have pointers that will point to these objects.
So where do these objects get constructed? In the Board constructor.
It turns out that it is easier to put a BstIterator into a BST
than the other way around. Now that I have had time to check this, we
are changing it in this fashion. In Bst.h:
private:
Node<T> * root;
BstIterator<T> it;
BstIterator.h remains unchanged from the first version posted.
We can change the implementation by adding one line of
code to
BstIterator.h. EVERYONE must do this even if you don't get the iterator to
work. I will change the header file to:
private:
Bst<T> * ptr;
Node<T> * curr;
You need not use the pointer to a Bst object but you can use it if you want.
Yes, this is a bit confusing:
Neither. Since we extracted BaseRobot from Robot and Stalker and since Robot was templatized on Pair, BaseRobot is templatized on Pair also.
Apparently, I am going for the world's record on the number of mistakes in these projects. I'm sorry. The comments were old - from when the data structure was a dll. Now it is a bst. The comments have been changed in BOTH projects and the files are updated. Don't worry about your project. I will ask the TAs to accept BOTH answers on P3. Please change the message to "empty tree" for P4
Sorry, we will have to regrade these. Wait until you get your grade for P3 and then submit a regrade request.
But now that we all know, put converter in reader() in the Bst class. We will avoid this problem in the future.
I have added Bst.h and Node.h since these files don't depend upon inheritance. I changed a comment in reader() in Bst to indicate that you are supposed to call converter (as well as stripper()) in reader().
This is a public university and therefore we do not give extensions or special accomodations for religious observances. So, NO, I will not be able to give individual students an extension for religious reasons. However, I have looked at the schedule and we can squeeze in 2 extra days for all students to complete project 4. As it was initially due in 13 days, I have extended that to 15 days. This, unfortunately, takes 2 days away from project 5. We believe that project 5 can be completed in less than 2 weeks (and you have 2 weekends in there). Please do not expect me to extend project 5. We are running out of time and project 5 will be due when originally scheduled, April 28.
My main.cpp is clearly templatized on int and Pair. However, I gave you alot of leeway to determine what you want to templatize in the Board class. So if you have 3 or 4 fields templatized, you must change main() to correspond with your Board class. We will run the projects using your main.cpp
The reason I only provided limited header files is because you are supposed to use inheritance which will change the header files of Robot, Stalker, Pair and Mpair. Yes you will change these MINIMALLY. That means remove fields and methods from these 4 files that are already provided in the 2 base classes. However, do not change the files drastically. You may not add new data fields, change the data structures, or change the implementations that were provided in project 3.
Robot and Stalker must be templatized if the base class they are inheriting from is templatized.
Project #4 is due by 11pm on Tuesday, April 13th, 2004.
|
See the class syllabus for policies concerning email Last Modified: March 30, 2004 |
|
|
|
|
|