CS1322 - Fall 2002 - Program 4

*** NOTE: THIS FILE IS BEST VIEWED IN AN EDITOR WITH 80 CHARACTER
    COLUMNS PER ROW ***

Assigned: Tuesday, October 15th, 2002
Due: Monday, October 28th, 2002 at 23:59:59
Stop Accepting: Tuesday, October 29th, 2002 at 08:00:00
Phase II Instant Feedback Deadline: Monday, October 21st, 2002 at 23:59:59
Phase IV Instant Feedback Deadline: Monday, October 28th, 2002 at 23:59:59

Title: "Java Goes to Sea"


TOPICS
======================================================================

Topics you should already understand that are relevant to this project:

       o .equals method
       o Polymorphism/Dynamic Binding
       o Linked Lists
       o Object I/O
       o Useful Tools (Vector, StringTokenizer)

Topics you will learn from this project:

       o Comparable
       o Binary Search Trees
       o Heaps
       o File I/O

Files provided to you for this project:

       o P4.nfo.txt		This file
       o aircraftFile.txt	An input data file for this project

*NOTE: You are strongly encouraged to read this nfo file completely
 before starting on the project.



PROJECT OVERVIEW
======================================================================

Welcome to the 4th programming assignment!  After hearing about your
prowess with programming data structures in Java, the United States Navy
has asked you to develop a program to manage aircraft carrier flight
operations.  Aircraft storage in the hangar deck has become extremely
disorganized and badly needs a data structure to maintain order
efficiently.  At the same time, the aircraft launched off a carrier
must be deployed in a specific order to properly protect the
ship as well as complete mission objectives.  The Navy will provide
you a text file containing aircraft.  It is up to you to maintain a
representation of these aircraft in alphabetical order by aircraft
nickname while they are waiting in the hangar deck.  The skipper of
the carrier also wants to be able to locate an aircraft by nickname as
well as throw an aircraft overboard (delete it) if need be.  We will
call a group of aircraft a "Strike Package".  When the captain is
ready to launch the strike package, he needs the aircraft ordered no
longer by nickname but by their launch priority.  The Navy also wants
you to log (write to a file) the alphabetically ordered aircraft as
well as the launch of the strike package.  You will need a simple menu
system to control the Navy's new software.   



PHASE I - Aircraft (Approximate Coding Time: 1 hour)
======================================================================       

Comparable
-----------------------------------

So...why was the .equals method so great anyway?  It's great because
it allows the programmer to customize the notion of equality.  It was
up to him or her to decide whether or not certain attributes of an
object were relevant or not when determining the equality of two
instances of that class.  We will now take that concept one step
further by allowing the programmer to customize the notion of not just
equality but also "greater than" and "less than".  We are no longer
limited to saying that two instances are simply unequal.  We can now
say that this instance is "less than" that instance and that some
other instance is "greater than" yet another instance.  In order to
provide the ability for instances of a class to compare themselves to
each other, we need to have that class implement a special interface:
Comparable.  As in:

	   public class BabySeal implements Comparable {

Comparable has one method: 

	   public int compareTo(Object o)
	   
which is used in a similar manner to .equals.  The int return value of
compareTo represents our "less than", "greater than", or "equals"
concepts.  Lets say that objects A and B are both instances of the
same class.

     If A is LESS than B, the method call
     A.compareTo(B)
     will return an int LESS than zero.

     If A is GREATER than B, the method call
     A.compareTo(B)
     will return an int GREATER than zero.

     If A is EQUAL TO B, the method call
     A.compareTo(B)
     will return an int EQUAL TO zero.  


So how do we figure out what constitutes a "less than" or "greater
than" relationship.  That's up to you and the demands of the problem
we're trying to solve just as what constituted equality with .equals
was up to the demands of the problem.  The guts of a compareTo method
will remind you of .equals.  

     1. We first must check to see that the object passed in is, in
     fact, an instance of the same class to which we are comparing it.
     2. We then must cast the parameter (since it came in as an Object
     parameter) to the correct class.
     3. We then perform the necessary operation to decide the
     relationship and return an int representing that relationship.

See the lecture slides for more help


Aircraft.java
-----------------------------------

Create a class called Aircraft.	 The instances of this class will
represent the aircraft we're managing for our aircraft carrier.  We
are going to be sorting these Aircraft instances in a couple different
ways: alphabetically by nickname and by launch priority.  Since we are sorting
them, we will need to determine whether any given Aircraft is greater
than or less than another Aircraft.  Sounds like we're going to need
to have Aircraft implement Comparable.

Your Aircraft class should have the following:

     o A private instance variable called "model" of type String
     o A private instance variable called "nickname" of type String
     o A private instance variable called "role" of type String
     o A private instance variable called "launchPriority" of type Integer
     o All accessors and modifiers
     o A public Constructor taking in all four above instance variables
     o A public Constructor taking in only the nickname and chaining to the
       first Constructor

     o A fifth private instance variable called "comparator" of type
     Comparable.  This variable is what we will use to determine the
     greater than/less than relationship between Aircraft.  It will
     hold a duplicate of either the nickname or the launchPriority.
     Remember, we want to order the Aircraft by nickname while they are
     waiting and we want to order them by launchPriority when they are
     being deployed from the carrier.  This variable should initially be
     set to the nickname.

     o A public method called switchComparators which takes in no parameters
     and returns void.  This method will toggle the comparator
     variable between the nickname and the launchPriority.  If the
     comparator is currently holding the nickname when this method is
     called, switch it to the launchPriority and vice versa.

     o the public compareTo method which will compare the comparator
     variables of the two Aircraft instances and return this
     comparison. (HINT: String and Integer also implement Comparable)

     How you choose to handle the case where the parameter is not the
     same class as "this" is up to you.  Your means of handling such a
     case should be for debugging purposes only.  You should never
     allow such a case to actually occur.

     o A public toString method which prints out the following: 

     <model> <nickname> of Type <role> with launch priority <launchPriority>
     (i.e.  F-14 Tomcat of Type Interceptor with launch priority 8)

     NOTE:  All instance variables should be private



PHASE II - Binary Search Trees - INSTANT FEEDBACK
(Approximate Coding Time: 2 hours)
======================================================================

So what exactly _is_ a Binary Tree? A Binary Tree is a dynamic data
structure that is similar to a linked list, except that each node has two
"nexts" instead of just one.  We don't call them "next1" and "next2";
instead we call them "left" and "right".  Any nodes to the left or right
of a node are it's children.

So what exactly _is_ a Binary Search Tree (BST)?  A BST is a special Binary
Tree that takes on a certain structure based on the ordering (values) of
the nodes.  This structure dictates that all children on the left of a node
are "less than" that node and all children on the right are "greater than"
that node.  The ordering (the concept of "greater than" and "less than") is
whatever we define it to be for certain data.

For example, the simplest BST is the empty BST.  In this case, the "root"
reference would be null.

     _|_
     ---

Suppose we have a Binary Search Tree (BST) with just one node in it.  In
this case, root would refer to a node, and that node's left and right
references would be null.  Let's say its value is 5.

    +-----+
    |  5  |
    +-----+
   _/_   _\_
   ---   ---

If we add 3 to this tree, the BST would determine whether 3 is less than 5.
Since it is, the BST would add 3 to the left.  This maintains the order of
the BST.

        +-----+
        |  5  |
        +-----+
       /
+-----+
|  3  |
+-----+

If we add 7 to the tree, the BST would add it to the right since 7 is
greater than 5.

        +-----+
        |  5  |
        +-----+
       /       \
+-----+         +-----+
|  3  |         |  7  |
+-----+         +-----+

If we add 4 to the tree, the BST would go the left since 4 is less than 5,
then it would compare 4 to 3 and add 4 to the right since 4 is greater
than 3.

         +-----+
         |  5  |
         +-----+
        /       \
       /         \
+-----+           +-----+
|  3  |           |  7  |
+-----+           +-----+
       \
        +-----+
        |  4  |
        +-----+

That was a quick intro to Binary Trees.  This program will require you to
implement some more sophisticated algorithms.

Traversals
---------------------------------------------

A traversal is the examination of each node in the BST

Pre-order traversal-                                     15
    perform action->go left->go right                 /      \
    (15,8,4,12,37,31,97)                            8	       3
                                                  /   \      /    \
In-order traversal-                             4      12  31      97
    go left->perform action->go right          
    (4,8,12,15,31,37,97)

Post-order traversal- 
    go left->go right->perform action
    (4,12,8,31,97,37,15)


A few Algorithms for your viewing pleasure...
---------------------------------------------
Below are a few Algorithms that should prove useful.

   ADDING
   ------
      1) Check and see if your root is null.
         a) If your root is null, then go ahead and set the root to a new
            Node containing the data passed in.
         b) If the root isn't null, then pass the data and root to the
            helper.
      2) Compare the value in current to the value passed in. If the value
         of the new data is greater than that of the data already in current,
         then we want to go right. Otherwise we want to recurse left.
         a) Before going left or right, check and see if that direction is
            null. If it is, then go ahead and do a current.setLeft() or
            current.setRight() with a new Node. Otherwise, even when you
            change the value of current passed in, it's parent is still
            pointing to null.
      3) Recurse in the direction you decided, and continue doing the checks
         until a null value is found.

   FIND
   ----

      1)  Check and see if your root is null.
          a) If your root is null, return null - the value wasn't found
          b) If the root isn't null, then pass the data and root to the
            helper.
      2) Compare the value in current to the value passed in.  If the
          value in current is equal to the value passed in, we found
          our target.  If the value of the new data is greater than
          that of the data already in current, then we want to go
          right. Otherwise we want to recurse left. 
         a) Before going left or right, check and see if that direction is
            null. If it is, then go ahead and return null - the value
	    isn't present.
      3) Recurse in the direction you decided, and continue doing the checks
         until a null value is found.


   DELETE
   ------

      The exact algorithm of deletion from a list is left up to you.
      Here are a few guidelines though.  There are three cases of node
      deletion to consider:

      - Deleting a node with no children (i.e. a leaf node): Simply
        set this node's parent to null.

      - Deleting a node with one child: Have the parent of the node to
        delete point to the child of the node to delete effectively
        skipping over the target node

      - Deleting a node with two children: This case is significantly
        more involved.  You must replace the target node with the node
        from the left subtree with the greatest value or replace the
        target node with the node from the right subtree with the
        least value.  As an example:


                          10  <- 10 is the root and the node to delete
                        /    \
                      5        15
                    /   \     /   \
                   3     7   12    18
                  / \   / \  /\    / \
                 1   4 6  9 11 14 17  19
                
		
	   9 is the greatest node of the left subtree
	   11 is the least node of the right subtree

	   The resulting tree would be: (we could have used 11 too.
	   It's up to you)

                          9
                        /    \
                      5        15
                    /   \     /   \
                   3     7   12    18
                  / \   /    /\    / \
                 1   4 6    11 14 17  19

	   If we were deleting 15, 14 would be the greatest node of
	   the left subtree and 17 would be the least node of the
	   right subtree.
	
	Replacing the target node with the appropriate node ensures we
	maintain the proper BST structure


Now for the project ....

Create a class called BSTNode.  We want to be able to compare our
BSTNodes to each other to determine where they would go in a Binary
Search Tree.  So make sure your BSTNode implements Comparable.

Your BSTNode class should include the following:

     o A private instance variable called "data" of type Comparable
     o A private instance variable called "left" of type BSTNode
     o A private instance variable called "right" of type BSTNode
     o All accessors and modifiers
     o The public compareTo method which should return the value of the
       compareTo method of the "data" instance variable
     o A public toString method which should return the value of the
       toString method of the "data" instance variable

Create a class called BST.  This class will arrange BSTNode instances
in the proper "left < parent < right" order.

Your BST class should include the following:

     o A private instance variable called "root" of type BSTNode
     o The public method "add" which takes in a Comparable and returns void.
       The Comparable parameter will be the data to add, not a
       BSTNode.  So you will need to create a new BSTNode with this
       Comparable.  Why don't we take in an Object as with
       LinkedLists?  We need to ensure that the data coming can, in
       fact, be compared to other data in the tree so we can order the
       tree properly.
     
     o The public method "find" which takes in a Comparable and returns
       Comparable.  This method should locate the data in the tree
       that matches the parameter passed in (according to the
       compareTo method).  If no such match exists, return null;

     o The public method "remove" which takes in a Comparable and returns
       Comparable.  This method will locate the data in the tree that
       matches the parameter passed in (according to the compareTo
       method) and remove it from the tree while maintaining the BST
       property.  You should then return the data in the tree that
       matched this parameter.  If no data matching the parameter is
       found, return null.

     


PHASE III - Reading in the Aircraft from a file
(Approximate Coding Time: 2 hours)
========================================================================

This phase deals with reading in the aircraft from a file and storing
them.  Provided to you is a file called "aircraftFile.txt".  If you
open this file, you'll notice that there is one aircraft per line each
with four pieces of data separated by spaces.  These correspond to the
four instance variables of the Aircraft class.  You will be reading in
each line of this file, creating a new Aircraft instance from the data
on this line, and then storing it in a BST.  Since the comparator
variable in Aircraft is initially set to the nickname, we can be sure
that the Aircraft are stored in the BST alphabetically by nickname.

Create a class called AircraftCarrier.  Your class should have the
following:
	
	o A constant (use the keyword "final") called FILE_NAME which
	matches the name of the file to read in

	o A private instance variable called "aircraftBST" which is of type
	BST.  This variable will store our Aircraft instances in
	alphabetical order by nickname. 

	o A private instance variable called "strikePackageReady" which is of
	type boolean.  This variable should initially be set to
	false.  This variable will ensure we do not try to launch a
	strike package before the BST is filled with aircraft

	o A method "findAircraft" which takes in no parameters and
	returns void.  This method will be private.  This method will
	prompt the user to enter the nickname of an aircraft to find
	using the keyboard. (You can use IOHelper if you wish)  You
	should then perform a search of aircraftBST for an Aircraft
	matching this nickname.  If a match is made, print out the
	Aircraft, otherwise print "No Aircraft Found".  If
	strikePackageFound is set to false then the above actions
	should not be performed.  Instead you should print "Strike
	Package Not Ready".

	o A method "throwAircraftOverboard" which takes in no
	parameters and returns void.  This method will be private.
	This method will prompt the user to enter the nickname of an
	aircraft to remove using the keyboard. (You can use IOHelper
	if you wish)  You should then attempt to remove the Aircraft
	matching this nickname from the BST.  If a removal is made,
	print out the Aircraft removed, otherwise print "No Aircraft
	Found".  If strikePackageFound is set to false then the above
	actions should not be performed.  Instead you should print
	"Strike Package Not Ready".


	NOTE:  You cannot simply pass in the String containing the
	nickname to the find and remove methods.  You cannot call
	compareTo between two different instances (Aircraft and
	Strings).  Think about the Constructors you made in Aircraft.


	o a method "createNewStrikePackage" which takes in no
	parameters and returns void.  This method will be private.
	This method opens aircraftFile.txt for reading and loads the
	BST with the newly created Aircraft instances.  Use a
	StringTokenizer to separate the four pieces of data per line:

	private void createNewStrikePackage() {

	  assign a new BST to aircraftBST  (Be sure you do this! We
	  don't want any old aircraft from our previous strike package
	  in the BST representing this new strike package)

	  open file for reading
	  while more lines
	     use a StringTokenizer to gather the model, nickname, role
	        and launchPriority for this Aircraft
	     instantiate the Aircraft
	     add it to the BST
	  end loop

	  close the file
	  
	  set strikePackageReady to true  (Our strike package is now
	  ready for launch)

	*NOTE: The data the autograder will use always contains 4
         tokens per line: 3 Strings and an int.

	o a private method "printStrikePackage" which takes in no parameters
	and returns void.  This method will be private.  This method
	opens a file called "strikePackage.txt" for writing.  The
	method will perform an in-order traversal of aircraftBST and
	print one node per line.  At the end, your file should have
	one Aircraft per line sorted by nickname.  You should not have
	any aircraft from any previous printings.  Don't forget to
	close the file. 



PHASE IV - Heap - INSTANT FEEDBACK
(Approximate Coding Time: 3 hours)
========================================================================

Please refer to the following for all your Heap learning needs:

http://www.cc.gatech.edu/classes/AY2003/cs1322_fall/
test_resources/current/study.html#heaps
 


Create a class called Heap that includes the following:

     o a private instance variable called "data" of type Vector.  This
     Vector will hold the data of your heap. 

     o the public method "insert" which will take in a Comparable and
     return void.  This method will insert the Comparable into the
     heap maintaining heap structure.

     o the public method "remove" which will take in no parameters and
     return a Comparable.  This should remove the next element from
     the heap (which should be the element with the highest priority)
     while maintaining heap structure.  If the heap is empty, return
     null.

     o the public method "isEmpty" which takes in no parameters and
     returns a boolean.  The method will return true if there are no
     more elements in the heap and false if there is at least one more
     element.



PHASE V - Filling in AircraftCarrier
(Approximate Coding Time: 1.5 hours)
========================================================================

Go back to AircraftCarrier.  We will now be adding the ability to
launch our Aircraft in order by launchPriority.  Our program will be
controlled through the use of a text menu displayed in the console.

Add the following to the class AircraftCarrier:
   
     o a private instance variable called "launchQueue" of type Heap.  This
     variable will hold the aircraft ordered not by nickname as in
     aircraftBST but instead by launchPriority.  
			
     o a method "launchAircraft" which takes in no parameters
     and returns void.  This method will be private.  In this method,
     you first must instantiate launchQueue.  Then you must traverse
     aircraftBST in a manner of your choosing.  At each node, store
     the aircraft data in a temporary variable.  You should then delete
     that Aircraft from the tree.  Then insert the aircraft into
     launchQueue.  Remember, however, we want to order the aircraft by
     launchPriority now.  But the compareTo method of Aircraft
     currently orders instances by nickname because that's what the
     comparator is set to.  So before you insert the data into the
     launchQueue, call switchComparators on the temporary Aircraft variable
     to switch the compareTo method to order instances by launchPriority.

     After filling your heap, launch the aircraft from the carrier.
     (Remove each Aircraft from launchQueue until the launchQueue is
     empty)  When you launch an Aircraft, you should display that
     Aircraft to the screen as well as write that Aircraft to a file
     called "launchLog.txt".  At the end of the launching you should
     have a file containing each Aircraft launched.  You should not
     have any previous aircraft from any previous launches.  The
     aircraft should appear sequentially by launchPriority.  Don't
     forget to close the file.

     Be sure to set "strikePackageReady" to false since the BST is empty.

     o a private method "doMenu" that should display the following to the 
       screen

         1) Create New Strike Package
	 2) Find Aircraft
	 3) Throw Aircraft Overboard
	 4) Print Strike Package to file
	 5) Launch Aircraft
	 6) Quit
     
     Your method should read in the user's choice and call the
     appropriate method.  If the user enters something other than a
     number between 1 and 6, print an appropriate error message and
     redisplay the menu.  If the user enters 6, the program should
     exit gracefully.

     o a public constructor that takes in no parameters.  This constructor
     will call doMenu.



PHASE VI - Wrapping it up
(Approximate Coding Time: 1 hour)
========================================================================

Create a driver class called P4 with a main method.  This main method
will instantiate AircraftCarrier.

TEST TEST TEST!!

     o Verify the output files generated by your program contain the
     proper data in the proper order.

     o You may feel free to make up your own aircraft if you feel the
     ones we provide aren't enough.  Keep in mind that the data the
     autograder will use to test is not the data in the file provided
     to you.  The data the autograder uses will in no way attempt to
     "trick" your program.

     o Your program should exit gracefully in all circumstances.  This
     means no uncaught exceptions/stack traces.

     o Many of you have been doing debug printing in your project
     through bDEBUG or otherwise.  This is outstanding.  Keep it up.
     Problem is, you're supposed to stop printing debug prints for the
     final submission.  You may lose style points if you leave them in.

     o !!! HEY !!!  At no point during your program should you put
     System.exit(...).  When we are grading your project this will
     cause the autograder to quit as well and we, the TAs, will be
     most unhappy about this.

As an aside, you are permitted and in some cases encouraged to add any
helper methods or instance variables not explicitly mentioned that you
feel will help to accomplish the above tasks.  

Don't forget that when submitting files to webwork, submit ALL your
files.  Good Luck!

     
     


	      
