Quick links to supporting pages:  Main page, BodyParts, MVC, Sounds, View & controller

Here is a study in ways of looking at collections of data.    Consider a word made up of letters:   "supercalifragelisticexpialidocious".     What is a word, you say?   Chopped ham?    Well, almost.   

A word can be either empty or an object that contains a character and reference to another word.

Sound familiar?   That is, "dog" is really just "d" and a reference to the word "og" (which comes from the ancient Babylonian word for, well, the back end of a dog).

We already have seen a data structure that can represent a linear recursive structure like a word -- the Scheme list.  So we can simply model a word in as a slightly modified Scheme list.   Also, for the hangman game, the characters could be displayed as either their usual representations or as a "-".     How the character is displayed depends on whether or not the character has been guessed correctly yet. That is, the "first" of our "wordlist" could be either visible or invisible, thus suggesting that a State design pattern should also be incorporated.

Study the documentation for the wordlist package. See the sections titled: "WordList", "Word Component" and "Word Algorithm".

A few things bear a bit of explanation:

IWord

IWord is basically a Scheme-list except that the non-empty case has two states: visible and invisible. (Note that the two states are not "empty" and "non-empty".) The visibility only refers to the visibility of first, not the visibility of the data held in its rest! That is, suppose that IWords in their invisible state display their firsts as "-" then "po-y-orp--s-" would involve 13 IWord objects, consisting of 1 IEmptyWord object, and 12 INEWord objects, of which 7 are in their visible state and 5 are in their invisible state. By default, the state of an NEWord object should be invisible.

The only state-dependent methods of NEWord are execute() and toggleState().    Thus, these are the only methods delegated to the abstract state.    execute() is a standard visitor pattern algorithm (see IWordAlgo below) execution.   toggleState() does just that -- it flips one state to the other ("toggles").

Note that an IWord has no intrinsic ability to display itself, either visibly or invisibly.   Convince yourself that such behavior is purely extrinsic.    An NEWord only has a notion that there exists two states, not about how those two states differ in behavior.

WordFactory

There are no public implementations of the IWord , IEmptyWord and INEWord interfaces in the wordlist package. Any objects that use the wordlist package deal only with those public interfaces and have no knowledge of the underlying implementations. They can obtain concrete IWord objects by using an abstract factory, IWordFactory. WordFactory is a specific concrete implementation of IWordFactory and is capable of instantiating a particular implementation of IWord . To further hide the details of that implementation from the clients, WordFactory employs private nested classes to implement IWords.

The makeWord() method simply walks backwards through a String using a for-loop ( start i at the length of the String minus 1 and use i-- as the "increment" ) and builds the IWord object from the back of the String towards the front because the constructor for NEWord requires a first and a rest.  The String.charAt(i) method is used to pick individual characters out of the String and thus construct the WordChar.   The list is then returned. The makeWord() method can be written as such:

IWord makeWord(String w) {
    IWord wordList = EmptyWord.Singleton;
    for(int i=w.length()-1; i>=0; i--) {
	wordList = new NEWord(w.charAt(i), wordList);
    }
    return wordList;
}

Since the WordFactory doesn't hold any information (it's "stateless" in CS parlance), there only ever needs to be one instance of it .    We use the Singleton design pattern ensures that only one instance ever exists.   

The Singleton design pattern

This is used when only one instance of an object is desired.   The advantage of a singleton over a static class is that a singleton is a real object and thus can be abstracted and treated as any other object, which is impossible with a static class.  Here, we only want one instance of a WordFactory .    The code for the factory looks as such:

public class WordFactory  {
    public static final WordFactory Singleton = new WordFactory();

   private WordFactory()   { /// hide the constructor!
       //  etc.....
   }

Another (Java) implementation of the Singleton pattern that you should be aware of is:

public class WordFactory  {
    private static final WordFactory instance = new WordFactory();

   private WordFactory()    { /// hide the constructor!
   }

   public static WordFactory singleton()   {
       return instance;
   }

    //  etc.....
}

We have been using the first implementation, but many people prefer the second. Why do think they do? (Incidentally, StructureBuilder can automatically generate a third implementation of the Singleton pattern-- a style that is less elegant than the above two styles but that works for both Java and C++ and is most useful if the class is very large.)

To use the factory (first implementation above), you simply refer to the static Singleton field of the class to get a reference to the one WordFactory object, e.g.   

IWord myWord = WordFactory.Singleton.makeWord("Tinky Winky");

Note that we don't even need an WordFactory variable.

Testing: Do this before attempting the ToStringAlgo below, otherwise you won't know if  the problem is the algorithm or the list.

1. Set the default state of NEWord to be visible and write a test program that asks WordFactory to instantiate an IWord object with at least 4 characters in it. Use the following algorithm to print the contents of the IWord object. The call to execute the algorithm would something like: myWord.execute(PrintWordAlgo.Singleton, null).

   import wordList.*;
   
   public class PrintWordAlgo implements IWordAlgo {
       public final static PrintWordAlgo Singleton = new PrintWordAlgo();	
       private PrintWordAlgo() {
       }
   
       public Object emptyCase(IEmptyWord host, Object inp) {
   	System.out.println("\n");   //goes to the next line.
   	return null;
       }
   
       public Object visibleCase(INEWord host, Object inp)	{
   	System.out.println(host.getFirst()+" ");
   	return host.getRest().execute(this, inp);
       }
   
       public Object invisibleCase(INEWord host, Object inp) {
   	System.out.println("- ");
   	return host.getRest().execute(this, inp);
       }
   }
   
   The above code can be downloaded here.
   

2. Now change the default state back to invisible and check that executing the above algorithm on the desk is what you think it ought to be.

IWordAlgo

A visitor pattern algorithm for IWord that provides an emptyCase(), a visibleCase() and an invisibleCase().  Note that the visitor has no real knowledge of the existence of the states, only that there appear to be three concrete hosts.

ToStringAlgo

This IAlgo algorithm produces a String where the characters are their normal value if the corresponding first in the IWord is in its visible state or a '-' (dash) if the IWord is in its invisible state.

emptyCase():   Return an empty string.

visibleCase():  Return the value of the host's character concatenated on the front of the return value of the recursive call to the rest of the list .

invisibleCase(): Return a '-' concatenated on the front of the return value of the recursive call to the rest of the list .

Testing:

1. Modify your test code to print the result of running this algorithm on word .     
2. Try changing the default NEWord state to double check that it still works..

GuessAlgo

This IAlgo algorithm takes a Character object and attempts to find all the matching values held in the firsts in the IWord list with the following side effect: the state of the matching values is toggled.    A Boolean object with a true value is returned a match was found, otherwise a Boolean object of false value is returned.  The algorithm is structurally very similar to the ToStringAlgo algorithm.  Here's a block outline:

emptyCase():   Return Boolean.FALSE.

visibleCase():  Return the value of the recursive call to the rest of the list. What does this mean in terms of guessing the same letter twice?

invisibleCase(): Use the Character.toLowerCase() method to make the comparison case insensitive:

Value of parameter matches value of the INEWord host's first: Toggle the state of the INEWord host.   Recur on the rest of the list.  Return  Boolean.TRUE.

Value of parameter does not match the value of the INEWord host's first:  Return the value of recurring on the rest of the list.

Testing

1. Test the algorithm by
   1. Printing out the return value of the call to IWord.execute(GuessAlgo....).
   2. Printing out the returned String from executing the ToStringAlgo on the IWord.
2. Be sure you cover at least the following situations:
   1. The guessed character is not in the word.
   2. The guessed character appears only once and is not the first element in the list.
   3. The guessed character appears multiple times in the word.
   4. All of the above, except that the word contains some characters that have been successfully guessed.

IsAllVisibleAlgo

This algorithm should return a Boolean.TRUE object if all the IWords are in their visible states or a Boolean.FALSE object if even one IWord in the list is still invisible.

This is a pretty straightforward algorithm of the above basic structure.   You can figure this one out yourself.

Testing

1. Be sure to test the situations where all the characters are visible and where only some of them area visible.. 

The ability to handle spaces in the word

You will notice that the above design does not handle spaces in the word (i.e. a phrase) very well.  Spaces are treated the same as other characters.   How can you modify the above design to handle the inclusion of spaces such that the spaces are always visible, i.e. never shown as a dash?  Remember, nothing outside an IWord knows what state it is in!

Last Revised Thursday, 03-Jun-2010 09:52:20 CDT

©2006 Stephen Wong and Dung Nguyen