Chapter Three. Object-Oriented Programming

Your next step in programming effectively is conceptually simple. Now that you know how to use primitive types of data, you will learn in this chapter how to use, create, and design higher-level data types.

An abstraction is a simplified description of something that captures its essential elements while suppressing all other details. In science, engineering, and programming, we are always striving to understand complex systems through abstraction. In Java programming, we do so with object-oriented programming, where we break a large and potentially complex program into a set of interacting elements, or objects. The idea originates from modeling (in software) real-world entities such as electrons, people, buildings, or solar systems and readily extends to modeling abstract entities such as bits, numbers, colors, images, or programs.

A data type is a set of values and a set of operations defined on those values. The values and operations for primitive types such as int and double are predefined by Java. In object-oriented programming, we write Java code to define new data types. An object is an entity that holds a data-type value; you can manipulate this data-type value by applying one of the object’s data-type operations.

This ability to define new data types and to manipulate objects holding data-type values is also known as data abstraction, and leads us to a style of modular programming that naturally extends the procedural programming style for primitive types that was the basis for CHAPTER 2. A data type allows us to isolate data as well as functions. Our mantra for this chapter is this: whenever you can clearly separate data and associated tasks within a computation, you should do so.

The eight primitive data types (boolean, byte, char, double, float, int, long, and short) that you have been using are supplemented in Java by extensive libraries of reference types that are tailored for a large variety of applications. The String data type is one such example that you have already used. You will learn more about the String data type in this section, as well as how to use several other reference types for image processing and input/output. Some of them are built into Java (String and Color), and some were developed for this book (In, Out, Draw, and Picture) and are useful as general resources.

You certainly noticed in the first two chapters of this book that our programs were largely confined to operations on numbers. Of course, the reason is that Java’s primitive types represent numbers. The one exception has been strings, a reference type that is built into Java. With reference types you can write programs that operate not just on strings, but on images, sounds, or any of hundreds of other abstractions that are available in Java’s libraries or on our booksite.

In this section, we focus on client programs that use existing data types, to give you some concrete reference points for understanding these new concepts and to illustrate their broad reach. We will consider programs that manipulate strings, colors, images, files, and web pages—quite a leap from the primitive types of CHAPTER 1.

In the next section, you will take another leap, by learning how to define your own data types to implement any abstraction whatsoever, taking you to a whole new level of programming. Writing programs that operate on your own types of data is an extremely powerful and useful style of programming that has dominated the landscape for many years.

You also have been using a data type that is not primitive—the String data type. You know that values of the String data type are sequences of characters and that you can perform the operation of concatenating two String values to produce a String result. You will learn in this section that there are dozens of other operations available for processing strings, such as finding a string’s length, extracting individual characters from the string, and comparing two strings.

Every data type is defined by its set of values and the operations defined on them, but when we use the data type, we focus on the operations, not the values. When you write programs that use int or double values, you are not concerning yourself with how they are represented (we never did spell out the details), and the same holds true when you write programs that use reference types, such as String, Color, or Picture. In other words, you do not need to know how a data type is implemented to be able to use it (yet another mantra)

We will write programs that declare, create, and manipulate values of type String. We begin by describing the String API, which documents the available operations. Then, we consider Java language mechanisms for declaring variables, creating objects to hold data-type values, and invoking instance methods to apply data-type operations. These mechanisms differ from the corresponding ones for primitive types, though you will notice many similarities.

The following table summarizes the instance methods from Java’s String API that we use most often; the full API has more than 60 methods! Several of the methods use integers to refer to a character’s index within a string; as with arrays, these indices start at 0.

The first entry, with the same name as the class and no return type, defines a special method known as a constructor. The other entries define instance methods that can take arguments and return values in the same manner as the static methods that we have been using, but they are not static methods: they implement operations for the data type. For example, the instance method length() returns the number of characters in the string and charAt() returns the character at a specified index.

String s;

declares a variable s of type String. This statement does not create anything; it just says that we will use the variable name s to refer to a String object. By convention, reference types begin with uppercase letters and primitive types begin with lowercase letters.

Click here to view code image

String s = new String("Hello, World");

You can create any number of objects from the same class; each object has its own identity and may or may not store the same value as another object of the same type. For example, the code

Click here to view code image

String s1 = new String("Cat");
String s2 = new String("Dog");
String s3 = new String("Cat");

creates three different String objects. In particular, s1 and s3 refer to different objects, even though the two objects represent the same sequence of characters.

Click here to view code image

String a = new String("now is");
String b = new String("the time");
String c = new String(" the");

The following code fragments illustrate the use of various string-processing methods. This code clearly exhibits the idea of developing an abstract model and separating the code that implements the abstraction from the code that uses it. This ability characterizes object-oriented programming and is a turning point in this book: we have not yet seen any code of this nature, but virtually all of the code that we write from this point forward will be based on defining and invoking methods that implement data-type operations.

String s = args[0];
int dot = s.indexOf(".");
String base      = s.substring(0, dot);
String extension = s.substring(dot + 1, s.length());

String query = args[0];
while (StdIn.hasNextLine())
{
   String line = StdIn.readLine();
   if (line.contains(query))
      StdOut.println(line);
}

public static boolean isPalindrome(String s)
{
   int n = s.length();
   for (int i = 0; i < n/2; i++)
      if (s.charAt(i) != s.charAt(n-1-i))
         return false;
   return true;
}

public static String translate(String dna)
{
   dna = dna.toUpperCase();
   String rna = dna.replaceAll("T", "U");
   return rna;
}

PotentialGene (PROGRAM 3.1.1) is a program that serves as a first step. The isPotentialGene() function takes a DNA string as an argument and determines whether it corresponds to a potential gene based on the following criteria: length is a multiple of 3, starts with the start codon, ends with a stop codon, and has no intervening stop codons. To make the determination, the program uses a variety of string instance methods: length(), charAt(), startsWith(), endsWith(), substring(), and equals().

Although the rules that define genes are a bit more complicated than those we have sketched here, PotentialGene exemplifies how a basic knowledge of programming can enable a scientist to study genomic sequences more effectively.

In the present context, our interest in the String data type is that it illustrates what a data type can be—a well-developed encapsulation of an important abstraction that is useful to clients. Before proceeding to other examples, we consider a few basic properties of reference types and objects in Java.

public class PotentialGene
{
   public static boolean isPotentialGene(String dna)
   {
      // Length is a multiple of 3.
      if (dna.length() % 3 != 0) return false;

      // Starts with start codon.
      if (!dna.startsWith("ATG")) return false;

      // No intervening stop codons.
      for (int i = 3; i < dna.length() - 3; i++)
      {
         if (i % 3 == 0)
         {
            String codon = dna.substring(i, i+3);
            if (codon.equals("TAA")) return false;
            if (codon.equals("TAG")) return false;
            if (codon.equals("TGA")) return false;
         }
      }

      // Ends with a stop codon.
      if (dna.endsWith("TAA")) return true;
      if (dna.endsWith("TAG")) return true;
      if (dna.endsWith("TGA")) return true;

      return false;
   }
}

 dna  | string to analyze
codon | 3 consecutive bases

% java PotentialGene ATGCGCCTGCGTCTGTACTAG
true
% java PotentialGene ATGCGCTGCGTCTGTACTAG
false

Why not just process the object itself? For small objects, it might make sense to do so, but for large objects, cost becomes an issue: data-type values can consume large amounts of memory. It does not make sense to copy or move all of its data every time that we pass an object as an argument to a method. If this reasoning seems familiar to you, it is because we have used precisely the same reasoning before, when talking about passing arrays as arguments to static methods in SECTION 2.1. Indeed, arrays are objects, as we will see later in this section. By contrast, primitive types have values that are natural to represent directly in memory, so that it does not make sense to use a reference to access each value.

We will discuss properties of object references in more detail after you have seen several examples of client code that use reference types.

• As an argument or return value for a method

• In an assignment statement

• In an array

We have been using String objects in this way ever since HelloWorld: most of our programs call StdOut.println() with a String argument, and all of our programs have a main() method that takes an argument that is a String array. As we have already seen, there is one critically important addition to this list for variables that refer to objects:

• To invoke an instance method defined on it

This usage is not available for variables of a primitive type, where operations are built into the language and invoked only via operators such as +, -, *, and /.

Click here to view code image

String bad;
boolean value = bad.startsWith("Hello");

leads to the compile-time error variable bad might not have been initialized because it is trying to use an uninitialized variable.

The basic concepts that we have just covered are the starting point for object-oriented programming, so it is worthwhile to briefly summarize them here. A data type is a set of values and a set of operations defined on those values. We implement data types in independent modules and write client programs that use them. An object is an instance of a data type. Objects are characterized by three essential properties: state, behavior, and identity. The state of an object is a value from its data type. The behavior of an object is defined by the data type’s operations. The identity of an object is the location in memory where it is stored. In object-oriented programming, we invoke constructors to create objects and then modify their state by invoking their instance methods. In Java, we manipulate objects via object references.

To demonstrate the power of object orientation, we next consider several more examples. First, we consider the familiar world of image processing, where we process Color and Picture objects. Then, we revisit our input/output libraries in the context of object-oriented programming, enabling us to access information from files and the web.

Java has hundreds of data types in its libraries, so we need to explicitly list which Java libraries we are using in our program to avoid naming conflicts. Specifically, we include the statement

import java.awt.Color;

at the beginning of any program that uses Color. (Until now, we have been using standard Java libraries or our own, so there has been no need to import them.)

To represent color values, Color uses the RGB color model where a color is defined by three integers (each between 0 and 255) that represent the intensity of the red, green, and blue (respectively) components of the color. Other color values are obtained by mixing the red, green, and blue components. That is, the data-type values of Color are three 8-bit integers. We do not need to know whether the implementation uses int, short, or char values to represent these integers. With this convention, Java is using 24 bits to represent each color and can represent 256³ = 2²⁴ ≈ 16.7 million possible colors. Scientists estimate that the human eye can distinguish only about 10 million distinct colors.

The Color data type has a constructor that takes three integer arguments. For example, you can write

Click here to view code image

Color red      = new Color(255,   0,   0);
Color bookBlue = new Color(  9,  90, 166);

to create objects whose values represent pure red and the blue used to print this book, respectively. We have been using colors in StdDraw since SECTION 1.5, but have been limited to a set of predefined colors, such as StdDraw.BLACK, StdDraw. RED, and StdDraw.PINK. Now you have millions of colors available for your use. AlbersSquares (PROGRAM 3.1.2) is a StdDraw client that allows you to experiment with them.

---

Program 3.1.2 Albers squares

Click here to view code image

import java.awt.Color;

public class AlbersSquares
{
    public static void main(String[] args)
    {
       int r1 = Integer.parseInt(args[0]);
       int g1 = Integer.parseInt(args[1]);
       int b1 = Integer.parseInt(args[2]);
       Color c1 = new Color(r1, g1, b1);

       int r2 = Integer.parseInt(args[3]);
       int g2 = Integer.parseInt(args[4]);
       int b2 = Integer.parseInt(args[5]);
       Color c2 = new Color(r2, g2, b2);

       StdDraw.setPenColor(c1);
       StdDraw.filledSquare(.25, 0.5, 0.2);
       StdDraw.setPenColor(c2);
       StdDraw.filledSquare(.25, 0.5, 0.1);
       StdDraw.setPenColor(c2);
       StdDraw.filledSquare(.75, 0.5, 0.2);
       StdDraw.setPenColor(c1);
       StdDraw.filledSquare(.75, 0.5, 0.1);
    }
}

---

r1, g1, b1 | RGB values
    c1     | first color
r2, g2, b2 | RGB values
    c2     | second color

This program displays the two colors entered in RGB representation on the command line in the familiar format developed in the 1960s by the color theorist Josef Albers, which revolutionized the way that people think about color.

---

---

As usual, when we address a new abstraction, we are introducing you to Color by describing the essential elements of Java’s color model, not all of the details. The API for Color contains several constructors and more than 20 methods; the ones that we will use are briefly summarized next.

Our primary purpose is to use Color as an example to illustrate object-oriented programming, while at the same time developing a few useful tools that we can use to write programs that process colors. Accordingly, we choose one color property as an example to convince you that writing object-oriented code to process abstract concepts like color is a convenient and useful approach.

Y = 0.299 r + 0.587g + 0.114b

Since the coefficients are positive and sum to 1, and the intensities are all integers between 0 and 255, the luminance is a real number between 0 and 255.

Having an abstraction for color is important not just for direct use, but also in building higher-level data types that have Color values. Next, we illustrate this point by building on the color abstraction to develop a data type that allows us to write programs to process digital images.

import java.awt.Color;

public class Luminance
{
   public static double intensity(Color color)
   {  // Monochrome luminance of color.
      int r = color.getRed();
      int g = color.getGreen();
      int b = color.getBlue();
      return 0.299*r + 0.587*g + 0.114*b;
   }

   public static Color toGray(Color color)
   {  // Use luminance to convert to grayscale.
      int y = (int) Math.round(intensity(color));
      Color gray = new Color(y, y, y);
      return gray;
   }

   public static boolean areCompatible(Color a, Color b)
   {  // True if colors are compatible, false otherwise.
      return Math.abs(intensity(a) - intensity(b)) >= 128.0;

   }

   public static void main(String[] args)
   {  // Are the two specified RGB colors compatible?
      int[] a = new int[6];
      for (int i = 0; i < 6; i++)
         a[i] = Integer.parseInt(args[i]);
      Color c1 = new Color(a[0], a[1], a[2]);
      Color c2 = new Color(a[3], a[4], a[5]);
      StdOut.println(areCompatible(c1, c2));
   }
}

r, g, b | RGB values

y | luminance of color

a[] | int values of args[]
 c1 | first color
 c2 | second color

% java Luminance 232 232 232    0   0   0
true
% java Luminance   9  90 166  232 232 232
true
% java Luminance   9  90 166    0   0   0
false

Our class Picture is a data type for digital images whose definition follows immediately from the digital image abstraction. The set of values is nothing more than a two-dimensional matrix of Color values, and the operations are what you might expect: create a blank image with a given width and height, load an image from a file, set the value of a pixel to a given color, return the color of a given pixel, return the width or the height, show the image in a window on your computer screen, and save the image to a file. In this description, we intentionally use the word matrix instead of array to emphasize that we are referring to an abstraction (a matrix of pixels), not a specific implementation (a Java two-dimensional array of Color objects). You do not need to know how a data type is implemented to be able to use it. Indeed, typical images have so many pixels that implementations are likely to use a more efficient representation than an array of Color objects. In any case, to write client programs that manipulate images, you just need to know this API:

By convention, (0, 0) is the upper-leftmost pixel, so the image is laid as in the customary order for two-dimensional arrays (by contrast, the convention for StdDraw is to have the point (0,0) at the lower-left corner, so that drawings are oriented as in the customary manner for Cartesian coordinates). Most image-processing programs are filters that scan through all of the pixels in a source image and then perform some computation to determine the color of each pixel in a target image. The supported file formats for the first constructor and the save() method are the widely used PNG and JPEG formats, so that you can write programs to process your own digital photos and add the results to an album or a website. The show() window also has an interactive option for saving to a file. These methods, together with Java’s Color data type, open the door to image processing.

---

Program 3.1.4 Converting color to grayscale

Click here to view code image

import java.awt.Color;

public class Grayscale
{
   public static void main(String[] args)
   {  // Show image in grayscale.
      Picture picture = new Picture(args[0]);
      for (int col = 0; col < picture.width(); col++)
      {
         for (int row = 0; row < picture.height(); row++)
         {
            Color color = picture.get(col, row);
            Color gray  = Luminance.toGray(color);
            picture.set(col, row, gray);
         }
      }
      picture.show();
   }
}

---

 picture | image from file
col, row | pixel coordinates
  color  | pixel color
  gray   | pixel grayscale

This program illustrates a simple image-processing client. First, it creates a Picture object initialized with an image file named by the command-line argument. Then it converts each pixel in the picture to grayscale by creating a grayscale version of each pixel’s color and resetting the pixel to that color. Finally, it shows the picture. You can perceive individual pixels in the picture on the right, which was upscaled from a low-resolution picture (see “Scaling” on the next page).

---

---

---

In some cases, the strategy is clear. For example, if the target image is to be half the size (in each dimension) of the source image, we simply choose half the pixels, say, by deleting half the rows and half the columns. This technique is known as sampling. If the target image is to be double the size (in each dimension) of the source image, we can replace each source pixel by four target pixels of the same color. Note that we can lose information when we downscale, so halving an image and then doubling it generally does not give back the same image.

A single strategy is effective for both downscaling and upscaling. Our goal is to produce the target image, so we proceed through the pixels in the target, one by one, scaling each pixel’s coordinates to identify a pixel in the source whose color can be assigned to the target. If the width and height of the source are w_s and h_s (respectively) and the width and height of the target are w_t and h_t (respectively), then we scale the column index by w_s/w_t and the row index by h_s/h_t. That is, we get the color of the pixel in column c and row r and of the target from column c×w_s /w_t and row r×h_s /h_t in the source. For example, if we are halving the size of an image, the scale factors are 2, so the pixel in column 3 and row 2 of the target gets the color of the pixel in column 6 and row 4 of the source; if we are doubling the size of the image, the scale factors are 1/2, so the pixel in column 4 and row 6 of the target gets the color of the pixel in column 2 and row 3 of the source. Scale (PROGRAM 3.1.5) is an implementation of this strategy. More sophisticated strategies can be effective for low-resolution images of the sort that you might find on old web pages or from old cameras. For example, we might downscale to half size by averaging the values of four pixels in the source to make one pixel in the target. For the high-resolution images that are common in most applications today, the simple approach used in Scale is effective.

---

Program 3.1.5 Image scaling

Click here to view code image

public class Scale
{
   public static void main(String[] args)
   {
      int w = Integer.parseInt(args[1]);
      int h = Integer.parseInt(args[2]);
      Picture source = new Picture(args[0]);
      Picture target = new Picture(w, h);
      for (int colT = 0; colT < w; colT++)
      {
         for (int rowT = 0; rowT < h; rowT++)
         {
            int colS = colT * source.width()  / w;
            int rowS = rowT * source.height() / h;
            target.set(colT, rowT, source.get(colS, rowS));
         }
      }
      source.show();
      target.show();
   }
}

---

   w, h    | target dimensions
  source   | source image
  target   | target image
colT, rowT | target pixel coords
colS, rowS | source pixel coords

This program takes the name of an image file and two integers (width w and height h) as command-line arguments, scales the picture to w-by-h, and displays both images.

---

---

The same basic idea of computing the color value of each target pixel as a function of the color values of specific source pixels is effective for all sorts of image-processing tasks. Next, we consider one more example, and you will find numerous other examples in the exercises and on the booksite.

import java.awt.Color;

public class Fade
{
   public static Color blend(Color c1, Color c2, double alpha)
   {  // Compute blend of colors c1 and c2, weighted by alpha.
      double r = (1-alpha)*c1.getRed()   + alpha*c2.getRed();
      double g = (1-alpha)*c1.getGreen() + alpha*c2.getGreen();
      double b = (1-alpha)*c1.getBlue()  + alpha*c2.getBlue();
      return new Color((int) r, (int) g, (int) b);
   }
   public static void main(String[] args)
   {  // Show m-image fade sequence from source to target.
      Picture source = new Picture(args[0]);
      Picture target = new Picture(args[1]);
      int n = Integer.parseInt(args[2]);
      int width  = source.width();
      int height = source.height();
      Picture picture = new Picture(width, height);
      for (int i = 0; i <= n; i++)
      {
         for (int col = 0; col < width; col++)
         {
            for (int row = 0; row < height; row++)
            {
               Color c1 = source.get(col, row);
               Color c2 = target.get(col, row);
               double alpha = (double) i / n;
               Color color = blend(c1, c2, alpha);
               picture.set(col, row, color);
            }
         }
         picture.show();
      }
   }
}

   n    | number of pictures
picture | current picture
   i    | picture counter
  c1    | source color
  c2    | target color
 color  | blended color

Specifically, we define in this section the data types In, Out, and Draw for input streams, output streams, and drawings, respectively. As usual, you must make these classes accessible to Java (see the Q&A at the end of SECTION 1.5).

These data types give us the flexibility that we need to address many common data-processing tasks within our Java programs. Rather than being restricted to just one input stream, one output stream, and one drawing, we can easily define multiple objects of each type, connecting the streams to various sources and destinations. We also get the flexibility to assign such objects to variables, pass them as arguments or return values from methods, and create arrays of them, manipulating them just as we manipulate objects of any type. We will consider several examples of their use after we have presented the APIs.

This arrangement makes it possible to process multiple files within the same program. Moreover, the ability to directly access the web opens up the whole web as potential input for your programs. For example, it allows you to process data that is provided and maintained by someone else. You can find such files all over the web. Scientists now regularly post data files with measurements or results of experiments, ranging from genome and protein sequences to satellite photographs to astronomical observations; financial services companies, such as stock exchanges, regularly publish on the web detailed information about the performance of stock and other financial instruments; governments publish election results; and so forth. Now you can write Java programs that read these kinds of files directly. The In data type gives you a great deal of flexibility to take advantage of the multitude of data sources that are now available.

public class Cat
{
   public static void main(String[] args)
   {
      Out out = new Out(args[args.length-1]);
      for (int i = 0; i < args.length - 1; i++)
      {
         In in = new In(args[i]);
         String s = in.readAll();
         out.println(s);
      }
   }
}

out | output stream
 i  | argument index
 in | current input stream
 s  | contents of in

% more in1.txt
This is
% more in2.txt
a tiny
test.

% java Cat in1.txt in2.txt out.txt
% more out.txt
This is
a tiny
test.

Click here to view code image

...
(GOOG)</h2> <span class="rtq_
exch"><span class="rtq_dash">-</span>
NMS  </span><span class="wl_sign">
</span></div></div>
<div class="yfi_rt_quote_summary_rt_top
sigfig_promo_1"><div>
<span class="time_rtq_ticker">
<span id="yfs_l84goog">1,100.62</span>
</span> <span class="down_r time_rtq_
content"><span id="yfs_c63_goog">
...

HTML code from the web

Suppose that we want to take a stock trading symbol as a command-line argument and print that stock’s current trading price. Such information is published on the web by financial service companies and Internet service providers. For example, you can find the stock price of a company whose symbol is goog by browsing to http://finance.yahoo.com/q?s=goog. Like many web pages, the name encodes an argument (goog), and we could substitute any other ticker symbol to get a web page with financial information for any other company. Also, like many other files on the web, the referenced file is a text file, written in a formatting language known as HTML. From the point of view of a Java program, it is just a String value accessible through an In object. You can use your browser to download the source of that file, or you could use

Click here to view code image

% java Cat "http://finance.yahoo.com/q?s=goog" goog.html

to put the source into a file goog.html on your local computer (though there is no real need to do so). Now, suppose that goog is trading at $1,100.62 at the moment. If you search for the string "1,100.62" in the source of that page, you will find the stock price buried within some HTML code. Without having to know details of HTML, you can figure out something about the context in which the price appears. In this case, you can see that the stock price is enclosed between the substrings <span id="yfs_l84goog"> and </span>.

With the String data type’s indexOf() and substring() methods, you easily can grab this information, as illustrated in StockQuote (PROGRAM 3.1.8). This program depends on the web page format used by http://finance.yahoo.com; if this format changes, StockQuote will not work. Indeed, by the time you read this page, the format may have changed. Even so, making appropriate changes is not likely to be difficult. You can entertain yourself by embellishing StockQuote in all kinds of interesting ways. For example, you could grab the stock price on a periodic basis and plot it, compute a moving average, or save the results to a file for later analysis. Of course, the same technique works for sources of data found all over the web, as you can see in examples in the exercises at the end of this section and on the booksite.

These examples are convincing illustrations of the utility of working with text files, with multiple input and output streams, and with direct access to web pages. Web pages are written in HTML precisely so that they are accessible to any program that can read strings. People use text formats such as .csv files rather than data formats that are beholden to particular applications precisely to allow as many people as possible to access the data with simple programs like Split.

public class StockQuote
{
   private static String readHTML(String symbol)
   {  // Return HTML corresponding to stock symbol.
      In page = new In("http://finance.yahoo.com/q?s=" + symbol);
      return page.readAll();
   }

   public static double priceOf(String symbol)
   {  // Return current stock price for symbol.
      String html = readHTML(symbol);
      int p     = html.indexOf("yfs_l84", 0);
      int from  = html.indexOf(">", p);
      int to    = html.indexOf("</span>", from);
      String price = html.substring(from + 1, to);
      return Double.parseDouble(price.replace(",", ""));
   }

   public static void main(String[] args)
   {  // Print price of stock specified by symbol.
      String symbol = args[0];
      double price = priceOf(symbol);
      StdOut.println(price);
   }
}

symbol | stock symbol
 page  | input stream

 html | contents of page
   p  | yfs_184 index
 from | > index
  to  | </span> index
price | current price

% java StockQuote goog
1100.62
% java StockQuote adbe
70.51

public class Split
{
   public static void main(String[] args)
   {  // Split file by column into n files.
      String name = args[0];
      int n = Integer.parseInt(args[1]);
      String delimiter = ",";

      // Create output streams.
      Out[] out = new Out[n];
      for (int i = 0; i < n; i++)
         out[i] = new Out(name + i + ".txt");

      In in = new In(name + ".csv");
      while (in.hasNextLine())
      {  // Read a line and write fields to output streams.
         String line = in.readLine();
         String[] fields = line.split(delimiter);
         for (int i = 0; i < n; i++)
            out[i].println(fields[i]);
      }
   }
}

   name   | base file name
    n     | number of fields
delimiter | delimiter (comma)
    in    | input stream
   out[]  | output streams
   line   | current line
 fields[] | values in current line

% more DJIA.csv
...
31-Oct-29,264.97,7150000,273.51
30-Oct-29,230.98,10730000,258.47
29-Oct-29,252.38,16410000,230.07
28-Oct-29,295.18,9210000,260.64
25-Oct-29,299.47,5920000,301.22
24-Oct-29,305.85,12900000,299.47
23-Oct-29,326.51,6370000,305.85
22-Oct-29,322.03,4130000,326.51
21-Oct-29,323.87,6090000,320.91
...

% java Split DJIA 4
% more DJIA2.txt
...
7150000
10730000
16410000
9210000
5920000
12900000
6370000
4130000
6090000
...

As for any data type, you can create a new drawing by using new to create a Draw object, assign it to a variable, and use that variable name to call the methods that create the graphics. For example, the code

Draw draw = new Draw();
draw.circle(0.5, 0.5, 0.2);

draws a circle in the center of a window on your screen. As with Picture, each drawing has its own window, so that you can address applications that call for displaying multiple different drawings at the same time.

A reference captures the distinction between a thing and its name. This distinction is a familiar one, as illustrated in these examples:

A given object may have multiple names, but each object has its own identity. We can create a new name for an object without changing the object’s value (via an assignment statement), but when we change an object’s value (by invoking an instance method), all of the object’s names refer to the changed object.

The following analogy may help you keep this crucial distinction clear in your mind. Suppose that you want to have your house painted, so you write the street address of your house in pencil on a piece of paper and give it to a few house painters. Now, if you hire one of the painters to paint the house, it becomes a different color. No changes have been made to any of the pieces of paper, but the house that they all refer to has changed. One of the painters might erase what you’ve written and write the address of another house, but changing what is written on one piece of paper does not change what is written on another piece of paper. Java references are like the pieces of paper: they hold names of objects. Changing a reference does not change the object, but changing an object makes the change apparent to everyone having a reference to it.

The famous Belgian artist René Magritte captured this same concept in a painting where he created an image of a pipe along with the caption ceci n’est pas une pipe (this is not a pipe) below it. We might interpret the caption as saying that the image is not actually a pipe, just an image of a pipe. Or perhaps Magritte meant that the caption is neither a pipe nor an image of a pipe, just a caption! In the present context, this image reinforces the idea that a reference to an object is nothing more than a reference; it is not the object itself.

Aliasing is a common source of bugs in Java programs, as illustrated by the following example:

Click here to view code image

Picture a = new Picture("mandrill.jpg");
Picture b = a;
a.set(col, row, color1);  // a updated
b.set(col, row, color2);  // a updated again

After the second assignment statement, variables a and b both refer to the same Picture object. Changing the state of an object impacts all code involving aliased variables referencing that object. We are used to thinking of two different variables of primitive types as being independent, but that intuition does not carry over to reference objects. For example, if the preceding code assumes that a and b refer to different Picture objects, then it will produce the wrong result. Such aliasing bugs are common in programs written by people without much experience in using reference objects (that’s you, so pay attention here!).

Click here to view code image

   Color a = new Color(160, 82, 45);
   Color b = new Color(160, 82, 45);
   Color c = b;

Now (a == b) is false and (b == c) is true, but when you are thinking about equality testing for Color, you probably are thinking that you want to test whether their values are the same—you might want all three of these to test as equal. Java does not have an automatic mechanism for testing the equality of object values, which leaves programmers with the opportunity (and responsibility) to define it for themselves by defining for any class a customized method named equals(), as described in SECTION 3.3. For example, Color has such a method, and a.equals(c) is true in our example. String also contains an implementation of equals() because we often want to test whether two String objects have the same value (the same sequence of characters).

One important consequence of this arrangement is that a method cannot directly change the value of a caller’s variable. For primitive types, this policy is what we expect (the two variables are independent), but each time that we use a reference type as a method argument, we create an alias, so we must be cautious. For example, if we pass an object reference of type Picture to a method, the method cannot change the caller’s object reference (for example, make it refer to a different Picture), but it can change the value of the object, such as by invoking the set() method to change a pixel’s color.

• Create the array by using new and the square bracket syntax for array creation

• Create each object in the array, by using new to call a constructor

For example, we would use the following code to create an array of two Color objects:

Click here to view code image

Color[] a = new Color[2];
a[0] = new Color(255, 255, 0);
a[1] = new Color(160, 82, 45);

Naturally, an array of objects in Java is an array of object references, not the objects themselves. If the objects are large, then we gain efficiency by not having to move them around, just their references. If they are small, we lose efficiency by having to follow a reference each time we need to get to some information.

For reference, we summarize the examples that we have considered in this section in the table below. These examples are chosen to help you understand the essential properties of data types and object-oriented programming.

A data type is a set of values and a set of operations defined on those values. With primitive data types, we worked with a small and simple set of values. Strings, colors, pictures, and I/O streams are high-level data types that indicate the breadth of applicability of data abstraction. You do not need to know how a data type is implemented to be able to use it. Each data type (there are hundreds in the Java libraries, and you will soon learn to create your own) is characterized by an API (application programming interface) that provides the information that you need to use it. A client program creates objects that hold data-type values and invokes instance methods to manipulate those values. We write client programs with the basic statements and control constructs that you learned in CHAPTERS 1 and 2, but now have the capability to work with a vast variety of data types, not just the primitive ones to which you have grown accustomed. With greater experience, you will find that this ability opens up new horizons in programming.

When properly designed, data types lead to client programs that are clearer, easier to develop, and easier to maintain than equivalent programs that do not take advantage of data abstraction. The client programs in this section are testimony to this claim. Moreover, as you will see in the next section, implementing a data type is a straightforward application of the basic programming skills that you have already learned. In particular, addressing a large and complex application becomes a process of understanding its data and the operations to be performed on it, then writing programs that directly reflect this understanding. Once you have learned to do so, you might wonder how programmers ever developed large programs without using data abstraction.

A. Performance. Java provides the wrapper reference types Integer, Double, and so forth that correspond to primitive types and can be used by programmers who prefer to ignore the distinction (for details, see SECTION 3.3). Primitive types are closer to the types of data that are supported by computer hardware, so programs that use them usually run faster and consume less memory than programs that use the corresponding reference types.

Q. What happens if I forget to use new when creating an object?

A. To Java, it looks as though you want to call a static method with a return value of the object type. Since you have not defined such a method, the error message is the same as when you refer to an undefined symbol. If you compile the code

Click here to view code image

Color sienna = Color(160, 82, 45);

you get this error message:

Click here to view code image

cannot find symbol
symbol  : method Color(int,int,int)

Constructors do not provide return values (their signature has no return type)—they can only follow new. You get the same kind of error message if you provide the wrong number of arguments to a constructor or method.

Q. Why can we print an object x with the function call StdOut.println(x), as opposed to StdOut.println(x.toString())?

A. Good question. That latter code works fine, but Java saves us some typing by automatically invoking the toString() method in such situations. In SECTION 3.3, we will discuss Java’s mechanism for ensuring that this is the case.

Q. What is the difference between =, ==, and equals()?

A. The single equals sign (=) is the basis of the assignment statement—you certainly are familiar with that. The double equals sign (==) is a binary operator for checking whether its two operands are identical. If the operands are of a primitive type, the result is true if they have the same value, and false otherwise. If the operands are object references, the result is true if they refer to the same object, and false otherwise. That is, we use == to test object identity equality. The data-type method equals() is included in every Java type so that the implementation can provide the capability for clients to test whether two objects have the same value. Note that (a == b) implies a.equals(b), but not the other way around.

Q. How can I arrange to pass an array as an argument to a function in such a way that the function cannot change the values of the elements in the array?

A. There is no direct way to do so—arrays are mutable. In SECTION 3.3, you will see how to achieve the same effect by building a wrapper data type and passing an object reference of that type instead (see Vector, in PROGRAM 3.3.3).

Q. What happens if I forget to use new when creating an array of objects?

A. You need to use new for each object that you create, so when you create an array of n objects, you need to use new n + 1 times: once for the array and once for each of the n objects. If you forget to create the array:

Click here to view code image

Color[] colors;
colors[0] = new Color(255, 0, 0);

you get the same error message that you would get when trying to assign a value to any uninitialized variable:

Click here to view code image

variable colors might not have been initialized
      colors[0] = new Color(255, 0, 0);
      ^

In contrast, if you forget to use new when creating an object within the array and then try to use it to invoke a method:

Click here to view code image

Color[] colors = new Color[2];
int red = colors[0].getRed();

you get a NullPointerException. As usual, the best way to answer such questions is to write and compile such code yourself, then try to interpret Java’s error message. Doing so might help you more quickly recognize mistakes later.

Q. Where can I find more details on how Java implements references and garbage collection?

A. One Java system might differ completely from another. For example, one natural scheme is to use a pointer (machine address); another is to use a handle (a pointer to a pointer). The former gives faster access to data; the latter facilitates garbage collection.

Q. Why red, green, and blue instead of red, yellow, and blue?

A. In theory, any three colors that contain some amount of each primary would work, but two different color models have evolved: one (RGB) that has proven to produce good colors on television screens, computer monitors, and digital cameras, and the other (CMYK) that is typically used for the printed page (see EXERCISE 1.2.32). CMYK does include yellow (cyan, magenta, yellow, and black). Two different color models are appropriate because printed inks absorb color; thus, where there are two different inks, there are more colors absorbed and fewer reflected. Conversely, video displays emit color, so where there are two different-colored pixels, there are more colors emitted.

Q. What exactly is the purpose of an import statement?

A. Not much: it just saves some typing. For example, in PROGRAM 3.1.2, it enables you to abbreviate java.awt.Color with Color everywhere in your code.

Q. Is there anything wrong with allocating and deallocating thousands of Color objects, as in Grayscale (PROGRAM 3.1.4)?

A. All programming-language constructs come at some cost. In this case the cost is reasonable, since the time to allocate Color objects is tiny compared to the time to draw the image.

Q. Why does the String method call s.substring(i, j) return the substring of s starting at index i and ending at j-1 (and not j)?

A. Why do the indices of an array a[] go from 0 to a.length-1 instead of from 1 to length? Programming-language designers make choices; we live with them. One nice consequence of this convention is that the length of the extracted substring is j-i.

Q. What is the difference between pass by value and pass by reference?

Q. With pass by value, when you call a method with arguments, each argument is evaluated and a copy of the resulting value is passed to the method. This means that if a method directly modifies an argument variable, that modification is not visible to the caller. With pass by reference, the memory address of each argument is passed to the method. This means that if a method modifies an argument variable, that modification is visible to the caller. Technically, Java is a purely pass-by-value language, in which the value is either a primitive-type value or an object reference. As a result, when you pass a primitive-type value to a method, the method cannot modify the corresponding value in the caller; when you pass an object reference to a method, the method cannot modify the object reference (say, to refer to a different object), but it can change the underlying object (by using the object reference to invoke one of the object’s methods). For this reason, some Java programmers use the term pass by object reference to refer to Java’s argument-passing conventions for reference types.

Q. I noticed that the argument to the equals() method in String and Color is of type Object. Shouldn’t the argument be of type String and Color, respectively?

A. No. In Java, the equals() method is a special and its argument type should always be Object. This is an artifact of the inheritance mechanism that Java uses to support the equals() method, which we consider on page 454. For now, you can safely ignore the distinction.

Q. Why is the image-processing data type named Picture instead of Image?

A. There is already a built-in Java library named Image.

3.1.2 Write a program that takes from the command line three integers between 0 and 255 that represent red, green, and blue values of a color and then creates and shows a 256-by-256 Picture in which each pixel has that color.

3.1.3 Modify AlbersSquares (PROGRAM 3.1.2) to take nine command-line arguments that specify three colors and then draws the six squares showing all the Albers squares with the large square in each color and the small square in each different color.

3.1.4 Write a program that takes the name of a grayscale image file as a command-line argument and uses StdDraw to plot a histogram of the frequency of occurrence of each of the 256 grayscale intensities.

3.1.5 Write a program that takes the name of an image file as a command-line argument and flips the image horizontally.

3.1.6 Write a program that takes the name of an image file as a command-line argument, and creates and shows three Picture objects, one that contains only the red components, one for green, and one for blue.

3.1.7 Write a program that takes the name of an image file as a command-line argument and prints the pixel coordinates of the lower-left corner and the upper-right corner of the smallest bounding box (rectangle parallel to the x- and y-axes) that contains all of the non-white pixels.

3.1.8 Write a program that takes as command-line arguments the name of an image file and the pixel coordinates of a rectangle within the image; reads from standard input a list of Color values (represented as triples of int values); and serves as a filter, printing those color values for which all pixels in the rectangle are background/foreground compatible. (Such a filter can be used to pick a color for text to label an image.)

3.1.9 Write a static method isValidDNA() that takes a string as its argument and returns true if and only if it is composed entirely of the characters A, T, C, and G.

3.1.10 Write a function complementWatsonCrick() that takes a DNA string as its argument and returns its Watson–Crick complement: replace A with T, C with G, and vice versa.

3.1.11 Write a function isWatsonCrickPalindrome() that takes a DNA string as its input and returns true if the string is a Watson–Crick complemented palindrome, and false otherwise. A Watson–Crick complemented palindrome is a DNA string that is equal to the reverse of its Watson–Crick complement.

3.1.12 Write a program to check whether an ISBN number is valid (see EXERCISE 1.3.35), taking into account that an ISBN number can have hyphens inserted at arbitrary places.

3.1.13 What does the following code fragment print?

String string1 = "hello";
String string2 = string1;
string1 = "world";
StdOut.println(string1);
StdOut.println(string2);

3.1.14 What does the following code fragment print?

String s = "Hello World";
s.toUpperCase();
s.substring(6, 11);
StdOut.println(s);

Answer: "Hello World". String objects are immutable—string methods each return a new String object with the appropriate value (but they do not change the value of the object that was used to invoke them). This code ignores the objects returned and just prints the original string. To print "WORLD", replace the second and third statements with s = s.toUpperCase() and s = s.substring(6, 11).

3.1.15 A string s is a circular shift of a string t if it matches when the characters of one string are circularly shifted by some number of positions. For example, ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a function isCircularShift() that checks whether two given strings s and t are circular shifts of one another. Hint: The solution is a one-liner with indexOf() and string concatenation.

3.1.16 Given a string that represents a domain name, write a code fragment to determine its top-level domain. For example, the top-level domain of the string cs.princeton.edu is edu.

3.1.17 Write a static method that takes a domain name as its argument and returns the reverse domain name (reverse the order of the strings between periods). For example, the reverse domain name of cs.princeton.edu is edu.princeton. cs. This computation is useful for web log analysis. (See EXERCISE 4.2.36.)

3.1.18 What does the following recursive function return?

Click here to view code image

public static String mystery(String s)
{
   int n = s.length();
   if (n <= 1) return s;
   String a = s.substring(0, n/2);
   String b = s.substring(n/2, n);
   return mystery(b) + mystery(a);
}

3.1.19 Write a test client for PotentialGene (PROGRAM 3.1.1) that takes a string as a command-line argument and reports whether it is a potential gene.

3.1.20 Write a version of PotentialGene (PROGRAM 3.1.1) that finds all potential genes contained as substrings within a long DNA string. Add a command-line argument to allow the user to specify the minimum length of a potential gene.

3.1.21 Write a filter that reads text from an input stream and prints it to an output stream, removing any lines that consist only of whitespace.

3.1.22 Write a program that takes a start string and a stop string as command-line arguments and prints all substrings of a given string that start with the first, end with the second, and otherwise contain neither. Note: Be especially careful of overlaps!

3.1.23 Modify StockQuote (PROGRAM 3.1.8) to take multiple symbols on the command line.

3.1.24 The example file DJIA.csv used for Split (PROGRAM 3.1.9) lists the date, high price, volume, and low price of the Dow Jones stock market average for every day since records have been kept. Download this file from the booksite and write a program that creates two Draw objects, one for the prices and one for the volumes, and plots them at a rate taken from the command line.

3.1.25 Write a program Merge that takes a delimiter string followed by an arbitrary number of file names as command-line arguments; concatenates the corresponding lines of each file, separated by the delimiter; and then prints the result to standard output, thus performing the opposite operation of Split (PROGRAM 3.1.9).

3.1.26 Find a website that publishes the current temperature in your area, and write a screen-scraper program Weather so that typing java Weather followed by your ZIP code will give you a weather forecast.

3.1.27 Suppose that a[] and b[] are both integer arrays consisting of millions of integers. What does the following code do, and how long does it take?

Click here to view code image

int[] temp = a; a = b; b = temp;

Solution. It swaps the arrays, but it does so by copying object references, so that it is not necessary to copy millions of values.

3.1.28 Describe the effect of the following function.

Click here to view code image

public void swap(Color a, Color b)
{
   Color temp = a;
   a = b;
   b = temp;
}

3.1.30 Sound visualization. Write a program that uses StdAudio and Picture to create an interesting two-dimensional color visualization of a sound file while it is playing. Be creative!

3.1.31 Kamasutra cipher. Write a filter KamasutraCipher that takes two strings as command-line argument (the key strings), then reads strings (separated by whitespace) from standard input, substitutes for each letter as specified by the key strings, and prints the result to standard output. This operation is the basis for one of the earliest known cryptographic systems. The condition on the key strings is that they must be of equal length and that any letter in standard input must appear in exactly one of them. For example, if the two keys are THEQUICKBROWN and FXJMPSVLAZYDG, then we make the table

T H E Q U I C K B R O W N
F X J M P S V L A Z Y D G

which tells us that we should substitute F for T, T for F, H for X, X for H, and so forth when filtering standard input to standard output. The message is encoded by replacing each letter with its pair. For example, the message MEET AT ELEVEN is encoded as QJJF BF JKJCJG. The person receiving the message can use the same keys to get the message back.

3.1.32 Safe password verification. Write a static method that takes a string as an argument and returns true if it meets the following conditions, false otherwise:

• At least eight characters long

• Contains at least one digit (0–9)

• Contains at least one uppercase letter

• Contains at least one lowercase letter

• Contains at least one character that is neither a letter nor a number

Such checks are commonly used for passwords on the web.

3.1.33 Color study. Write a program that displays the color study shown at right, which gives Albers squares corresponding to each of the 256 levels of blue (blue-to-white in row-major order) and gray (black-to-white in column-major order) that were used to print this book.

3.1.34 Entropy. The Shannon entropy measures the information content of an input string and plays a cornerstone role in information theory and data compression. Given a string of n characters, let f_c be the frequency of occurrence of character c. The quantity p_c = f_c / n is an estimate of the probability that c would be in the string if it were a random string, and the entropy is defined to be the sum of the quantity –p_c log₂ p_c, over all characters that appear in the string. The entropy is said to measure the information content of a string: if each character appears the same number times, the entropy is at its minimum value among strings of a given length. Write a program that takes the name of a file as a command-line argument and prints the entropy of the text in that file. Run your program on a web page that you read regularly, a recent paper that you wrote, and the fruit fly genome found on the website.

3.1.35 Tile. Write a program that takes the name of an image file and two integers m and n as command-line arguments and creates an m-by-n tiling of the image.

3.1.36 Rotation filter. Write a program that takes two command-line arguments (the name of an image file and a real number θ) and rotates the image θ degrees counterclockwise. To rotate, copy the color of each pixel (s_i, s_j) in the source image to a target pixel (t_i, t_j) whose coordinates are given by the following formulas:

t_i = (s_i – c_i)cos θ – (s_j – c_j)sin θ + c_i
t_j = (s_i – c_i)sin θ + (s_j – c_j)cos θ + c_j

where (c_i, c_j) is the center of the image.

3.1.37 Swirl filter. Creating a swirl effect is similar to rotation, except that the angle changes as a function of distance to the center of the image. Use the same formulas as in the previous exercise, but compute θ as a function of (s_i, s _j), specifically π/256 times the distance to the center.

3.1.38 Wave filter. Write a filter like those in the previous two exercises that creates a wave effect, by copying the color of each pixel (s_i, s _j) in the source image to a target pixel (t_i, t _j), where t_i = s_i and t_j = s_j +20 sin(2 π s_j / 64). Add code to take the amplitude (20 in the accompanying figure) and the frequency (64 in the accompanying figure) as command-line arguments. Experiment with various values of these parameters.

3.1.39 Glass filter. Write a program that takes the name of an image file as a command-line argument and applies a glass filter: set each pixel p to the color of a random neighboring pixel (whose pixel coordinates both differ from p’s coordinates by at most 5).

3.1.40 Slide show. Write a program that takes the names of several image files as command-line arguments and displays them in a slide show (one every two seconds), using a fade effect to black and a fade from black between images.

3.1.41 Morph. The example images in the text for Fade do not quite line up in the vertical direction (the mandrill’s mouth is much lower than Darwin’s). Modify Fade to add a transformation in the vertical dimension that makes a smoother transition.

3.1.42 Digital zoom. Write a program Zoom that takes the name of an image file and three numbers s, x, and y as command-line arguments, and shows an output image that zooms in on a portion of the input image. The numbers are all between 0 and 1, with s to be interpreted as a scale factor and (x, y) as the relative coordinates of the point that is to be at the center of the output image. Use this program to zoom in on a relative or pet in some digital photo on your computer. (If your photo came from an old cell phone or camera, you may not be able to zoom in too close without having visible artifacts from scaling.)

Implementing a data type as a Java class is not very different from implementing a library of static methods. The primary difference is that we associate data with the method implementations. The API specifies the constructors and instance methods that we need to implement, but we are free to choose any convenient representation. To cement the basic concepts, we begin by considering an implementation of a data type for charged particles. Next, we illustrate the process of creating data types by considering a range of examples, from complex numbers to stock accounts, including a number of software tools that we will use later in the book. Useful client code is testimony to the value of any data type, so we also consider a number of clients, including one that depicts the famous and fascinating Mandelbrot set.

The process of defining a data type is known as data abstraction. We focus on the data and implement operations on that data. Whenever you can clearly separate data and associated operations within a program, you should do so. Modeling physical objects or familiar mathematical abstractions is straightforward and extremely useful, but the true power of data abstraction is that it allows us to model anything that we can precisely specify. Once you gain experience with this style of programming, you will see that it helps us address programming challenges of arbitrary complexity.

To implement the Charge data type, we need to define the data-type values and implement the constructor that creates a charged particle, a method potentialAt() that returns the potential at the point (x, y) due to the charge, and a toString() method that returns a string representation of the charge.

• Allocates memory for the object

• Invokes the constructor code to initialize the instance variables

• Returns a reference to the newly created object

The constructor in Charge is typical: it initializes the instance variables with the values provided by the client as arguments.

• Parameter variables

• Local variables

• Instance variables

The first two are the same as for static methods: parameter variables are specified in the method signature and initialized with client values when the method is called, and local variables are declared and initialized within the method body. The scope of parameter variables is the entire method; the scope of local variables is the following statements in the block where they are defined. Instance variables are completely different: they hold data-type values for objects in a class, and their scope is the entire class. How do we specify which object’s value we want to use? If you think for a moment about this question, you will recall the answer. Each object in the class has a value: the code in an instance method refers to the value for the object that was used to invoke the method. For example, when we write c1.potentialAt(x, y), the code in potentialAt() is referring to the instance variables for c1.

The implementation of potentialAt() in Charge uses all three kinds of variable names, as illustrated in the diagram at the bottom of the previous page and summarized in this table:

Be sure that you understand the distinctions among the three kinds of variables that we use in implementing instance methods. These differences are a key to object-oriented programming.

public class Charge
{
   private final double rx, ry;
   private final double q;

   public Charge(double x0, double y0, double q0)
   {  rx = x0; ry = y0; q = q0;  }

   public double potentialAt(double x, double y)
   {
      double k = 8.99e09;
      double dx = x - rx;
      double dy = y - ry;
      return k * q / Math.sqrt(dx*dx + dy*dy);
   }

   public String toString()
   {
      return q + " at (" + rx + ", " + ry + ")";
   }

   public static void main(String[] args)
   {
      double x = Double.parseDouble(args[0]);
      double y = Double.parseDouble(args[1]);
      Charge c1 = new Charge(0.51, 0.63, 21.3);
      Charge c2 = new Charge(0.13, 0.94, 81.9);
      StdOut.println(c1);
      StdOut.println(c2);
      double v1 = c1.potentialAt(x, y);
      double v2 = c2.potentialAt(x, y);
      StdOut.printf("%.2e
", (v1 + v2));
   }
}

rx, ry | query point
   q   | charge

   k   | electrostatic constant
dx, dy | delta distances to query point

x, y | query point
 c1  | first charge
 v1  | potential due to c1
 c2  | second charge
 v2  | potential due to c2

% java Charge 0.2 0.5
21.3 at (0.51, 0.63)
81.9 at (0.13, 0.94)
2.22e+12

% java Charge 0.51 0.94
21.3 at (0.51, 0.63)
81.9 at (0.13, 0.94)
2.56e+12

These are the basic components that you need to understand to be able to define your own data types in Java. Every data-type implementation (Java class) that we will develop has the same basic ingredients as this first example: instance variables, constructors, instance methods, and a test client. In each data type that we develop, we go through the same steps. Rather than thinking about which action we need to take next to accomplish a computational goal (as we did when first learning to program), we think about the needs of a client, then accommodate them in a data type.

The first step in creating a data type is to specify an API. The purpose of the API is to separate clients from implementations, so as to enable modular programming. We have two goals when specifying an API. First, we want to enable clear and correct client code. Indeed, it is a good idea to write some client code before finalizing the API to gain confidence that the specified data-type operations are the ones that clients need. Second, we want to be able to implement the operations. There is no point in specifying operations that we have no idea how to implement.

The second step in creating a data type is to implement a Java class that meets the API specifications. First we choose the instance variables, then we write the code that manipulates the instance variables to implement the specified constructors and instance methods.

The third step in creating a data type is to write test clients, to validate the design decisions made in the first two steps.

What are the values that define the data type, and which operations do clients need to perform on those values? With these basic decisions made, you can create new data types and write clients that use them in the same way as you have been using built-in types. You will find many exercises at the end of this section that are intended to give you experience with data-type creation.

In other words, a Stopwatch is a stripped-down version of an old-fashioned stopwatch. When you create one, it starts running, and you can ask it how long it has been running by invoking the method elapsedTime(). You might imagine adding all sorts of bells and whistles to Stopwatch, limited only by your imagination. Do you want to be able to reset the stopwatch? Start and stop it? Include a lap timer? These sorts of things are easy to add (see EXERCISE 3.2.12).

The implementation of Stopwatch uses the Java system method System.currentTimeMillis(), which returns a long value giving the current time in milliseconds (the number of milliseconds since midnight on January 1, 1970 UTC). The data-type implementation could hardly be simpler. A Stopwatch saves its creation time in an instance variable, then returns the difference between that time and the current time whenever a client invokes its elapsedTime() method. A Stopwatch itself does not actually tick (an internal system clock on your computer does all the ticking); it just creates the illusion that it does for clients. Why not just use System.currentTimeMillis() in clients? We could do so, but using the Stopwatch leads to client code that is easier to understand and maintain.

The test client is typical. It creates two Stopwatch objects, uses them to measure the running time of two different computations, then prints the running times. The question of whether one approach to solving a problem is better than another has been lurking since the first few programs that you have run, and plays an essential role in program development. In SECTION 4.1, we will develop a scientific approach to understanding the cost of computation. Stopwatch is a useful tool in that approach.

public class Stopwatch
{
   private final long start;

   public Stopwatch()
   {  start = System.currentTimeMillis();  }

   public double elapsedTime()
   {
       long now = System.currentTimeMillis();
       return (now - start) / 1000.0;
   }

   public static void main(String[] args)
   {
      // Compute and time computation using Math.sqrt().
      int n = Integer.parseInt(args[0]);
      Stopwatch timer1 = new Stopwatch();
      double sum1 = 0.0;
      for (int i = 1; i <= n; i++)
         sum1 += Math.sqrt(i);
      double time1 = timer1.elapsedTime();
      StdOut.printf("%e (%.2f seconds)
", sum1, time1);

     // Compute and time computation using Math.pow().
      Stopwatch timer2 = new Stopwatch();
      double sum2 = 0.0;
      for (int i = 1; i <= n; i++)
         sum2 += Math.pow(i, 0.5);
      double time2 = timer2.elapsedTime();
      StdOut.printf("%e (%.2f seconds)
", sum2, time2);
   }
}

start | creation time

% java Stopwatch 100000000
6.666667e+11 (0.65 seconds)
6.666667e+11 (8.47 seconds)

To implement a data type, you must first determine which instance variables to use. In this case, we need to use an array as an instance variable. Specifically, Histogram (PROGRAM 3.2.3) maintains an instance variable freq[] so that freq[i] records the number of times the data value i appears in the data, for each i between 0 and n-1. Histogram also includes an integer instance variable max that stores the maximum frequency of any of the values (which corresponds to the height of the tallest bar). The instance method draw() method uses the variable max to set the y-scale of the standard drawing window and calls the method StdStats.plotBars() to draw the histogram of values. The main() method is a sample client that performs Bernoulli trials. It is substantially simpler than Bernoulli (PROGRAM 2.2.6) because it uses the Histogram data type.

By creating a data type such as Histogram, we reap the benefits of modular programming (reusable code, independent development of small programs, and so forth) that we discussed in CHAPTER 2, with the additional benefit that we separate the data. Without Histogram, we would have to mix the code for creating the histogram with the code for the managing the data of interest, resulting in a program much more difficult to understand and maintain than the two separate programs. Whenever you can clearly separate data and associated operations within a program, you should do so.

---

Program 3.2.3 Histogram

Click here to view code image

public class Histogram
{
    private final double[] freq;
    private double max;

    public Histogram(int n)
    {  // Create a new histogram.
       freq = new double[n];
    }

    public void addDataPoint(int i)
    {  // Add one occurrence of the value i.
       freq[i]++;
       if (freq[i] > max) max = freq[i];
    }

    public void draw()
    {  // Draw (and scale) the histogram.
       StdDraw.setYscale(0, max);
       StdStats.plotBars(freq);
    }

   public static void main(String[] args)
   {  // See Program 2.2.6.
      int n = Integer.parseInt(args[0]);
      int trials = Integer.parseInt(args[1]);
      Histogram histogram = new Histogram(n+1);
      StdDraw.setCanvasSize(500, 200);
      for (int t = 0; t < trials; t++)
         histogram.addDataPoint(Bernoulli.binomial(n));
      histogram.draw();
   }
}

---

freq[] | frequency counts
 max   | maximum frequency

---

This data type supports simple client code to create histograms of the frequency of occurrence of integers values between 0 and n-1. The frequencies are kept in an instance variable that is an array. An integer instance variable max tracks the maximum frequency (for scaling the y-axis when drawing the histogram). The sample client is a version of Bernoulli (PROGRAM 2.2.6), but is substantially simper because it uses the Histogram data type.

---

Imagine a turtle that lives in the unit square and draws lines as it moves. It can move a specified distance in a straight line, or it can rotate left (counterclockwise) a specified number of degrees. According to the API, when we create a turtle, we place it at a specified point, facing a specified direction. Then, we create drawings by giving the turtle a sequence of goForward() and turnLeft() commands.

For example, to draw an equilateral triangle, we create a Turtle at (0.5, 0) facing at an angle of 60 degrees counterclockwise from the origin, then direct it to take a step forward, then rotate 120 degrees counterclockwise, then take another step forward, then rotate another 120 degrees counterclockwise, and then take a third step forward to complete the triangle. Indeed, all of the turtle clients that we will examine simply create a turtle, then give it an alternating sequence of step and rotate commands, varying the step size and the amount of rotation. As you will see in the next several pages, this simple model allows us to create arbitrarily complex drawings, with many important applications.

Turtle (PROGRAM 3.2.4) is an implementation of this API that uses StdDraw. It maintains three instance variables: the coordinates of the turtle’s position and the current direction it is facing, measured in degrees counterclockwise from the x-axis. Implementing the two methods requires changing the values of these variables, so they are not final. The necessary updates are straightforward: turnLeft(delta) adds delta to the current angle, and goForward(step) adds the step size times the cosine of its argument to the current x-coordinate and the step size times the sine of its argument to the current y-coordinate.

The test client in Turtle takes an integer command-line argument n and draws a regular polygon with n sides. If you are interested in elementary analytic geometry, you might enjoy verifying that fact. Whether or not you choose to do so, think about what you would need to do to compute the coordinates of all the points in the polygon. The simplicity of the turtle’s approach is very appealing. In short, turtle graphics serves as a useful abstraction for describing geometric shapes of all sorts. For example, we obtain a good approximation to a circle by taking n to a sufficiently large value.

You can use a Turtle as you use any other object. Programs can create arrays of Turtle objects, pass them as arguments to functions, and so forth. Our examples will illustrate these capabilities and convince you that creating a data type like Turtle is both very easy and very useful. For each of them, as with regular polygons, it is possible to compute the coordinates of all the points and draw straight lines to get the drawings, but it is easier to do so with a Turtle. Turtle graphics exemplifies the value of data abstraction.

---

Program 3.2.4 Turtle graphics

Click here to view code image

public class Turtle
{
   private double x, y;
   private double angle;

   public Turtle(double x0, double y0, double a0)
   {  x = x0; y = y0; angle = a0;  }

   public void turnLeft(double delta)
   {  angle += delta;  }

   public void goForward(double step)
   {  // Compute new position; move and draw line to it.
      double oldx = x, oldy = y;
      x += step * Math.cos(Math.toRadians(angle));
      y += step * Math.sin(Math.toRadians(angle));
      StdDraw.line(oldx, oldy, x, y);
   }

   public static void main(String[] args)
   {  // Draw a regular polygon with n sides.
      int n = Integer.parseInt(args[0]);
      double angle = 360.0 / n;
      double step = Math.sin(Math.toRadians(angle/2));
      Turtle turtle = new Turtle(0.5, 0.0, angle/2);
      for (int i = 0; i < n; i++)
      {
         turtle.goForward(step);
         turtle.turnLeft(angle);
      }
   }
}

---

 x, y | position (in unit square)
angle | direction of motion (degrees, counterclockwise from x-axis)

This data type supports turtle graphics, which often simplifies the creation of drawings.

---

---

---

---

The client code is straightforward, except for the value of the step size. If you carefully examine the first few examples, you will see (and be able to prove by induction) that the width of the curve of order n is 3ⁿ times the step size, so setting the step size to 1/3ⁿ produces a curve of width 1. Similarly, the number of steps in a curve of order n is 4ⁿ, so Koch will not finish if you invoke it for large n.

You can find many examples of recursive patterns of this sort that have been studied and developed by mathematicians, scientists, and artists from many cultures in many contexts. Here, our interest in them is that the turtle graphics abstraction greatly simplifies the client code that draws these patterns.

Click here to view code image

public class Koch
{
   public static void koch(int n, double step, Turtle turtle)
   {
      if (n == 0)
      {
         turtle.goForward(step);
         return;
      }
      koch(n-1, step, turtle);
      turtle.turnLeft(60.0);
      koch(n-1, step, turtle);
      turtle.turnLeft(-120.0);
      koch(n-1, step, turtle);
      turtle.turnLeft(60.0);
      koch(n-1, step, turtle);
   }

   public static void main(String[] args)
   {
      int n = Integer.parseInt(args[0]);
      double step = 1.0 / Math.pow(3.0, n);
      Turtle turtle = new Turtle(0.0, 0.0, 0.0);
      koch(n, step, turtle);
   }
}

Spiral (PROGRAM 3.2.5) is an implementation of this curve. It takes n and the decay factor as command-line arguments and instructs the turtle to alternately step and turn until it has wound around itself 10 times. As you can see from the four examples given with the program, if the decay factor is greater than 1, the path spirals into the center of the drawing. The argument n controls the shape of the spiral. You are encouraged to experiment with Spiral yourself to develop an understanding of the way in which the parameters control the behavior of the spiral.

The logarithmic spiral was first described by René Descartes in 1638. Jacob Bernoulli was so amazed by its mathematical properties that he named it the spira mirabilis (miraculous spiral) and even asked to have it engraved on his tombstone. Many people also consider it to be “miraculous” that this precise curve is clearly present in a broad variety of natural phenomena. Three examples are depicted below: the chambers of a nautilus shell, the arms of a spiral galaxy, and the cloud formation in a tropical storm. Scientists have also observed it as the path followed by a hawk approaching its prey and as the path followed by a charged particle moving perpendicular to a uniform magnetic field.

One of the goals of scientific enquiry is to provide simple but accurate models of complex natural phenomena. Our tired turtle certainly passes that test!

---

Program 3.2.5 Spira mirabilis

Click here to view code image

public class Spiral
{
   public static void main(String[] args)
   {
      int n         = Integer.parseInt(args[0]);
      double decay  = Double.parseDouble(args[1]);
      double angle  = 360.0 / n;
      double step   = Math.sin(Math.toRadians(angle/2));
      Turtle turtle = new Turtle(0.5, 0, angle/2);

      for (int i = 0; i < 10 * 360 / angle; i++)
      {
         step /= decay;
         turtle.goForward(step);
         turtle.turnLeft(angle);
      }
   }
}

---

  step | step size
 decay | decay factor
 angle | rotation amount
turtle | tired turtle

This code is a modification of the test client in PROGRAM 3.2.4 that decreases the step size at each step and cycles around 10 times. The angle controls the shape; the decay controls the nature of the spiral.

---

---

---

Or perhaps our turtle has friends, all of whom have had one too many. After they have wandered around for a sufficiently long time, their paths merge together and become indistinguishable from a single path. Astrophysicists today are using this model to understand observed properties of distant galaxies.

Turtle graphics was originally developed by Seymour Papert at MIT in the 1960s as part of an educational programming language, Logo, that is still used today in toys. But turtle graphics is no toy, as we have just seen in numerous scientific examples. Turtle graphics also has numerous commercial applications. For example, it is the basis for PostScript, a programming language for creating printed pages that is used for most newspapers, magazines, and books. In the present context, Turtle is a quintessential object-oriented programming example, showing that a small amount of saved state (data abstraction using objects, not just functions) can vastly simplify a computation.

Click here to view code image

public class DrunkenTurtle
{
   public static void main(String[] args)
   {
      int trials = Integer.parseInt(args[0]);
      double step = Double.parseDouble(args[1]);
      Turtle turtle = new Turtle(0.5, 0.5, 0.0);
      for (int t = 0; t < trials; t++)
      {
         turtle.turnLeft(StdRandom.uniform(0.0, 360.0));
         turtle.goForward(step);
      }
   }
}

Click here to view code image

public class DrunkenTurtles
{
   public static void main(String[] args)
   {
      int n = Integer.parseInt(args[0]);          // number of turtles
      int trials = Integer.parseInt(args[1]);     // number of steps
      double step = Double.parseDouble(args[2]);  // step size
      Turtle[] turtles = new Turtle[n];
      for (int i = 0; i < n; i++)
      {
         double x = StdRandom.uniform(0.0, 1.0);
         double y = StdRandom.uniform(0.0, 1.0);
         turtles[i] = new Turtle(x, y, 0.0);
      }
      for (int t = 0; t < trials; t++)
      {  // All turtles take one step.
         for (int i = 0; i < n; i++)
         {  // Turtle i takes one step in a random direction.
            turtles[i].turnLeft(StdRandom.uniform(0.0, 360.0));
            turtles[i].goForward(step);
         }
      }
   }
}

Developing a data type for complex numbers is a prototypical example of object-oriented programming. No programming language can provide implementations of every mathematical abstraction that we might need, but the ability to implement data types gives us not just the ability to write programs to easily manipulate abstractions such as complex numbers, polynomials, vectors, and matrices, but also the freedom to think in terms of new abstractions.

The operations on complex numbers that are needed for basic computations are to add and multiply them by applying the commutative, associative, and distributive laws of algebra (along with the identity i² = –1); to compute the magnitude; and to extract the real and imaginary parts, according to the following equations:

• Addition: (x + iy) + (v + iw) = (x + v) + i(y + w)

• Multiplication: (x + iy) × (v + iw) = (xv – yw) + i(yv + xw)

• Magnitude: |x+iy|=x2+y2

• Real part: Re(x + iy) = x

• Imaginary part: Im(x + iy) = y

For example, if a = 3 + 4i and b =–2 + 3i, then a +b = 1 + 7i, a × b = –18 + i, Re(a) = 3, Im(a) = 4, and | a | = 5.

With these basic definitions, the path to implementing a data type for complex numbers is clear. As usual, we start with an API that specifies the data-type operations:

For simplicity, we concentrate in the text on just the basic operations in this API, but EXERCISE 3.2.19 asks you to consider several other useful operations that might be included in such an API.

Complex (PROGRAM 3.2.6) is a class that implements this API. It has all of the same components as did Charge (and every Java data type implementation): instance variables (re and im), a constructor, instance methods (plus(), times(), abs(), re(), im(), and toString()), and a test client. The test client first sets z₀ to 1 + i, then sets z to z₀, and then evaluates

z = z² + z₀ = (1 + i)² + (1 + i) = (1 + 2i –1) + (1 + i) = 1 + 3i
z = z² + z₀ = (1 + 3i)² + (1 + i) = (1 + 6i –9) + (1 + i) = –7 + 7i

This code is straightforward and similar to code that you have seen earlier in this chapter, with one exception: the code that implements the arithmetic methods makes use of a new mechanism for accessing object values.

Complex numbers are the basis for sophisticated calculations from applied mathematics that have many applications. With Complex we can concentrate on developing applications programs that use complex numbers without worrying about re-implementing methods such as times(), abs(), and so forth. Such methods are implemented once, and are reusable, as opposed to the alternative of copying this code into any applications program that uses complex numbers. Not only does this approach save debugging, but it also allows for changing or improving the implementation if needed, since it is separate from its clients. Whenever you can clearly separate data and associated tasks within a computation, you should do so.

To give you a feeling for the nature of calculations involving complex numbers and the utility of the complex number abstraction, we next consider a famous example of a Complex client.

public class Complex
{
   private final double re;
   private final double im;

   public Complex(double real, double imag)
   {  re = real; im = imag;  }

   public Complex plus(Complex b)
   {  // Return the sum of this number and b.
      double real = re + b.re;
      double imag = im + b.im;
      return new Complex(real, imag);
   }

   public Complex times(Complex b)
   {  // Return the product of this number and b.
      double real = re * b.re - im * b.im;
      double imag = re * b.im + im * b.re;
      return new Complex(real, imag);
   }

   public double abs()
   {  return Math.sqrt(re*re + im*im);  }

   public double re()  { return re; }
   public double im()  { return im; }

   public String toString()
   {  return re + " + " + im + "i";  }

   public static void main(String[] args)
   {
      Complex z0 = new Complex(1.0, 1.0);
      Complex z = z0;
      z = z.times(z).plus(z0);
      z = z.times(z).plus(z0);
      StdOut.println(z);
   }
}

re | real part
im | imaginary part

% java Complex
-7.0 + 7.0i

The set of points in the Mandelbrot set cannot be described by a single mathematical equation. Instead, it is defined by an algorithm, and therefore is a perfect candidate for a Complex client: we study the set by writing a program to plot it.

The rule for determining whether a complex number z₀ is in the Mandelbrot set is simple. Consider the sequence of complex numbers z₀, z₁, z₂, . . ., z_t, . . ., where z_t+1 = (z_t)² + z₀. For example, this table shows the first few elements in the sequence corresponding to z₀ =1 + i:

Now, if the sequence | z_t | diverges to infinity, then z₀ is not in the Mandelbrot set; if the sequence is bounded, then z₀ is in the Mandelbrot set. For many points, the test is simple. For many other points, the test requires more computation, as indicated by the examples in this table:

For brevity, the numbers in the rightmost two columns of this table are given to just two decimal places. In some cases, we can prove whether numbers are in the set. For example, 0 + 0i is certainly in the set (since the magnitude of all the numbers in its sequence is 0), and 2 + 0i is certainly not in the set (since its sequence dominates the powers of 2, which diverges to infinity). In some other cases, the growth is readily apparent. For example, 1 + i does not seem to be in the set. Other sequences exhibit a periodic behavior. For example, i maps to –1 + i to –i to –1 + i to –i, and so forth. Still other sequences go on for a very long time before the magnitude of the numbers begins to get large.

To visualize the Mandelbrot set, we sample complex points, just as we sample real-valued points to plot a real-valued function. Each complex number x + i y corresponds to a point (x, y) in the plane, so we can plot the results as follows: for a specified resolution n, we define an evenly spaced n-by-n pixel grid within a specified square and draw a black pixel if the corresponding point is in the Mandelbrot set and a white pixel if it is not. This plot is a strange and wondrous pattern, with all the black dots connected and falling roughly within the 2-by-2 square centered at the point –1/2 + 0i. Large values of n will produce higher-resolution images, at the cost of more computation. Looking closer reveals self-similarities throughout the plot. For example, the same bulbous pattern with self-similar appendages appears all around the contour of the main black cardioid region, of sizes that resemble the simple ruler function of PROGRAM 1.2.1. When we zoom in near the edge of the cardioid, tiny self-similar cardioids appear!

But how, precisely, do we produce such plots? Actually, no one knows for sure, because there is no simple test that would enable us to conclude that a point is surely in the set. Given a complex number, we can compute the terms at the beginning of its sequence, but may not be able to know for sure that the sequence remains bounded. There is a test that tells us for sure that a complex number is not in the set: if the magnitude of any number in its sequence ever exceeds 2 (such as for 1 + 3i), then the sequence surely will diverge.

Mandelbrot (PROGRAM 3.2.7) uses this test to plot a visual representation of the Mandelbrot set. Since our knowledge of the set is not quite black-and-white, we use grayscale in our visual representation. It is based on the function mand(), which takes a Complex argument z0 and an int argument max and computes the Mandelbrot iteration sequence starting at z0, returning the number of iterations for which the magnitude stays less than (or equal to) 2, up to the limit max.

For each pixel, the main() method in Mandelbrot computes the complex number z0 corresponding to the pixel and then computes 255 - mand(z0, 255) to create a grayscale color for the pixel. Any pixel that is not black corresponds to a complex number that we know to be not in the Mandelbrot set because the magnitude of the numbers in its sequence exceeds 2 (and therefore will go to infinity). The black pixels (grayscale value 0) correspond to points that we assume to be in the set because the magnitude did not exceed 2 during the first 255 Mandelbrot iterations.

The complexity of the images that this simple program produces is remarkable, even when we zoom in on a tiny portion of the plane. For even more dramatic pictures, we can use color (see EXERCISE 3.2.35). And the Mandelbrot set is derived from iterating just one function f(z) = (z² + z₀): we have a great deal to learn from studying the properties of other functions as well.

The simplicity of the code masks a substantial amount of computation. There are about 0.25 million pixels in a 512-by-512 image, and all of the black ones require 255 Mandelbrot iterations, so producing an image with Mandelbrot requires hundreds of millions of operations on Complex values.

Fascinating as it is to study, our primary interest in Mandelbrot is as an example client of Complex, to illustrate that computing with a data type that is not built into Java (complex numbers) is a natural and useful programming activity. Mandelbrot is a simple and natural expression of the computation, made so by the design and implementation of Complex. You could implement Mandelbrot without using Complex, but the code would essentially have to merge together the code in PROGRAM 3.2.6 and PROGRAM 3.2.7 and, therefore, would be much more difficult to understand. Whenever you can clearly separate tasks within a program, you should do so.

---

Program 3.2.7 Mandelbrot set

Click here to view code image

import java.awt.Color;

public class Mandelbrot
{
   private static int mand(Complex z0, int max)
   {
      Complex z = z0;
      for (int t = 0; t < max; t++)
      {
         if (z.abs() > 2.0) return t;
         z = z.times(z).plus(z0);
      }
      return max;
   }

   public static void main(String[] args)
   {
      double xc   = Double.parseDouble(args[0]);
      double yc   = Double.parseDouble(args[1]);
      double size = Double.parseDouble(args[2]);
      int n = 512;
      Picture picture = new Picture(n, n);
      for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
         {
            double x0 = xc - size/2 + size*i/n;
            double y0 = yc - size/2 + size*j/n;
            Complex z0 = new Complex(x0, y0);
            int gray = 255 - mand(z0, 255);
            Color c = new Color(gray, gray, gray);
            picture.set(i, n-1-j, c);
         }
      picture.show();
   }
}

---

x0, y0 | point in square
  z0   | x0 + i y0
  max  | iteration limit
xc, yc | center of square
 size  | square is size-by-size
   n   | grid is n-by-n pixels
  pic  | image for output
   c   | pixel color for output

---

---

This program takes three command-line arguments that specify the center and size of a square region of interest, and makes a digital image showing the result of sampling the Mandelbrot set in that region at a size-by-size grid of evenly spaced points. It colors each pixel with a grayscale value that is determined by counting the number of iterations before the Mandelbrot sequence for the corresponding complex number exceeds 2.0 in magnitude, up to 255.

---

Suppose that a stockbroker needs to maintain customer accounts containing shares of various stocks. That is, the set of values the broker needs to process includes the customer’s name, number of different stocks held, number of shares and ticker symbol for each stock, and cash on hand. To process an account, the broker needs at least the operations defined in this API:

The broker certainly needs to buy, sell, and provide reports to the customer, but the first key to understanding this kind of data processing is to consider the StockAccount() constructor and the save() method in this API. The customer information has a long lifetime and needs to be saved in a file or database. To process an account, a client program needs to read information from the corresponding file; process the information as appropriate; and, if the information changes, write it back to the file, saving it for later. To enable this kind of processing, we need a file format and an internal representation, or a data structure, for the account information.

As a (whimsical) running example, we imagine that a broker is maintaining a small portfolio of stocks in leading software companies for Alan Turing, the father of computing. As an aside: Turing’s life story is a fascinating one that is worth investigating further. Among many other things, he worked on computational cryptography that helped to bring about the end of World War II, he developed the basis for the theory of computing, he designed and built one of the first computers, and he was a pioneer in artificial intelligence research. It is perhaps safe to assume that Turing, whatever his financial situation as an academic researcher in the middle of the last century, would be sufficiently optimistic about the potential impact of computing software in today’s world that he would make some small investments.

% more Turing.txt
Turing, Alan
10.24
4
100 ADBE
 25 GOOG
 97 IBM
250 MSFT

File format

• A String value for the account name

• A double value for the cash balance

• An int value for the number of stocks

• An array of String values for stock symbols

• An array of int values for numbers of shares

public class StockAccount
{
   private final String name;
   private double cash;
   private int n;
   private int[] shares;
   private String[] stocks;
   ...
}

Data structure blueprint

We directly reflect these choices in the instance variable declarations in StockAccount (PROGRAM 3.2.8). The arrays stocks[] and shares[] are known as parallel arrays. Given an index i, stocks[i] gives a stock symbol and shares[i] gives the number of shares of that stock in the account. An alternative design would be to define a separate data type for stocks to manipulate this information for each stock and maintain an array of objects of that type in StockAccount.

StockAccount includes a constructor, which reads a file in the specified format and creates an account with this information. Also, our broker needs to provide a periodic detailed report to customers, perhaps using the following code for printReport() in StockAccount, which relies on StockQuote (PROGRAM 3.1.8) to retrieve each stock’s price from the web.

Click here to view code image

public void printReport()
{
   StdOut.println(name);
   double total = cash;
   for (int i = 0; i < n; i++)
   {
      int amount = shares[i];
      double price = StockQuote.priceOf(stocks[i]);
      total += amount * price;
      StdOut.printf("%4d %5s ", amount, stocks[i]);
      StdOut.printf("%9.2f %11.2f
", price, amount*price);
   }
   StdOut.printf("%21s %10.2f
", "Cash: ", cash);
   StdOut.printf("%21s %10.2f
", "Total:", total);
}

Implementations of valueOf() and save() are straightforward (see EXERCISE 3.2.22). The implementations of buy() and sell() require the use of basic mechanisms introduced in SECTION 4.4, so we defer them to EXERCISE 4.4.65.

On the one hand, this client illustrates the kind of computing that was one of the primary drivers in the evolution of computing in the 1950s. Banks and other companies bought early computers precisely because of the need to do such financial reporting. For example, formatted writing was developed precisely for such applications. On the other hand, this client exemplifies modern web-centric computing, as it gets information directly from the web, without using a browser.

Beyond these basic methods, an actual application of these ideas would likely use a number of other clients. For example, a broker might want to create an array of all accounts, then process a list of transactions that both modify the information in those accounts and actually carry out the transactions through the web. Of course, such code needs to be developed with great care!

public class StockAccount
{
   private final String name;
   private double cash;
   private int n;
   private int[] shares;
   private String[] stocks;

   public StockAccount(String filename)
   {  // Build data structure from specified file.
      In in = new In(filename);
      name = in.readLine();
      cash = in.readDouble();
      n = in.readInt();
      shares = new int[n];
      stocks = new String[n];
      for (int i = 0; i < n; i++)
      {  // Process one stock.
         shares[i] = in.readInt();
         stocks[i] = in.readString();
      }
   }

   public static void main(String[] args)
   {
      StockAccount account = new StockAccount(args[0]);
      account.printReport();
   }
}

  name   | customer name
  cash   | cash balance
   n     | number of stocks
shares[] | share counts
stocks[] | stock symbols

% more Turing.txt
Turing, Alan
10.24
4
100 ADBE
 25 GOOG
 97 IBM
250 MSFT

% java StockAccount Turing.txt
Turing, Alan
 100  ADBE     70.56     7056.00
  25  GOOG    502.30    12557.50
  97   IBM    156.54    15184.38
 250  MSFT     45.68    11420.00
               Cash:       10.24
               Total:   46228.12

When you learned how to define functions that can be used in multiple places in a program (or in other programs) in CHAPTER 2, you moved from a world where programs are simply sequences of statements in a single file to the world of modular programming, summarized in our mantra: whenever you can clearly separate subtasks within a program, you should do so. The analogous capability for data, introduced in this chapter, moves you from a world where data has to be one of a few elementary types of data to a world where you can define your own data types. This profound new capability vastly extends the scope of your programming. As with the concept of a function, once you have learned to implement and use data types, you will marvel at the primitive nature of programs that do not use them.

But object-oriented programming is much more than structuring data. It enables us to associate the data relevant to a subtask with the operations that manipulate that data and to keep both separate in an independent module. With object-oriented programming, our mantra is this: whenever you can clearly separate data and associated operations for subtasks within a computation, you should do so.

The examples that we have considered are persuasive evidence that object-oriented programming can play a useful role in a broad range of activities. Whether we are trying to design and build a physical artifact, develop a software system, understand the natural world, or process information, a key first step is to define an appropriate abstraction, such as a geometric description of the physical artifact, a modular design of the software system, a mathematical model of the natural world, or a data structure for the information. When we want to write programs to manipulate instances of a well-defined abstraction, we can just implement it as a data type in a Java class and write Java programs to create and manipulate objects of that type.

Each time that we develop a class that makes use of other classes by creating and manipulating objects of the type defined by the class, we are programming at a higher layer of abstraction. In the next section, we discuss some of the design challenges inherent in this kind of programming.