From the book
From the book
From the book
STATIC METHODS
Every Java program in this book is either a data-type definition (which we describe in detail in Section 1.2) or a library of static methods (which we describe here). Static methods are called functions in many programming languages, since they can behave like mathematical functions, as described next. Each static method is a sequence of statements that are executed, one after the other, when the static method is called, in the manner described below. The modifier static distinguishes these methods from instance methods, which we discuss in Section 1.2. We use the word method without a modifier when describing characteristics shared by both kinds of methods.
Defining a static method.
A method encapsulates a computation that is defined as a sequence of statements. A method takes arguments (values of given data types) and computes a return value of some data type that depends upon the arguments (such as a value defined by a mathematical function) or causes a side effect that depends on the arguments (such as printing a value). The static method rank() in BinarySearch is an example of the first; main() is an example of the second. Each static method is composed of a signature (the keywords public static followed by a return type, the method name, and a sequence of arguments, each with a declared type) and a body (a statement block: a sequence of statements, enclosed in curly braces). Examples of static methods are shown in the table on the facing page.
)
Figure 1.3 Anatomy of a static method
Invoking a static method.
A call on a static method is its name followed by expressions that specify argument values in parentheses, separated by commas. When the method call is part of an expression, the method computes a value and that value is used in place of the call in the expression. For example the call on rank() in BinarySearch() returns an int value. A method call followed by a semicolon is a statement that generally causes side effects. For example, the call Arrays.sort() in main() in BinarySearch is a call on the system method Arrays.sort() that has the side effect of putting the entries in the array in sorted order. When a method is called, its argument variables are initialized with the values of the corresponding expressions in the call. A return statement terminates a static method, returning control to the caller. If the static method is to compute a value, that value must be specified in a return statement (if such a static method can reach the end of its sequence of statements without a return, the compiler will report the error).
|
task |
implementation |
|
absolute value of an int value |
public static int abs(int x) |
|
absolute value of a double value |
public static double abs(double x) |
|
primality test |
public static boolean isPrime(int N) |
|
square root |
public static double sqrt(double c) |
|
hypotenuse of |
public static double hypotenuse(double a, double b) |
|
Harmonic number (see page 185) |
public static double H(int N) |
Typical implementations of static methods
Properties of methods.
A complete detailed description of the properties of methods is beyond our scope, but the following points are worth noting:
- Arguments are passed by value. You can use argument variables anywhere in the code in the body of the method in the same way you use local variables. The only difference between an argument variable and a local variable is that the argument variable is initialized with the argument value provided by the calling code. The method works with the value of its arguments, not the arguments themselves. One consequence of this approach is that changing the value of an argument variable within a static method has no effect on the calling code. Generally, we do not change argument variables in the code in this book. The pass-by-value convention implies that array arguments are aliased (see page 19)—the method uses the argument variable to refer to the caller’s array and can change the contents of the array (though it cannot change the array itself). For example, Arrays.sort() certainly changes the contents of the array passed as argument: it puts the entries in order.
- Method names can be overloaded. For example, the Java Math library uses this approach to provide implementations of Math.abs(), Math.min(), and Math.max() for all primitive numeric types. Another common use of overloading is to define two different versions of a function, one that takes an argument and another that uses a default value of that argument.
- A method has a single return value but may have multiple return statements. A Java method can provide only one return value, of the type declared in the method signature. Control goes back to the calling program as soon as the first return statement in a static method is reached. You can put return statements wherever you need them. Even though there may be multiple return statements, any static method returns a single value each time it is invoked: the value following the first return statement encountered.
- A method can have side effects. A method may use the keyword void as its return type, to indicate that it has no return value. An explicit return is not necessary in a void static method: control returns to the caller after the last statement. A void static method is said to produce side effects (consume input, produce output, change entries in an array, or otherwise change the state of the system). For example, the main() static method in our programs has a void return type because its purpose is to produce output. Technically, void methods do not implement mathematical functions (and neither does Math.random(), which takes no arguments but does produce a return value).
The instance methods that are the subject of Section 2.1 share these properties, though profound differences surround the issue of side effects.
Recursion.
A method can call itself (if you are not comfortable with this idea, known as recursion, you are encouraged to work Exercises 1.1.16 through 1.1.22). For example, the code at the bottom of this page gives an alternate implementation of the rank() method in BinarySearch. We often use recursive implementations of methods because they can lead to compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion. For example, the comment in the implementation below provides a succinct description of what the code is supposed to do. We can use this comment to convince ourselves that it operates correctly, by mathematical induction. We will expand on this topic and provide such a proof for binary search in Section 3.1. There are three important rules of thumb in developing recursive programs:
- The recursion has a base case—we always include a conditional statement as the first statement in the program that has a return.
- Recursive calls must address subproblems that are smaller in some sense, so that recursive calls converge to the base case. In the code below, the difference between the values of the fourth and the third arguments always decreases.
- Recursive calls should not address subproblems that overlap. In the code below, the portions of the array referenced by the two subproblems are disjoint.
Violating any of these guidelines is likely to lead to incorrect results or a spectacularly inefficient program (see Exercises 1.1.19 and 1.1.27). Adhering to them is likely to lead to a clear and correct program whose performance is easy to understand. Another reason to use recursive methods is that they lead to mathematical models that we can use to understand performance. We address this issue for binary search in Section 3.2 and in several other instances throughout the book.
public static int rank(int key, int[] a)
{ return rank(key, a, 0, a.length - 1); }
public static int rank(int key, int[] a, int lo, int hi)
{ // Index of key in a[], if present, is not smaller than lo
// and not larger than hi.
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}
Recursive implementation of binary search
Basic programming model.
A library of static methods is a set of static methods that are defined in a Java class, by creating a file with the keywords public class followed by the class name, followed by the static methods, enclosed in braces, kept in a file with the same name as the class and a .java extension. A basic model for Java programming is to develop a program that addresses a specific computational task by creating a library of static methods, one of which is named main(). Typing java followed by a class name followed by a sequence of strings leads to a call on main() in that class, with an array containing those strings as argument. After the last statement in main() executes, the program terminates. In this book, when we talk of a Java program for accomplishing a task, we are talking about code developed along these lines (possibly also including a data-type definition, as described in Section 1.2). For example, BinarySearch is a Java program composed of two static methods, rank() and main(), that accomplishes the task of printing numbers on an input stream that are not found in a whitelist file given as command-line argument.
Modular programming.
Of critical importance in this model is that libraries of static methods enable modular programming where we build libraries of static methods (modules) and a static method in one library can call static methods defined in other libraries. This approach has many important advantages. It allows us to
- Work with modules of reasonable size, even in program involving a large amount of code
- Share and reuse code without having to reimplement it
- Easily substitute improved implementations
- Develop appropriate abstract models for addressing programming problems
- Localize debugging (see the paragraph below on unit testing)
For example, BinarySearch makes use of three other independently developed libraries, our StdIn and In library and Java’s Arrays library. Each of these libraries, in turn, makes use of several other libraries.
Unit testing.
A best practice in Java programming is to include a main() in every library of static methods that tests the methods in the library (some other programming languages disallow multiple main() methods and thus do not support this approach). Proper unit testing can be a significant programming challenge in itself. At a minimum, every module should contain a main() method that exercises the code in the module and provides some assurance that it works. As a module matures, we often refine the main() method to be a development client that helps us do more detailed tests as we develop the code, or a test client that tests all the code extensively. As a client becomes more complicated, we might put it in an independent module. In this book, we use main() to help illustrate the purpose of each module and leave test clients for exercises.
External libraries.
We use static methods from four different kinds of libraries, each requiring (slightly) differing procedures for code reuse. Most of these are libraries of static methods, but a few are data-type definitions that also include some static methods.
- The standard system libraries java.lang.*. These include Math, which contains methods for commonly used mathematical functions; Integer and Double, which we use for converting between strings of characters and int and double values; String and StringBuilder, which we discuss in detail later in this section and in Chapter 5; and dozens of other libraries that we do not use.
- Imported system libraries such as java.util.Arrays. There are thousands of such libraries in a standard Java release, but we make scant use of them in this book. An import statement at the beginning of the program is needed to use such libraries (and signal that we are doing so).
- Other libraries in this book. For example, another program can use rank() in BinarySearch. To use such a program, download the source from the booksite into your working directory.
- The standard libraries Std* that we have developed for use in this book (and our introductory book An Introduction to Programming in Java: An Interdisciplinary Approach). These libraries are summarized in the following several pages. Source code and instructions for downloading them are available on the booksite.
|
standard system libraries |
Math |
Integer† |
Double† |
String† |
StringBuilder |
System |
|
imported system libraries |
java.util.Arrays |
|
our standard libraries |
StdIn |
StdOut |
StdDraw |
StdRandom |
StdStats |
In† |
Out† |
† data type definitions that include some static methods
Libraries with static methods used in this book
To invoke a method from another library (one in the same directory or a specified directory, a standard system library, or a system library that is named in an import statement before the class definition), we prepend the library name to the method name for each call. For example, the main() method in BinarySearch calls the sort() method in the system library java.util.Arrays, the readInts() method in our library In, and the println() method in our library StdOut.
Libraries of methods implemented by ourselves and by others in a modular programming environment can vastly expand the scope of our programming model. Beyond all of the libraries available in a standard Java release, thousands more are available on the web for applications of all sorts. To limit the scope of our programming model to a manageable size so that we can concentrate on algorithms, we use just the libraries listed in the table at right on this page, with a subset of their methods listed in APIs, as described next.