Java Reference

In-Depth Information

Swap
s[0]
and
s[s.length() - 1];

Swap
s[1]
and
s[s.length() - 2];

Swap
s[2]
and
s[s.length() - 3];

…

The invariant must state what has and what has not been swapped into its

final position thus far. Based on the above sequence of statements, we see that

there is a prefix and a suffix of
s
that contain their final values, while the middle

remains to be reversed. We use two variables
k
and
n
to define the boundaries of

these three segments of
t
and write the invariant as:

inv:
s[0..k-1]
and
s[n+1..]
contain their final values, and

s[k..n]
remains to be reversed

How does it start?
By setting
k
to
0
and
n
to
b.length() - 1
, so that the prefix

and suffix that contain their final values are empty.

When does it stop?
The loop can stop when the middle segment contains at

most one character, because then the middle segment is its own reverse. On the

other hand, when the middle segment contains more than one element, that is,

when
k<n
, more elements need to be reversed.

How does it make progress?
By incrementing
k
or decrementing n (or both).

How does it fix the invariant?
The elements
s[k]
and
s[n]
need to be

swapped. Then
k
can be incremented and
n
decremented.

This completes the development of the program segment —see Fig. 7.5.

Remarks

Using
k!=n
as the loop condition is incorrect because it is not guaranteed

//
Set
t
to the reverse of
t

StringBuffer s=
new
StringBuffer(t);

int
k= 0;

int
n= s.length() - 1;

// {
invariant:
s[0..k-1]
and
s[n+1..]
contain their final values, and

// s[k..n]
remains to be reversed
}

while
(k < n) {

char
c= s.getChar(k);

s.setChar(k, s.getChar(n));

s.setChar(n, c);

k= k + 1;

n= n - 1;

}

t= s.toString();

Figure 7.5:

Reversing a
String

Search WWH ::

Custom Search