Reference Types

Java has eight primitive types. Only four of these are commonly used: boolean, char, double, and int. The other four are byte, float, long, and short. A variable (or field or argument) of a primitive type holds its value directly. In other words, if we declare

int x;

then Java sets aside a certain amount of memory to hold the bits of this number. When we ask for the value of x, Java simply looks in this location.

All other types, including array types and object types, are reference types. A variable of a reference type holds a reference to an array or object. If we declare

int[] numbers;

then Java can't set aside enough memory to hold the array, because we haven't specified how big the array is. Instead, Java sets aside enough memory to hold the reference, which is the address of another location in memory. Later, when we actually create the array, this reference is altered to point to the array's location. This ability of the variable numbers to refer sometimes to an array of 10 ints and sometimes to an array of 100 ints is an example of polymorphism.

Similarly, if we declare

Beetle bug;

then Java sets aside enough memory for a reference. When we initialize the variable with

bug = new Beetle();

the reference is set to point to this new instance.

The assiduous reader may think, "Okay, I see the need for references when using arrays, but why is it necessary with objects? Don't all Beetles take up exactly the same amount of memory?"

Surprisingly, the answer is, "not necessarily"more on that later. In the meantime, consider what happens when we pass an object as an argument to a method. We did this in the takeTurn() method of the BeetleGame class (Figure 1-28). If we didn't use a reference, we would have to copy all of the fields of the Beetle in question into the area of memory set aside for the argument bug. Not only would this waste time, but any methods invoked on bug would affect the copy instead of the original!

Most of the time, the distinction between "the variable v contains something" and "the variable v contains a reference to something" is unimportant. There are, however, a few things to watch out for.

Null

As mentioned in Chapter 1, the default value of a field with a reference type is null. Null is a reference to nothing in particular. We must be careful never to follow a null reference. For example, we cannot invoke a method on null. If we try to do so, our program will crash with an error message like this:

Exception in thread "main" java.lang.NullPointerException

(Pointer is just another word for reference, as is link.) This message is often a sign that we have forgotten to initialize one of our fields.

References and Equality

Suppose we have rolled two dice and want to determine if we rolled doubles. In other words, we want to know if the dice are equal. What does it mean for two Die instances to be equal? The answer is not as simple as it appears.

Suppose we evaluate the code in Figure 2-1. The resulting situation is shown in Figure 2-2.

Figure 2-1. Code producing the situation in Figure 2-2.

1 Die die1 = new Die();
2 Die die2 = die1;
3 Die die3 = new Die();

Figure 2-2. UML instance diagram of the situation after executing the code in Figure 2-1.

The variables die1 and die2 are equal in a strong sense: they are references to the same object. The variables die2 and die3 are equal in a weaker sense: they are references to two different objects which happen to be identical.

The == operator checks for equality in the strong sense. Thus,

die1 == die2

is true, but

die2 == die3

is false.

If we want to check whether two objects are identical, we have to check the fields. In this example,

die2.getTopFace() == die3.getTopFace()

is true.

This is all well and good for the Die class, but what about a more complicated class like Beetle? We would have to compare six different fields every time we wanted to see if two Beetles were identical. This sort of work should be done in a method of the Beetle class.

The method to do this checking is always called equals(). In our example,

die2.equals(die3)

is true. We will write the equals() method for the Die class in a moment.

The Polymorphic Type Object

The equals() method takes one argument. For reasons that will be explained in Chapter 3, the type of this argument must always be Object. A variable of type Object can hold a reference to an instance of any class or even to an array. For example, it is perfectly legal to say:

Object it;
it = new Beetle();
it = new double[10];
it = new Die();

Because a variable of type Object can hold a reference to any of a wide variety of things, Object is called a polymorphic type. A polymorphic type must be a reference type, because it is not clear when the variable is declared how much memory will be needed to hold the value to which it will refer.

It is important to distinguish between the type of a variable and the actual class of the instance to which it refers. These might be the same, but with a polymorphic type they might not. Java can't tell, at compile time, what methods are available for it. If we want to invoke a method on it, we generally have to cast the value to a specific class:

((Die)it).roll();

There are a few things we can do with an Object without casting. These are explained in Chapter 3.

Returning to equals(), a first shot at writing the method for the Die class is shown in Figure 2-3.

Figure 2-3. This version of equals() is not good enough.

1 /** Return true if that Die has the same top face as this one. */
2 public boolean equals(Object that) {
3 return topFace == ((Die)that).topFace;
4 }

This seems reasonable enough, but there are some problems.

  • If this == that, we should return true immediately. If there are a lot of fields, this can save considerable time.
  • If that is null, we should return false immediately rather than trying to follow the null reference.
  • The argument that might not be an instance of the same class as this. In this case, we should return false immediately.

A more robust version of the method is given in Figure 2-4. This makes use of the method getClass(), which can be invoked on any Object. It returns a representation of Object's class. Two instances of the same class return the same representation, so

a.getClass() == b.getClass()

exactly when a and b are instances of the same class.

Figure 2-4. A much better version of equals(). Only the parts in bold (and the comment) need to change from one class to another.

 1 /** Return true if that Die has the same top face as this one. */
 2 public boolean equals(Object that) {
 3 if (this == that) {
 4 return true;
 5 }
 6 if (that == null) {
 7 return false;
 8 }
 9 if (getClass() != that.getClass()) {
10 return false;
11 }
12 Die thatDie = (Die)that;
13 return topFace == thatDie.topFace;
14 }

For other classes, the equals() method looks almost identical. Figure 2-5 shows the method for the Beetle class.

Primitives and Wrappers

A variable of type Object can hold any object or array, but it can't hold a value of a primitive type. This appears to present a problem: what if we've created a general-purpose data structure to hold Objects, and we want to put integers in it?

To deal with this situation, Java provides a wrapper class for each of the primitive types. The wrapper classes are Boolean, Byte, Character, Double, Float, Integer, Long, and Short. The upper-case letter at the beginning of each class name helps distinguish it from the corresponding primitive type.

If we want to store a primitive value in a variable of type Object, we can first wrap it in a new instance of the appropriate class:

Object number = new Integer(23);

Each wrapper class has a method to extract the original primitive value. For example, the method in the Integer class is intValue(). Of course, for a variable of type Object, we must first cast the reference to an Integer before we can use this method.

Figure 2-5. The equals() method for the Beetle class.

 1 /** Return true if that Beetle has the same parts as this one. */
 2 public boolean equals(Object that) {
 3 if (this == that) {
 4 return true;
 5 }
 6 if (that == null) {
 7 return false;
 8 }
 9 if (getClass() != that.getClass()) {
10 return false;
11 }
12 Beetle thatBeetle = (Beetle)that;
13 return body == thatBeetle.body
14 && eyes == thatBeetle.eyes
15 && feelers == thatBeetle.feelers
16 && head == thatBeetle.head
17 && legs == thatBeetle.legs
18 && tail == thatBeetle.tail;
19 }
int n = ((Integer)number).intValue();

Before Java 1.5, code was often cluttered with wrapping and unwrapping, also called boxing and unboxing. Java is now smart enough to do this automatically, so we can do things like:

Object number = 5;
int n = (Integer)number;

If the type of number were Integer, we wouldn't even need the cast:

Integer number = 5;
int n = number;

This makes our code much clearer, but we should still be aware that boxing and unboxing takes time. A wrapped Integer also uses considerably more memory than a primitive int. The tradeoff here is between generality (writing code once to handle all sorts of Objects) and efficiency (using the primitive types to save time and memory).

In Chapter 4, we will discuss Java's new generic type feature, which provides an even more powerful way to write general-purpose code without casting all over the place.

Strings

We usually want to use equals() instead of == to compare objects. This is especially true for Strings, because Java sometimes reuses Strings.

Suppose we execute this code:

String s1 = "weinerdog";
String s2 = "weinerdog";

Java creates a single instance of the String class, with s1 and s2 containing references to the same instance, so s1 == s2. This saves some space. There is no danger that invoking a method on s1 will alter s2, because Java Strings are immutabletheir fields cannot change. (There is another class, called StringBuilder, for mutable Strings. We'll discuss that in Chapter 13.)

Unfortunately, Java cannot always tell if two Strings are identical. Specifically, if we execute the code

String s3 = "weiner";
s3 += "dog";

then s3 refers to an instance which happens to be identical to s1 and s2. Thus, while s1.equals(s3), it is not true that s1 == s3.

Because the behavior of == is difficult to predict when Strings are involved, we should always use equals() to compare Strings.

Exercises

2.1

Is int a polymorphic type? Explain.

2.2

How could we convert the String "25" into the primitive int 25? (Hint: Look up the Integer class in the API.)

2.3

Is it ever necessary to assert that this != null? Explain.

2.4

Suppose we have two Die variables d1 and d2. Can the method invocation d1.roll() affect the state of d2 if d1 == d2? What if d1 != d2?

2.5

If two objects are equal in the sense of ==, are they automatically equal in the sense of equals()? What about vice versa?

2.6

Suppose we have two references, foo and bar. After evaluating the statement

foo = bar;
 

is it definitely true, possibly true, or definitely false that foo == bar? What about foo.equals(bar)?

2.7

Through experimentation, determine whether equals() can be used to compare arrays.

2.8

The robust equals() method in Figure 2-5 will produce the same output if lines 35 are omitted. What is the point of these lines?

2.9

Write an equals() method for the complex number class you wrote in Problem 1.20.


Arrays

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index





Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net