CS 303E: Assignment #1001 (Fall 2004)
Linked Structures; More Inheritance and Packages (200 Points)

Due: Sunday evening, November 21 by midnight via turnin. If you have problems with turnin from outside the Elements Lab, be sure to use turnin from the Elements Lab so that you submit your work on time.

Purpose: This assignment is a continuation of Assignment #1000 which contained exercises demonstrating inheritance, packages, recursively-defined classes, and class collaborations. In particular, this assignment asks you to implement a general-purpose data structure.

Remember: If you aren't clear on a topic covered in this class, you can post on the class newsgroup or you can attend the many office hours held by the teaching staff. In particular, if you're not clear on any of the terms or concepts described in this assignment, please ask questions. The earlier you ask your questions, the better!

Further, remember that Assignment #1000 established a new requirement that your Java class definitions should all be placed into package "edu.utexas.cs303e.student" or, when explicitly stated, a sub-package thereof. If an exercise does not explicitly state the package, you should place it into edu.utexas.cs303e.student. For example, if an exercise asks you to place your implementation into a "class named AnArbitraryName", your source code should define a class which has full name edu.utexas.cs303e.student.AnArbitraryName.

Part 1: Phrase Translation. Assignment #1000 asked you to implement a class named Phrase that represented the words of a phrase by defining a collaboration with another class named Word. You also implemented a subclass of Word named CognatePair. If you don't recall the details of these classes, you should first review Assignment #1000. This assignment asks you to extend Phrase to implement a simple language translator from English to Pig Latin. The basic idea can be further extended, with some additional work (not in the scope of this assignment!), to implement simple-minded language translation as per babelfish. Sophisticated language translation, though, is much harder.

1. (60 points) Implement a class named CognatePhrases (in which package?) by extending your previously defined class Phrase. This new class will also represent a phrase, as did Phrase, except that the phrase will be represented in two languages. For our purposes, we'll think of one language as being English and we'll call the other language the cognate language. Implement the following constructors and methods:

   • Constructor public CognatePhrases (CognatePair word) should behave as does the similar constructor in Phrase: public Phrase (Word word). Error-checking should ensure that the word parameter is non-null. Further, the parameter should then be placed in an instance variable and an accessor should be made available for it. However, you've done this work before in the superclass! So, save yourself effort this time with only a one-line use of the keyword super. If this is not obvious to you, please ask about it!

   • Method public String getCognateLanguage() returns the cognate language of a CognatePhrases instance. This is done by returning the cognate language of the leading word. Ok, now think about this a bit before implementation. If you understood the use of super in the previous constructor, you'll be able to access the leading word by using the getWord() method that was inherited from Phrase. Again, if this is not clear, ask! The return type of getWord() is Word, but it was initialized with a CognatePair. This is legal because CognatePair is a subclass of Word and, therefore, an instance of CognatePair can be used wherever a Word is used. However, to implement getCognateLanguage(), it's necessary to cast the result of getWord() back to a CognatePair, then invoke that object's version of getCognateLanguage(). One more time: If this is not clear, ask!

   • Constructor public CognatePhrases (CognatePair word, CognatePhrases suffix) should behave as does the similar constructor in Phrase: public Phrase (Word word, Phrase suffix). Error-checking should ensure that both parameters, word and suffix, are non-null, and both parameters should be placed into instance variables with appropriate accessors provided. Again, because this constructor is so similar to a constructor in superclass Phrase, a one-line use of the keyword super provides much, though not all, of the implementation. One additional error-check is necessary: The cognate language of word should be equal to the cognate language of suffix. If this is not the case, it should throw an IllegalArgumentException. So, if this constructor is implemented correctly, it should be impossible to create CognatePhrases instances that have different cognate languages. Test this!
   • Method public String toPhraseString() returns the English form of the represented phrase. If the suffix is null, this returns only the leading word in English. This, again, will probably require you to cast the leading word to a CognatePair in order to invoke an appropriate accessor. If, however, the suffix is non-null, concatenate the English leading word and the English form of the suffix (how do you access this?) with a space separator, and return the result.
   • Method public String toCognateString(), returns the represented phrase in the cognate language. The implementation is similar to that of toPhraseString() above, except that it uses the cognate language form of the leading word and, if non-null, of the suffix phrase.
   • Override method public String toString(), using the same technique as in the previous two methods, except representing the leading word with both parts in parentheses. For example, if the leading word is a CognatePair with the English word "fish" and the French word "poisson", it should be represented in the form ("fish","poisson"). Further, label the result with the name of the cognate language. For example, if a CognatePhrases instance represents the two-word phrase "two fish" along with its French cognates "duo poisson", then printing the result of toString() should produce the following:

     Cognates in French: ("two","duo") ("fish","poisson")

     where the label is "Cognates in French: ". Be careful! It is not proper to include the label more than once! Hint: Implement a helper method to do some of the work.

   At this point, your implementation of CognatePhrases should be complete, but you should test it to ensure that it works properly. The following code, if placed into a standard main method in CognatePhrases, is a test case that uses your FrenchCognate class (which must be imported so that this main method will compile):

   CognatePair one = new FrenchCognate ("one", "un") ;
   CognatePair young = new FrenchCognate ("young", "jeune") ;
   CognatePair heart = new FrenchCognate ("heart", "coeur") ;
   CognatePhrases phrase = new CognatePhrases (heart) ;
   phrase = new CognatePhrases (young, phrase) ;
   phrase = new CognatePhrases (one, phrase) ;
   System.out.println (phrase) ;
   System.out.println (phrase.toPhraseString()) ;
   System.out.println (phrase.toCognateString()) ;
   

   The above code, when executed, should print the following:

   Cognates in French: ("one","un") ("young","jeune") ("heart","coeur")
   one young heart
   un jeune coeur
   

   When you've completed your implementation, put your Java source code into a file named CognatePhrases.java and submit it via turnin. You may include a standard main method if you'd like, but you won't be graded on that part of your implementation.

2. (40 points) Implement a class named PigLatin, in package edu.utexas.cs303e.student.pig_latin, that extends the class CognatePhrases (remember to import it) to translate English phrases to corresponding phrases in Pig Latin. You should implement two constructors, a public static factory method, and a standard main method as described below (and you may implement as many private helper methods as you want):
   • Constructor public PigLatin (String word) accepts a non-null String word parameter which is used to construct a PigLatinCognate for use in the super constructor. This parameter must also be non-empty when trimmed. All of these properties must be error-checked. (What's the easiest way to do this?) Finally, the super constructor must invoke the one-parameter constructor in CognatePhrases.
   • Constructor public PigLatin (String word, PigLatin phrase) accepts a non-null non-empty String word and a non-null PigLatin phrase. As above, error-check these in the easiest way possible, converting the word to a PigLatinCognate instance. You don't have to convert the phrase. (Why not?). These are used to invoke the two-parameter super constructor in CognatePhrases.
   • Factory method public static PigLatin valueOf (String phrase) accepts a String parameter phrase containing an English phrase, which is represented as a whitespace-separated sequence of words. The phrase must be non-null and non-empty when trimmed, so it will contain at least one word. This method must use the phrase to create a PigLatin instance that represents the phrase in both English and Pig Latin. Hint: Not counting error-checking or blank lines, this can be done, using recursion, in about six lines of code (and they're short lines, too!).

     Recall that a factory method is a method that encapsulates the creation of an instance. In this case, it's encapsulating the creation of a PigLatin instance that represents the entire String argument. Why did I ask you to implement this as a factory method instead of a constructor?

   • The standard main method, with an appropriate prompt, must read lines from standard input until either a blank line (after trimming) is entered or the end-of-input is reached. Each non-blank line should be an English phrase which is converted to a PigLatin instance using the factory method valueOf(String) described above. Then, the Pig Latin form of the phrase is printed using the toCognateString() method in PigLatin (where did this method originate?). Finally, when the program exits because either a blank line or end-of-input was encountered, it should print the Pig Latin form of Goodbye now. As an example, here's a sample run of my version of this main method:

     Enter phrase: Eighty percent of success is making Java do the work
     Eightyay ercentpay ofay uccesssay isay akingmay Avajay oday ethay orkway
     Enter phrase: I like Java because it is powerful
     Iay ikelay Avajay ecausebay itay isay owerfulpay
     Enter phrase:
     Oodbyegay ownay
     

     How did I get the Pig Latin translation of Java and Goodbye to change their capitalization like that? It's not necessary that you do this, but it's a nice touch!

   Put your PigLatin class into a file named PigLatin.java and submit it via turnin.

Part 2: List Data Structures. Have you ever tried to get yourself organized? You probably started by making a list. Maybe it was a list of assignments, or a list of classes to take, or maybe even list of relatives to whom you owe money. If you've ever had to buy a lot of items (clothing, school supplies, books, ...), you probably made a shopping list. If you've ever organized a formal gathering, such as a wedding or a political rally or a motorcycle race, you probably made a list of people to invite.

The point is that a list is a fundamental way of organizing information that is largely independent of the type of information. Similarly, in computer programming, lists are a fundamental building block for representing data. In this part, the core task is to implement a recursively-defined list that is generic (which means that it can be used with any type of data).

1. (25 points) The starting point is to define a class to hold a list item. Conventionally, the most common name for a class like this seems to be Node, so that's the name we'll use. Put it into package edu.utexas.cs303e.student.utility. Your version will be immutable, but it's also possible to implement a mutable version. When you code the constructors and method described below, look for similarities to the class Phrase that you implemented for Assignment #1000. Also, look for differences! The Node class should have package access, as should its constructors, and it must have the following constructors and methods:
   • Constructor Node (Object item, Node next) is a general-purpose two-parameter constructor. The first parameter is item which represents an item in a list. This parameter has type Object because the goal is to implement a generic list that can contain any type of data. (How is it that using Object allows this to happen?) To pursue genericity further, your implementation must also allow item to be null! The second parameter is next which references the next part of the list, if any. If there are no remaining items in the list, then next will be null. Whatever the values in these parameters, save them into appropriate instance variables.
   • Constructor Node (Object item) is a convenience constructor that is to be defined to be exactly equivalent to invoking Node (item, null). What's the easiest way to implement this? (Hint: One line with three words and some punctuation.) A convenience constructor is one which, when invoked, is simply short-hand for a longer constructor invocation. Similarly, a convenience method is one that, when invoked, is short-hand for a longer method invocation. For an example, consider the two versions of the substring method in String.
   • Facilitator public Node add (Object item) is a non-static factory method that returns a new Node with its item field set to this method's parameter and with its next field set to this Node. Ok, using this method, how can you create a list with, say, three items in just one statement of Java code?
   • Accessor public Object getItem() returns the value of the item instance variable.
   • Accessor public Node getNext() returns the value of the next instance variable.
   • Facilitator public String toString() returns a textual representation of the item in this Node and the following Node instances, if any. Place a ", " String between adjacent items. This is similar to the toString() method of class Phrase. If you need more explanation, ask someone.

   Put your Node class into a file named Node.java and submit it via turnin.

   Did you answer the question about Node's add(Object) method above? How can add(Object) be used to quickly create multi-item lists? If you haven't determined the answer yet, it's time to ask someone! This is a fundamental operation. For example, suppose someone wants to use your Node class to create a sequence of three Node objects that, in turn, reference three different items. The first Node in the sequence is to be referenced by a variable (of type Node) named head. A diagram of the desired result is shown below:

   

   This could be achieved with the following code that uses constructors:

   Node head = new Node ("xyz") ;
   head = new Node (new Integer (17), head) ;
   head = new Node (Double.parseDouble ("61.7"), head) ;

   Do the same thing with one line of code using the add method.

Ok, if you answered the question at the end of the previous exercise, you now should realize that the purpose of Node is to use it as a building block to represent lists (aka, sequences) of other objects. When you consider lists, one question to ask is, "How can I compute with the items in a list?" The two answers are: Recursion, as we did with the Phrase class; and Iteration (aka, loops) as we've done for sequences of actions. If we want to write a loop to process a sequence of items in Node objects, we can write a loop that follows the next fields, as shown below:

// Initialize the loop by determining a starting Node:
//
Node node = ... ;

// Continue looping while we have a valid Node reference:
//
while (node != null) {

    // Get the item from the current Node and compute with it:
    //
    Object item = node.getItem() ;
    /* ... */

    // Advance to the next Node by "following"
    // the "next" field in the Node:
    //
    node = node.getNext() ;
}

2. (15 points) In package edu.utexas.cs303e.student.utility, implement a public class named Cursor that provides a view of a Node as follows:
   • Constructor Cursor (Node startNode) (with only package access) initializes a Node data field to the parameter startNode. This represents the initialization of a loop. Notice that this constructor is only package access, even though the class is public. This is because Cursor instances will be created only by the code that we encapsulate in the edu.utexas.cs303e.student.utility package.
   • Facilitator public boolean hasNext() returns true if the Node field is non-null, and returns false otherwise. This represents the test in a loop.
   • Facilitator public Object next() first error-checks the Node field to ensure that it's not null. If it is null, this method throws a NoSuchElementException. Otherwise, this method returns the item in the current Node, and updates the Node field to the next Node. This represents part of the action in a loop, including the update of the test variable.
   Put your source code for Cursor into a file named Cursor.java and submit it via turnin.

   With the Cursor, it now becomes possible to loop through the items in a sequence of Node objects with the following type of code (test this!):

   Cursor cursor = new Cursor (node) ; // node already defined.
   while (cursor.hasNext()) {
       Object item = cursor.next() ;
       // do something with item ...
   }
   

   Even better, Cursor is public to our users, yet it also hides the implementation of Node! Therefore, if we want to change our Node implementation in a later release of our software, we can do so as long as we provide an updated version of Cursor for our users.

Ok, both Node and Cursor have various elements with only package access. So, how does a user get to use them? The next step (and last, for this assignment) is to implement a wrapper class that is public and that combines Node and Cursor objects to let our users create and process items in lists.

3. (60 points) Implement a public class named LinkedList, with public access, in package edu.utexas.cs303e.student.utility, that has two private instance variables: A Node and an int size. The Node field, when non-null, references the first Node in a sequence of Node objects that contain the items in a list. The size field holds the number of Node objects that are in that sequence and, therefore, the size will be zero if the Node field is null. As the LinkedList is mutated, the size field must always be kept up-to-date. (Why do you think the name of this class is LinkedList?) Your class should have the following constructors and methods:
   • Constructor public LinkedList() creates a list that is initially empty. The size field is set to zero and the Node field is set to null. Both fields should be private.
   • Constructor public LinkedList (LinkedList source) accepts a non-null source and constructs a new LinkedList that has the same size and items as source. Since your Node class is immutable, what is the easy way to do this? If your Node class had been implemented to be mutable, why would the easy way not be a good idea?
   • Facilitator public LinkedList add (Object item) adds an item to the LinkedList, updating the Node and size fields appropriately.
   • Non-static factory method public Cursor cursor() returns a Cursor instance initialized to the beginning of the sequence of Node instances in this LinkedList. Notice that this method is publicly accessible so that users can call it from outside this package. Further, since this class is inside this package, it can access Cursor's constructor and access Node instances. Yet, non-package users can't directly access either Cursor or Node. Non-static factory methods like this are the only way that this can be done.
   • Facilitator public boolean equals (Object object), when it compares two LinkedList objects, returns true exactly when the two lists are the same size with exactly the same items in exactly the same order. Your implementation should satisfy the requirements for an .equals(Object) method that we discussed during lecture, and, since a LinkedList is a complex structure, I strongly recommend using the efficiency test that I described. Further, are there other efficiency tests that are useful? After all, the list sizes are known in advance and the Node objects in a LinkedList are immutable.
   • Virtual accessor public boolean isEmpty() returns true exactly when the list has no elements.
   • Accessor public int size() returns the size of the LinkedList instance. Note: This name deliberately does not follow the "Bean convention".
   • Facilitator public String toString() returns the textual representation of the items in the LinkedList, surrounded by brackets. For example, if the items in the Node objects referenced by the Node field are String objects "abc", "xyz" and "omega", the value returned by this method should be

     ["abc", "xyz", "omega"]
     

     You can either use the toString() method in Node to help out, or use a Cursor to loop through the Node objects in this LinkedList.

   Put your implementation into a file named LinkedList.java and submit it via turnin.

   That's the only implementation that you're asked to do for LinkedList, but you can undoubtedly see that there are other methods that could be useful (like deleting an item). Why not think of a few useful methods and consider how you'd implement them? Those methods that mutate the list, other than by adding, are the ones can may seem difficult to implement. How can you implement these without making Node mutable?

Consider, for future work, how you might extend LinkedList to make other useful classes. For example, how could you implement a different version of your Phrase class using a LinkedList as a base?

As a more generic example, how would you implement a set structure? The basic operation required for a set is the boolean ∈ operation (often named contains or isElementOf) that returns true exactly when an element, specified via a parameter, is in the set. Further, if an element is in a set, it can only be in the set once. However, a list can have as many copies of an element as desired. So, how would you implement the add operation for a set to ensure that no element can be added more than once? As examples of more advanced operations, how would you implement set union and set intersection?