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, the address to which they should be forwarded. 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).
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 which a piece of mail should be sent, based on the address on the envelope.
The program should support the following commands: See image.
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.
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. (Note that you do not have to write your code recursively; you can use a loop to solve this problem instead.) 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.
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.
The following is an example of the program's execution, as it should be. Boldfaced, italicized text indicates input, while normal text indicates output. See image.
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.
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.)
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.
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.
There is less code provided in this project than the previous one, because we'd like you to begin thinking more carefully about how to design a program. It is important to realize that the go() method in the Forwarder class — which is called from the main() method in ForwardingProgram — is where the user interface begins, but the entirety of your user interface shouldn't be written in this one method. Instead, you should consider ways to split this large problem into smaller ones (e.g., separate methods for each of the user interface's commands).
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 use JUnit to write unit tests for your LinkedList
Aside from your LinkedList E class, 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 ouptut can be problematic, requiring skills that we don't have under our belts yet, so this is probably best avoided for the time being.)
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.