Click above before submitting (LINK not ready).

Updates

You are expected to read FAQ on a daily basis.

Project #3 FAQ

Get started right away.

1. To write a BstSortedList template class, which implements a binary search tree with nodes which have pointers to left and right children as well as predecessors and successors. This class has the same functionality as SortedList but is implemented using BSTs.
2. To write recursive functions. In particular, many of the BstSortedList methods will be recursive.
3. To add some features to the Sokoban game.
4. (EXTRA CREDIT) To write a BstMap class. You will be provided a Pair class and a PairComparator class. BstMap is similar to STL's implementation of its map class (it uses a BST of pair objects).
5. To debug code from previous project, so that it doesn't give you problems on this one.

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

• add
• remove
• contains
• update

Interestingly, a binary search three also implements this same interface. From the class user's point of view, a SortedList implemented as a doubly linked list and a SortedList implemented as a binary search tree are the same. While, you, the implementer will notice the differences right away, the user of the class should not notice the difference in functionality.

The user of the class never has to know exactly how SortedList is implemented, unless they really are concerned about efficiency of the operations.

Good coding practice suggests that you "program to an interface". This is easier done in Java than in C++, but the idea is that an interface (which is a list of public methods defining an abstract data type (ADT)) allows many implementations, and you can simply substitute the appropriate implementation as needed without chaing the interface.

We won't quite do this in this project, but you should appreciate the idea of a binary search tree is implementing a SortedList interface, and that semantically, a user only needs to know it's a sorted list.

• How Locate Works CLICK
• How to Delete in a BST CLICK
• Setting Predecessor/Successor Pointers CLICK

• TreeExercise.questions This is a list of questions about BST. You will write the solutions to this in a file called TreeExercise.answers. A skeleton of that file will be provided to you as well.
• ItemBstSortedList.h The header file for class ItemBstSortedList. You will implement this, and then templatize the file. Again, it's usually easier to write a non-template class and debug it, then templatize than to templatize
• BstSortedList.h The header file for template class BstSortedList.
• BstMap.h The header file for template class BstMap
• Pair.cpp, Pair.h, PairComparator.cpp, and PairComparator.h. These files will be provided to you for use in BstMap.h (again, extra credit).

Note: Implementing BstMap will be worth up to 5 points of the project. If you find yourself pressed for time, you may wish to skip the implementation of this class.

• MovieBstSortedList
• BstMap (EXTRA CREDIT)

Task 1: Finish Project 2

Since the game has only small changes, you should get the commands to work, and finish that up.

Debug code as needed.

Task 2: Answer questions from TreeExercise.questions

Answers should be typed in TreeExercise.answers. The purpose of this is to help you understand BSTs before writing any code. This is often a good exercise. Once you understand the "theory", it should be easier to write the code.

Task 3: Finish up any code you didn't write, and documentation from Project 2.

These facts are from P2, but placed here for additional clarity.

1. Food items may initially appear on target squares.
2. When a box with food items on top moves, the food items move with the box.
3. There will be at least one target square without a box on it.
4. There will be at least one target square.
5. A player is initially placed on an empty square or an empty target square.
6. When listing a range of boxes for error messages, list the box closest to the player to the box furthest away.
7. When listing boxes that are too heavy, list the fewest number of boxes that are too heavy (thus, if there are 6 boxes that the player is pushing, but the nearest 3 boxes are too heavy for the player, only list the range of the 3 boxes).
8. Ranges should be listed even for a single box that is too heavy. In that case, the range is the same coordinate of the box in both cases.
9. In commands from the input file, food items are written with double quotes. Box color are written using no quotes.

New changes to the game.

1. The number of boxes no longer have to match the number of target squares. There may be more boxes than target squares or fewer boxes than target squares. There will be at least one target square, but zero or more boxes.
2. If a player is on a target square, you should now print "&" (ampersand). If a player is not on a target square, print "=".

Commands

• TARGET_INFO

  This is now modified to indicate players and food items on target squares.

  Input BNF is the same as before:

  The output BNF is:

  <targetinfo-out> :=  [ "Player is on target square at " <coord> ]?
                        "BOXES ON TARGET" <endl>
                        "----*----*----*" <endl>
                        [ <target-list> | <no-target-list> ]
                        <endl>
                        "EMPTY TARGET SQUARES" <endl>
                        "----*----*----*----*" <endl>
                        [ <empty-target-list> | <no-empty-target-list> ]
                        "FOOD TARGET SQUARES" <endl>
                        "----*----*----*----*" <endl>
                        [ <food-target-list> | <no-food-target-list> ]
  <target-list>          :=   [ "  " <box-color> " " <coord> <food-target> <endl> ]+
  <food-target>          :=  [ " " <brack-name-of-item> ]*
  <brack-name-of-item>   := "[" <name-of-item> "]"
  <name-of-item>         := <word> [ %% <word> ]*
  <food-target-list>     :=  [ <brack-name-of-item> " " <coord> <endl> ]+
  <empty-target-list>    :=  [ "  " <coord> <endl> ]+
  <no-target-list>       := "  No BOXES lie on target squares" <endl>
  <no-empty-target-list> := "  There are NO empty target squares" <endl>
  <no-food-target-list>  := "  No FOOD ITEMS lie on target squares" <endl>
  

  • If a player is on a targets sqquare, print out the location of the player, otherwise don't print the information.
  • Boxes on target squares with food items on top should print the list of food items after the coordinates in brackets separated by one space (i.e. [bagel] [sugar COOKIE]).
  • Food items on target squares, but not on boxes, should be printed under FOOD TARGET SQUARES.

• HISTORY

  The input BNF is:

     <history-in> := % HISTORY [ %% <udigit> ] % <endl>
  

  HISTORY can either be a command by itself (with no arguments) or can take a single argument. The single argument is a positive number, which indicates which run the command to run.

  If the user enters HISTORY with no commands, then the list of commands by the user is printed out. Only VALID commands are listed (invalid commands are not listed). The last command

  This is the output BNF of HISTORY without arguments, which appears after the command echo.

     <history-out> := "  Command History" <endl>
                            "  ----*----*----*" <endl>
                            [ " (" <udigit> ") [" <command-list> "]" <endl> ]+
     <command-list> := [ <word> | <dquote-word< ] 
                             [ " " [ <word> | <dquote-word< ] ]+
  

  The command list is the command echo, which puts a single space between the commands and each of its arguments. However, double quoted arguments still preserve spacing. The number of the command is the same number used in the command echo.

  The last command will be the HISTORY command itself.

  HISTORY with argument

  If the HISTORY command has an argument, it will be a valid number of a command that has PREVIOUSLY been run (thus, it won't be the current history command being run right now). You may assume that this is a valid number (i.e., it has appeared earlier). The number is the one that's printed with the command echo.

  What happens if you run a command like DISPLAY by using, say, HISTORY 3, followed by HISTORY again? Instead of printing HISTORY 3 in the Command History output, you will print the command that was numbered 3 (preserving the capitalization as in command 3).

  The command echo will be [HISTORY 3], however, when future calls to the HISTORY command are called, you will see [DISPLAY] for the same number (or whatever was command 3).

  There are simple ways to implement this command. First, you can have an ArrayList of strings, which represent the command, or better yet, create some sort of History class which has an ArrayList (of Command objects) data member, and perhaps create a Command objects which stores the command.

  Storing a list of commands allows re-execution of old commands, and potentially, with work, allows you to "undo" commands. However, you will NOT undo commands in this project.

• PICKUP

  You can now pick up all items on a box (in addition to picking up indidivdual items as in P2). You may assume that boxes do not have the same names as food items.

  The input BNF is:

    <pickup-cmmd2> := % "PICKUP" %% <box-color> % <endl>
  

  The output BNF for this is:

     <pickup-out2>     := <pickup-good2> | <pickup-nobox2> 
     <pickup-good2>    := "  Player successfully picked up ALL items on ["
                               <box-color> "] " <dir8> 
                              " of player at " <box-coord> <endl>
     <box-coord>      := <coord>
     <pickup-nobox2>  := "  PICKUP ERROR. Player not adjacent to box [" 
                             <box-color> "]" <endl>
  

  Even if there are no items on the box, you can say the player successfully picked them all up, as long as the player is adjacent to the box (in one of 8 directions).

  You should add the items to the player's list at the END of the list (recall the player stores item in the order that was picked up, and the box also stores items in the order placed on the box).

  Once the command is complete, the box will hold no items.

  As in P2, <coord> refers to the coordinate of the box

• DROP

  In P2, a player could drop one item on a box. Now, a player can drop all items on a box (this is an additional feature of the DROP command).

  This is the input BNF.

     <drop-cmmd> := % "DROP" %% <box-color> % <endl>
  

  This is the output BNF.

   <drop-out2>  := <drop-good> | <drop-nobox2> 
   <drop-good2> := "  Player successfully dropped ALL items on ["
                      <box-color> "] " <dir8> 
                      " of player at " <coord> <endl>
   <dir8>       := "NORTH" | "SOUTH" | "EAST" | "WEST" |
                      "NE" | "NW" | "SE" | "SW"
   <drop-nobox2> := "  DROP ERROR. Player not adjacent to box [" 
                         <box-color> "]" <endl>
  

  Again, even if the player is not carrying any items, you still print the player dropped all items if the player is adjacent to a box in one of eight directions.

  This should be added at the end of the ArrayList of food items for the box, in the same order that the player was carrying the items. Thus, if the player picked up a "doughnut", then a "bagel", the "doughtnut" and "bagel" are added at the end of the list of items on the box, in that order.

  As in P2, <coord> refers to the coordinate of the box

Case-insensitive

Furthermore, the box color or item name can also be in any case. You should print the output BNF for the box color and item name using the same case as in the command from the input file.

If a player wants to pickup a BAGEL, or bagel, or Bagel, from a "red" or "RED" or "ReD" box, this should work, provided there is a bagel on a red box adjacent to the player.

Older commands

• You should have three original classes in this project related to the Sokoban game. If you have already implemented three classes, you do not need to implement additional classes.
• Document this class as you have the classes with the .mine.h and the .mine.cpp extensions.

Also, make sure any class that USES a template class adds the .cpp file as a dependency. For example, if Foo.mine.cpp or Foo.mine.h uses a ArrayList<int>, list BOTH ArrayList.h and ArrayList.cpp as dependencies.

Also, for ArrayList, 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.

Also, if your executable exceeds about 5 M, you should make sure that you run:

  unlimit filesize

This prevents core dumps because of excessive file sizes.

If you use the -g option, the size of the executable will be much larger, so use this option only when you need to use the debugger.

Furthermore, for quota purposes, go to earlier projects and remove .o files, executables, etc. If you have space in your WAM account, you may wish to copy files of earlier projects there, to back them up (again, removing .o files). Remove core dumps too.

You may also wish to gzip your tar file. This compresses your file, and addds a .gz extension. You say something like gzip p1.tar and it creates p1.tar.gz. You can uncompress it by saying gunzip p1.tar.gz.

As a precaution:

• Use the makefile to issue commands to "remove files" and test it before you write too many files. Too many people call "rm *" too easily. You would like to have a make clean option.
• Make backups of your .cpp files in a SIDE directory. For example, if you do you work in a P2 directory, create a directory called P2backup at the same level as the P2 directory, i.e., not as a subdirectory.
• Use the -i option when removing files. For example, rm -i. Sure, it asks if you want to remove each and every file, but it's better than deleting all your files accidentally.
• Type pwd before deleting all files in a directory. Make sure you are in the correct directory.
• If you still end up deleting files, contact your instructor. You must say "I give permission to the instructors of CMSC 214 to recover the files in directory so-and-so" and specify the directory. Note: recovery usually takes a day, and possibly longer if the request is made over the weekend. OIT personnel handle the recovery, and it's not the job of 214 instructors to do the recovery.

Extensions are unlikely to be given for anyone who accidentally deletes files. You can ask, but we reserve the right to refuse. So be extremely careful.

ladebug p3 core

Unfortunately, rathet than indicate that this operation is happening on invalid memory, it prints that the operation has core dumped. If the method is particularly simple, you may need to look at what calls the method to debug it.

1. Create a subdirectory. Make sure it is empty.
2. Copy your tarfile into that directory.
3. Copy any files from the posting account, as needed, such as the primary input and primary output.
4. Untar your file.
5. Run "make p3" on the file.
6. Redirect the primary input into your program, and redirect the output into some file like "my.output".
7. Run diff -bwi between your files and ours. If the only difference is blank lines, then you should be ready to submit.

A successful SUBMISSION of your tar file does NOT always guarantee you have passed the primary input

This is why you should test your tarfile prior to submission.

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.

   p3 < primary.input

Your program must use cxx with the options -w0 -std strict_ansi. Unfortunately, while we have aliased this for you, it doesn't always work with Makefile, so use the full name in your makefiles.

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 p3.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 p3.tar 3