1.2 Java as an Algorithm Language its prototype).A static method is not"attached"to any particular object.Static methods behave like the usual functions and procedures of programming languages like C,Pascal. and so on.However,their names must he prefixed by the class in which they are defined, as in"List.first(x)"to apply method first defined in class List to parameter x. In Java,instance fields of an object are private by default,which means that they can be accessed only by methods (functions and procedures)that are defined within the class This is consistent with the theme of abstract data type (ADT)design that objects should be accessed only through the operations defined for the ADT.The code that implements these ADT operations (or static methods,or functions and procedures)exists within the class and is aware of the private instance fields and their types.Methods are also private by default.but usually are specified as "public,"so that methods defined in other classes may call them.However."low-level"methods that should be called only by other methods in the same class may also be private. The client.s of the ADT (procedures and functions that call the ADT)are implemented outside the class in which the ADT "lives,"so they have access only to the public parts of the ADT class.The maintenance of private data is called encapsulation,or information hiding. Instance fields of an obiect retain the values that are assigned to them for the lifetime of the object,or until overwritten by a subsequent assignment.Here we can see the advantage of having them private to the class in which they are defined.A public instance field could be assigned an arbitrary value by any part of the overall program.A private instance field can be assigned a value only by going through a method for the ADT class that is designed for the purpose.This method can perform other computations and tests to be sure that the value assigned to an instance field is consistent with the ADT specifications,and is consistent with values stored in other instance fields of the same object. A new object is created by the phrase"new className0,"for example: Date dueDate new Date(; This statement causes Java to invoke a default constructor for the Date class.A constructor reserves storage for a new object (or instance)of the class and returns a reference (probably an address)for accessing this object.The instance fields of this new ohject might not be initialized. Java sidelight:The programmer may write additional constructor functions for a class, the bodies of which may initialize various instance fields and perform other computations. In the interest of language-independence,this text does not use such constructors,so details are omitted. Arrays are declared somewhat differently in Java than in C and C++,and their prop- erties are also slightly different.The Java syntax to declare an array of integers (more precisely,to declare a variable whose type is"array of integers")is "int]x,"whereas C might use"int x."This statement does not initialize x;that is accomplished with x new int(howMany];
8 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples where howMany is either a constant or a variable whose value denotes the desired length of the array.Declarations of arrays for classes are similar.The declaration and initialization may be,and usually should be,combined into one statement: int[]x new int[howMany]; Date[]dates new Date[howMany] While these statements initialize x and dates in the sense of reserving storage for the arrays, they only initialize the elemenis to default values,which are unlikely to be useful.Therefore individual clements dates(o],dates[1],...must be assigned values (possibly using the new operator)before they are used.The syntax,outside the Date class,is dates[o]new Date(); datesio].month =1; dates[o].day =1; dates[0].year new Date.Year(); dates[0].year.number 2000: dates(o].year.isLeap true; Notice that field names come after the index that selects a specific array element.Also notice that the inner class name,Year,is qualified by the outer class name,Date,in the second new statement,because the statement is outside the Date class.As mentioned,Java programmers can write constructors that take parameters to accomplish such initialization of newly constructed objects,but this text does not use such constructors in the interest of language independence. Once array x is initialized with a new statement,as shown a few paragraphs above,the length of the array it references cannot changc.Java provides a way to query this length. which is x.length.That is,the instance field length is automatically "attached"to the array object as part of the new operation,and can be accessed through x,as shown,as long as x refers to this object. The valid indexes (or subscripts)for elements of this array are 0 through(x.length- 1).Java will stop the program (technically,throw an exception)if the program attempts to access an element with an index outside this range.We will often wish to use indexes in the range I through n,and therefore will initialize arrays with"new intIn+1]"in these cases. Java permits overloading and overriding of methods.A method is said to be over- loaded if it has multiple definitions with varying parameter types,but the same return type. Many arithmetic operators are overloaded.Overriding means there are multiple definitions of a single method in the class hicrarchy with the same parameter typcs.and Java applics the "closest"definition.(Again,for compatibility with other languages and because this capability is not central for understanding the algorithms,we avoid these features and refer interested readers to books on the Java language.)The same names for methods may be used in different classes,but this is not really overloading because the class name (or ob- ject name)appears as a qualifier when the names are used outside the class in which they are defined.Later examples will make this clear. For readers acquainted with C++,it is worth pointing out that Java does not permit the programmer to define new meanings for operators.This text uses such operators for
1.2 Java as an Algorithm Language readability in pseudocode (e.g.,x y,where x and y are in some nonnumeric class,such as String).However,if you define a class and you develop an actual Java program with it,you must write named functions (e.g.,less()and call them to compare objects in your class. 1.2.2 Organizer Classes We coin the term organizer class,which is not a standard Java term,to describe a very sim- ple class that merely groups several instance fields.This construct fulfills a role somewhat analogous to the C struct and the Pascal or Modula record;analogous constructs exist in Lisp,ML and most other programming languages.Organizer classes are diametrically op- posite from abstract data types in their purpose;they merely organize some storage,but do not limit access to it and do not provide any customized operations on it.It is often conve- nient to define an organizer class within some other class;in this case,the organizer class is called an inner class in Java terminology. An organizer class has just one method,called copy.Since variables are references to objects in Java,the assignment statement copies only the reference,not the fields of the object,as was illustrated in Examplc 1.I with dueDate and noticeDate.If these variables are declared in an organizer class named Date,then we could use the statements noticeDate Date.copy(dueDate); noticeDate.day dueDate.day-7; to copy the fields of dueDate into a new object referenced by noticeDate,then modify the day field of noticeDate only. Definition 1.1 The copy function for organizer classes The general rule for how the copy function(or method)in an organizer class should assign values to the instance fields of the new object (illustrated by assuming object d is being copied into a new object d2)is as follows: 1.If the instance field (say year)is in another organizer class,then the copy method for that class is invoked,as in d2.year Year.copy(d.year). 2.If the instance field (say day)is not in an organizer class,a simple assignment is used, as in d2.day d.day. The complete example is given in Figure 1.2. The programmer must ensure that cycles do not occur in the definitions of organizer classes,or else copy might not terminate.Of course,a new object in an organizer class can also be created in the usual way: Date someDate new Date(; Java sidelight:Java provides a facility for making a one-level copy of an object without having to write out each assignment statement,based on the clone method,but this will not handle nested structures such as Date automatically;you will still need to write some code for these cases.Appendix A gives the code for a"generic"copyl level function
10 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples class Date { public Year year; public int month; public int day; public static class Year public int number; public boolean isLeap; public static Year copy(Year y) Year y2 new Year(); y2.number y.number; y2.isLeap y.isLeap; return y2; } public static Date copy(Date d) Date d2 new Date(); d2.year Year.copy(d.year):/organizer class d2.month d.month; d2.day =d.day: return d2; public static int defaultCentury; Figure 1.2 An organizer class Date with an inner organizer class Year An organizer class contains only public instance fields.If the static keyword also appears in the field declaration,the field is not associated with any particular object,but is essentially a global variable. Example 1.2 Typical organizer classes In Figure 1.2 the classes of Example 1.1 are embellished with copy functions,so they will qualify as organizer classes.As we see,the definition of copy is mechanical,though tedious.Its details will be omitted from future examples.For completeness,we included defaultCentury as an example of a"global variable,"although most organizer classes will not contain globai variables
1.3 Mathematical Background 11 To summarize,we invented the term organizer class to denote a class that simply groups together some instance fields and defines a function to make copies of them. 1.2.3 Java-Based Pseudocode Conventions Most algorithms in this book use Java-based pseudocode,rather than strict Java,for easier readability.The following conventions are used (except in the Java-specific Appendix A). 1.Block delimiters ("and"")are omitted.Block boundaries are indicated by indenta- tion. 2.The keyword static is omitted from method (function and procedure)declarations. All methods declared in the text are static.(Nonstatic built-in Java methods appear occasionally;in particular,s.length()is used to obtain the length of strings.)The keyword static does appear where needed for instance fields and inner classes. 3.Class name qualifiers are omitted from method (function and procedure)calls.For example,x=cons(z,x)might be written when the Java syntax requires x IntList. cons(z,x).(The IntList class is described in Section 2.3.2.)Class name qualifiers are reguired in Java whenever static methods are called from outside the class in which they are defined. 4.Keywords to control visibility,public,private,and protected,are omitted.Placing all files related to one Java program in the same directory eliminates the need to deal with visibility issues. 5.Mathematical relational operators“≠，”“"≤，”and“≥"are usually written,instead of their keyboard versions.Relational operators are used on types where the meaning is clear,such as String,even though this would be invalid syntax in Java. 6.Keywords,which are either reserved words or standard parts of Java,are set in this font:int,String.Comments are set in this font.Code statements and program variable names are set in this font.However,pseudocode statements are set in the regular font of the text,like this sentence. Oceasional departures from this scheme occur when we are making a specific point about the Java language. 1.3 Mathematical Background We use a variety of mathematical concepts,tools,and techniques in this book.Most should already be familiar to you,although a few might be new.This section collects them to provide a ready reference,as well as a brief review.Proof concepts are covered in greater depth in Chapter 3. 1.3.1 Sets,Tuples,and Relations This section provides informal definitions and a few elementary properties of sets and related concepts.A set is a collection of distinct elements that we wish to treat as a single object.Usually the elements are of the same "type"and have some additional common