3.5. INHERITANCE

This section under major construction.

Inheritance.

Language support to define relationships among objects. Two main types of inheritance: interface inheritance and implementation inheritance.

Implementation inheritance.

Implementation inheritance is when one subclass (child) "inherits" instance variables and instance methods from a superclass (parent). It is a powerful technique that enables the programmer to change the behavior of a class and add functionality without rewriting the entire class from scratch. For example, we might have a superclass called Mammal, and subclasses Dog and Cat. In Java, all classes inherit from the universal superclass named Object. Note: subclass contains more methods than superclass. Implementation inheritance is widely used for building extensible libraries, including GUI. In Java, you can only inherit from one superclass. Single inheritance vs. multiple inheritance.

Give simple example.

Example: Swing hierarchy. Button -> AbstractButton -> JComponent -> Container -> Component -> Object.

Liskov Substitution Principle: if A inherits from B, then whenever you expect to use a B object, you can safely use an object of type A instead and you will get the desired behavior. When you use extends Java checks that the two classes have compatible method signatures, but does not check that the behavior is consistent. Circle-ellipse problem is source of alot of bad inheritance. Intuition with when to use inheritance is often wrong. The "IS A" rule is not sufficient.

Open-closed principle: software should be designed to be open for extension (can extend the module to behave in new ways), but closed for modification (no one shold ever change the source code). Ex: square, circle, triangle. Don't want a switch statement in base class for each type.

Problems with inheritance. Improper use of inheritance can create lots of programming nightmares since it often breaks encapsulation and makes future changes more troublesome. Coupling = reliance of one part of a program on another. Prime tenet of OOP is to reduce the level of coupling. With implementation inheritance, the subclass becomes tightly coupled with the superclass class. This is sometimes referred to as the fragile base class problem. The design is fragile because if you want to change the superclass, you must know the details of all of the subclasses or risk breaking them. This is not always possible, e.g., if you are Sun Microsystems and are re-implementing a Java library which has been subclassed by millions of programmers! Moreover, by overriding methods, the subclass can break the contracts promised by the superclass. This is especially difficult if you are For these reasons, many experienced programmers recommend avoiding implementation inheritance whenever possible. When using implementation inheritance, be sure that the subclasses depend only on the behavior of the superclass, not on the implementation. Reference.

Simple example: adding a method to the superclass with different return type than an existing method in a subclass (won't compile). Violates the "is a" rule: Sun's implementation of Stack which inherits from Vector and Sun's implementation of Properties which inherits from HashTable. Subtle example: use inheritance to create a subclass of Stack that counts the total number of elements inserted by maintaining an extra field, overriding add and addAll. Problem: superclass implements addAll by invoking add so we get twice the count when using addAll. We could then rely on addAll calling add, but now we are relying on the superclass not changing its implementation in the future. (Use composition and forwarding instead.) Reference

Interface inheritance.

Interfaces provide a mechanism for specifying a relationship between otherwise unrelated classes, typically by specifiying a set of common methods that each implementing class must contain. Interface inheritance is widely used to implement callbacks or dynamic dispatch. The Comparable interface for finding the maximum of a bunch of elements (or sorting them). Inherit only constants from an interface, not implementations of methods. Interface hierarchy is independent of class hierarchy. In Java, you can implement any number of interfaces. Danger: if you subsequently change the interface, this can break all of the classes that implement it.

To specify an interface in Java, you use the keyword interface instead of class, and specify only the list of interface methods (without the implementation code). The code fragment below indicates that there is a complex data type which supports four operations: abs, add, multiply, and toString.

public interface Complex {
    double abs();
    Complex add(Complex x);
    Complex multiply(Complex x);
    String toString();
}

Java interfaces suffer a number of important limitations. First, you cannot specify constructors or static methods to be a part of the interface. Second, the contract only describes which operations are permissible. Typically, the programmer documents the expected behavior of the ADT (in English), but there is no way to enforce this specification. These restrictions limit their usefulness since they cannot enforce certain desirable behavior. For example, the following is taken from Sun's Javadoc describing the map interface.

All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but all of the general-purpose map implementations in the SDK comply.

Real-valued functions.

Create an interface for a real-valued function and plot it. Perhaps sin(x) vs. Taylor expansion to sin(x).

Method polymorphism.

Polymorphism = many forms, e.g., water can be a liquid, solid (ice), or gas (steam). The principle of inheritance is what enables System.out.println to "know" how to print an object when you supply a method called toString. The toString method is implemented in Object, and hence common to all classes. This method returns a String representation of the object. The default behavior on many systems is to return the memory address where the object is stored. We often override this method to display a customized view of the object. This is especially useful for debugging. Overriding a method means to redefine a method in a subclass that was defined in a superclass. When you do this, the object in the subclass has two methods with the same name and signature. When you call System.out.print with an object as an argument, the system automatically invokes the object's toString method. Which toString method does the system use? It uses the one in the subclass, if it is defined, otherwise it uses the one from the superclass. This is an example of method polymorphism.

Resistor networks.

When electricity moves through a wire, it is subject to electrical friction or resistance. When a resistor with resistance R is connected across a potential difference V, Ohm's law asserts that it draws current I = V / R and dissipates power V^2 / R. A network of resistors connected across a potential difference behaves as a single resistor, which we call the equivalent resistance. The simplest way to conect more than resistor network is to use one of the following two composition rules. Each leads to a particularly simple formula for computing the equivalent resistance of the resulting network.

Series: Connect two resistor networks end-to-end in a single chain. If the equivalent resistance of the two networks are R₁ and R₂, then the equivalent resistance of the combined network is given by additive rule: R₁ + R₂. Ex: old christmas lights - if one burns out, then it would break circuit and all other lights would go out.
Parallel: Connect two resistor networks in parallel. If the equivalent resistance of the two networks are R₁ and R₂, then the equivalent resistance of the combined network is given by the reciprocal rule: 1 / (1/R₁ + 1/R₂). Parallel (e.g., electrical wiring in homes so that you can turn on lights independently).

Although the two rules for composition are simple, we can repeatedly apply them to design arbitrarily complex circuits. When series and parallel components are mixed in a circuit, we can simplify each series or parallel section into one resistor equivalent to its total resistance and apply this idea recursively.

The resistors R2 and R3 and connected in series, so we apply the series formula to them to get a total resistance of R2 + R3. This total resistance is shown in the black box, which is connected in parallel with resistor R1. Now apply the parallel formula to R1 and the box, obtaining the circuit's resistance, 1 / (1/R1 + 1/(R2+R3)).

However, not all resistor networks are series-parallel networks, e.g., a bridge with 5 resistors. In these cases, we need to use a more powerful technique known as Kirchoff's method (see section xyz).

To create series-parallel resistor networks in Java, we define a superclass Circuit.java that encapsulates the basic properties of a resistor network. For now, each network has a method resistance that returns the equivalent resistance of the circuit.

public abstract class Circuit {
    public abstract double resistance();
}

A series-parallel resistor network is either (i) a single resistor or (ii) built up by connecting two resistor networks in series or parallel. We create three subclasses Resistor.java, Series.java, and Parallel.java. Our goal is to be able to compose circuits as in the following code fragment, which represents the circuit depicted below. Series and Parallel Resistor network

Circuit a = new Resistor(3.0);
Circuit b = new Resistor(3.0);
Circuit c = new Resistor(6.0);
Circuit d = new Resistor(3.0);
Circuit e = new Resistor(2.0);
Circuit f = new Series(a, b);
Circuit g = new Parallel(c, d);
Circuit h = new Series(g, e);
Circuit circuit = new Parallel(h, f);
double R = circuit.resistance();

The class Resistor contains a constructor which sets the resistance in Ohms and an accessor method to return it.

public class Resistor extends Circuit {
    private double resistance;
    public Resistor(double r) {
        resistance = r;
    }
    public double resistance() {
        return resistance;
    }
}

The class Series contains a constructor which takes two resistor circuit objects as inputs and represents a circuit with the two components in series.

public class Series extends Circuit {
   private Circuit a;
   private Circuit b;

   public Series(Circuit a, Circuit b) {
      this.a = a;
      this.b = b;
   }

   public double resistance() {
      return a.resistance() + b.resistance();
   }
}

The class Parallel is almost identical to Series except that it uses the reciprocal rule instead of the additive rule to compute the equivalent resistance.
public double resistance() { double R1 = a.resistance(); double R2 = b.resistance(); return 1.0 / (1.0 / R1 + 1.0 / R2); }

Electricity moving through a wire is comprised of voltage (V), current (I), and resistance (R). The resistance measures the electrical friction. Ohm's law relates the three quantites by the famous formula V = I * R. When a battery is attached to a circuit, it creates a "potential difference" across the circuit. Smaller potential differences are created across each circuit segment. The potential difference across each section depends on whether the circuit is series or parallel. For a parallel circuit, the potential difference across each branch is equal to the potential difference across the whole parallel circuit. For a series circuit, first find the current (I) from Ohm's law I = V/R, where V is the potential difference across the series circuit and R is its total resistance. The potential difference across each resistor is equal to the current times the resistance of that resistor.

Event-based programming. The program Draw.java is our central object for creating graphics. The program InteractiveDraw.java is a subclass that supports various user interaction, including mouse clicks and keyborad controls. The interface DrawListener deals with keyboard and mouse callbacks, e.g., mouseClicked(double x, double y), mouseDragged(double x, double y), and keyPressed(char c). For use with InteractiveDraw.java.

Keyboard input. The program MovingJoker.java displays an image (the joker) and moves it when the user types one of the keys 'i', 'j', 'k', or 'l'.

Mouse input. Program Squares.java takes a command line parameter N and draws an N-by-N grid of cells. When the user clicks in a cell, draw a blue circle. Repeat, but alternate colors between red and blue. Mouse clicks and dragging.

Potential fields. Recursive nearest neighbor using quadtree.

Program Graffiti.java waits for the user to click and drag the mouse, and draws a trail as the user drags the mouse. It changes colors as the user drags.

Program Zoom.java waits for the user to click and drag the mouse, and draws a circle of the user-specified diameter. It uses XOR mode to erase and redraw the circle. Program MandelbrotZoom.java plots the Mandelbrot set, and then zooms in on the rectangle the user selects. Note that the interface is not very responsive since the user must wait for the whole to be drawn before they can re-zoom. We would need to use "threads" to make the GUI respond instantly.

Linear regression. Program LeastSquares.java plots points wherever the user clicks, and then draws the least squares fit line through the points after each point is added.

Computational geometry.

Shape super class. Rectangle, circle, point, triangle, polygon subclasses.

public abstract class Shape {
    private Color color;

    public void  setColor(Color c) { color = c;    }
    public Color getColor()        { return color; }
    public abstract void draw();
    public abstract double area();
    public abstract double perimeter();
}

Create random shapes and compute area using Monte Carlo integration.

public static void main(String[] args) {
    int M = Integer.parseInt(args[0]);   // # shapes
    int N = Integer.parseInt(args[1]);   // # samples
    Shape[] shapes = new Shape[M];
    for (int i = 0; i

Voronoi diagram.

Program Voronoi.java plots points wherever the user clicks, and then draws the Voronoi diagram. The Voronoi diagram (and its cousin, the Delaunay triangulation) have numerous applications ranging from anthropology to typography. References: voronoi.com and David Eppstein.

Delaunay triangulation.

Program Delaunay.java plots points wherever the user clicks, and then draws the Delaunay triangulation. The Delaunay triangulation has numerous scientific applications. Perhaps the most important is finite element methods for computational fluid dynamics. Here, a PDE is simulated over a continuous surface, which is decomposed into a mesh of triangular elements. The Delaunay triangulation has many appealing computational properties (triangles are as close to equilateral as possible), and it is efficiently computable.

Pong. Pong is a primitive video game. Pong.java is the beginning of a Java implementation of Pong using Turtle graphics. Ultimately, we should create data types to represent the ball nad paddles. We use the images paddle.png, ball.png, and background.png from TomPong. As per the GPL license, here is the original original source code. The original source of the paddle is LBreakout2 and the ball is KBounce. Here is a screen snapshot of the game as it will appear in progress.

GUI widgets. Program Celsius2Fahrenheit.java provides a text field for the user to enter a temperature in degrees Fahrenheit, and converts this to degrees Celsius. (To be replaced by an interesting example....) When the user types enter, this generates an ActionEvent and triggers a callback to the actionPerformed method.

Program ImageProcessor.java illustrates using a pulldown menu in an image processing application. The user can load an image from the file system in JPEG, PNG, or GIF format. Then the user can apply one of several image processing filters to the image. At any time the user can save the current image. We use the JFileChooser library for the open and save dialog boxes. This represents a significant amount of code that we don't want or need to re-implement every time we open a file. Moreover, by always using the built-in widget, we provide the user with a consistent interface. We re-use our Picture.java library for creating the image and accessing the pixels. Its method getJPanel enables us to embed the picture into the frame.

Program Slider.java draws a spirograph. The figure is characterized by three parameters, R, r, and a. The user can adjust these parameters using sliders, and the figure is drawn as the slider is moved.

BlackJack. Blackjack is a popular online card game. In a simple version (See the Exercises for more complicated variants), there are two players, the dealer and the gambler. Each player is dealt 2 cards from a standard 52 card deck of cards. The goal is to have a hand value of closer than 21 than the dealer, without going over. (Jacks, queens, and kings count as 10, aces count as 1 or 11, the cards 2 through 9 count as indicated. The suits are irrelevant.) The dealer's strategy is fixed: hit on 16 or below, stand or 17 or above. The gambler has two basic options: to draw another card (hit) or to stop (stick). The gambler is permitted to continue hitting until they exceed 21. The gambler gets to see one of the dealer's cards, and should base their hitting strategy, in part, on this information.

One of the main challenges in designing a computerized Blackjack program is the design. We embrace the OOP paradigm and decompose our program into components representing real world objects. A number of objects spring to mind: an individual playing card, a deck of cards, a player, and the game itself. Our program is organized accordingly.

Card.java is a data type that represents one of the 52 playing cards. Each Card stores the rank and suit of a single plaing card. There are many sensible ways to do this. We choose to maintain two instance variables, suit and rank. The variable suit stores an integer from 0 to 3, representing clubs, hearts, diamonds, and spades, respectively. The variable suit stores an integer from 0 to 12, representing 2, 3, 4, ..., Jack, Queen, King, and Ace. We a toString method to return a text description of the Card and a draw method to draw it in Turtle graphics. For Blackjack, it is also convenient to have a method isAce to tell us whether the card is an Ace, and a method rank to tell us the Blackjack value of a card. We also include an instance variable isConcealed that stores a boolean value to indicate whether or not the card is face down or face up. We use two helper methods conceal and reveal to set the isConcealed bit.
Deck.java is a data type that represents a deck of 52 playing cards. The Deck constructor creates a new deck of 52 cards, in sorted order. It has a method shuffle for shuffling the deck, a method size for returning the number of cards left in the deck, and a method get for deleting and returning the top card. As in Section 3.2 we use the library cards.jar to display images of the playing cards.
Player.java is a data type that represents one of the blackjack players, either the dealer or the gambler. It stores the hand of cards that a player holds. In Blackjack, a player will never have more than 9 cards, but to make the object more general, we enable each Player to hold up to 52 cards. We include a method add to insert a Card, a method reset to discard the hand, and a method value to return the blackjack value of the hand. We make Player extend TurtlePanel so that it has drawing capabilities. Perhaps, a better design would be to have separate Player and PlayerPanel objects.
BlackJack.java represents the game itself, including the GUI. Here is a screen snapshot of the game in progress.

Lessons

Exercises

Write a program to create a resistor network for the following circuits
Write a program to create a resistor network for the following circuits
Modify the the resistor network data type to support operations involving getting the potential and power of various components of a circuit according to Ohm's Law.
Modify Graffiti.java so the size of the circle is adjusted if the user types the key 0-9.
Modify Graffiti.java so that the color of the circle changes according to the spectrum.
Modify Graffiti.java so that each time the user clicks, it draws a circle centered at the current location with the integer i printed in the middle for the ith circle.
Modify Graffiti.java so it when you click on points, it connects the new one to the previously drawn one with a line segment.
Modify Graffiti.java so that it saves the graffiti in a file when the user types 's'.
Write a program ColorMandelbrotZoom.java that plots the Mandelbrot set using a 256 color palette such as mandel.txt, and lets the user zoom in as in MandelbrotZoom.java.
Extend Turtle in various ways. Add a version that supports error checking. For example, throw a TurtleOutOfBounds exception if turtle goes outside designated boundary.

Creative Exercises

Capacitor networks. Write a superclass CapacitorNetwork and subclasses Capacitor, Parallel, and Series to build up a capacitor network. Works exactly like resistor networks, except rules for series and parallel and reversed.
Slider puzzle. Write a program that chooses 8 of the 9 images slider1.gif through slider9.gif and arranges them in a 3-by-3 grid with one blank tile blank.gif. If the user clicks a tile and it is adjacent to the empty tile, "slide" that tile to the empty square and play a sounde effect.
15-slider puzzle. Write a program that prints 15 tiles labeled 1 through 15 in a 4-by-4 grid. If the user clicks a tile and it is adjacent to the empty tile, "slide" that tile to the empty square and play a sound effect.
Pong with multiples balls. Modify Pong.java so that there are three simultaneous balls.
Pong with spin. Modify Pong.java so that if the ball strikes the paddle while the paddle is moving, the ball spins according to the laws of physics.
Blackjack. Redo where the user types H for hit, S for stick, and D for deal. Use Turtle graphics.
Blackjack variants.
1. Use 4 decks instead of one.
2. Keep track of the number of times the player has won and lost, and print out the results after each game.
3. Add a button that allows the player to place 1, 2, or 4 dollar bets on each hand.
4. If the gambler gets 21 with two cards (blackjack), then she wins 1.5 times her bet. A natural blackback beats a 21 obtained with three or more cards.
5. Allow the gambler to double down: if the gambler has exactly two cards, then the gambler can double the size of the bet if she agree to receive exactly one additional card.
6. Allow the gambler to buy insurance if the dealer's face up card is an ace.
7. Allow the gambler to surrender: before making any other decisions, the gambler can fold her cards, and receive half her bet back.
8. Allow the gambler to split pairs: if the gambler's two initial cards are the same (ignoring the suits), she can split the hand into two individual hands, and play them independently.
Blackjack strategy. Create an automated strategy for the gambler and see how well it does by playing a million hands. (You'll probably want to lose the GUI for this type of experiment.) Use the basic strategy. By counting cards, you may be able to win money consistently. If your program does so, plan a trip to Las Vegas.
Poker. Write a program that evaluates 5 card poker hands and prints out the best hand according to the standard order: royal flush, straight flush, four of a kind, full house, flush, straight, three of a kind, two pair, one pair, high card. If there is a tie, a pair of 8's beats a pair of 7's, etc.
Five of a kind. Suppose you add a joker that acts as a wild card in five card poker. Determine mathematically whether a royal flush should beat five of a kind or vice versa. Repeat if you add two jokers.
Texas Hold 'Em. Texas Hold 'Em is a popular variant of poker. Before each hand, the dealer shuffles a standard 52 card deck. The dealer deals two cards face down (the hole cards) to each player. Then, the dealer deals five cards face up (the communal cards) in the middle of the table. Each player selects their best 5 card hand from the hole cards and the communal cards. Write a program to determine the best hand given two hole cards and five communal cards.
World Series of Poker. The World Series of Poker is played using Texas Hold 'Em. There is a round of betting after the first three communal cards (the flop) are dealt, and then again after the fourth communal card (the turn card), and again after the fifth communal card (the river card). ESPN televises the event and displays the probability that each hand will win after the flop, based on knowledge of every player's hole cards and the flop. Write a program to determine the exact probabilities by enumerating over all pairs of possible turn and river cards.
Moving circle. Write a program that draws a circle. It moves left, right, up, or down, if the user types the corresponding key. It changes color to red, green, or blue if the user types 'r', 'g', or 'b'.
Coordinates. Modify Graffiti.java so that it writes the (x, y) coordinate of each mouse click to the screen, centered at the location (x, y) of the mouse click.
Paint. Modify Graffiti.java so that it changes the color to red, green, or blue if the user types 'r', 'g', or 'b'. Also, have it change shapes from square to circle if the user types 's' or 'c'. Change the diameter of the circle or square if the user types '1' (small) through '9' (large).
Delaunay triangulation. Modify Voronoi.java to plot the Delaunay triangulation. For each pixel look at the input point to which it is closest, and do the same for its 8 neighboring pixels. If the inputs points are different, draw a line between the two points. This produces a triangulation which maximizes the minimum angle. This makes it especially useful for generating finite element meshes. Limitation: doesn't necessarily work for boundary edges....
Concentration. Implement the game of concentration. There is an N-by-N grid of cards, displayed face down. The user selects two of them to reveal. If they match, then the two cards are removed from the grid. Otherwise, the user is charged with 1 point and the cards are concealed. Repeat until the board is cleared.
Minesweeper. Implement the game of Minesweeper.
Tic-tac-toe. Implement the game of tic-tac-toe with two human players (or one human and one computer player).