Session 29

The Strategy Pattern


810:062
Computer Science II
Object-Oriented Programming


A Warm-Up Exercise

Here is a quickie:

Write a class RemoveReturns whose main() echoes a file to standard output,
except that it replaces each new line character with a space.

Remember, in Java, the new line character is written '\n'.

For example:

    mac os x > less test-in.txt 
    a
    b
    c
    1234
    e
    567890
    ff
    ghij
    kl
    12
    34
    56
    78
    90





    next
    mac os x > java RemoveReturns test-in.txt
    a b c 1234 e 567890 ff ghij kl 12 34 56 78 90      nextmac os x > _


The clock is ticking...

We have learned at least three ways to do this...

I prefer the latter, if only to save me from having to write the replacement code yet again.


Using Computing to Solve a Real Problem

A news story last year in the Dallas-Fort Worth Star-Telegram (local mirror) reported the use of a computer program to identify novelist Henry James as the author of some older writings whose attribution was unknown. This sort of statistical literary analysis is a growing area of research in the humanities, where scholars seek to identify or confirm who wrote a document by comparing the document to a corpus of works known to have been written by an author.

The most famous problem of this kind is "Who wrote Shakespeare?" There are some literary scholars who believe that the Elizabethan actor named Shakespeare did not write the works attributed to him, but that they were written by some other person with a motive for concealing his identity. Among the most prominent people proposed are Francis Bacon, Christopher Marlowe, and Edward de Vere, 17th Earl of Oxford. This debate rages on... If you google for "shakespeare de vere", you will hit approximately 72,500 web pages. (If you are interested in this question, I suggest that you visit the web sites of The Shakespeare Fellowship and The Shakespeare Oxford Society.)

While statistical literary analysis requires some complex computer algorithms, you know enough Java to begin writing simple literary analysis programs. Let's do it!

For our examples today, we will use Shakespeare's Hamlet and Much Ado About Nothing. For your own programming, feel free to use the Bible and the Declaration of Independence. The Bible text file is rather large, so feel free to grab all four documents as a single .zip file.


A First Step

Suppose that we have written a class named Play that has a String instance variable named fileName.

    public class Play
    {
        private String fileName;
        ...
    }

A Play responds to a startsWith( char initial ) message by returning the number of Strings in its file that begin with the character initial.

Your task: write the

int startsWith( char initial )

method.

Here is a possible solution. Does it work?

    mac os x > java PlayDemo1 hamlet.txt
    The play in the file hamlet.txt contains 4533 words that start with 't'.


Another Exercise
(But an Easy One!)

Now we need to add to the Play class a method names wordsOfLength( int length ). In response to this message, a Play returns the number of Strings in the File named fileName that are length characters long.

What would we change from your previous solution?

Answer: just the test on the loop counter!

Here is a possible solution. Does it work?

    mac os x > java PlayDemo2 hamlet.txt
    The play in the file hamlet.txt contains 4533 words that start with 't'.
    The play in the file hamlet.txt contains 4313 words of length 5.


Yet Another Exercise
(But Still Easy!)

Now we need to add to the Play class a method names numberOfPalindromes(). In response to this message, a Play returns the number of Strings in the File named fileName that read the same forward and backward.

What would we change from your previous solution?

Answer: just the test on the loop counter!

Here is yet another solution. Does it work?

    mac os x > java PlayDemo3 hamlet.txt
    The play in the file hamlet.txt contains 4533 words that start with 't'.
    The play in the file hamlet.txt contains 4313 words of length 5.
    The play in the file hamlet.txt contains 1206 palindromes.


The Real Problem: Duplication

Each of these methods is nearly identical. How can we make the duplication go away?

What programming techniques do you know that you could use to do the job?

Well, we could factor out a helper method.

One Possible Solution

One way to implement this idea is the Template Method pattern. The template method factors out a helper method in a way that is backwards from how we usually think of it: The helper method, which captures what is common among the three methods, is the calling methods. The called methods are the code that differs among the three solutions.

So, Play would have a method that does all of the file processing and calls a method to do the test. Then we write subclasses of Play to implement specific counting behaviors.

First, we would create a "template" method named countWords with a call to a "hook" method that runs the test:

    public int countWords() throws IOException
    {
        ...
        while( words.hasMoreTokens() )
        {
            String word = words.nextToken();
            if ( passesTest( word ) )
                wordCount++;
        }
        ...
    }

Then, we might write a subclass named WordsStartWithPlay that implements the passesTest method in its own way:

    public int startsWith( char targetChar ) throws IOException
    {
        this.targetChar = targetChar;
        return countWords();
    }

    protected boolean passesTest( String word )
    {
        return word.charAt( 0 ) == targetChar();
    }

A Big Problem

This solution works fine, if we have a particular set of needs. Template methods are a common and useful tool for letting subclasses fill in details in an otherwise specified process.

But in our play-processing scenario, this approach has a huge drawback. What is it?

What if I want to ask a Play both how many of its words start with a particular letter and how many of its words have a particular length?


Repeat After Me

"Say it once and only once."

We know it.
We believe it.
We love it.

But how do we do it?

We do! We've done it. In fact, you did it when you wrote your startsWith() method earlier. Even if I had not told you to write a method that takes the initial character as an argument, you would have done so naturally. I doubt anyone would have felt a desire to writing a method called startsWithT() and a method called startsWithJ() and a method startsWithS() and .... Why not?

Because you understand the idea of parameterized behavior -- even if you've never heard that phrase before. startsWith( char ) implements the behavior. The argument to the method parameterizes the behavior to work for a specific data value.

We parameterize a procedure by passing to it the value that differs among the various uses of the method.

So... The answer to "How do we do it?" in our Play class is to parameterize the behavior of the word-counting code by passing to it what differs:

Make the test we use on the String a parameter.

And I send you off to do the job.


Um, Excuse Me,
Professor Wallingford, ...

Then I wake up the next morning, go to my office as happy as can be, and find in my e-mail the following:

     Date: Wed, 28 Apr 2004 00:59:33 -0500 (CDT)
     From: Happy User (somestudent@cns.uni.edu)
     To: My Favorite Teacher (wallingf@cs.uni.edu)
     Subject: say it once and only once

     How exactly do I do that ??

     I mean, I know how to pass characters and numbers
     to functions because, like, they're data, ya
     know?  How can I pass a function as an argument?
     How can a test be a parameter?

     Patiently awaiting enlightenment...


Enlightenment Arrives

Ah, Little One, you know the answer. You even know two possible answers, one of which is better than the other. You just don't realize that you know.

Idea #1: Objects are data, too.

Idea #2: Objects can do things!


A Better Solution

What changes in our set of applications is not the kind of play, but the way we count words in the query methods.

Why not make what changes -- the test -- an object?

So, for our Play problem:

This is the Strategy design pattern.


Our Experience with the Strategy Pattern

We have encountered this pattern before, in the AWT. Our Frames hold a LayoutManager, which is an algorithm that lays out the Frame's items on the screen.

Making tests and functions and whole algorithms into objects that can be created, passed, and replaced is a common idea in object-oriented programming. The result is much more flexible programs!


Using the Strategy Pattern in our Word-Counting Program

First, let's factor out what is different about our solutions. The "variable" here is determining whether a certain word has a certain characteristic.

We define such a strategy using an interface:

    public interface CountedFeature
    {
        public boolean hasFeature( String s );
    }

We can then implement different checking strategies as classes. For example:

    public class StartWith     implements CountedFeature

    public class OfLength      implements CountedFeature

    public class IsAPalindrome implements CountedFeature


Implementing a Strategy Object

Here's how we might implement one:

    public class StartsWith implements CountedFeature
    {
        private char targetChar;

        public StartsWith( char target )
        {
            targetChar = target;
        }

        public boolean hasFeature( String s )
        {
            if ( s == null || s.length() == 0 )
                return false;
            return s.charAt(0) == targetChar;
        }
    }


Using a Strategy Object

Any class that needs to test strings to see whether they start with a particular letter can create an instance of StartsWith ...

          StartsWith test = new StartsWith( 't' );

... and send it a message:

          if ( test.hasFeature( "the" ) ) ...

To do this in our Play class, let's extract the common parts of our three methods into a word-counting method:

    public int countWords( CountedFeature test ) throws IOException
    {
        BufferedReader inputFile = new BufferedReader(
                                       new FileReader( fileName) );
        int wordCount = 0;

        while( true )
        {
            String buffer = inputFile.readLine();
            if ( buffer == null ) break;

            buffer = buffer.toLowerCase();
            StringTokenizer words = new StringTokenizer( buffer, DELIMITERS );
            while( words.hasMoreTokens() )
            {
                String word = words.nextToken();
                if ( test.hasFeature( word ) )
                    wordCount++;
            }
        }

        return wordCount;
    }

This is almost exactly the code that we re-wrote before...

Now, we implement the specific methods we need, with calls to countWords():

    public int startsWith( char targetChar )
    {
        return countWords(
                   new StartsWith( targetChar ) );
    }

And:

    public int wordsOfLength( int targetSize )
    {
        return countWords(
                   new OfLength( targetSize ) );
    }

And:

    public int numberOfPalindromes()
    {
        return countWords( new IsAPalindrome() );
    }

To add new word-counting methods, we need only...

  1. to write a new CountedFeature class and
  2. to add a one-line method to the Play class.

Writing such a class isn't much more work than writing a method, because that is all there is. Very nice!


An Exercise: Implementing a Strategy

This can be a quickie:

Write the class OfLength that tests strings to see if they are a particular length.

Here's a solution. It's that easy!


Wrap Up


Eugene Wallingford ..... wallingf@cs.uni.edu ..... April 26, 2005