Algorithms: The Basic Programming Model

From the book

Algorithms: Part I, 4th Edition

Learn More Buy

From the book

From the book 

Algorithms: Part I, 4th Edition

Learn More Buy

INPUT AND OUTPUT

The primary purpose of our standard libraries for input, output, and drawing is to support a simple model for Java programs to interact with the outside world. These libraries are built upon extensive capabilities that are available in Java libraries, but are generally much more complicated and much more difficult to learn and use. We begin by briefly reviewing the model.

In our model, a Java program takes input values from command-line arguments or from an abstract stream of characters known as the standard input stream and writes to another abstract stream of characters known as the standard output stream.

Figure 1.4 A bird’s-eye view of a Java program

Necessarily, we need to consider the interface between Java and the operating system, so we need to briefly discuss basic mechanisms that are provided by most modern operating systems and program-development environments. You can find more details about your particular system on the booksite. By default, command-line arguments, standard input, and standard output are associated with an application supported by either the operating system or the program development environment that takes commands. We use the generic term terminal window to refer to the window maintained by this application, where we type and read text. Since early Unix systems in the 1970s this model has proven to be a convenient and direct way for us to interact with our programs and data. We add to the classical model a standard drawing that allows us to create visual representations for data analysis.

Commands and arguments. 

In the terminal window, we see a prompt, where we type commands to the operating system that may take arguments. We use only a few commands in this book, shown in the table below. Most often, we use the .java command, to run our programs. As mentioned on page 35, Java classes have a main() static method that takes a String array args[] as its argument. That array is the sequence of command-line arguments that we type, provided to Java by the operating system. By convention, both Java and the operating system process the arguments as strings. If we intend for an argument to be a number, we use a method such as Integer.parseInt() to convert it from String to the appropriate type.

Typical operating-system commands

Standard output. 

Our StdOut library provides support for standard output. By default, the system connects standard output to the terminal window. The print() method puts its argument on standard output; the println() method adds a newline; and the printf() method supports formatted output, as described next. Java provides a similar method in its System.out library; we use StdOut to treat standard input and standard output in a uniform manner (and to provide a few technical improvements).

Figure 1.5 Anatomy of a command

API for our library of static methods for standard output

To use these methods, download into your working directory StdOut.java from the booksite and use code such as StdOut.println("Hello, World"); to call them. A sample client is shown at right.

public class RandomSeq
{
   public static void main(String[] args)
   {  // Print N random values in (lo, hi).
      int N = Integer.parseInt(args[0]);
      double lo = Double.parseDouble(args[1]);
      double hi = Double.parseDouble(args[2]);
      for (int i = 0; i < N; i++)
      {
         double x = StdRandom.uniform(lo, hi);
         StdOut.printf("%.2f\n", x);
      }
   }
}

Sample StdOut client

% java RandomSeq 5 100.0 200.0
123.43
153.13
144.38
155.18
104.02

Formatted output. 

In its simplest form, printf() takes two arguments. The first argument is a format string that describes how the second argument is to be converted to a string for output. The simplest type of format string begins with % and ends with a one-letter conversion code. The conversion codes that we use most frequently are d (for decimal values from Java’s integer types), f (for floating-point values), and s (for String values). Between the % and the conversion code is an integer value that specifies the field width of the converted value (the number of characters in the converted output string). By default, blank spaces are added on the left to make the length of the converted output equal to the field width; if we want the spaces on the right, we can insert a minus sign before the field width. (If the converted output string is bigger than the field width, the field width is ignored.) Following the width, we have the option of including a period followed by the number of digits to put after the decimal point (the precision) for a double value or the number of characters to take from the beginning of the string for a String value. The most important thing to remember about using printf() is that the conversion code in the format and the type of the corresponding argument must match. That is, Java must be able to convert from the type of the argument to the type required by the conversion code. The first argument of printf() is a String that may contain characters other than a format string. Any part of the argument that is not part of a format string passes through to the output, with the format string replaced by the argument value (converted to a String as specified). For example, the statement

StdOut.printf("PI is approximately %.2f\n", Math.PI);

prints the line

PI is approximately 3.14

Note that we need to explicitly include the newline character \n in the argument in order to print a new line with printf(). The printf() function can take more than two arguments. In this case, the format string will have a format specifier for each additional argument, perhaps separated by other characters to pass through to the output. You can also use the static method String.format() with arguments exactly as just described for printf() to get a formatted string without printing it. Formatted printing is a convenient mechanism that allows us to develop compact code that can produce tabulated experimental data (our primary use in this book).

int

d

512

"%14d"
"%-14d"

"           512"
"512           "

double

f

1595.1680010754388

"%14.2f"
"%.7f"
"%14.4e"

"       1595.17"
"1595.1680011"
"    1.5952e+03"

e

String

s

"Hello, World"

"%14s"
"%-14s"
"%-14.5s"

"  Hello, World"
"Hello, World  "
"Hello         "

Format conventions for printf() (see the booksite for many other options)

Standard input. 

Our StdIn library takes data from the standard input stream that may be empty or may contain a sequence of values separated by whitespace (spaces, tabs, newline characters, and the like). By default, the system connects standard output to the terminal window—what you type is the input stream (terminated by <ctrl-d> or <ctrl-z>, depending on your terminal window application). Each value is a String or a value from one of Java’s primitive types. One of the key features of the standard input stream is that your program consumes values when it reads them. Once your program has read a value, it cannot back up and read it again. This assumption is restrictive, but it reflects physical characteristics of some input devices and simplifies implementing the abstraction. Within the input stream model, the static methods in this library are largely self-documenting (described by their signatures).

public class Average
{ 
   public static void main(String[] args)
   {  // Average the numbers on StdIn.
      double sum = 0.0;
      int cnt = 0;
      while (!StdIn.isEmpty())
      {  // Read a number and cumulate the sum.
         sum += StdIn.readDouble();
         cnt++;
      }
      double avg = sum / cnt;
      StdOut.printf("Average is %.5f\n", avg);
   }
}

Sample StdIn client

% java Average
1.23456
2.34567
3.45678
4.56789
<ctrl-d>
Average is 2.90123

public class StdIn

static boolean

isEmpty()

static     int

readInt()

static  double

readDouble()

static   float

readFloat()

static    long

readLong()

static boolean

readBoolean()

static    char

readChar()

static    byte

readByte()

static  String

readString()

static boolean

hasNextLine()

static  String

readLine()

static  String

readAll()

API for our library of static methods for standard input

Redirection and piping. 

Standard input and output enable us to take advantage of command-line extensions supported by many operating-systems. By adding a simple directive to the command that invokes a program, we can redirect its standard output to a file, either for permanent storage or for input to another program at a later time:

% java RandomSeq 1000 100.0 200.0 > data.txt

This command specifies that the standard output stream is not to be printed in the terminal window, but instead is to be written to a text file named data.txt. Each call to StdOut.print() or StdOut.println() appends text at the end of that file. In this example, the end result is a file that contains 1,000 random values. No output appears in the terminal window: it goes directly into the file named after the > symbol. Thus, we can save away information for later retrieval. Not that we do not have to change RandomSeq in any way—it is using the standard output abstraction and is unaffected by our use of a different implementation of that abstraction. Similarly, we can redirect standard input so that StdIn reads data from a file instead of the terminal application:

% java Average < data.txt

Figure 1.6 Redirection and piping from the command line

This command reads a sequence of numbers from the file data.txt and computes their average value. Specifically, the < symbol is a directive that tells the operating system to implement the standard input stream by reading from the text file data.txt instead of waiting for the user to type something into the terminal window. When the program calls StdIn.readDouble(), the operating system reads the value from the file. Combining these to redirect the output of one program to the input of another is known as piping:

% java RandomSeq 1000 100.0 200.0 | java Average

This command specifies that standard output for RandomSeq and standard input for Average are the same stream. The effect is as if RandomSeq were typing the numbers it generates into the terminal window while Average is running. This difference is profound, because it removes the limitation on the size of the input and output streams that we can process. For example, we could replace 1000 in our example with 1000000000, even though we might not have the space to save a billion numbers on our computer (we do need the time to process them). When RandomSeq calls StdOut.println(), a string is added to the end of the stream; when Average calls StdIn.readInt(), a string is removed from the beginning of the stream. The timing of precisely what happens is up to the operating system: it might run RandomSeq until it produces some output, and then run Average to consume that output, or it might run Average until it needs some output, and then run RandomSeq until it produces the needed output. The end result is the same, but our programs are freed from worrying about such details because they work solely with the standard input and standard output abstractions.

Input and output from a file. 

Our In and Out libraries provide static methods that implement the abstraction of reading from and writing to a file the contents of an array of values of a primitive type (or String). We use readInts(), readDoubles(), and readStrings() in the In library and writeInts(), writeDoubles(), and writeStrings() in the Out library. The named argument can be a file or a web page. For example, this ability allows us to use a file and standard input for two different purposes in the same program, as in BinarySearch. The In and Out libraries also implement data types with instance methods that allow us the more general ability to treat multiple files as input and output streams, and web pages as input streams, so we will revisit them in Section 1.2.

public class In

static    int[]

readInts(String name)

static double[]

readDoubles(String name)

static String[]

readStrings(String name)

public class Out

static void

write(int[] a, String name)

static void

write(double[] a, String name)

static void

write(String[] a, String name)

APIs for our static methods for reading and writing arrays

Standard drawing (basic methods). 

Up to this point, our input/output abstractions have focused exclusively on text strings. Now we introduce an abstraction for producing drawings as output. This library is easy to use and allows us to take advantage of a visual medium to cope with far more information than is possible with just text. As with standard input/output, our standard drawing abstraction is implemented in a library StdDraw that you can access by downloading the file StdDraw.java from the booksite into your working directory. Standard draw is very simple: we imagine an abstract drawing device capable of drawing lines and points on a two-dimensional canvas. The device is capable of responding to the commands to draw basic geometric shapes that our programs issue in the form of calls to static methods in StdDraw, including methods for drawing lines, points, text strings, circles, rectangles, and polygons. Like the methods for standard input and standard output, these methods are nearly self-documenting: StdDraw.line() draws a straight line segment connecting the point (x₀ , y₀) with the point (x₁ , y₁) whose coordinates are given as arguments. StdDraw.point() draws a spot centered on the point (x, y) whose coordinates are given as arguments, and so forth, as illustrated in the diagrams at right. Geometric shapes can be filled (in black, by default). The default scale is the unit square (all coordinates are between 0 and 1). The standard implementation displays the canvas in a window on your computer’s screen, with black lines and points on a white background.

Figure 1.7 StdDraw examples

public class StdDraw

static void

line(double x0, double y0, double x1, double y1)

static void

point(double x, double y)

static void

text(double x, double y, String s)

static void

circle(double x, double y, double r)

static void

filledCircle(double x, double y, double r)

static void

ellipse(double x, double y, double rw, double rh)

static void

filledEllipse(double x, double y, double rw, double rh)

static void

square(double x, double y, double r)

static void

filledSquare(double x, double y, double r)

static void

rectangle(double x, double y, double rw, double rh)

static void

filledRectangle(double x, double y, double rw, double rh)

static void

polygon(double[] x, double[] y)

static void

filledPolygon(double[] x, double[] y)

API for our library of static methods for standard drawing (drawing methods)

Standard drawing (control methods). 

The library also includes methods to change the scale and size of the canvas, the color and width of the lines, the text font, and the timing of drawing (for use in animation). As arguments for setPenColor() you can use one of the predefined colors BLACK, BLUE, CYAN, DARK_GRAY, GRAY, GREEN, LIGHT_GRAY, MAGENTA, ORANGE, PINK, RED, BOOK_RED, WHITE, and YELLOW that are defined as constants in StdDraw (so we refer to one of them with code like StdDraw.RED). The window also includes a menu option to save your drawing to a file, in a format suitable for publishing on the web.

public class StdDraw

static void

setXscale(double x0, double x1)

static void

setYscale(double y0, double y1)

static void

setPenRadius(double r)

static void

setPenColor(Color c)

static void

setFont(Font f)

static void

setCanvasSize(int w, int h)

static void

clear(Color c)

static void

show(int dt)

API for our library of static methods for standard drawing (control methods)

In this book, we use StdDraw for data analysis and for creating visual representations of algorithms in operation. The table at on the opposite page indicates some possiblities; we will consider many more examples in the text and the exercises throughout the book. The library also supports animation—of course, this topic is treated primarily on the booksite.

int N = 100;
>StdDraw.setXscale(0, N);
StdDraw.setYscale(0, N*N);
StdDraw.setPenRadius(.01);
for (int i = 1; i <= N; i++)
{>
   StdDraw.point(i, i);
   StdDraw.point(i, i*i);
   StdDraw.point(i, i*Math.log(i));
}

int N = 50;
double[] a = new double[N];
for (int i = 0; i < N; i++)
   a[i] = StdRandom.random();
for (int i = 0; i < N; i++)
{
   double x = 1.0*i/N;
   double y = a[i]/2.0;
   double rw = 0.5/N;
   double rh = a[i]/2.0;
   StdDraw.filledRectangle(x, y, rw, rh);
}

int N = 50;
double[] a = new double[N];
for (int i = 0; i < N; i++)
   a[i] = StdRandom.random();
Arrays.sort(a);
for (int i = 0; i < N; i++)
{
   double x = 1.0*i/N;
   double y = a[i]/2.0;
   double rw = 0.5/N;
   double rh = a[i]/2.0;
   StdDraw.filledRectangle(x, y, rw, rh);
}

StdDraw plotting examples