16 May 2000
|
Previous
Article |
|
Next Article |
INTO JAVA, PART 5
Up to this point we have rushed through
quite a few basic topics on both Java and Object Oriented Programming (OOP). That
is, we may now build ourselves apps with a GUI, or at least with a frame since we
do not know how to interact with the stuff within the frame yet. And that will wait
for a while because I would like to pace down and discuss some commonly used classes
and some programming techniques.
Today we will continue with the MyFirstFrame
from the previous column. Hence, please make yourself a new folder and copy MyFirstFrame.java
into this folder. We will make it Find / Replace enabled, but only through the terminal
window. This will guide us through the commonly used String and StringBuffer classes,
point us to some pitfalls and introduce us to another programming concept, using
recursion.
|
Recursion vs. Iteration
The easiest way to grasp programming
is to think of some task being done one step after another. You may for example-
open a new text file
-
read one line from the file
-
add the line to a text area
-
repeat from No 2 as long as there is
more lines
-
close the file
-
do some finishing tasks
It is not always that simple to write
a computer program, many times we must break the task apart into simpler problems,
but still similar to the first task. Think of a long text line and you would like
to find a set word, e.g. "Java". You may let the method indexOf() (in
the String class) do the workload, it will let you know both if the word exist in
a certain line and where the first occurrence is. But note, it will only tell you
the first occurrence.
Then the iteration above is no good,
since if you ask for an occurrence and is given one, how do you ask for the next
one on the same line in an easy way? If there is another one? It can be solved of
course, but not elegantly.
Recursion is the answer! That is,
the method will call itself repeatedly if necessary, down to a point that is called
"the trivial case". What is the trivial case? That may differ,
but in the "find the word" case it simply is the answer "No",
there is no more occurrence of "Java". Other times it is more tricky,
but there is always a trivial case, else the recursion (the re-call to itself)
will never end.
So, in our case, if we found an occurrence
of "Java" we simply call the method again with the rest of the text line.
And if there still is another occurrence another recursion will take place with
the new remainder of the line and so forth. If there is no further occurrence, the
method will simply go on with the line after the recursive call. That is, it will
return from the trivial case.
The return
Let me stress that any method will "return"
to the point it was called from. Look at the MyFirstFrameDriver example. Every call
to the frame.readFile(...) will finally be completed and the "thread"
comes back to the do/while loop for another turn. Since the while loop ends directly
after the frame.readFile(...) call, it will start from the beginning again with
the print command.
do {
try {
System.out.print("Specify a valid file name: ");
/* send user input to readFile */
frame.readFile(in.readLine());
} catch (IOException e) {} // some IO error is ignored
} while(true); // loops until the window is closed
|
If recursion is used it might look
like this pseudo code
public DataType myMethod(DataType input) {
if ( trivial case ) {
return input;
} else {
newInput = ( recomputed input );
temp = myMethod(newInput);
return temp;
}
}
|
1 2 3 4 5 6 7 8 9 |
If the trivial case is found immediately
the method will simply return as usual. But imagine that first a recursive call
was made (let us call it B), and then another one (called C), to what point will
the method that is now called three times return?
Obviously the last call to myMethod()
will return from the trivial case (line 3) back to C. But C did the last call from
line 6 that says temp = myMethod(newInput); Obviously we will continue with line 7 and
return to the one called C, that was B.
Back to line 6 in B then and on to
line 7 that will return to the one called B, that was the original caller. And in
the original caller of myMethod() we will continue with the next line.
Which value was then returned this
somewhat lengthy way? Imagine we got the value any from the trivial case,
then any was returned into C and any was assigned to
temp that seems to be the
variable returned in C at line 7. Hence any is returned from C and is in
turn assigned to temp in
B, thus B will return any to the original caller.
Obviously the recursion might be
used to compute most problems in a top-down style. But to implement these methods
we have to analyze the problem carefully and start from bottom-up and both find
the trivial case and start with it. Then we may continue with the different cases
to consider. In a future column we will use recursion in a few ways. Today we will
use recursion as mentioned above, a simple re-call with the remainder of the line
and no return value. Even with no return value we will go back in the same style,
from C to B to the original caller.
A recursion pitfall
In spite of working this elegantly recursion
still causes some overhead since the CPU has to "remember" quite a few
internal states and stuff, as to know which way to go back and reinstate everything
as it looked like at the time of the recursive call. Thus a rule of thumb is "avoid
recursion when there is an obvious solution by iteration." -- Algorithms +
Data Structures = Programs, by Niklaus Wirth.
The Find & Replace
The final
modifier prohibits any later
change to the class or variable. |
String vs. StringBuffer
Since the String class is final we
cannot alter the string contained within a String object after its creation. A common
mistake by programmers is to write this kind of code
String str;
String temp;
while ((temp = bf.readLine()) != null) {
str = str + temp + "\n";
}
|
Obviously they believe that the temp and
EOL-mark (end-of-line) will be added to str, but that is not the case. Actually every
loop will instantiate a new str object, and let the old object be a case for the
garbage collection. The new object will upon creation be a compound of the old str, the temp and
the EOL. Is that bad then? Yes, since creation of new objects causes CPU overhead.
The correct, and a lot faster, code
shall make use of StringBuffer. Let str be declared as a StringBuffer and then use
the method append().
StringBuffer str;
String temp;
while ((temp = bf.readLine()) != null) {
str.append(temp + "\n");
}
temp = str.toString(); // convert back to String
|
Any time you plan to have a string
that shall be altered with or added to, use StringBuffer. But as you shall see,
sometimes the most convenient methods to make use of resides in String and then
we have to swap between String and StringBuffer. That is, as stated before, planning
by pencil saves you time and sweat.
The Find & Replace Methods
In our renamed FindAndRepl class we
have to add a new method, that we may name findString(). It is possible to add it
anywhere within the class boundary, so let us add it after the
readFile(). Further, make
it a nice habit to comment your code right away. If you can state the behavior of
your method in a few easily read lines, then that is a sign of you have probably
found the right algorithm. If it is not an easily understood comment, your code
is most likely not working as expected, as said: "the words dimly spoken, are
the ones dimly thought"*. In fact, quite a few programmers write the comments
first, to see what is expected from the methods, and later implement them
from the comments.
/*
* Get the document and finds the occurrences of the
* the specified string. Second argument is the optional
* replace String. This method calls a helper method.
*/
public void findString(String find, String replace) {
String doc = text.getText();
doc = helpFind(doc, find, replace);
text.setText(doc);
}
|
We plan to call this method with
two arguments, the string to find and the replacement string, both are objects of
String type. The method will return nothing since it operates directly on the JTextArea
through text.
Fetch the text displayed in the text
area as a huge (depends on the size of the displayed text) String object, assign
it to the String variable doc.
Next statement is very common when
using recursion, we call another method, a helper method. This time we do that since
the helper method will make use of three arguments, the document to search,
the string to find and the replacement string. It is the document to search that
is the clue to get this recursion to work.
Initially the document will contain
the complete text displayed in the text area. But if we find the string searched
for, we will re-call the helper method with the remainder of the document, not the
complete one. At last we will find no more occurrence of the string to find and
that will be the trivial case that is returned from.
We cannot use
findString() to
make re-calls to, since it is not possible to call it with the remainder of the
document.
Imagine the
helpFind() works as expected,
it returns the complete document with the found strings marked or the replacements
done. Then, assign the return value to doc and set that altered document as the text
displayed at the text area. And this method is done.
The helper method
|
|
|
|
|
|
|
private |
|
|
|
|
|
protected |
|
|
|
|
|
public |
|
|
|
|
Since a helper method normally is
not called from outside the class we may specify it private
and thus hide it. But it
is good to ponder over private, protected or public, since the visible scopes are not the same.
Here comes the code:
/*
* A helper method (hence private) that will do the
* recursion. It is called from findString. If no replacement
* argument is given, that is 'replace' is null, this method
* will replace the found string with itself uppercased.
*/
private String helpFind(String txt, String fnd, String rpl) {
int fIndex = txt.indexOf(fnd);
if (fIndex < 0) { // no more occurrences of fnd is found
return txt; // the trivial case
} else { // index points to the first occurrence of fnd
/* gets the first part (the substring) of the text,
* up to the string searched for */
StringBuffer buff =
new StringBuffer(txt.substring(0, fIndex));
/* Here comes the replacement */
if (rpl.equals("")) { // no replacement argument
buff.append(fnd.toUpperCase());
} else {
buff.append(rpl);
}
/* Here comes the recursive call, with the remainder
* of the given string txt. Now buff will hold
* the "middle value" of the text, that is from the
* former index+length_of_fnd and up to the index of
* this turn in helpfind()', and appended will be
* the value returned from the recursive call.
*/
/* Note that it is possible to break statements
* almost at any place of your choice, Java is very
* forgiving. It is still one statement, ending
* with a semicolon. Note the matching pairs of
* parentheses as well. */
buff.append(
helpFind(txt.substring(fIndex + fnd.length()),
fnd, rpl)
);
/* Now buff holds the same middle value and the
* remainder of the text appended to it. */
return buff.toString();
}
}
|
First we will test if it is the trivial
case, that is if indexOf() returned -1 which is "the string is not found".
If so, return the string since it is the remainder and have to be appended upon
the former part(s) of the complete document.
If no occurrence is found in the
very first instance, the helper method will return immediately to the findString() method.
But imagine we had the document "My
very first test of this very fine recursive lesson will end now." And we are
looking for "very" and there is no replacement string given. What will
happen?
-
The txt will be the complete sentence
The fIndex will be 3, since "very" starts at character number 3 of the string. Remember index 0 (zero) is counted as the first character. Hence we dive into the else clause:
-
The StringBuffer
buff will be "My ",
since substring() will
take anything from character zero up to, but not including,
fIndex.
-
Since rpl
equals the empty string,
no replacement text was given, we will append to buff the fnd string, turned to
upper case so we can see it found.
-
The buff
is now the "My VERY"
string, held as a StringBuffer object.
-
Now we will append the result from another
call to helpFind().
What are the arguments to use?
Since we have used the first part of the sentence, including the string to look for, we would like to send the remainder of the string, that is found from index «fIndex plus the length of the fnd» (since we do not like to get that part added again). Further we use the very same arguments again, fnd and rpl, since they will be the same arguments throughout the operation.
-
The StringBuffer
buff will be "My ",
since substring() will
take anything from character zero up to, but not including,
fIndex.
-
The txt is now " first test of this very fine
recursive lesson will end now."
The fIndex will be 20, since "very" starts at that index of the actual txt.
-
The new StringBuffer buff will be "
first test of this ".
-
"very" is turned into upper
case.
-
The buff
is now the " first
test of this VERY" string.
-
Append the result from another call
to helpFind() with
the remainder of txt.
-
The new StringBuffer buff will be "
first test of this ".
-
The txt is now " fine recursive lesson will end
now."
The fIndex will be -1 since no further occurrence of "very" is found, that is "the trivial case". The if clause will be true and we return txt unchanged.
-
Now we can go backwards, from 3 to 2d,
that will append the unaltered string to buff, that then will look like " first test
of this VERY fine recursive lesson will end now." (Compare with 2c)
-
One step further, from 2d we go to the
conversion of the StringBuffer to String and return the result into 1d. The resulting
buff in 1d will look like "My VERY first test of this VERY fine recursive lesson
will end now." (Compare with 1c)
-
The last step will be from 1d back to
the original caller, findString(), after a conversion of buff
to a String.
-
Finally, in
findString() we replaces
the value in doc with
the new result and put it visible in the text area.
Only one thing remains. How do we
get it to work?
First of all, add another line to
this class:
import java.awt.*;
Then, turn to the FindAndReplDriver.java
and add a few lines to it
do {
try {
System.out.print("Specify a valid file name: ");
/* send user input to readFile */
frame.readFile(in.readLine());
/* add the part below */
System.out.print("Enter the string to find"
+ " [ENTER if none]: ");
String f = in.readLine(); // reads your answer
if (!f.equals("")) {
/* a string to find was entered */
System.out.print("Enter a replacement string"
+ " [ENTER if none]: ");
String r = in.readLine(); // reads the answer
frame.findString(f, r); // do the search
}
/* end of added part */
} catch (IOException e) {} // some IO error is ignored
} while(true); // loops until the window is closed
|
The lines give you an opportunity
to enter an optional search string and an optional replacement string. Then findString() is
called with those arguments. Note, you can see the result from reading the file
in the window right away, and after you entered the optional arguments you will
see the next result.
The if clause may contribute to your
confusion, what are we asking for really? We would like to dive into the if-block
if, and only if, anything was entered and assigned to
f. But it looks like we
ask for the opposite, that f is the empty string. Yes, we are, but note the
little exclamation mark, '!'. An exclamation mark works as a logical not
that turns false into true and turns true into false. So whenever
f is not equal to the empty
string, we turn that false into true and, voila, the clause behaves
our way.
You may compare this use of the exclamation
mark with the != as opposed to ==.
Further, note that we do not test
if (f == "") that
will always return false. That is because that test tests if the object f has the
same reference as "" has. The method equals()
in the String class will
compare both string objects character by character. Compare with this code snippet
String str = "Simon";
String txt = "Simon";
if (str == txt) {
/* this will never happen */
}
txt = str; // second "Simon" is discarded
if (str == txt) {
/* this is true */
}
|
Since the first two objects are two
different objects with different references, they will not be located at the same
place in your computers memory, and hence the references are not equal. The internal
state of the object is not compared, but equals() will dig into the inner state of them both.
Later we assign the
str reference to txt, and
then their references may be compared. Because the one reference, held by two variables,
refers to only one object, the variables are of course equal with respect to the
state as well. And, "Yes!" I know this seems stupid! But believe me, both
the mistake with comparisons is very common, and very often the comparison of references
is needed. Hence, commit the two different comparison styles to memory, please.
User interaction
To be able to do consecutive searches
on the former result, change the first if to a while loop. But then we have to add another inquiry
for an optional string to find. The final code for today will look like
System.out.print("Enter the string to find"
+ " [ENTER if none]: ");
String f = in.readLine();
while (!f.equals("")) { // a string to find was entered
System.out.print("Enter a replacement string"
+ " [ENTER if none]: ");
String r = in.readLine();
frame.findString(f, r);
System.out.print("Enter the string to find"
+ " [ENTER if none]: ");
f = in.readLine();
}
|
Summary
Recursion may be a most powerful tool,
but as the careful reader may have noticed, this find&replace lesson could easily
have been done using iterative coding style. Method indexOf(String
str, int fromIndex) can
be helpful then. So, what algorithm will you use then? Pick the one easiest to code,
unless you have a good argument why not to do that.String and StringBuffer are two classes
heavily used in almost every application, please take your time and study the Java
API carefully.
Complete code to FindAndRepl.java
and to FindAndReplDriver.java
* If correctly translated.
Simon
Gronlund is earning his Master of Science in Computer Science at the Royal Institute
of Technology, Sweden, as an adult student. He also teaches Java and computer-related
courses on a college level. When he isn't tampering with his Warp 4 PC, he spends
his spare time with his two boys and his wife.