Latest Posting

This was posted October 25, 2001.

Checklist

A link to a checklist will be provided. You should read the checklist several times, but especially before submitting your project. (To be posted soon)

Project 3 Checklist

Purpose

The purpose of the Project 3

1. To get practice using recursion.
2. To write a binary search tree with predecessor/successor nodes using nested classes.
3. To finally see minor CMSC 214 Style Specifications.

Hardcoding is a Violation of Academic Integrity

If you "hardcode" the output, i.e., attempt to produce the primary output by using print statements or other similar techniques, or use simplified data structures (for example, using an array when you've been asked to use a binary search tree), you may be receive a 0 on the project, and be brought up on charges of academic dishonesty.

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:

1. failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.

2. using any ideas or any part of another student's project, or copying any other individual's work in any way.

3. giving any parts or ideas from your project, including test data, to another student.

4. having programs on an open account or on a PC that other students can access.

5. transferring any part of a project to or from another student or individual by any means, electronic or otherwise.

6. 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.

Style Guide

Here it is

FAQ

We will provide corrections and announcements, as well as "frequently asked questions" on the Project 3 FAQ page.

Project Overview

You will create a binary search tree template class.

The program you write will support commands for printing out information of the tree, to verify a tree has been constructed.

As with previous projects, this project will be released in parts.

1. You will be provided Movie.h, Movie.cpp, and MovieBstSortedList.h.
2. Implement MovieBstSortedList.cpp. This is NOT a template class. You can use MovieBstSortedListDriver.cpp to test the code. This is a minimal driver. You should add more to test the class fully. The more you can test, the fewer bugs you should have.
3. You will be provided a minimal ObjBstSortedList.h, which will be a template class version of MovieBstSortedList.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.
4. Data should contain a key, and a getKey() method to retrive that key. The BST will be sorted based on that key. You should also define relational operators such as < and ==. This will allow you to compare objects by keys using two different methods.
5. Implement ObjBstSortedList.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). Make sure that it works with the ObjBstSortedListDriver.cpp, the driver. This should produce the same output as MovieBstSortedListDriver.cpp.
6. Finally, write a BstSortedList.cpp, which you will use in BstSortedList.h to replace SortedList.h. You can make this version handle pointers.
7. The ArrayList class should remain the same. (Of course, debug it as needed).
8. Replace the SortedList object with the BstSortedList object in Team. Make sure your code still works with the P2 primary.

NOTE: It's a good idea to test the BstSortedList classes thoroughly, before incorporating it into your other classes. Don't implement new commands until the changes have been made.

Files Provided

Files That Aren't Needed in Project 3

You shouldn't need the following files:

• SortedList.cpp or SortedList.h.

You shouldn't need to submit it. However, these files may be used in Project 4.

Files You Still Need from Project 2

Pretty much everything else used to create p2, the executable.

Files Provided

• Movie class.
• MovieBstSortedListDriver.cpp file.
• MovieBstSortedList.h file.
• ObjBstSortedList.h file.
• ObjBstSortedListDriver.cpp file.
• BstSortedList.h file.

Files You Write

• MovieBstSortedList.cpp file.
• ObjBstSortedList.cpp file.
• BstSortedList.cpp file.

Background Reading

Background readings may be provided.

Commands

There are the additional commands. You may need to refer to P1 and P2 project descriptions for other definitions of BNF not mentioned here.

• PRINT_INORDER

  The input looks like:

  PRINT_INORDER <seps> <teamname>
  

  Prints the team (stored in a BST) in inorder. The output looks like:

    <print_inorder_out> ::== "[PRINT_INORDER]" <endl>
                          [ <empty_tree> | <tlist_players> ]
                          <endl> 
    <empty_tree> ::== "   EMPTY TREE" <endl>
    <tlist_players> ::== [ <tlist_one_player> ]+
    <tlist_one_player> ::== "  (" <digits> ")" 
                                    <lastname> ", "  <firstname>
                                    <endl>
  

• PRINT_PREORDER

  The input looks like:

  PRINT_PREORDER <seps> <teamname>
  

  Prints the team (stored in a BST) in preorder. The output looks like:

    <print_preorder_out> ::== "[PRINT_PREORDER]" <endl>
                          [ <empty_tree> | <tlist_players> ]
                          <endl> 
    <empty_tree> ::== "   EMPTY TREE" <endl>
    <tlist_players> ::== [ <tlist_one_player> ]+
    <tlist_one_player> ::== "  (" <digits> ")" 
                                    <lastname> ", "  <firstname>
                                    <endl>
  

• PRINT_POSTORDER

  The input looks like:

  PRINT_POSTORDER <seps> <teamname>
  

  Prints the team (stored in a BST) in postorder. The output looks like:

    <print_postorder_out> ::== "[PRINT_POSTORDER]" <endl>
                              [ <empty_tree> | <tlist_players> ]
                              <endl>
    <empty_tree> ::== "   EMPTY TREE" <endl>
    <tlist_players> ::== [ <tlist_one_player> ]+
    <tlist_one_player> ::== "  (" <digits> ")" 
                                    <lastname> ", "  <firstname>
                                    <endl>
  

• PRINT_TREE

  The input looks like:

  PRINT_TREE <seps> <teamname>
  

  Prints the team (stored in a BST) using the tree print function provided. The output looks like:

    <print_tree_out> ::== "[PRINT_TREE]" <endl>
                          [ <empty_tree> | <tree_out> ]
                          <endl> <endl>
    <empty_tree> ::== "   EMPTY TREE" <endl>
    <tree_out> ::== "   Tree for team: (" <teamname> ")" <endl>
                          "   ----*----*----*----*----*----*"  <endl>
                          <endl>
                          <tree_graphic> <endl>
  

  I won't try to list the BNF for how to print the tree itself, suffice it to say that you can look at the primary output to see what it looks like.

• PRINT_TREE_HEIGHT

  The input looks like:

  PRINT_TREE_HEIGHT <seps> <teamname>
  

  Prints the height of the tree which stores the team members. If the tree is empty, the height is -1. If it has one node, the height is 0.

    <print_tree_height_out> ::== "[PRINT_TREE_HEIGHT]" 
                               " The tree height is " [-]? <digits>
                                <endl> <endl>
  

• LEAVE_TEAM

  The input looks like:

  LEAVE_TEAM <seps> <firstname> <seps> <lastname>
  

  This command can be applied to robots or players. Once a player leaves a team, s/he is not on any team (recall a player starts off not being on any team). A robot is never on any team. If a player is not on a team, then print <player_gone>.

    <leave_team_out> ::== "[LEAVE_TEAM]" 
                          [ <player_leave> | <player_gone> |
                             <robot_gone> ]
                          <endl> <endl>
    <player_leave> ::== "(" <personname> ") leaves team ("
                              <teamname> ")"
    <player_gone> ::== "(" <personname> ") is not on any team"
    <robot_gone> ::== "Robot (" <robotname> ") is not on any team"
    <robotname> ::== <personname> 
  

• LEAVE_DUNGEON

  The input looks like:

  LEAVE_DUNGEON <seps> <firstname> <seps> <lastname>
  

  This command can be applied to robots or players. Once a player/robot leaves the dungeon, they are no longer in any room. Therefore, they can not pickup nor drop items. If the player or robot is already outside the dungeon, then print the messages associated with <player_went> or <robot_went>.

    <leave_dungeon_out> ::== "[LEAVE_DUNGEON] " 
                          [ <player_goes> | <player_went> |
                            <robot_goes> | <robot_went> ]
                          <endl> <endl>
    <player_goes> ::== "(" <personname> ") is exiting dungeon "
                             " from room (" <roomname> ")"
                             <endl> <endl>
    <player_went> ::== "(" <personname> ") is already outside "
                              "the dungeon" 
                             <endl> <endl>
    <robot_goes> ::== "Robot (" <robotname> ") is exiting dungeon "
                             " from room (" <roomname> ")"
                             <endl> <endl>
    <robot_went> ::== "Robot (" <robotname> ") is already outside "
                              "the dungeon" 
                             <endl> <endl>
  

• DROP

  The input is still the same as it was in project 1 and 2. However, since a player or robot might not be in the dungeon.

  Once a player/robot leaves the dungeon, they are no longer in any room. Therefore, they can not drop items. The following are messages for dropping when the player/robot is outside the dungeon. The previous BNF for dropping still apply when a player or robot is in some room of the dungeon.

    <drop_outside> ::== "[DROP] " 
                          [ <player_outside> |
                            <robot_outside> ]
                          <endl> <endl>
    <player_outside> ::== "(" <personname> ") is not in any"
                             " room, and therefore can't drop"
                             <endl> <endl>
    <robot_outside> ::== "Robot (" <robotname> ") is not in any"
                             " room, and therefore can't drop"
                             <endl> <endl>
  

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

1. The only new assumption is that robots can't join any team.
2. 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.
3. You can assume a Robot can't drop any items if it's not in a room. The same can be said of a Player. Appropriate error messages will be provided in the BNF.

Description of Files

Movie.h/Movie.cpp

Same as last time.

MovieBstSortedList.h

This stores a BST containing BstMovieSortedList::Node objects. Each of these objects contains a Movie object stored by value.

Node nested class

Most of these operators should be familiar to you now, so they won't be explained.

The important parts to note:

• left and right are pointers to the left and right child, respectively.
• pred and succ are pointers to the predecessor and successor respectively. The predecessor of a Node is the Node in the BST with the next lowest key value. (If you printed the list in inorder, it would be the value just before the value in the Node). The successor of a Node is the Node in the BST with the next highest key value. The predecessor of the Node with the smallest value is NULL. The successor of the Node with the largest value is NULL.
• getCurrent() has been renamed to getData() to make it correspond better to getKey().
• Note: do not add a parent pointer. You should use recursion to traverse a tree. Adding a parent pointer makes it too tempting to use iterative techniques (which are actually more challenging).

Iterator nested class

The iterators are nearly identical to the Iterators of SortedList. However, instead of using next and prev pointers, you use succ and pred pointers. There's also an overloaded -> operator.

MovieBstSortedList main class

Most of the methods are the same as before. However, because this is a BST, the implementation is different. locate() should be implemented using recursion.

• add() should use a recursive locate() to place "curr". It should then correctly place the new node using curr, including pointers to predecessor/successor. The new node (if added) must always be a leaf.
• remove() should be handled in one of four ways: "left standard", "right standard", "left easy", "right easy". Pick the one you like. (This will be explained in a separate tutorial on BST). Identify which one you used in the README. remove() should use locate() to help. When removing a leaf, only the leaf should be removed. The rest of the tree should be unaffected. However, the tree will clearly differ, depending on which method you pick to remove elements from the tree.
• contains(). Use locate() to determine whether a node is in a tree or not.
• size() Either use recursion to implement, or maintain the size using a listSize data member. Don't use iterators to count the size. (Again, more practice with recursion).
• clear() Remove all nodes from the tree, to create an empty tree. Use recusion do implement (hint: use freeMem()).
• first and cfirst. Use findMin() to implement.
• last and clast. Use findMax() to implement.
• visitPreorder, visitPostorder, visitInorder

  This will print the tree in the order described. The output should look like:

     (1) A.I.
     (2) Jaws
     (3) Patton
     (4) Quack
  

  With numbers on each line, and the "key" printed. If the tree is empty, print:

      EMPTY TREE
  

• print This has been implemented for you. It prints the tree in a somewhat similar way to how Windows prints directory trees. Use this for debugging your trees. If the tree is empty, it merely prints "NULL".
• height should compute the height of a tree, recursively. The height is the depth of the deepest node. This is the number of left/right pointers you would need to traverse from the root to reach the node furthest from the root. The root has depth 0. If the tree is empty, then let the height be -1.
• findMin and findMax take "curr" as a parameter. When called, the caller will set "curr" to some node in a tree, which will serve as the root of a SUBtree. It returns the minimum element and maximum element, respectively, of the subtree. This is the leftmost and rightmost element, respectively.
• addBst and addPredSucc are useful to implement "add". These functions assume that "add" has run "locate()" and set "curr" correctly. Also, they assume that a newNode has been dynamically allocated, and is ready to be set correctly. Use both methods in succession to "add" the node into the tree. You may wish to write similar methods for "remove".

In general, you should have private helper functions to implement recursive functions.

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.

Recursive Functions

A recursive function is defined as follows.

• The function must call itself, OR
• The function must call a helper function, which calls itself. (Thus, the original function is a "bootstrap" function, which starts the recursion). If the helper function has EXACTLY the same parameters as the bootstrap function, then it makes no sense to write a helper function. The original function can be made recursive.
• Functions can be mutually recursive (Function A calls B, and function B calls A). There should be no need to write mutually recursive functions.
• Neither the bootstrap function, nor the helper function should use any loops. If you are using loops, don't use loops to traverse the tree. Use recursion to process the tree. You may use loops in arrays, vectors, etc.

Requirements/Restrictions

The following requirements/restrictions are specific to this project.

1. The following functions should be recursive:
   • locate()
   • add() (using locate())
   • remove() (using locate())
   • contains() (using locate())
   • clear() (using freeMem)
   • freeMem() (using freeMemRec, a recursive helper function)
   • height()
   • first() and cfirst() (using findMin)
   • last() and clast() (using findMax)
   • findMin(), findMax()
   • visitPreorder(), visitInorder(), visitPostorder()
2. You must NOT use a separate doubly linked list for handling predecessor/successor. The node is both part of a tree (using left/right pointers) and a doubly linked list (using pred/succ).
3. You should use predecessor/successors to implement iterators.
4. end() and cend() should set "curr" to NULL.

The following requirements/restrictions should be observed.

1. 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.
2. You should comment code. You will be given instructions on how to do this later on.
3. You should use namespaces. In particular, in your .h files (ONLY), all of objects should
4. You should use namespaces. In particular, in your .cpp files, you should write "using namespace std".
5. Hardcoded outputs will be severely penalized.
6. Write helper functions. You will gain more credit if you do. They should be clearly labelled as helper functions.
7. Your program must create an executable called exactly p3. If you create other executables, the "main()" must be in a file with the name "Driver" at the end. For example, if you wish to create a "BstSortedListDriver.o" that has a "main()", that is fine. However, a file such as "test.cpp" should not have a "main()". This will allow us to test your files.

README

Submit a README with your files. Add the usual stuff:

• Which classes did you write copy constructors, destructors, and assignment operators (recall you should only write it for classes that it's NECESSARY, not because you feel like it). Necessary is defined to mean "if you don't write it, then when you copy or assign, the object will not behave correctly).
• How you declared the "BstSortedTree" in "Team" (did you use pointers or not).
• Whether you did the extra credit below or not.

Extra Credit

For 5 points extra credit, reimplement sort214 using quicksort. You may need to find an implementation of this algorithm from some book. You are permitted to search on the web to do this. However, you are not permitted to post your solutions (or read other's posted solutions). Of course, the actual version uses array elements. You will have to adapt it to use pointers.

How to Submit Your Project

As with Project 1

submit p3.tar 3 SUBMIT

Your executable must be called exactly p3. Any other name will cause your program not to be submitted.

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).

Please do not submit until a primary input and output have been posted. If you do, you may receive a 0 for failing to pass the primary.

Web Accessibility