# Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

## Section1.15Object-Oriented Programming in Java: Defining Classes

We stated earlier that Java is an object-oriented programming language. So far, we have used a number of built-in classes to show examples of data and control structures. One of the most powerful features in an object-oriented programming language is the ability to allow a programmer (problem solver) to create new classes that model data that is needed to solve the problem.
Remember that we use abstract data types to provide the logical description of what a data object looks like (its state) and what it can do (its methods). By building a class that implements an abstract data type, a programmer can take advantage of the abstraction process and at the same time provide the details necessary to actually use the abstraction in a program. Whenever we want to implement an abstract data type, we will do so with a new class.

### Subsection1.15.1A Fraction Class

A very common example to show the details of implementing a user-defined class is to construct a class to implement the abstract data type Fraction. We have already seen that Java provides a number of numeric classes for our use. There are times, however, that it would be most appropriate to be able to create data objects that look like fractions to the user.
A fraction such as $$\frac{3}{5}$$ consists of two parts. The top value, known as the numerator, can be any integer. The bottom value, called the denominator, can be any integer greater than 0 (negative fractions have a negative numerator). Although it is possible to create a floating point approximation for any fraction, in this case we would like to represent the fraction as an exact value.
The operations for the Fraction type will allow a Fraction data object to behave like any other numeric value. We need to be able to add, subtract, multiply, and divide fractions. We also want to be able to show fractions using the standard “slash” form, for example 3/5. In addition, all fraction methods should return results in their lowest terms so that no matter what computation is performed, we always end up with the most common form.
In Java, we define a new class by providing a name and a set of method definitions. For this example,
class Fraction {
// properties and methods go here
}

provides the framework for us to define the class. We normally start off by specifying the class’s properties. These are declared inside the class, but not inside any method.
class Fraction {
int numerator;
int denominator;
}

If you do not initialize properties, the default values will be 0 for int, 0.0 for double, false for boolean, and null for reference types such as String.
Next, we define a constructor. The constructor defines the way in which objects are created. To create a Fraction object, we will need to provide two pieces of data, the numerator and the denominator. In Java, the constructor method has the same name as the class. Unlike other methods, which have a return value (or void), constructors do not have a return type:
In line 5, you see that we have named the constructor parameters the same as the properties. That is why, on lines 6 and 7, we use the keyword this to qualify the variables on the left hand side of the assignment. You can think of this as meaning “the object currently under consideration”. Thus, this.numerator = numerator; means “assign the numerator parameter to the numerator property of the object currently being constructed”.
To create an instance of the Fraction class, we must invoke the constructor. This happens by using the new operator with the name of the class and passing actual values for the necessary properties. For example,
Fraction myFraction = new Fraction(3, 5);

creates an object called myFraction representing the fraction $$\frac {3}{5}$$ (three-fifths). Figure 1.15.2 shows this object as it is now implemented.

### Subsection1.15.2Printing a Fraction

The next thing we need to do is implement the behavior that the data type requires. To begin, consider what happens when we try to print a Fraction object in this program:
public class FractionTest {
public static void main(String[] args) {
Fraction myFraction = new Fraction(3, 5);
System.out.println(myFraction);
}
}


#### Note1.15.3.

This class starts with the keyword public. The class containing your main method must be declared public.
The Fraction class, on the other hand, is not declared public. This means that the class has default access; other classes and subclasses in the same package (in this case, in the same directory as this file) can access the class.
You can put each class in its own file, or you can put as many classes as you want into a single file. If you choose the latter, only one class can be public, and its name determines the file name.
We get this output:
Fraction@1dbd16a6

The Fraction object, myFraction, does not know how to respond to this request to print. The print function requires that the object convert itself into a string so that the string can be written to the output. The default method gives us the class name and the memory address of the reference. This is not what we want.
There are two ways we can solve this problem. One is to define a method called show that will allow the Fraction object to print itself as a string. Unfortunately, writing a show() method does not work in general. In order to make printing work properly, we need to override Java’s default method for converting a Fraction to a string. We do this by writing a method named toString() that has no parameters and returns a String. This goes into the Fraction class:
This method uses String.format(), which works exactly like System.out.format(), except that the result goes into a String variable rather than out to the screen. We don’t include the %n here; whoever calls toString() will be responsible for outputting a newline (or not).
Once we add this method and recompile, the output gives us 3/5.
It is important to note that the toString method doesn’t have parameters. It doesn’t need any extra information because it builds the string representation by using the object’s internal state data to “fill in the blanks” in the format string.

Let us now turn our attention to adding two fractions. We will write a method called add, which will add the fraction that we are currently working with to another fraction. Two fractions must have the same denominator to be added. The easiest way to make sure they have the same denominator is to use the product of the two denominators as a common denominator so that $$\frac {a}{b} + \frac {c}{d} = \frac {ad}{bd} + \frac {cb}{bd} = \frac{ad+cb}{bd}\text{.}$$ The implementation, which is part of the Fraction class, is shown in Listing 1.15.5.
The addition function returns a new Fraction object with the numerator and denominator of the sum. We can use this method by writing a standard arithmetic expression involving fractions, assigning the result of the addition, and then printing our result.
Let’s add this code to our main() method in FractionTest to test addition:
Fraction f1 = new Fraction(1, 4);
Fraction f2 = new Fraction(1, 2);
System.out.println(f3);

On the third line, the call f1.add(f2) will use f1 as this (the object we are currently working with), and f2 will be the value for the formal parameter other.
The addition method works as we desire, but one thing could be better. Note that $$6/8$$ is the correct result ($$\frac {1}{4} + \frac {1}{2}$$) but that it is not in the “lowest terms” representation. The best representation would be $$3/4\text{.}$$ In order to be sure that our results are always in the lowest terms, we need a helper function that knows how to reduce fractions. This function will need to look for the greatest common divisor, or GCD. We can then divide the numerator and the denominator by the GCD and the result will be reduced to lowest terms.
The best-known algorithm for finding the greatest common divisor is Euclid’s algorithm, which will be discussed in detail in Chapter 8. It states that the greatest common divisor of two integers $$m$$ and $$n$$ is $$n$$ if $$n$$ divides $$m$$ evenly. However, if $$n$$ does not divide $$m$$ evenly, then the answer is the greatest common divisor of $$n$$ and the remainder of $$m$$ divided by $$n\text{.}$$ We will provide an iterative implementation here (see Listing 1.15.6). Note that this implementation of the GCD algorithm works only when the denominator is positive. This is acceptable for our fraction class because we have said that a negative fraction will be represented by a negative numerator.
Now we can use this function to help reduce any fraction. To put a fraction in lowest terms, we will divide the numerator and the denominator by their greatest common divisor. So, for the fraction $$6/8\text{,}$$ the greatest common divisor is 2. Dividing the top and the bottom by 2 creates a new fraction, $$3/4$$ (see Listing 1.15.7).
Our Fraction object now has two very useful methods as depicted in Figure 1.15.8.

### Subsection1.15.4Comparing Fractions

An additional method that we need to include in our example FractionTest class will allow two fractions to compare themselves to one another. Consider this code:
Fraction f4 = new Fraction(3, 5);
Fraction f5 = f4;
Fraction f6 = new Fraction(3, 5);

System.out.println(f4 == f5);
System.out.println(f4 == f6);

The assignment f5 = f4 copies the reference for f4 into f5; we now have two references to the same object in memory. f6, on the other hand, refers to a completely different area of memory, as depicted in Figure 1.15.9. When we do the comparison f4 == f5, the == operator does a shallow equality comparison: it only checks to see that the references are the same, and evaluates as true. The shallow comparison f4 == f6 will evaluate as false because the references are not the same.
We can create deep equality–equality by the same value, not the same reference–by implementing an equals() method (see Figure 1.15.9). This method will compare the contents of the objects (in their state), not merely their references,
In the Fraction class, we can implement the equals method by again putting the two fractions in common terms and then comparing the numerators (see Listing 1.15.10).
If we now evaluate f4.equals(f6) in our FractionTest program, the equals() method will do a deep equality comparison and evalute as true.

### Subsection1.15.5Adding Fractions with a static Method

Perhaps you found the way we added fractions: f1.add(f2) to be a bit strange. As it currently stands, add is an instance method; we need to invoke add on an instance of the Fraction class (in our example, that is f1).
What if you wanted a more “conventional” way of adding fractions, such as this code fragment:
Fraction f7 = new Fraction(1, 2);
Fraction f8 = new Fraction(1, 3);
System.out.println(f9);

We want this new add method to also belong to the Fraction class, but not require an instance to use it. We can do this by making a static method—it belongs to the class as a whole, not to any particular instance:
public static Fraction add(Fraction fracA, Fraction fracB) {
}

To save duplication of code, we will have this new add method invoke the instance add method with fracA as the instance and fracB as the argument.
Now we have two methods with the same name. Java allows this, as long as the number of parameters and type of parameters are different. This is called overloading a method. There’s no conflict here; when Java encounters fracA.add(fracB), it will use the instance method that has one parameter instead of calling the two-argument method that is already in progress.
We can now complete our FractionTest program with one additional change: because our two-argument add method belongs to the class, we must prefix it with the class name:
Fraction f7 = new Fraction(1, 2);
Fraction f8 = new Fraction(1, 3);

The complete Fraction and FractionTest classes, up to this point, are shown in Listing 1.15.11.
To make sure you understand how methods work in Java classes, write some methods to implement subtract(), multiply(), and divide(). Also implement a method named compareTo(), which compares this to some other fraction (thus, the method will have only one parameter). Your method will return -1 if this is less than other, 0 if this is equal to other, and 1 if this is greater than other.