CSE 132 (Spring 2015)
Lab 2a: KWIC Index (ADT Review and I/O)

Abstract:

In CSE 131, you studied the following ADTs:

• Map implements a function, and
• Set is a duplicate-free collection of objects.

In the upcoming studio and lab sessions, you will design an interface for using the KWIC index and add some interesting features.

Getting Started

1. You are encouraged, but not required, to work in pairs on this lab.

   • If you work in pairs, then do all the work together in one person's repo.
   • When you demo, indicate that you want the results propagated to the other person's repo.

2. Use Eclipse version 3.7 or later for this lab. It is available on all of the lab machines.
3. Open Eclipse and update your repository.
4. Look for the kwic package in the labs source folder.
5. Run the KWICTest class as a JUnit test.

   It should fail at this point with a NullPointerException.

Overview

Supose you wanted to search a document for all phrases that include a given word, say "swordfish". There are two approaches that could be used in this endeavor:

1. Once "swordfish" is supplied, a computer could search the document and return each phrase that contains that word. Every time a word is supplied, the entire document is scanned to find matching phrases.
2. The document could be preprocessed offline , in anticipation of the need for search. When "swordfish" is supplied, the result is already computed and simply returned.

• How stable is the document? Do phrases come and go or is the document relatively constant?
• How often is the same word supplied for a search? Would "swordfish" be supplied many times or just once?

We shall assume that offline preprocessing pays off, and that it would be expensive to search the document each time a word is supplied. As an analogy, consider the difficult task undertaken by Google to index the WWW. Imagine how slow it would be for Google to search the entire WWW each time you ask it to find a word.

As an example, consider the following phrases:

• Swordfish goes well with pasta; the pasta should not be overcooked.
• The password for entry to the castle is: "swordfish".
• All's well that ends well.

The following table shows how phrases should be returned for words that might be supplied for KWIC:

Word	Set of Phrases
swordfish	Swordfish goes well with pasta; the pasta should not be overcooked. The password for entry to the castle is: "swordfish".
Well	Swordfish goes well with pasta; the pasta should not be overcooked. All's well that ends well.

Notice that case and punctuation do not matter in matches, but that the returned phrases are exactly as they were entered. Also, although "well" is contained twice in one phrase, the set of phrases contains each phrase once (as sets are supposed to do).

You can find may sites that offer KWIC or concordance indices. For example this site has Shakespeare's works. Check out the results for rogue.

In summary, our KWIC index will:

1. Process lines of text, decoding each into words.
   • A line of text is represented by an instance of the Phrase object.
   • A word is represented by an instance of the Word object.
2. For each Word in a Phrase, remember that the Word occurs in that Phrase. We accomplish this using the ADT Map<Word, Set<Phrase>>. Each Word is mapped to a Set of Phrases that contain the Word.
3. On demand, produce all Phrases that contain a given Word. The Map makes this easy.

Implementation notes

• Be sure to consult the documentation, as it specifies what must be done by each method

  Remember that the summary of a method just contains the first line of the documentation. The rest is found in the detailed section of the JavaDoc. You get there by clicking on the method name in the summary section or by scrolling down.

  For example, see the Phrase documentation, which mentions the equals method in the summary. But the detailed documentation is found by clicking on the equals method.

• As much as possible, use the shorthand notation for iteration.

  For example, if you have a Set<Word> s, then you can iterate over its words using the relatively beautiful:

  for (Word w : s) {
  }
  

  instead of the relatively ugly:

  Iteration<Word> i = s.iterator();
  while (i.hasNext()) {
     Word w = i.next();
  }
  

  Your code will be penalized for failure to be concise and clear, so use the short form of the iteration.

Classes

KWICTest

• This is written for you. You are welcome to add tests, but your code must pass this test when this lab is due.
• This contains the unit testing for your lab. You should use this incrementally as you develop, as the early tests will exercise your Word and Phrase classes. The later tests build up to testing the KWIC class.
• The last test (test()) runs the same exercise on two KWIC objects: one is generated from an array of Strings, and the other uses the File I/O that you must implement in KWIC.

  Get your lab working first without doing the File part.

WordFilter

will show up in the documentation, because I found it useful to have a separate class for this. You do not necessarily need to write this class.

Word

• Work on implementing this class first. When it is done, the testWord() part of the KWICTest should pass.
• Follow the comments in the Word file, and get help where things don't make sense.
• It will be important that equals and hashCode work properly. Moreover, all objects must obey the hashCode() and equals() contracts. You can have Eclipse generate those automatically, but you will have to modify them so that Word objects compare as equal if their matching versions are the same.
  • Consider two Words, one constructed for "DOG" and one for "dog".
  • The getOriginalWord() form of each Word will be different.
  • The getMatchWord() form of each Word will be the same.
  • The hashCode of the two words must be the same, even though the original words are different.
  • Each of the two Word objects should equal each other, even though the original words are different.
  • The above is tested by the following code in your KWICTest unit test:

    Word w = new Word("Dog");
    assertEquals("Dog", w.getOriginalWord());
    assertEquals("dog", w.getMatchWord());
    assertEquals(new Word("dog"), w);
    assertEquals(new Word("DOG"), w);
    assertEquals(new Word("DOG").hashCode(), new Word("dog").hashCode());
    

Phrase

• There is less work to do here than meets the eye.
• You can leave equals and hashCode alone for now.

  But be sure to fix them up before you test!

• For getWords()

  You must use StringTokenizer to break apart the String into words. This is something you are supposed to learn in CSE132.

  Build a Set of Words from the tokens and return that Set in this method.
• cleanUp(String s) must also be implemented as described in the comments. Look through the String API for methods that might help you do this easily.

KWIC

• The methods that require your attention have FILL ME IN comments in them.
• Although the method addPhrases(File) is near the top of the file, leave its implementation for last. Once you get everything else working, your code should pass the first half of the KWICTest.

  Notes about reading the input file:

  • In Studio 2, you read a file using the DataInputStream.
  • While you might be tempted to use its readLine() method, that has been deprecated, so don't do that!
  • Follow the advice given in the JavaDoc for DataInputStream's readLine().
  • This should lead you to BufferedReader's readLine() to read one complete line of the input file.

  You can also open the fortunes.txt file in Eclipse to see how it looks.

• The PropertyChangeSupport code in the class should be left as-is, and will be used in the next installment of this project. These calls will notify your swing implementation (next lab) that the KWIC object has changed.

For the Demo

• There is some dispute among us as to how many "you" words occur in the target text.

  • If you find 68, or 70, or 71, or something like that, that's fine; change the unit test if you need to for that.
  • You may be overlooking commas, and a nice way to get rid of stuff is the replaceAll(String,String) method. That in turn will expose you to regular expressions, which is something good to know.
  • Ask for help if you need it!

• If you are having trouble passing unit test, it's likely that the equals and/or hashCode methods are not properly defined for Word or Phrase.

  Review the material here (slides 44 and beyond) to gain an understanding of how those two methods work:

  • Think of hashCode as a mapping from the object at hand to a bucket. If the object you seek is anywhere in the collection, then it will be in the bucket indicatded by hashCode. The contract for those methods insists that:

    if a.equals(b) then a.hashCode() == b.hashCode()

  • For Word and for Phrase, define each using the mechansim by which you judge one instance of the object to be equal to another instance of the same type of object. For example, when should two Phrase equal each other?

Submitting your work

• Make sure you completed the cover-sheet
• Make sure your work is committed
• All team members must be present

Demo

When you done with this studio, you must be cleared by the TA to receive credit.

• Commit all your work to your repository!

  If you do not commit, the TAs cannot grade your work and you will receive a 0 for this assignment!

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

	Last name	WUSTL Key	Propagate?
		(or your numeric ID)		Do not propagate
e.g.	Smith	j.smith
1				Copy from 1 to all others
2				Copy from 2 to all others

---

TA: Make sure they commit their code before you sign them out!

TA: Password: