CS 112 Lab 9 - Generics redux

In today's lab we will modify a non-generic map datatype implementation to its generic version. In previous labs we typically used one type parameter <T> for generic Java classes. The generic classes we will see in today's lab use two type paramters written as <K, V>. The purpose of defining such type pairs will become clear below.

HashClient.java provides an example to create a Scanner object from a file in your directory. We use this Scanner object to read the homework 5 string list into memory.

TASKS:

1. Save TWL.txt file to your Z:\ drive (i.e., as Z:\TWL.txt).
   
   
2. Follow the "Lab description" in WordList.java and complete the tasks listed within.
   
   
3. Complete the tasks in HashClient.java.

package lab09;
import java.util.*;
 

/* Lab description:
 * 
 *   We give below "non-generic" versions of Entry, WordListNode, WordListIterator 
 *   and WordList classes. By non-generic we mean that the Entry class is programmed 
 *   to store an Integer keyValue and a String dataValue.
 *    
 *   We wish to allow the Entry class to store arbitrary datatypes for dataKey and dataValue.
 *   Note that dataKey and dataValue can have the same type (e.g., both can be Strings) 
 *   or can be of different types (Integer and String in the above example). We hence 
 *   create a "generic" Entry class with two parameterized types (K & V) that looks
 *   as follows,
 *   
 *   class Entry <K, V> {
 *       K dataKey;    // dataKey is determined by input type K     
 *       V dataValue;  // dataValue is determined by V which can be different from K
 *   
 *      // .... methods in Entry class
 *   }
 *   
 *   Examples: 
 *               Entry<Integer, String> corresponds to an Entry class 
 *                                      with Integer key and String data
 * 
 *               Entry<String, String> corresponds to an Entry class 
 *                                      with String key and String data
 *  
 *   TASKS:
 *       (a) Follow the generic Entry class example above and modify it and other classes 
 *           to create their corresponding generic versions.
 *           Note that some generic class instances are already present 
 *           (e.g., Iterator<Entry>, Iterable<Entry>). Be careful when you modify these.
 *   
 *      (b) Change HashClient.java to use the generic classes that you have created.
 */

  
// The classes below are non-generic, change to their generic implementation
class Entry {
    Integer dataKey;
    String dataValue;
    
    Entry(Integer newKey, String newValue) {dataKey = newKey; dataValue = newValue;}
    Integer getKey(){ return dataKey; }
    String getValue(){ return dataValue; }
}
 
class WordListNode {
    Entry nodeEntry;
    WordListNode nextNode;
    
    WordListNode(Entry newEntry, WordListNode newNext){
        nodeEntry = newEntry;
        nextNode = newNext;
    }
    Entry getEntry(){    return nodeEntry; }
    WordListNode getNext(){ return nextNode; }
}
 
class WordListIterator implements Iterator<Entry> {
    WordListNode currentWordListNode;
    
    WordListIterator( WordListNode wordListHead ) {
        currentWordListNode = wordListHead;
    }
    public boolean hasNext() {
        return (currentWordListNode != null);
    }
    public Entry next() {
        Entry currentEntry = currentWordListNode.getEntry();
        currentWordListNode = currentWordListNode.getNext();
        return currentEntry;
    }
    public void remove() {}
}
 
public class WordList implements Iterable<Entry> {
    WordListNode wordListHead;
    
    WordList() { wordListHead = null; }
    void addToHead( Entry newEntry ) {
        wordListHead = new WordListNode( newEntry, wordListHead ); 
    }
    public Iterator<Entry> iterator() {
        return new WordListIterator( wordListHead );
    }
}

package lab09;
 
import java.io.FileInputStream;
import java.util.*;
 
public class HashClient {
    
    // The hashKey for this lab is an Integer given by sum of chars in str.
    // In hw5: hashKey is a String with letters in str sorted alphabetically
    public static Integer getLabHashKey(String str) {
        Integer hashKey = 0;
        for( int i = 0; i < str.length(); i++ )
            hashKey += str.charAt(i);
        return hashKey;
    }
    
    public static void main(String [] args) throws Exception {
        
        // HashTable array below stores reference to WordList chains
        
        // TASK: Change LHS in the following statement to use generic version of WordList class.
        // Note: Do not change the RHS to use generic. JAVA seems to have a bug that throws an error
        //       when creating a generic array, hence leave the RHS unchanged (only for this line).
        WordList [] hashTable = new WordList[20];
        
        // Initialize hashTable[ 0,...,99 ] to empty WordLists
        for( int j = 0; j < hashTable.length; j++ )
            // TASK: Change the following line to use generic version of WordList class 
            hashTable[j] = new WordList();
        
        // Create a Scanner object to read from TWL file
         
        Scanner scan = new Scanner(new FileInputStream("Z:\\TWL.txt"));
 
        while( scan.hasNext() ){
            String curStr = scan.next();
            
            // curKey below is an Integer for today's lab purposes
            // In hw5: curKey is the alphagram of curStr and should be a String  
            Integer curKey = getLabHashKey(curStr);
            
            // Create a new Entry instance
            // TASK: Change the following line to use generic version of Entry class
            Entry newEntry = new Entry(curKey, curStr);
            
            // For lab purposes we use curKey to get hashBucket 
            int hashBucket = curKey % hashTable.length;
            hashTable[hashBucket].addToHead(newEntry);
        }
        
        // Now use the wordList iterator to print 10 items from each list 
        for( int j = 0; j < hashTable.length; j++ ) {
            
            // Get the iterator for the j'th word list
            // TASK: Change the following line to use generic version of Entry class 
            Iterator<Entry> wordListIterator = hashTable[j].iterator();
            
            // Use the iterator to print 10 items
            int k = 0;
            while( wordListIterator.hasNext() && k < 10 ){
                // Prints ten (hashKey, dataValue) pairs for each wordList  
                System.out.print("("+ wordListIterator.next().getKey() + "," 
                                       + wordListIterator.next().getValue() + ") ");
                k++;
            }
            System.out.println();
        }
    }
}

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab09.html