Fall 2005»CSCI 221 Homework 4

CSCI 221 Homework 4

Assigned Date: Wednesday, Nov. 16, 2005 (sec 2 +1 day)
Due Date: Thursday, Dec. 1, 2005 (sec 2 +1 day)
Due Time: Noon

Last modified on November 17, 2005, at 03:32 PM (see updates)

Purpose

This assignment focuses on linked lists.

Assignment

Implement a TextAnalyzer ADT in Java. This ADT encapsulates a list of items stored using a sorted doubly-linked list with dummy head and tail nodes. The list contains unique words sorted lexicographically (case insensitive) and corresponding counts. Adding a duplicate word simply increments the corresponding count. Deleting a word, decrements the corresponding count. Deleting the last instance of a word, completely removes that word (and corresponding count) from the list.

In terms of implementation, TextAnalyzer objects should have three Node references, head, tail, and currentPosition. There should NOT be a numItems (or similar) variable, i.e., the length of the list will be calculated dynamically whenever it is needed.

Class Node should be implemented as an internal class. It should encapsulate a word and a count, as well as a prev and next link.

TextAnalyzer has the following API:

  • public TextAnalyzer()
    which creates an empty list, i.e., a list with two dummy head and tail Node objects linked appropriately.
  • public void add(String word)
    which adds word into the list, as described above.
  • public void remove(String word)
    which removes word from the list, as described above.
  • public int getFrequency(String word)
    which returns the count of the word, or zero if the word is not in the list. (Note: This should not be confused with the meaning of frequency in Physics.)
  • public double getProbability(String word)
    which returns the probability of the word to appear in the text, or zero if the word is not in the list. The probability of a word is defined as its count divided by the total number of words -- thatís the total number of words added to the list, NOT the number of unique words. (Another term for this is relative frequency.)
  • public void reset()
    which resets the current position to the beginning of the list.
  • public String getNextWord()
    which returns the current word and advances the current position. It returns null if current position is past the end of the list.
  • public int getUniqueWordCount()
    which returns the number of unique words in the list.
  • public int getAllWordCount()
    which returns the number of items added to the list (including duplicate word additions).

Bonus

Here is something extra for bonus points.

Documentation

Your code should be fully documented via javadoc. Your code should throw approppriate runtime exceptions to test preconditions and handle errors.

Include the following in each class:

       Certification of Authenticity:

       I certify that this submission is entirely my own work, 
       as per course collaboration policy.


       Name: ________________________ Date: ___________

Submission

  1. Open your BlueJ project.
  2. Ensure it contains the following: TextAnalyzer.java and README.TXT.
  3. Under the Project menu, click Create Jar File... . In the dialog box that opens, select Include Source, and press Continue.
  4. Email the generated .jar file to manaris@cs.cofc.edu, by the due date and time.