/* Lab 4 CSU 213 Spring 2006
This lab assignment will give you practice with developing methods for class 
hierarchies involving union, containment, and self-reference.  In addition, 
we will write comparison methods to build proper test suites in the 
Examples class.  
*/

//
// Part I:  Unions & Containment
//
/* We will use and build on this class hierarchy throughout the lab:
+-------------------------------------+
|             IShape                  |<----.
|double area()                        |     |
|boolean smallerThan(IShape that)     |     |
|IShape zoomIn(int factor)            |     |
|                                     |     |
|                                     |     |
|                                     |     |
|                                     |     |
+----------------------.--------------+     |
                      /|\                   |
      +----------------+-----------+        |
      |                |           |        |
+-----+-----+     +----+-----+ +---+-----+  |
|  Circle   |     |Rectangle | | Overlay |  |
|Posn center+--.--|Posn nw   | |IShape s1|--|
|int radius |  |  |int width | |IShape s2|--'
+-----------+  |  |int height| +---------+
               |  +----------+
               v
  +---------------------------+
  |          Posn             |
  |int x                      |
  |int y                      |
  |boolean samePosn(Posn that)|
  +---------------------------+

Now do the following:
I(a)  Translate this class diagram into Java code.  Do not forget your
      templates & examples!

Design the following two methods.  For each method, augment
the above class diagram with the method headers.
I(b)  // produce the area of this shape
      double area()

I(c)  // determine if this shape's area is smaller than `that' shape's area
      boolean smallerThan(IShape that)

Finally, design one more method:
I(d)  Design the method `zoomIn'.  It consumes a zoom-factor and produces an
      IShape like `this' one, except larger in both dimensions.
      Work out examples for each shape to figure out what this means!
*/

//
// Part II:  Comparisons for Union & Containment
//
/* Now we will write comparison methods to determine when a given 
   shape is equal to `this' one.

Let's recall how this works for a smaller example:
+------------------------------+
|           IMedia             |
|boolean sameMedia(IMedia that)|
|boolean sameBook(Book that)   |
|boolean sameCD(CD that)       |
+---------------.--------------+
               /|\
       .--------'----------.
+------'-----+        +----'-----+
|   Book     |        |    CD    |
|String title|        |int tracks|
+------------+        +----------+

The interface contains one `same' method for each class
(including the interface itself).

Each class that implements the interface must define each of the methods.
*/
// represent media in the library (a Book or a CD)
interface IMedia {
  // determine if this is the same IMedia as that
  boolean sameMedia(IMedia that);
  // determine if this is the same Book as that
  boolean sameBook(Book that);
  // determine if this is the same CD as that
  boolean sameCD(CD that);
}
/* In the Book class, sameBook(Book that) simply compares this.title with
that.title, and in the CD class sameBook(Book that) simply returns false
because Books and CDs are never the same.
*/
// represent a book by its title
class Book implements IMedia {
  String title;
  Book(String title) { this.title = title; }
  boolean sameMedia(IMedia that) {
    return that.sameBook(this);
  }
  boolean sameBook(Book that) {
    return this.title.equals(that.title);
  }
  boolean sameCD(CD that) { return false; }
}
/*
Likewise, in the CD class, sameCD(CD that) compares this.tracks with
that.tracks, and in the Book class, sameCD(CD that) always returns false.
*/
// represent a CD by the number of tracks
class CD implements IMedia {
  int tracks;
  CD(int tracks) { this.tracks = tracks; }
  boolean sameMedia(IMedia that) {
    return that.sameCD(this);
  }
  boolean sameBook(Book that) { return false; }
  boolean sameCD(CD that) {
    return this.tracks == that.tracks;
  }
}
/* To tie these pieces together, each class must then implement
sameMedia(IMedia that).  In order to tell if two media are the same,
we need to know two things:
1.  Are they instances of the same class?
2.  If so, are the fields in `this' equal to the fields in `that'?

We let Java answer question 1 for us (in two steps).  Suppose we have 
some IMedia:

  IMedia m = new ...;
  IMedia n = new ...;

We would like to know if m and n are equivalent.  When we say

  m.sameMedia(n)

Java will notice that there are 2 different sameMedia methods (one in Book,
another in CD).  To decide which one to invoke, it will look up the class of 
which m is an instance.  

Suppose m is a Book object.  Then Java will execute the sameMedia(..) method
inside the Book class.  This will, in turn, invoke 

  n.(sameBook(this))

where `this' is the book m.  At this point Java knows that m is a Book.
But, since n is an IMedia, Java must now look up the class of n to determine
 which sameBook(..) method to invoke.  If n is a CD, we will invoke CD's 
sameBook(..) and return false.  If n is a Book, then we will invoke Book's 
sameBook(..) and compare the two titles.
*/

/* 
II(a)
   Now it's your turn.  Design comparison methods for shapes.
   We have left room in the diagram above for you to fill in
   the necessary method headers.  Do this before you begin coding.
   This step involves a lot of code.  Work on one method at a time, and
   design the sameShape method last. 
*/

//
// Part III:  Lists of IShapes
//
/* Now we will build lists of IShapes.  We will then design methods
 (1) to compare equality of two lists of shapes
 (2) to compute the total area of all of the shapes in a list of shapes
 (3) to zoom all of the shapes in a list of shapes by a given factor
 (4) to sort a list of shapes in increasing order of their area

III(a):  Design a class hierarchy for a list of shapes.  You must
         produce the class diagram.  Use the ASCII art tool JavE
         at http://www.jave.de to draw it.  Use version 6, not 5.

Once you download and start JavE, copy and paste the IShape hierarchy
from above into it.  Then add the boxes and arrows to represent list of
shapes to the diagram.  Once you do this, copy and paste the whole thing
back into this lab below.
*/

/*
III(b):  Design method (1) above to compare lists of shapes for equality.
         Follow the same pattern that you used to design the methods
         for shape equality.  Once you have tested these methods, use
         them to write tests for the rest of the methods in this section.
*/

/*
III(c):  Design methods (2) and (3) from above:
         - compute the total area of all of the shapes
         - zoom all of the shapes by a given factor
         
         Test these methods using the comparisons you designed in III(b).
*/

/*
III(d):  Design method (4).  Use the insertion sort technique as discussed in
         lecture.  Remember that this will require you to write two methods on
         list of shapes:
         - One helper method `insert' for inserting a given Shape into a sorted
           list of shapes.
         - Another method `insertionSort' that sorts `this' list of shapes.
*/

//
// Part IV (Challenge Problem):  Quick Sort
//
/* What, you're done with Parts I, II, and III already?  
   Then try designing a quickSort method!  It ought to behave just like the
   insertion sort above, but it often runs much faster on large lists.

We will illustrate by example how quickSort works:
Consider the following list of integers L.
  
  L = (list 8 2 7 9 3)

We begin by choosing an arbitrary element called the "pivot".  For
simplicity, we will always choose the first element.  So let 

  pivot = 8.

We then proceed to partition the rest of the list, (list 2 7 9 3), into two
smaller lists.  The first list contains those elements smaller than the pivot,
and the second list contains those elements larger than the pivot.  So let

  smallerInts = (list 2 7 3)
  largerInts  = (list 9)

We sort each of these using a recursive call to quickSort.  Then, to build the
whole sorted list, we simply append the sorted list of smaller elements to the 
list of sorted larger elements, sticking the pivot in the middle (hence the 
name -- the pivot stays put while the other elements "revolve" around it).

  smallerInts.quickSort() = (list 2 3 7)
  largerInts.quicksort()  = (list 9)
  pivot = 8

  Answer = (append (list 2 3 7) (cons 8 (list 9))) 
         = (list 2 3 7 8 9)

That concludes our example.  To design quickSort, you will need helper methods 
for appending lists, for selecting elements smaller than a given element, and 
for selecting elements larger than a given element.

After you've designed and tested quickSort, ponder this:  on what kinds of lists
will your quickSort perform the worst on (in terms of running-time)?  Why?
What part of your implementation would you have to improve to avoid performing
poorly on these kinds of lists?
*/