Link Search Menu Expand Document
CSE 143

Letter Inventory

Implementing data types by manipulating strings and arrays.

ed Workspace

Table of contents

  1. Method summary
  2. Development strategy
  3. Character arithmetic
  4. Character and string manipulation
  5. Grading
  6. Reflection
  7. Submission

Implement a LetterInventory class that represents an inventory of the 26 letters in the English alphabet. Each instance of the LetterInventory class keeps track of how many a’s, how many b’s, etc. are contained in a given string. For example, the letter inventory for the string “Washington State” corresponds to [aaeghinnosstttw]. The case of the letter is ignored, so ‘s’ and ‘S’ are exactly the same.

Get started by opening the ed Workspace above. Download the workspace to your computer to work on the assessment in jGRASP, which has helpful visualization and debugging tools. When you want to collaborate with course staff, copy your files from jGRASP into a new workspace and share the link with the staff member. (If you haven’t used jGRASP before, follow the CSE 14x Course Software setup instructions.)

Method summary

LetterInventory(String data)
Constructs an inventory (a count) of the alphabetic letters in the given string, ignoring the case of letters and ignoring any non-alphabetic characters. Store the inventory (how many a’, how many b’s, …) as an array of 26 counters (one for each letter) along with any other necessary data fields.
int get(char letter)
Returns a count of how many of this letter are in the inventory. Letter might be lowercase or uppercase. If a nonalphabetic character is passed, throw an IllegalArgumentException.
void set(char letter, int value)
Sets the count for the given letter to the given value. The given letter might be lowercase or uppercase. If a nonalphabetic character is passed or if value is negative, throw an IllegalArgumentException.
int size()
Returns the sum of all of the counts in this inventory. This operation should be fast in that it should store the size rather than having to compute it each time this method is called.
boolean isEmpty()
Returns true if this inventory is empty (all counts are 0). This operation should be fast in that it should not need to examine each of the 26 counts when it is called.
String toString()
Returns a String representation of the inventory with the letters all in lowercase and in sorted order and surrounded by square brackets. The number of occurrences of each letter should match its count in the inventory. For example, an inventory of 4 a’s, 1 b, 1 l and 1 m would be represented as “[aaaablm]”.
LetterInventory add(LetterInventory other)
Constructs and returns a new LetterInventory object that represents the sum of this letter inventory and the other given LetterInventory. The counts for each letter should be added together. The two LetterInventory objects being added together (this and other) should not be changed by this method.
LetterInventory inventory1 = new LetterInventory("George W. Bush");
LetterInventory inventory2 = new LetterInventory("Hillary Clinton");
LetterInventory sum = inventory1.add(inventory2);

The first inventory would correspond to [beegghorsuw], the second would correspond to [achiilllnnorty] and the third would correspond to [abceegghhiilllnnoorrstuwy].

Implement the add method efficiently. Do not call the toString method or otherwise build a String to pass to the LetterInventory constructor.

LetterInventory subtract(LetterInventory other)
Constructs and returns a new LetterInventory object that represents the result of subtracting the other inventory from this inventory (i.e., subtracting the counts in the other inventory from this object’s counts). If any resulting count would be negative, return null. The two LetterInventory objects being subtracted (this and other) should not be changed by this method.

Development strategy

One of the most important techniques for software professionals is to develop code in stages rather than trying to write it all at once. This development strategy is formally known as iterative enhancement or stepwise refinement. Writing code in stages enables software developers to test each stage independently for correctness.

We recommend developing the program in three stages:

  1. Constructing a LetterInventory and examining its contents. First, implement the constructor, size, and isEmpty methods. Then, implement the get method. Finally, implement the toString method. The testing program will test them in this order, so it will be possible to implement them one at a time.
  2. Methods for modifying a LetterInventory. Add the set method to the class, which allows the client to change the number of occurrences of an individual letter. The testing program will verify that other methods work properly in conjunction with set (the get, isEmpty, size, and toString methods).
  3. Complex behavior. Implement the add method and then implement the subtract method. The testing program first tests add, so don’t worry that the tests on subtract fail initially.

Character arithmetic

In a computer, all data are ultimately represented as numbers. The values of type char have corresponding integer values. There is a character with value 0, a character with value 1, a character with value 2, and so on. Dfferent values of type char can be compared using the less-than and greater-than operators.

if (ch >= 'a') {
    ...
}

All of the lowercase letters appear grouped together in type char (‘a’ is followed by ‘b’ followed by ‘c’ and so on). All of the uppercase letters appear grouped together in type char (‘A’ followed by ‘B’ followed by ‘C’ and so on). This numbering system allows us to determine the distance between two letters using subtraction. 'c' - 'a' is 2 since ‘c’ is 2 letters after ‘a’ in the alphabet. Likewise, if we want the character that is 8 letters after ‘a’ in the alphabet, we can use addition and then cast the result to type char.

char result = (char) ('a' + 8);

The variable result now stores the value ‘i’. Use this character arithmetic to determine array indices and offsets.

Character and string manipulation

The Java documentation for the String and Character classes provide several helpful methods for manipulating String and char data.

Reading documentation is a skill of its own. The Java documentation begins with a couple paragraphs introducing the class and its behaviors, but leaving implementation details out of the description. The String class documentation then contains three sections labeled Field Summary, Constructor Summary, and Method Summary. This style of documentation is similar to the method summary for this assignment: each summary includes the method’s return type, method signature (name and arguments), as well as a description of the expected behavior. The String methods are mostly instance methods because strings are objects.

The documentation for the Character class is similar, except that all methods are static because char is a primitive type. This difference means that manipulating strings requires different syntax from manipulating characters.

A String s is lowercased using an instance method.

s = s.toLowerCase();

But char values are not objects, so a char ch cannot call ch.toLowerCase(). Use the Character.toLowerCase static method instead.

ch = Character.toLowerCase(ch);

Grading

In terms of correctness, your class must provide all of the functionality described above and must satisfy all of the constraints mentioned in this writeup. In terms of style, we will be grading on your use of comments, good variable names, consistent indentation, minimal data fields and good coding style to implement these operations.

Introduce a class constant for the value 26 to make the class more readable. Make sure that the only public methods in the class are the ones described in the method summary.

The ArrayIntList class developed in the lessons provides a good example of the kind of documentation we expect you to include. You do not have to use the pre/post format, but you must include the equivalent information, including exactly what type of exception is thrown if a precondition is violated. Remember to mention all important behavior that a client would want to know about.

In addition, make sure to check your work for the following common style gotchas.

Commenting errors
  • Class header missing or doesn’t describe both student and program.
  • Method header missing or does not document pre and post-conditions.
  • Method header does not describe exceptions that are thrown when preconditions are violated, including the specific type of exception and the conditions under which it is thrown.
  • Method header does not document important behavior including subtle cases like an empty structure or a search value not found.
  • Blind copying of text from assignment writeup.
Readability errors
  • Bad indentation.
  • Method or constructor does not have a blank line before it.
Control structure errors
Data structure errors
  • Extra data structures that aren’t necessary.
  • Bad usage of arrays, e.g. unusual indexing/usage.
Class design errors

Reflection

Create a new file reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):

  1. What did you learn this week?
  2. What did you enjoy in the course this week?
  3. What did you find challenging or frustrating this week?
  4. What did you find particularly helpful for your learning this week?

Submission

Submit LetterInventory.java and reflection.txt to Grade-It!