1.2   Data Abstraction


Object-oriented programming.

Programming in Java is largely based on building data types. This style of programming is known as object-oriented programming, as it revolves around the concept of an object, an entity that holds a data type value. With Java's primitive types we are largely confined to programs that operate on numbers, but with reference types we can write programs that operate on strings, pictures, sounds, or any of hundreds of other abstractions that are available in Java's standard libraries or on our booksite. Even more significant than libraries of predefined data types is that the range of data types available in Java programming is open-ended, because you can define your own data types.

Using abstract data types.

A client does not need to know how a data type is implemented in order to be able to use it.

Examples of abstract data types.

Implementing abstract data types.

We implement ADTs with a Java class, putting the code in a file with the same name as the class, followed by the .java extension. The first statements in the file declare instance variables that define the data-type values. Following the instance variables are the constructor and the instance methods that implement operations on data-type values.

Designing abstract data types.

We put important information related to designing data types in one place for reference and to set the stage for implementations throughout this book.

Q + A.

Q. Are there any truly immutable classes in Java?

A. If you use reflection, you can access the private fields of any class and change them. Program MutableString.java demonstrates how to mutate a String. Program MutableInteger.java demonstrates that this is true even if the instance variable is final.

Exercises

  1. Write a Point2D.java client that takes an integer value N from the command line, generates N random points in the unit square, and computes the distance separating the closest pair of points.

  2. What does the following code fragment print?
    String string1 = "hello";
    String string2 = string1;
    string1 = "world";
    StdOut.println(string1);
    StdOut.println(string2);
    

    Solution:

    world
    hello
    

  3. A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular shifts of one another.

    Solution: (s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)

  4. What does the following recursive function return?
    public static String mystery(String s) {
        int N = s.length();
        if (N <= 1) return s;
        String a = s.substring(0, N/2);
        String b = s.substring(N/2, N);
        return mystery(b) + mystery(a);
    }
    

    Solution: Reverse of the string.

  5. Using our implementation of Date.java as a model, develop an implementation of Transaction.java.

  6. Using our implementation of equals() in Date.java as a model, develop an implementation of equals() for Transaction.java.

Creative Problems

  1. Rational numbers. Implement an immutable data type Rational.java for rational numbers that supports addition, subtraction, multiplication, and division.

    api for rational numbers
    You do not have to worry about testing for overflow, but use as instance variables two long values that represent the numerator and denominator to limit the possibility of overflow. Use Euclid's algorithm to ensure that the numerator and denominator never have any common factors. Include a test client that exercises all of your methods.

  2. Sample variance for accumulator. Validate that the following code, which adds the methods var() and stddev() to Accumulator.java to compute the mean, sample variance, and sample standard deviation of the numbers presented as arguments to addDataValue().

    Reference: Here is a good explanation of this one-pass method, that was first discovered by Welford in 1962. This approach can be applied to computing the skewness, kurtosis, regression coefficients, and Pearson's correlation coefficient.

  3. Parsing. Develop the parse constructors for your Date.java and Transaction.java implementations that take a single String argument to specify the initialization values, using the formats given in the table below.

    parsing for Date and Transaction