CS115 lecture notes, Spring 1999
Week 8, Wednesday

Homework solutions
------------------

Here are versions of first, last, and middle.
Notice that the comments indicate the conditions
that are necessary for the method to work properly.

These conditions are called preconditions, and they
are an excellent thing to make comments about.

  // middle returns a substring that includes all but the
  // first and last; only works if s has at least two characters
  public static String middle (String s) {
    int length = s.length();
    return s.substring (1, length-1);
  }

  // first returns the first character of a string
  // first only works if s has at least one characters
  public static char first (String s) {
    return s.charAt (0);
  }

  // last returns the last character of a string
  // last only works if s has at least one characters
  public static char last (String s) {
    int len = s.length();
    return s.charAt (len - 1);
  }

Here is the recursive version of isPalindrome.

By checking the length of the string before we invoke
first, last, or middle, we can guarantee that the
preconditions are satisfied, and that there cannot
be an error.

  public static boolean isPalindrome (String s) {
    int len = s.length();
    if (len == 0 || len == 1) {
      return true;
    }

    // at this point we know that len>=2, so it is safe
    // to invoke first, last, and middle

    if (first(s) != last(s)) {
      return false;
    } else {
      boolean recurse = isPalindrome (middle (s));
      return recurse;
    }
  }

This sort of checking is so common and useful that it
deserves a name.  Let's call it the Guardian Pattern.
The first condition guards the subsequent operations,
making them safe.

Here is the iterative version of ItPalindrome.  Notice
how different it is.  There is not usually an easy way to
translate one into the other.  Really you just have to
redesign the program from scratch.

  public static boolean isItPalindrome (String s) {
    int len = s.length();

    int i = 0;
    int j = len-1;

    while (i < j) {
      if (s.charAt(i) != s.charAt(j)) {
	return false;
      }
      i++;
      j++;
    }
    return true;
  }
}

Notice the use of the ++ operator.  See Section 7.8

This kind of loop is also fairly common.  We could
call it the Double Index pattern.

It is possible to "prove" that this method will never
cause a StringIndexOutOfBoundException?


Wrap-up of Strings
------------------

Read Sections 7.11 and 7.12

Strings are immutable.  Even things like toUpperCase do
not modify Strings.

You cannot use == to compare strings.

You have to use equals.  The syntax is horrible.

    if (name1.equals (name2)) {

    }


Interesting objects
-------------------

Although Strings are objects, they are atypical objects.

Now we're going to talk about interesting objects.

An object is a collection of storage locations that contain
related information.

Each storage location has a name, a type and a value, just
like a variable.

For example, a Point is an object that contains two storage
locations, both have type int.  They are named x and y.

Point is an object type in Java.

That means that you can create a variable with type Point.

     Point blank;

The problem is that creating a Point variable does not
create a Point object.  In order to create a Point
object, you have to use the new command:

    blank = new Point (3, 4);

Draw the diagram of these two statements.

Strictly speaking, the value of blank is a REFERENCE to
the object that contains the values 3 and 4.

The object that blank refers two contains two storage
locations.

The object that blank refers two is called an instance.

The storage locations inside the object are called instance
variables.

Every Point object is an instance of the Point class.

Every Point variable should refer to a Point object.

Instance variables
------------------

You can access the instance variables of an object using
dot notation.

    int x = blank.x;

This would set x to 3.

You can modify the instance variables of an object.

    blank.x = blank.x + 3;