(REVISED for clarity) The grading policy is as it was before with one major addition. Turn P4 in ontime and you don't get a late penalty. The late penalties are the same as before: -10 for 1 day late, -20 for 2 days late, -30 for 3 days late. Beyond three days late (but before December 13, at 4 PM), you get 10 points for passing primary (and using the BstSortedList, ArrayList, SortedList and Tokenizer classes in the project) beyond 3 days late but before December 13, 2002 at 4 PM. These criteria were stated in the syllabus.

If you fail to turn a working project 4 (i.e., passes primary, and uses the classes listed above) in by December 13, 4 PM, you will receive an F for the course regardless of other grades in the course.

Since the primary input may NOT fully indicate all the important aspects of the project, you will need to make sure you follow the necessary CODE requirements, to pass (which will be listed below).

Note: Final possible submission is due at 4 PM on December 13

Click above before submitting (LINK not ready).

Updates

You are expected to read FAQ on a daily basis.

Project #4 FAQ

Get started right away.

1. To reuse ArrayList, BstSortedList, SortedList, and Tokenizer from previous classes.
2. To work with inheritance, including virtual functions and dynamic casting.
3. To understand code that is provided to you, and to integrate your code with that code.
4. To understand clone() functions.
5. To understand Wrapper classes.

To more throughly test your code, we may be checking the copy constructor, assignment operator, etc. from your code. So, it's your responsibility to make sure they are working (i.e., not core-dumping).

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

In particular, some students duplicated code for moving in each of the four directions---a smart solution would have been to figure out how to avoid this duplication. It never hurts to build up enough math skill so your solution is simpler.

In this project, there will be less code for you to write, but you must spend some time understanding the code that is provided to you. Initially, you will simply be asked to understand the various classes, then you will be provided the code in the posting account to work with.

As the flight coordinator/planner, you must seat these passengers based on the kind of ship they are flying, and then you must plan the trip from one planet to the next. The "plan" is a series of "instructions" (a mini-program) which you must figure out.

• Grid

  Like projects 1-3, you will be provided a "map". In this case, you are provided a Grid. The Grid has some number of rows and columns. You will use the Grid provided to you to locate the planet which you start the flight, then determine how to get to the planet to end the flight.

  Internally, the Grid is declared as follows:

     ArrayList< ArrayList < ArrayList < PlanetWrap > > >  theGrid ;
  

  This appears to be a 3-dimensional array, but can be thought of as a 2-dimensional array with R rows and C columns.

  Each grid element consists of a ArrayList<PlanetWrap>. Since this is an ArrayList, it consists of 0 or more objects in the container. In particular, a grid element may consist of 0 or more "Planets". Some grid elements are empty, i.e., they contain no planets at all.

  Wrapper Classes

  A PlanetWrap is a "wrapper" class. It is sometimes convenient to store pointers in objects, because objects can more easily manage memory. In particular, a PlanetWrap object stores a single pointer, which is the pointer to a Planet object, which is a base class. You should study the PlanetWrap code that will be provided to you, to understand what it is.

  The goal of the wrapper class is to make it easier to copy and manage objects with a base class pointer to derived class objects. In particular, it makes it easier to have a SortedList of derived objects with "wrappers". If you were to have a SortedList of pointers, you would discover that you need to modify the code to handle pointers. In particular, SortedList expects objects. If it gets pointers, instead, it has difficulties printing (because you must dereference pointers, where you don't have to dereference objects).

  It is difficult to manage a template class that can both handle objects AND pointers. One solution is "wrappers" which are objects that store pointers (very similar to Iterators) to dynamically allocated objects.

• Planet

  Planet is a base class, and has a lot of information associated with it. In particular, it contains:

  • a landing bay

    Spaceships come in two categories: Warships and Peaceships. Warships are large bulky ships and must land on a planet with a "landing bay" (basically an "airport" for spaceships). Peaceships do not have such restrictions. Being much lighter, they can land on planets with or without a loading dock.

    "Warplanets" (which is a type of object) always have landing bays, where "Planets" may or may not.

  • a donation amount

    Peaceships are "generous". As they land on each planet, they offer donations to the planet. Each planet has a "donation" amount which the Peaceship offers, provided it has gifts. Since it is only a donation, if the Peaceship doesn't. Warships don't donate any amount (they're mean).

  • a tax amount

    Each planet also must pay Warships a tax. Thus, the WarShip collects "gifts" from each planet. (The planet generally makes this money back through other fees it imposes on all ships). Thus, warships collect a tax amount on each planet they land on.

  • cargo cost

    When a ship lands, it must pay a fee based on the total weight carried by the ship. This only applies to the weight of Cargo objects. Compute the total weight, multiply by the cargo cost to get the actual cost.

  • human landing fee

    For each human (a Human object) that lands on a planet, there is a fee. To compute the total fee, multiply the number of humans by the landing fee.

  • droid landing fee

    For each droid (a Droid object) that lands on a planet, there is a fee. To compute the total fee, multiply the number of droids on board by the landing fee.

  • fuel cost

    Each time a ship lands on a planet, it pays a fuel cost. This allows it to fly to the next planet. However, you pay this cost no matter what (except on the initial planet).

  • number of troops

    This quantity only applies to "Warplanets". "Planets" do not have any troops.

  Planet is an concrete base class, and WarPlaent is derived from it, having numTroops as a derived data member.

• Ship

  Ship is an abstract base class. It has two concrete derived classes: PeaceShip and WarShip. The two ships differ in the following way.

  PeaceShips can land on any planet with or without a landing bay. However, it can't land on a WarPlanet with more than 1000 troops (because it's too dangerous). They also donate money (if they have any) to each planet they land on. PeaceShips have passengers, and prefer to seat Humans in "better" seats than Droids

  WarShips must land on a planet with a landing bay. The number of troops don't affect whether a WarShip can land on a planet. They collect tax from each planet they land on. It's assumed the planet can pay the tax. WarShips have passengers, and prefer to seat Droids in "better" seats than Humans

• Passenger

  Passenger is an abstract base class. There are three kinds of concrete derived classes: Human, Droid, and Cargo. All three can be on a Ship.

A Ship consists of "seats" and the "cargo hold". Each ship has a limited number of seats, with seating preferences.

For a WarShip, Droids are given the best seats, and are seated in alphabetical order (at index 0, 1, 2, etc). If there are any other seats remaining, Humans are then seated after Droids. Should they run out of seats, they are placed in the cargo hold.

Cargo is always placed in the cargo hold.

For a PeaceShip, Humans are given the best seats, and are seated in alphabetical order (at index 0, 1, 2, etc). If there are any other seats remaining, Droids are then seated after Humans. Should they run out of seats, they are placed in the cargo hold.

1. Seat the passengers and put the cargo.
2. Determine the path between the source planet and destination planet, and produce a Plan (a series of instructions) to get from one planet to the next.

   A Plan object, and various Instructions will be provided to you.

   The plan does not have to be efficient. It merely has to work. The best plan involves using algorithms such as Dijkstra's algorithm, but you will not be required to implement it.

   Better plans may receive some extra credit (less planet hops, less overall cost, etc).

First, implement Name.cpp. Names can be one or more words. They should use exactly the same rules for comparison as food items in Project 2 (case-insensitive, check right to left).

Then, implement clone() and toString() methods for classes derived from Passenger (it's already been done for you). clone() should return a dynamically allocated copy of the object. toString() should print out the object using the format shown in the driver.output.

The Makefile provided requires that you add Tokenizer, ArrayList, and BstSortedList.

• Implement the rest of the methods in Ship.cpp that are not yet implemented.
• Implement the methods in PeaceShip.cpp and WarShip.cpp
• Make sure it compiles with the Makefile and produces the output in driver2.out

How do you seat passengers? For a PeaceShip

• Seat humans first. The priority among humans is based on their names. The priority of names uses the same rule as food items.
• Then, if any seats are left, seat droids. Use similar priority.
• If humans have not been seated, place them first in the cargo hold (in the same order they would have been seated, had there been enough seats).
• If droids have not been seated, place the in the cargo hold (in the same order they would have been seated, had there been enough seats).
• Finally, add the cargo in the order of their names.

You may assume no two Passenger objects have the same name.

For a WarShip, the same rules apply, but this time, droids are seated first, then humans. Cargo always goes in the cargo hold.

The cargo hold is infinitely large.

Finally, PassengerWrap.h is provided again. It is missing an assignment operator, so implement that method.

• Name does not need a clone() method. Usually, clone() methods are used when you are planning to use inheritance, and want to have a container class of derived objects (e.g., the wrapper classes are essentially an object storing a base class pointer), and you want to be able to make a "deep copy" (i.e., copy the object, not just the address--which is a shallow copy).

  Without clone(), you can't copy derived objects properly (because constructors aren't virtual).

• When seating passengers, you can assume that no passengers are seated. Although you can make this assumption, a better solution is to "clear" out the passengers by creating "empty" passengers (i.e., those whose data pointer is NULL) and seating them at each of the seats, prior to seating the passengers.
• You may write PRIVATE HELPER functions.
• Don't add/modify public methods without permission. (A common desire is to "change the methods to make the class more convenient", however, in the "real world", this is often not possible, except via inheritance. For example, if you aren't happy with Java classes, you can't just change existing methods of classes). In particular, changes may make it difficult to run with drivers.
• Until the passengers are seated, the number of filled seats is 0 (since no one has been seated).
• You may assume passengers always fill seats 0 to k - 1 where k are the number of seated passengers. Thus, seats k to n - 1 are empty (where "n" is the number of seats).
• The number of seats should not be changed (so, don't resize the number of seats). It is initialized in the constructor for the Ship object. The cargo hold is initially set to 0 (if you wish to "clear" the cargo hold before seating passengers/cargo, you may do so, however, you can assume that the cargo hold is initially empty---the better solution, again, is to clear the cargo hold first).

  Just add cargo using the provided method (note: humans and droids can go in the cargo hold).

You have now been provided several classes.

• Grid This represents some section of "space" where the planets are located. (0,0) is the northwest quadrant (just as in the Sokoban game). Each location in the grid contains an ArrayList of PlanetWrap. Thus, each location may have 0 or more planets.
• Planet The Grid consists of two kinds of planets. Planet is the base class, which may or may not contain a landing bay.
• WarPlanet This planet always has a landing bay, and may have military troops. You must implement WarPlanet.cpp which is not provided for you.
• PlanetWrap This is a wrapper class for pointers (which is nice, because it handles its own dynamic memory allocation).

There is also another driver main3.cpp and its corresponding output.

Just to get a feel for the class, write the function, findPlanet() in main3.cpp to generate the output shown in driver3.out.

Each Planet has a unique name (at least, when you compare their names using Name operator==).

Each WarPlanet has a unique name (at least, when you compare their names using Name operator==).

There is a possibility a Planet and a WarPlanet may have the same name. While this is bad "planet" management", it would force you to distinguish between a Planet and WarPlanet.

When Task Four arrives, the decision for whether to do this will be made.

• Instruction A base class for a set of instructions.
• Transport Derived class from Instruction. An instruction to transport the ship from one planet to the next planet.
• Donate Derived class from Instruction. The number of gifts to donate to a planet (only PeaceShips use this)
• Collect Derived class from Instruction. The number of gifts to collect from a planet (only WarShips use this)
• GetFuel Derived class from Instruction. The cost to fuel up on a planet.
• NoPlan Derived class from Instruction. Can't figure out a plan, so use this, instead.

First, you should implement the various methods in each derived instruction object. The header files indicate which methods need to be implemented.

You should eventually be able to produce the output of driver4.out given the Makefile.

The main functions you have to write appear in the Plan class. In particular, you need to implement createPlan. Here are the steps to do so.

• Each createPlan method takes a passenger list, a ship passed by reference, a grid, and a start and destination planet.
• You should make a copy of the ship object passed in (since it is const) and then seat the passengers on the copy.
• You should determine the coordinates of the source planet, (the planet you start from) and the dest planet (the planet you end up on).
• Create a plan by adding instructions (one of the derived objects) to the instruction list, iList, by calling addInstruction.

We will test your code by seating the passengers on a ship separately from the Plan class (by calling seatPassengers on the sorted list passed in), and then run this through a Verifier (to be provided by Task 5).

You will notice each ship has a data member called range. (A newer version of Ship.h has been added which adds a getRange() method---use this version, and implement this method).

The range is the distance a ship can travel. The distance is measure in "L" distance or Manhattan distance. Let (x₁, y₁) be the coordinate of the source planet (where you are starting from). Let (x₂, y₂) be the coordinate of the destination planet (where you are heading to).

The distance between the two planets will be defined as |x₁ - x₂| + |y₁ - y₂|, i.e., the sum of the absolute value of the difference in x and y.

This is called "Manhattan" distance because in Manhattan, streets are mostly perpendicular (with, say, lettered streets running one direction, and numbered streets running perpendicular to it). Thus, to navigate, you tell a person how many blocks to go east-west, and how many blocks to go north-south.

This kind of distance allows us to avoid using Pythagorean formula to compute distances (which creates floating point value). It allows us to access int values.

Your goal is to come up with a series of instructions (in the Plan object) that will get the passengers of a ship from the source planet to the destination planet and do so while attempting to minimize the cost. The cost will be the total fees (fuel and passenger). Gifts are not considered part of the cost of a flight.

HOWEVER, you are not required to find an optimal flight plan. As long as you find a plan that works, then that will be sufficient to pass the primary.

This is how you should compute the cost.

1. Find a nearby planet which can be reached from the source planet, and which the ship can land on (a WarShip lands on a planet can only land on a planet with a landing bay, a PeaceShip can not land on a WarPlanet with more than 1000 troops), within the range of the ship. If there's more than one planet, you can just pick one (of course, it is preferable to pick one with cheaper cost.

2. Add a Transport instruction to the plan. The cost of the Transport will be assessed at the next planet. Thus, if you are travelling from planet X to planet Y, and the nearest planet from X that's closer to Y is planet B, and you can land on planet B, then the fees are based on planet B (not on planet X).

   You should also add these fees to the total cost of the plan.

3. Once you are on the planet, you should then do a Collect instruction (add this instruction to the plan) if you have a WarShip, or Donate if you are a PeaceShip.

   A WarShip can always collect gifts from a planet (assume the planet has infinite number of gifts). The amount collected is determined by getTaxAmt on the planet that's just been landed on. Increment the number of gifts on the WarShip.

   A PeaceShip donates gifts at each planet, but may only do so if it has gifts. If it has no gifts, do not add a Donate instruction. If it has gifts, then donate the amount that the planet that's just landed on requires. Decrement the amount of gifts on the ship by that amount. If the ship has fewer gifts than the planet requires, then give the remaining gifts (it should now be at 0). When a ship has gifts to donate, it should add a Donate instruction.

   Update the number of total gifts donated/collected in the Plan object.

4. Finally, get fuel for the ship. The cost of the fuel on each planet is fixed. Each ship must fuel up on the planet it lands on (thus, if you source planet was X, and the first planet you land on is B, you must fuel up at planet B). Unlike gas prices, you do not base the cost per gallon. There is a single cost for fueling the entire ship.

5. Go back to step 1, and find the next planet.

The purpose of the Plan is similar to an itenerary that you might receive when you reserve a plane flight. That is, it tells you how much the flight will cost, and what are the intermediate stop points.

Again, you do NOT have to find an optimal plan. A simple heuristic is "find any planet that you can land on which is closer to the destination, and go to that planet".

You can make a smarter heuristic by making hops to the largest range the ship can fly and/or pick planets where the fuel cost and landing fees are the cheapest.

If you can't come up with a plan, just return a plan with a single instruction NoPlan. The primaries and secondaries will always have a valid plan, and all of them should work based on the heuristic given.

You may gain a little extra credit by producing plans with smaller total fees.

You must pay the landing fees, donation, and fuel costs at the final destination planet. However, no fees. donations and fuel costs are paid at the original source planet. Fees, fuel cost, etc. are paid at intermediate planets in the plan.

If the destination planet is invalid to begin with, return a plan that has NoPlan as its only instruction (for example, the destination planet may not have a landing bay, so a WarShip can't land on it, so it's not worth planning the trip).

Extra Credit

If you are concerned about time, then you may not want to do this.

Read the next task for more information.

It will do two things. It will verify that you have seated the passengers correctly. It will then verify that your plan actually works. If so, it will print a message that you are successful.

If not, it will print that you are unsuccessful. You will not be allowed to modify the Verifier program. Doing so may result in you not passing the primary (thus receiving a 0).

In the meanwhile, until this is posted, it's suggested that you do the following:

• Create a grid with two planets, within range of the ship, and see if you can create Plan that makes a single hop.
• Create a grid with three planets, and see if you can create Plan that makes a two hops.
• Create a grid with four planets. Put two planets in the middle and have one planet that you can land on, and one you can't. See if you can create a Plan that makes a two hops, but avoids the planet it can't land on.

There are other variations you should try testing on, which you should try before the primary is posted. It is strongly suggested you do these tests before then (only because there may be courses you take in the 400-level with no primaries, and therefore, it's your job to learn how to test the code the best you can, without such information).

These will check to see if your classes are working. However, you do not have to pass the drivers to submit primary (they should at least compile with the drivers, however).

These drivers will be posted in a few days.

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 p4 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 p4" 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.

   p4 < 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 p4.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 p4.tar 4