Program 7

Programming Using Collection Classes

Informatics Core II
INF-42

Introduction This programming assignment is designed to ensure that you know how to use combinations of collection classes to model and solve a wide variety of different programming problems. The kind of abstract thinking that goes into modeling solutions to these programming problems with collection classes is critical to your development as computer scientists. Collection classes are important and useful themselves, and they also rely on almost everything powerful that we have learned about Java: interfaces, classes in an inheritance hierarchy, casting, and general pupose iterators; and the complexity classes of their methods are also characterized using big-O notation. OK, I don't mean to oversell this assignment, but I do think that it is important: the final in-class programming exam will be devoted to writing a program, similar to these, using collection classes.

You will write five different programs (and one two ways) for this assignment, each requiring a "small" amount of code, mostly in a main method (and maybe a static helper method or another class). The collection classes you will use are sets, lists, and maps. You should write these programs using Generic collections. For parts 3 and 4 below, you have to write at least one solution without generics: using Object and casting when necessary.

We will discuss in lecture, a program using collections to read a file and produce a frequency count (printed two ways) of the tokens it contains. That problem appears at the end of this assignment. IMPORTANT: Some programs read semi-colon separated tokens from files. To do this, use the readline method and then construct a StringTokenizer for the line, which has ";" as its second argument.

My solutions to all these programs take 3-4 dozen lines each.

  1. Read files describing categories/words and the structure of sentence and generate a random sentence

  2. Read files describing breed/names and adoptions by breed and assign names to each adopter

  3. Read files describing all names/credentials and name/credential queries for validation, and determine whether the name in each query has all the required credentials

  4. Program that solves same task as #3, but uses non-generic classes. Solve it by modifying your code after solving #3.

  5. Read files describing the states/transitions of a machine and the input to a machine and execute the machine on the input

As always, you can check the behavior of your programs against mine by downloading, unzipping, and then running the file Program #7 Executables, to help you understand the specification of the problem and observe the programmer/user interaction that you are to implement.

Each of the first four programs has its own download, which includes a detailed description of the problem (just like you will receive during the In-Class Programming Exam). The final program is described in greater detail below, and you can download and unzip a Start Project Folder which contains the files needed for this programs. In all these programs, you write the main method in each class.

Only one programmer of the pair should dropoff the programs. It doesn't matter which of the pair submits. Of course, the program should contain both student names (in the comment: the same one you cut, pasted, ane filled in at the top of each program in Program #1).

I hope that while it might take you a while to complete the first few programs, that once you get accustomed to thinking about and using collections, that you will be able to write the last programs (which are more complicated) at the same speed.

General Information For problems in this exam suite, you must be familiar with the Java interfaces for OrderedCollection, List, Set, Map, Iterator, Comparable and Comparator. In addition, you must understand the use of the classes ArrayQueue, ArrayStack, ArrayPriorityQueue, ArrayList, HashSet, HashMap, which implement these collections, as well as StringTokenizer, including its two-parameter constructor whose signature is (String,String). You must also understand the use of the static sort methods defined in the Collections class, which uses the Comparable (and optionally the Comparator) interface. Finally, you should be familiar with casting generic (Object) references, when necessary. By using Collection Classes with Generics, you get this extra type-checking and avoid explicit casting; but you will have to write one program both using and not using generics.
Sample Collection
Exams #1-#4		 Examine and solve each of the following Sample Exams.
  1. SPE1: Random Sentence Generation
  2. SPE2: Animal Shelter
  3. SPE3: Validate Credentials
  4. SPE4: Machine

    Remember that SPE3 requires two solutions: one using Generics and one not using Generics.

Word Frequency Simple Statement: Read a file of words, building a map (Map[String] -> Integer) from each word to its frequency (the number of times that it occurs in the file), and print the map in two different ways. Then build a list (List[Map.Entry]) consisting of the word/frequency pairs in the map. Sort and print this list twice: first with the word/frequency pairs ordered alphabetically; second with the word/frequency pairs ordered from highest to lowest frequency (words with equal frequency can appear in any order).

Details: The following details describe more precisely the program that you are to write.

  1. Create the map while processing the input file using the standard call to readAllTokens and the StringTokenizer class; you can also read a line at a time, and use a StringTokenizer to process the line, but this is a bit more complicated and lines are not important in this problem.

  2. When printing the map (and later the list, twice) use a single line of Java code each time, calling the standard toString method on the collection being printed (either implicitly or explicitly).

  3. Build the list using the Map.Entry objects stored in the map.

  4. To sort the list,or write two small classes that implement Comparator) specifying the ways to order the Map.Entry objects stored in the list. Call them Alphabetically (I have written this one) and ByFrequency (you must write this one). Recall the Map.Entry interface supports both getKey and getValue methods to get the data you are going to sort by (keys alphabetically, values by frequency). Note the both the String and Integer wrapper class have a comapreTo method you can call.
Sample Input: Test your program on the input file input1.txt, which contains the following data 
  w x y z
  w x y
  w x w a c
  a b
  c
Sample Output/Interaction: The program will have the following interaction (computer-output appears bold-faced; user-input does not) 
  Enter name of file of words: input1.txt

  Map:
  {b=1, x=3, a=2, w=4, z=1, c=2, y=2}

  List (sorted alphabetically):
  [a=2, b=1, c=2, w=4, x=3, y=2, z=1]

  List (sorted by frequency):
  [w=4, x=3, a=2, c=2, y=2, b=1, z=1]