CS 261 Lab E - LetterSet

Due Wed Oct 01 at 3:00pm

Overview

For this lab, you will implement an ADT that represents a "bag of letters". This class will keep track of the number of occurances of each particular letter in the set--so the word "banana" would have three of the letter 'a', one of the letter 'b', and two of the letter 'n'. Your ADT will include methods for checking what items are in the LetterSet, as well as combining LetterSets together.

This assignment will give you a chance to practice working with sets (though you won't be implementing the java.util.Set interface). You'll also be able to practice with performing some mapping operations, though your ADT won't just act as a map.

This lab will be completed in pairs. Partner assignments for this lab can be found on Moodle

Remember to review the pair programming guidelines before you get started!

Objectives

To practice implementing developing sets and maps
To learn a little about character encoding
To practice working with testing (and writing code to match tests--called test-driven development)

Necessary Files

You will be creating your new ADT from scratch. However, you may want to download the LetterSetLab.zip file, which contains a "tester" for your LetterSet that you can use to confirm that it works. (Note: you will need to comment out tests for methods that you haven't written yet!)

Background: Characters and Unicode

Java, like all computer programs, stores all data in 0s and 1s. This includes chars, thus the letter 'a' is represented in memory by a series of 0s and 1s. Since those 0s and 1s also can be seen as a binary number (that is, a number in base 2 rather than base 10), each char is directly associated with an int. The number that represents each letter is known as it's Unicode value.

Moreover, you can easily convert a char to its Unicode number by casting it as an int. Thus:

(int)'a' //=> 97 
(int)'b' //=> 98
//etc.

In this way, casting can be seen as a mapping function from char to int! So if you want to, say convert a character into a number (such as for determining its location in an array for this assignment), you can just cast it!

This also means that you can compare letters using < and >, in the manner you'd expect (because their unicode values are compared instead).

Lab Details

You should Read through all of these instructions carefully before you begin!

Your task is to create a new class called LetterSet that will represent a set of letters. Your class should have the following public interface:

LetterSet(String data)
Constructs a new LetterSet object that represents the alphabetic letters in the given string (ignoring the case of letters and ignoring any non-alphabetic characters).
- Important note: because this is a set and we don't care about order, we only need to worry about keeping track of the counts of each letter (as with the banana example above). As long as we know we have three 'a's, one 'b', and two 'n's, and zero of everything else, then we know what is inside the LetterSet.
- For fastest access, you should store your letter counts in an array. You can use casting as a mapping function to get a number (and hence an array index) associated with a particular letter
  - Note that although the first letter ('a') has a int value of 97, you should not have 97 blank entries in your array! Subtract an "offset" to have the 'a' go in index 0, the 'b' go in index 1, etc.
  - Remember to use CONSTANTS rather than "magic numbers" for things like offsets!
- In this ADT you should ignore case and any non-alphabetic characters. Check the built-in Character class for static methods that might help (e.g., toLowerCase).
LetterSet()
Constructs a new empty LetterSet object (all letters have count of 0).
int size()
Gives the "size" (the number of total letters) in the set.
- This method should be fast (run in O(1)). Keep track of your Set's size as an instance variable (adjusting it whenever the size changes) and simply return it here.
int getCount(char c)
Returns a count of how many of the given letter (ignoring case) are in the set. (Note that this is sort of like a map function!)
void setCount(char c, int num)
Sets the count of how many times the given letter (ignoring case) appears in the set.
- Hint: remember to update your size variable!
String toString()
Returns a String representation of the set. The letters should be listed in order, without spaces, inside curly braces. For example, an inventory of three a's, one b, and two n's would be represented as "{aaabnn}".
LetterSet add(LetterSet other)
Returns a new LetterSet object that represents the "sum" (the union) of this and the given LetterSet. This is like we put all the letters in the same bag--the new LetterSet has the sum of the counts of each individual letter. See the example image below:
- Make sure you create a new LetterSet object to return, and that the new object has the correct size!
LetterSet sub(LetterSet other)
Returns a new LetterSet object that represents the "difference" (the complement) of this and the given LetterSet. This is like we removed a set of letters from the bag--the new LetterSet has letter counts that are the current counts minus the counts of the other set. If any of the letter counts would be negative (so the parameter cannot be subtracted), this method returns null.
- Make sure you create a new LetterSet object to return, and that the new object has the correct size!

You can test your class using the provided tester. However, I recommend you create your own tests (and/or use the debugger!) to make sure that everything works.

Submitting

Make sure both your names are on the LetterSet class. Once you're finished, upload the src code to the LabE submission folder on hedwig. One partner should to upload the code--we will only grade one partner's copy of the program. Make sure you upload your work to the correct folder! The lab is due at the start of class the day after lab.

After you have submitted your solution, log onto Moodle and submit the Lab E Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded out of 20 points:

[1pt] Your ADT properly uses an array to store letter counts
[2pt] Your ADT implements both constructors
[1pt] Your constructor ignores case as non-alphanumeric characters
[1pt] Your size() method works properly
[1pt] Your size() method works in O(1) time
[1pt] Your getCount() method returns the proper count
[1pt] Your setCount() method sets the letter count for the given letter
[1pt] Your setCount() method updates the size of the set
[2pt] Your toString() method returns a properly formatted string (letters in order in braces)
[2pt] Your add() method returns the union of the two LetterSets
[1pt] Your add() method returns a new LetterSet object with the correct size
[2pt] Your sub() method returns the complement of the two LetterSets
[1pt] Your sub() method returns a new LetterSet object with the correct size
[2pt] Your sub() method returns null if the sets cannot be subtracted
[1pt] You have completed your lab partner evaluation