Project #2: You Won't Find Me There

Due date and time: Wednesday, April 20, 11:59pm

This project is to be done in pairs using the "pair programming" technique

Introduction

Most of us have lived in more than one home in our lives; it's common for people to move from time to time. Moving poses a number of logistical challenges, not the least of which is getting all of your belongings to your new home. But even discounting the complexity of the physical move, there are other issues to be dealt with. One of them is making sure that people and companies that you correspond with — friends, employers, banks, utility companies, and so on — have your new address, so your correspondence can continue even after your move.

Try as we might to give everyone our new address when we move, though, there's always someone we forget — some friend we haven't heard from in years, some company that we do business with only rarely — or someone who doesn't make the appropriate change in their records. Fortunately, the U.S. Postal Service provides a service called mail forwarding. Any mail addressed to you at your old address will automatically be sent to your new address instead. They even put a yellow sticker on the envelope to remind you that you should notify the sender of your new address. Very handy!

In this project, we'll explore the technological side of mail forwarding a little bit, by writing a program that determines whether individual pieces of mail should be forwarded and, if so, what address they should be forward to. Along the way, you'll gain experience implementing your own data structure called a singly-linked list. You'll also learn how to implement generic classes, which are generic in the same way that ArrayList is generic — ArrayLists take a "type parameter" that configures what kinds of objects they store (e.g., ArrayList<Student>).

Choosing a partner

Pair programming is again required on this project, so you'll need to choose a partner from among the people enrolled in your lab section, different from the people with whom you've partnered previously.

If you're having trouble finding a partner, notify your TA, so that you can be assisted in finding one. If you have not found a partner and notified your TA of the pairing by the end of the lab meeting on Wednesday, April 13, you will be assigned a partner and notified via email; once your TA has selected a partner for you, we will not allow you to switch to another one.

You will not receive credit on this assignment if you work on it alone without the prior consent of the instructor. (Please note that "prior consent" does not include approaching us the day the project is due, having completed it on your own, and telling us that you haven't been able to find a partner.)

The program

Your program will maintain a list of forwarding entries, each consisting of a name, an old address, and a new address. The program consists of commands that allow the user to add a new forwarding entry, remove an existing forwarding entry, or report on the correct address to send a piece of mail, based on the address on the envelope.

The program should support the following commands:

Command Format Description Output
ADD ADD
name
old address
new address
Adds a new forwarding entry to the forwarding list, given the name, old address, and new address. Subsequent mailings to the named person at the old address will be forwarded to the new address. If an entry with the same name and old address exists already, adding should fail with an error message. If a forwarding entry is added, the output should consist of the word Added on a line by itself. If not (because an entry for the same name and original address exists), the output should consist of the phrase Entry already exists on a line by itself.
REMOVE REMOVE
name
old address
new address
Removes the forwarding entry from the forwarding list with the given name, old address, and new address, if there is one. Subsequent mailings to the named person at the old address will not be forwarded. If a forwarding entry is removed, the output should consist of the word Removed on a line by itself. If not, the output should consist of the phrase No such entry on a line by itself.
MAIL MAIL
name
address
A piece of mail is ready to be sent; it is addressed to the given name at the given address. This command checks to see if the mail should be forwarded to a different address. This command should output the phrase Send to, followed by the address that this piece of mail should be sent to, on a line by itself. (If the mail is to be forwarded, its forwarding address should be printed; if not, its original address should be printed.)
QUIT QUIT Quits the program. The output should consist of the word Goodbye on a line by itself.

Your program should read a sequence of commands from the console (System.in) and write its output to the console (System.out). It should print no prompts or other output, other than the output required in response to each command, as specified above.

A few minor, but important, notes

When you first start your program up, the list of forwarding entries should be empty.

The mail forwarding supported by your program should be recursive. For example, suppose that the following two forwarding entries are in the program's forwarding list:

If a piece of mail is sent to Alex Thornton at 123 Main St., Irvine, CA 92697, the program should determine that it should be forwarded not to 234 Main St., Irvine, CA 92697, but to 111 Beach Dr., Kihei, HI 96753. (Note that you do not have to write your code recursively; you can use a loop to solve this problem instead.)

Your program is not required to parse or understand names or addresses; it's fine if they're stored as strings, and it's also fine if your program only considers a piece of mail to match a forwarding entry if the name and old address match exactly.

An example of the program's execution

The following is an example of the program's execution, as it should be. Boldfaced, italicized text indicates input, while normal text indicates output.

    ADD
    Alex Thornton
    123 Main St., Irvine, CA 92697
    234 Main St., Irvine, CA 92697
    Added
    MAIL
    Alex Thornton
    123 Main St., Irvine, CA 92697
    Send to 234 Main St., Irvine, CA 92697
    MAIL
    Jane Doe
    123 Main St., Irvine, CA 92697
    Send to 123 Main St., Irvine, CA 92697
    ADD
    Alex Thornton
    234 Main St., Irvine, CA 92697
    111 Beach Dr., Kihei, HI 96753
    Added
    MAIL
    Alex Thornton
    123 Main St., Irvine, CA 92697
    Send to 111 Beach Dr., Kihei, HI 96753
    QUIT
    Goodbye
    

Notice, again, that there are no prompts or other output, other than the output that is required as a response to each command. This may seem strange, but there's a good reason for it, which is described a little bit later in the write-up.

Fair assumptions

It's fair to assume that your program will only receive valid input. We will not test your program with non-existent commands, nor with existing commands in the wrong format. This is not to say, of course, that error handling is unimportant in real programs, but it adds a level of complexity to this program that's more than I'd like you to be faced with. (You're free to implement error checking if you'd like, but it's not something that extra credit will be offered for.) In the event that your program receives input that doesn't follow the specifications above, it's fine for your program to ignore it, print an error message, or even crash; we won't be testing your program in these circumstances.

It's also fair to assume that there will be no "cycles" among the forwarding entries. In other words, you can assume that it will never be the case that two or more forwarding entries will exist like these, where mail is forwarded back to an address it originally came from:

Consider what would happen if we allowed entries like these to exist simultaneously. If someone sends mail to Alex at 123 Main St., Irvine, CA 92697, where should it be forwarded? To 234 Main St.? Back to 123 Main St. again? Then on to 234 Main St. again?

Your program need not check for this case. You can simply assume that this case will never come up, and we won't test your program in this case. It's fine for your program runs infinitely or even crashes in this case. (An algorithm for solving this kind of problem, which is called a cycle in a data structure called a graph, will be covered in ICS 23 / CSE 23.)

Storing your forwarding list

One of the central tasks that this program will perform is to store and access a list of forwarding entries. There are two primary ways we store lists of elements in most programming languages:

Since we explored the use of ArrayLists in the last project, you are required to use a linked list to store your list of forwarding entries in this project. It's fine to use a singly-linked list with a head reference, which I'll be describing in more detail during lecture; in this project, using a more complex variant of linked list provides little benefit, though we'll learn about situations later this quarter where a little extra complexity makes a big, positive difference.

Starting point

As a means of getting you started, I'm providing some code as a starting point. In particular, note that I've provided the main( ) method, which you should use without modification, as well as a skeleton for your LinkedList<E> class, which you are required to complete, rather than starting your own from scratch.

The starting point is available as a Zip archive.

Wait... what kind of crazy user interface is this?

Unlike the program you wrote in your last project, this program has no graphical user interface, or even an attempt at a "user-friendly" console interface. It's a fair question to wonder why there isn't one. Not all programs require the user-friendly interfaces that are important in application software like Microsoft Word or iTunes, for the simple reason that humans aren't the primary users of all software. For example, consider what happens when you used your web browser to load this page:

The details of how the web works are not the point of this assignment, but this example serves to suggest that not all software needs a clean, "user-friendly" interface. A web server is intended to simply run quietly for months at a time with no human intervention required. It may write some information into a log once in a while, especially when something goes wrong, but otherwise it does nothing but listen for requests (which are generated and formatted by browsers, in response to user activity) and respond to them appropriately.

Now consider again the requirements of the program you're being asked to write for this project. It waits for requests to be sent in via the console — though they could almost as easily be sent across the Internet, if we preferred — in a predefined format, then responds using another predefined format. Our program, in essence, can be thought of in the same way as a web sever; it's the engine on top of which lots of other interesting software could be built. When a new address change is added to the system, that could be coming from a web form filled out by a user. When an address is sent to the system to see if there is a forwarding address, that address could be typed by a human user in the post office, or even scanned (e.g., using optical character recognition, or OCR) automatically from the envelope with little or no human intervention. When a piece of mail is being processed and our program says to send it anywhere other than the original address, that could cause a yellow label to be printed and automatically placed on the envelope by a machine.

While we won't be building these other interesting parts, suffice it to say that there's a place for software with no meaningful user interface; it can serve as the foundation upon which other software can be built. You can think of your program as that foundation.

Testing

The previous project required you to write a test plan, detailing what specific actions you would perform to test your complete program when you were done with it. Testing a program as a whole is an important part of making sure that the program works, but relying solely on whole-program testing leads to at least a couple of problems:

We'll be discussing unit testing in lecture, a technique which supplements whole-program testing like you did in the previous project, by allowing you to get feedback about whether individual methods and classes are working correctly. A necessary — but not sufficient — condition for a large program to work correctly is that all of its individual pieces are working correctly. Of course, showing that the pieces are correct doesn't necessarily show that the program as a whole is correct, as there may also be problems with the way the pieces interact with one another. But if the pieces themselves don't work, the whole program certainly can't.

For this project, I'm requiring you to build an automated tester like the one we'll build in class for the biggest( ) method. (After we've had that conversation in lecture, check out the Course Home Page section of the web site if you'd like to see the "biggest" tester again.) This tester program should test your LinkedList<E> class as completely as possible. You are not required to test other parts of your program, though you're welcome to do so if you wish. (Note that testing the console-mode input and output can be problematic, requiring skills that we don't have under our belts yet, so this is probably best avoided for the time being.)

Your tester should be a separate program — a separate class from the others in your program, with its own main( ) method, different from the main( ) method in the provided ForwardingProgram class — which behaves in the same manner as the tester we wrote in lecture: it should write output only when a test case fails, and that output should specify what the inputs were, what the result was, and what the expected result was. Remember that the goal of an automated tester is to point out where the problems are, giving information about what failed, without cluttering the output with information about what succeeded.

Like the test plan in your last project, there is no predefined number of test cases that must be included; your tester is complete when all of the important cases are included. Pay attention to normal cases, boundary cases, and error cases. Note that the iterator is part of the linked list, so it's necessary also to test the iterator.

As we discussed in lecture, be sure that you're not duplicating large chunks of code in your tester. It should be possible for you to write one method that executes one kind of test case, based on a set of parameters; you can then use that method to run several similar kinds of tests.

Deliverables

It is only necessary for one of the two partners to submit the project; the TAs are aware of the partnerships and will figure out which project submissions belong to which pairing. Put the names and student IDs of both partners in a comment at the top of each of your .java files, then submit all of the .java files, including the ones that we provided to you, to Checkmate. Please do not turn in the .class files, or other files generated by Eclipse. Afterward, take a moment to be sure that you submitted all of the files; if you missed one, we won't be able to compile and run your program, which can result in a substantial penalty, since we won't be able to evaluate your program's correctness.

Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're responsible for submitting the version of the project that you want graded. We won't regrade a project simply because you submitted the wrong version by accident.

Limitations

The Java library contains a LinkedList class (java.util.LinkedList), but you are not permitted to use it in this project. It's a nice class to use in a practical context, but since one of the skills I'd like you to gain in this project is learning how to build your own linked list, the prebuilt version in the Java library is strictly off-limits.

Acknowledgements