3.3. MODULAR PROGRAMMING

This section under major construction.

Layers of abstraction.

When specifying the set of values for a Java class, we can include data members which are either primitive types or reference types. This enables us to build objects from other objects, and build layers of abstractions. In literature, we have letters, words, sentences, paragraphs, chapters, and books. In music we have notes, chords, measures, phrases, parts (musical event for one performer), movements, symphonies. Each note encapsulates its pitch, dynamic, and duration. In chemistry we have atoms, molecules, compounds. In a poker game, we have cards, the deck, hands, the dealer, and players. Classic example = networking (http, tcp, ip, etc.) Use abstratcion to understand and decompose complex systems.

Modules. Decompose problem into individual re-usable data types. Each data type has its own well-specified interface, which makes it suitable for use as a black-box component in more complex system. Composition: combine data types to build more complex data types. Intuition: Although commercial aircraft are sold by one company, no company manufactures all of the parts and components to build it. The airframe, engine, and avionics are all made by different companies. In order for them to interact properly, a system architect must completely spec out the interfaces of each part. Commodity PCs work the same way: video card, Ethernet adapter, mouse, monitor, operating system are typically made by different companies.

Modules in Java. In Section XYZ we built user-defined types from primitive types, strings, and arrays. In this section we will also build user-defined data types from other user-defined data types. Offers many advantages for building software systems.

Work flow. Team of programmers can each work on one data type in parallel.
Testing. Each data type can be tested and debugged independently.
Code reuse. Reuse the data types in other applications.

Computational geometry.

We create a number of data types for geometric objects in the plane. Although we will only introduce a tiny set of computational geometry primitives, they arise in numerous applications, including computer graphics (movies, games, virtual reality), computer vision, data mining, VLSI design, mathematical models of the physical world (maps, architecture, medical imaging), astronomical simulations, scientific computing, and and geographic information systems.

Points. Program Point.java is a data type for points in the plane. It contains methods for drawing and computing the distance to another point.
Circles. Program Circle.java is a data type for circles. We represent a circle by its center (a Point) and its radius (a double). It contains methods for computing the area and perimeter, determining whether a Point is inside the circle, and determining whether two circles intersect.
Create a data type BoundingBox that represents a bounding box. A bounding box is an axis-aligned rectangle. In addition to a constructor, it should have a method union so that a.union(b) return a new BoundingBox that is the smallest bounding box that contains both a and b. The constructor should take an array of points, and return the smallest bounding box containing each point. Also, add methods to determine whether a point is inside a bounding box or whether two bounding boxes intersect, area, perimeter. Program Rectangle.java is a data type for axis-aligned rectangles.
Polygons. Polygons are a useful mathematical abstraction for representing the shapes of real-world objects (letters for optical character recognition, obstacles to be avoided by a robot, US congressional district, pieces of an airfoil). Program Polygon.java is a data type for closed polygons. A polygon is a sequence of points p₀ through p_N, where we assume the first point is equal to the last point, i.e., the polygon is closed. The perimeter is the sum of the Euclidean distances of the N line segments. The signed area of a non self-intersecting polygon is given by

The polygon is counterclockwise if the area is positive. We assume the points are indexed 0 through N-1 and that point N equals point 0. The centroid (or center of mass) of a non self-intersecting polygon is given by the point (x, y) where x and y are defined by

To draw a shaded polygon on screen, we need to know whether each pixel (i, j) is inside or outside the polygon. Jordan curve theorem implies any polygon partitions plane into a finite inside region and an infinite outside region. Solution (ray crossing method): draw a ray from (i, j) down and count the number of times it crosses the polygon (even = outside, odd = inside). Intution: think of polygon as a fence and count # times you jump over the fence.

Reference: David Eppstein.

Composing data types.

Data type composed of an array and an integer (polynomials). Data type composed of two user-defined data types. Complex polynomial (implement as array of Complex objects, or two Polynomials, real and imaginary). Take power series of e^z = 1 + z + z^2/2! + ... and evaluate at z = i * Pi to get -1 (Euler's formula). Polynomial with rational coeffficients. Complex rational. Arbitrary precision rational polynomial: taylor series.

Transfer function. A transfer function models how the output of a system changes according to the input. Transfer functions arise in all areas of engineering, and can model the speaker in cell phone, the lens of a camera, or a nuclear reactor. The transfer functions associated with seismometers (and many other mechanical and analog electronic systems) are ratios of two (frequency domain) polynomials with real coefficients p(s) / q(s). Such transfer functions arise frequently in systems and control theory since the Laplace transform of common signals results in ratio of two polynomials. Zeros are values where numerator is 0, poles are values where denominator is 0. Poles are zeros are of fundmanental importance in understanding the behavior of the underlying system. Poles govern stability. If a system is stable and the input is changed, the output will converge to a constant value; if it is unstable (e.g., nuclear reactor at Chernobyl) the output will grow or fall indefinitely. If system is stable, then the real parts of all poles are positive. Zeros affect design of feedback controller. Ex: (3z - 1) / (z - 1/3)(z^2 - 1), 30(z-6)/ z(z^2+4z+13), (s+1)(s^2 + s + 25)/ s^2(s+3)(s^2+s+36).

A card game.

We will create a card game application that shuffles and deals out a deck of 52 cards to four players, as in bridge or hearts. We divide up our problem by creating objects for each of the main components in our card game. The physical game has playing cards (Queen of spades, four of clubs, etc), a deck (of 52 cards), and four players (each of which is dealt 13 cards). We build up our program in small modules by creating data types for each of these entities.

Program Card.java implements a data type for playing cards. Each object represents one of the 52 cards in a deck and supports the following operations: toString, less, and draw. The less method compares two cards based on their suit, then on their rank. It is useful to sort a hand of cards by suit, then by rank, as you would do in the card games bridge or hearts. We use Turtle graphics to display graphical representations of the playing cards. The archive file cards.jar contains a library of GIF images of playing cards. (As per the GPL license, here is the original source of the images). The images named 0.gif, 1.gif, through 51.gif are GIF images of the two of clubs, three of clubs, through the Ace of spades. The file back.gif represents the reverse side of the playing card. To use the library, put the file in your current directory, compile as usual, and execute with

java -classpath .:cards.jar Card.java

On Windows, replace the colon with a semicolon.

The data type Deck.java is a data type to represent a deck of 52 playing cards. The constructor initializes a new deck of 52 playing cards. The method shuffle rearrange the cards in random order using the algorithm from Section 2.5. The method dealFrom deletes one card from the deck and returns it. The method isEmpty is useful to check if the deck is empty. As an example, if we execute the following code

Deck deck = new Deck();
System.out.println(deck);
deck.shuffle();
System.out.println(deck);
System.out.println(deck.dealFrom());
System.out.println(deck);

then we might get the following output

Deck  2C 3C 4C 5C 6C 7C 8C 9C ... JS QS KS AS
Deck  4H 7H JH 9D 5D JD KC 3D ... 5H TC 7S 2S
4H
Deck  7H JH 9D 5D JD KC 3D ... 5H TC 7S 2S

The data type Player.java is a data type for representing a player in a card game of bridge or hearts. A player consists of a name, a location (for drawing), and a hand of cards. The method dealTo takes a Card as an argument and inserts that card into the player's hand. The internal method sort is used to sort the cards by suit and rank, before converting to a string representation for use with toString or plotting in Turtle graphics with show.

The data type Game.java represents the beginning of a card game application. It creates a deck of cards and four players (North, East, South, and West). It shuffles the 52 cards and deals them out to the four players. The cards for each player are printed to standard output

North  4C 6C 7C TC 5D 5H 8H 3S 4S 5S 8S TS KS
East   3C 8C QC 3D 4D 8D TD JD TH QH AH 2S QS
South  5C JC KC AC QD KD 2H 3H 4H 7H JH KH AS
West   2C 9C 2D 6D 7D 9D AD 6H 9H 6S 7S 9S JS

and then plotting using Turtle graphics. Note: picture below does not correspond to hands above, and it is sorted in "lefty" order.

Here's how you might do it Java 1.5 with enum

Q + A

Exercises

Re-implement Rectangle using two Point objects as instance variables instead of 4 doubles.
Create a data type Line.java that represents a line in the plane. Implement a line by including two Point data members or one Point and a slope.
Write a program that generates N circles at random in the unit box of diameter 0.05, draws them to the screen, and highlights all those pairs that overlap.
Create a data type Point.java to represent points in the plane. Each Point should have real valued x and y coordinates. Include a toString method and a method distanceTo(Point q) that returns the Euclidean distance between the invoking point and q.

What does the following code fragment print out?

public void mystery(Point p, Point q) {
   p.x = 17;
   p.y = 17;
   Point temp = p;
   p = q;
   q = p;
}

public static void main(String [] args) {
   Point a = new Point(0, 0);
   Point b = new Point(0, 0);

   System.out.println("a = " + a);
   System.out.println("b = " + b);
   System.out.println();

   mystery(a, b);

   System.out.println("a = " + a);
   System.out.println("b = " + b);
   System.out.println();
}

Answer: it makes a reference the point (17, 17), but does not swap a and b.

Create a data type Line.java that represents a line in the plane. Implement a line by including two Point data members or one Point and a slope.
Write a method distanceTo that computes the shortest distance from a point (x, y) to the line specified by (x₁, y₁) and (x₂, y₂). The formula is

Note that the denominator is the distance between the two points on the line so you should reuse the distanceTo method in Point. The numerator is signed, so this returns the signed distance - you may wish to take absolute values.
Write a method intersects so that s1.intersects(s2) returns true if the two line segments intersect and false otherwise. To determine if two line segments a-b and c-d intersect, compute

If 0 ≤ r ≤ 1 and 0 ≤ s &le 1, then the line segments intersect. Moreover, the point of intersection is (x, y) = (a_x + r(b_x-a_x), a_y + r(b_y-a_y)). If the denominator in equation 1 is zero, a-b and c-d are parallel. If the numerator in equation 1 is also zero, then a-b and c-d are collinear.
Create a static method ccw that takes three Point inputs a, b, and c and returns +1 if a-b-c is a counterclockwise angle, -1 if a-b-c is a clockwise angle, and 0 if a-b-c are collinear. Use the following determinant formula which gives twice the (signed) area of the triangle a-b-c. If the area is positive, then a-b-c is counterclockwise; if the area is negative, then a-b-c is counterclockwise; if the area is zero then a-b-c are collinear.
Create a data type Triangle that represents a triangle. It should have a constructor which take references to three Point objects as inputs and create a triangle with those endpoints. It should have methods area, perimeter, isIsosceles, isRight, isEquilateral, and isScalene.
Create a data type Circle.java that represents a circle in the plane. Each Circle should have a center Point and a real-valued diameter. Include a method double area() that returns the area of the circle.
Add a method boolean contains(Point p) to Circle that returns true if p is inside the invoking Circle, and false otherwise. Hint: use the method distanceTo in Point.java.
Add a method boolean intersects(Circle c) to Circle.java that returns true if c intersects the invoking Circle, and false otherwise.
Write a client program Pi.java that estimates the mathematical constant π using Monte Carlo simulation. Create a circle centered at (1/2, 1/2) of radius 1/2. Then repeatedly generate random points in the unit square and check if they are inside the circle. Print out the fraction of points that fall inside the circle. The true answer estimates π / 4 since the ratio of the area of the circle to the area of the square is π / 4.
Modify Card.java to add a more user-friendly constructor so the following code works
Card c = new Card(Card.KING, Card.HEARTS);
Add classwide variables to Card to achieve this effect.
Write a program to print the 52 cards in sorted order and then again in shuffled order, as in the picture below. Add a helper method draw to Deck.java.
Use Histogram.java to create an animated histogram for Benford's law from Section 2.5.

Creative Exercises

2-point correlation function. Given N points and a parameter r, the 2-point correlation function is the number of pairs of points that lie within distance r of each other. The 2-point correlation function roughly measures the clumpiness of a set of points. It is a fundamentally important statistic in astrophysics. Write a program that takes a command line parameter N, reads in N points, and calculates the number of points within a radius of r of each other for various values of r.
Rational roots. If a polynomial with integer coefficients has a rational root p/q (reduced) and a0 != 0, then p is a divisor of a0 and q is a divisor of a_n. Can enumerate all possibilities by factoring.
Bridge. One of the best ways to determine the strength of a bridge hand is to count up the number of high cards. The Milton Work Point Count assigns a numerical score to each hand by adding 4 points for each Ace, 3 for each King, 2 for each Queen, and 1 for each Jack. Deal out a million hands a compute a histogram of the number of points.
Here is the exact distribution of each of the high card point counts. Use the helper data type Histogram.java, which relies on Use the helper data type TurtlePanel.java and and TurtleFrame.java.
Bridge. It is advantageous in bridge to have suits with a large or small number of cards. Modify the program in the previous exercise to assign a bonus of 2 for each suit in which the hand has no cards of the given suit (void) and a bonus of 1 for each suit in which the hand has only a single card (singleton). Name your program BridgeExperiment.java. Use Histogram.java to create an animated histogram of the results.
Crazy 8s. In the card game Crazy 8s, each player typically sorts their cards according to rank (instead of suit as in Bridge). Modify the less method in Card so that the sort method in Player sorts in the appropriate order.
public boolean less(Card other) { return rank
I Doubt It. I Doubt It is a multiplayer card game in which it is convenient for each player to sort their cards in an interesting order...
Concentration. Implement the card game concentration.
Random sphere packing. Generate random disks of diameter d in the unit square and repeatedly add each new one as long as it doesn't intersect an existing disk. How many disks on average are placed? Use the Circle.java data type.