CSC 171
Homework 5
Polymorphism, Inheritance, and Lists

Assigned Apr 1, due Apr 15

For each method, be sure to follow the design recipe for methods.

For each animation, be sure to follow the design recipe for animations.

Be sure to choose meaningful names for methods and parameters, and watch for opportunities to re-use methods you, I, or Dr. Stemkoski have already written.

Also turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one ("mismatched parentheses" is self-explanatory, but more complex errors might need more description). You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

How to turn this in

You are encouraged to do this in teams of two students; turn in one copy of the project with both names on it (in the README file or in comments in the Java source files). Even if you do the assignment without a partner, make sure your name is on it.

1. Recall the PlacedCircle class from homework 4.

   • Define a data class named PlacedRect which represents a mathematical rectangle in the plane, with a width, a height, and a top-left corner. (Assume that the edges are parallel to the x and y axes.) As before, you should write a constructor, a toString method, a same method, getters, and a test class.
   • Write a method area, like that in PlacedCircle.
   • Write a method contains, like that in PlacedCircle.
   • Add a method perimeter to both this class and PlacedCircle.
   • Write a method overlaps, like that in PlacedCircle but taking in a PlacedRect instead of a PlacedCircle.
   • Add a method makeImage to both this class and PlacedCircle, producing an outlined image of the specified shape moved to the specified location.
   • Define an interface Shape which both PlacedCircle and PlacedRect implement. Put into it the methods that both classes define.
   • Write a method containsBoth that takes in two Posns and tells whether the shape contains both of them. Note that this method can be written exactly the same for both PlacedCircle and PlacedRect, so rather than writing it twice, put it in an abstract class AShape which “sits between” the interface and the classes.
   • Politicians are frequently accused of gerrymandering, which means drawing lines between voting districts to make sure they and their friends stay in office, while the other party can't get elected. This often shows up on the map in the form of long, skinny, oddly-shaped districts. Some people have proposed avoiding this with an objective standard that can't be skewed by political influence: for example, not allowing districts to be too long-and-skinny.
     Write a method named skinny which returns true if the square of the perimeter is more than 30 times the area, and false otherwise. Hint: Avoid writing the same code twice.
   • Extra credit: Modify the overlaps method so that it takes in a Shape, so it too can be put into the interface. (The tricky part is telling whether a circle and a rectangle overlap....)

2. Recall the StringList data structure from Mar. 27's class. Add the following methods to it:

   • toString, with a nice output format like "['larry', 'moe', 'curly']".
   • countMatches, which takes in a String, and counts how many elements of the list are the same as that String.

3. Define an IntList data structure to represent a variable-length list of integers. This should be very similar to the StringList data structure developed in lecture. Define the following methods on it:

   • countElements (just as in StringList).
   • addAll, which produces the sum of all the numbers in the list.
   • multiplyAll, which produces the product of all the numbers in the list. (Hint: what's the right answer to the empty case?)
   • countOver, which takes in an int and tells how many of the list elements are larger than it.
   • convertReversed, which converts a list of digits to a single number. The list of digits is presented ones place first (trust me, this makes the problem easier!). So for example if the numbers were 6,2,0,5,3, the right answer should be 35026.
     Do not use String operations for this problem: you should be able to do it with arithmetic.
   • bullsEye, which (given a list of numbers) produces an image with concentric black outlined circles at those radii. For example, if the list contained the numbers 13, 187, and 49, the result would be
     AImage.makeCircle(13).overlay(AImage.makeCircle(187).overlay(AImage.makeCircle(49)))
   • largest, which producs the largest of a list of numbers. This doesn't actually make sense for an empty list, so you'll probably want largest to live in the NonEmptyIntList class, but it'll need a helper function which is defined for IntLists in general.
   • deleteOver, which takes in an int and produces an IntList just like the given one, but leaving out any elements that were larger than the given number. For example, if the original list was 1,3,7,6,7,4 and we called deleteOver(4), we should get 1,3,4.
   • Extra credit: countBlocks. Given a list of numbers which may contain repetitions, this function tells how many blocks of repeated numbers there are. So for example, if the list was 3, 3, 2, 7, 7, 7, 2, 2, there would be four blocks: a block of 3's, a block of 2's, a block of 7's, and another block of 2's.
     Hint: You'll probably need a helper function that takes in an int as well as operating on a list.

4. Develop an animation that displays a bullseye pattern of black outlined circles on a white background. Each second, an additional ring is added three pixels outside the previous outer ring.

   Hint: Use an IntList as the model.

5. Develop an animation that starts with a blank screen, and every second adds a dot at a random location. If you click on any of the dots, the game ends. (As the screen fills up, this becomes really easy!)

   Hint: Use a PosnList as the model.

6. Back to the StringList class... Write a method tallyVotes which, given a list of Strings representing votes, produces a list of Candidates: each name that got at least one vote should appear exactly once in the list of Candidates, associated with the number of votes that name got. For example, if the votes were
   Bob, Alice, Mary, Bob, Mary, Bob
   then the answer should be something like
   new Candidate("Bob",3), new Candidate("Alice", 1), new Candidate("Mary",2)

   In the CandidateList class (which you wrote in order to do tallyVotes), add a method named sortByVotes that returns a CandidateList with the same elements, but sorted in decreasing order of vote count. So in the above example, the result of sortByVotes would be
   new Candidate("Bob",3), new Candidate("Mary",2), new Candidate("Alice",1)

7. Extra credit: Develop an animation that starts with a blank screen. Every time you press the + button, a ball is added at a random location, moving in a random direction, and bouncing off walls when it hits them. Every time you press the - button, the most-recently-added ball (if any) is removed.

   Here's a video of the game in action. (Actually, I wrote this one in Scheme, not Java, but it's the same problem.)

8. Extra credit: (This problem isn't particularly hard, but it's one more problem in an already-long assignment.)
   Recall that the Shape interface currently has two subclasses: PlacedCircle and PlacedRect.
   Add another subclass named CombinedShape. A CombinedShape is made up of two other Shapes: it could be two PlacedCircles, two PlacedRects, one of each, even one or two other CombinedShapes. Make sure the area, contains, perimeter, makeImage, and skinny methods work for this too.
   (For area and perimeter, assume the two shapes don't touch one another, so you can just add the areas or perimeters of the sub-Shapes. Trying to find all the intersections is much more difficult....)
   (If you got overlaps to work correctly between circles and rectangles, it's probably not hard to get it to also work with CombinedShapes.)

Grading standards

Error log:       /50
(I'm not grading on how many or how few errors you encountered, only on whether you recorded them adequately.)

Programming: To save time and get you feedback more quickly, we won't grade all of the problems, but a selection of them. Each animation requires writing a class with two or more methods; in some cases you'll also need to write a new class to be the model.

• 5 points for the contract and purpose of a method;
• 5-10 points for the test cases of a method;
• 5 points for the skeleton and inventory of a method;
• 10-20 points for the body of a method
• 10-20 points for the skeleton of a class

General skills: