CSCI 151 - Lab 4 - Spring 2009 Email directory

11:59.59pm, Sunday, March 8 Wednesday, March 11

Project Description

This week we are going to implementing a doubly linked list and using it to run an email directory application. You'll also implement your first "real" iterator and can use it in your project.

The directory information that I'm supplying has been culled from a number of campus sources, but should not be made available to anyone outside this class. This includes posting it on web sites.

NOTE: You may work with a partner on this assignment. I know that this means that some groups will have 2 people working on pieces individually instead of as a group. I'd like it if you initially sit down together and discuss the design of the overall program before splitting up the work instead of just trying to meld the two pieces together at the end.

NOTE: We're working on a way to easily share files between you and your partner. It should be working by the end of Monday, so during lab today, just use one person's account and look for an update in this space.

Getting started

Since I don't want the data files distributed outside the class, you'll need to copy the jar file from a lab machine instead of downloading it. 

    cp ~kuperman/pub/cs151/lab4.jar .

Part 1 - creating a doubly-linked list

You'll be creating a doubly linked list called MyLinkedList and an iterator for that class.

MyLinkedList

This is just a subset of LinkedList and should have the same behavior for the methods you write.

You should extend AbstractList and implement the Iterable interface. I've already done so in the sample file provided to you.

Be sure to test your implementation thoroughly. In doubly linked lists, the removal of items can be especially tricky as you need to be sure to properly update the neighbor's next and previous pointers, as well as handling the special cases for removal from the front or tail.

We will not be permitting "null" pointers to be inserted into the list. You should throw a NullPointerException if someone attempts to do so.

Constructors

You only need a 0-argument constructor that creates an empty list.

Private Methods

Create a getNth() method that returns the node at a specified index, not the content.

Public Methods

boolean add(T data)
void add(int index, T data)
add an element into this list (either at end or by index)
throw a NullPointerException if the user tries to add a null pointer
throw IndexOutOfBoundsException as needed
T get(int i)
get object at position i
throw IndexOutOfBoundsException as needed
T set(int i,T data)
set the value at index i to data
throw NullPointerException if data is null
throw IndexOutOfBoundsException as needed
T remove(int i)
remove the element from position i in this list
throw IndexOutOfBoundsException as needed
void clear()
remove all elements from the list
boolean isEmpty()
determine if the list is empty
int size()
return the number of elements being stored

Additional methods

These are methods that weren't in MyArrayList, but might be useful in a LinkedList.

T getFirst()
return the first element in the list
throw NoSuchElementException if the list is empty
T getLast()
return the last element in the list
throw NoSuchElementException if the list is empty
T removeFirst()
remove and return the first element in the list
throw NoSuchElementException if the list is empty
T removeLast()
remove and return the last element in the list
throw NoSuchElementException if the list is empty
void addFirst(T data)
insert the item at the front of the list
throw a NullPointerException if the user tries to add a null pointer
void addLast(T data)
insert the item at the end of the list
throw a NullPointerException if the user tries to add a null pointer

Iterator

There is a skeleton of an iterator factory method included in the file. You need to implement hasNext and next in order to make it work.

Programming hints

You'll probably want to create a nested class to represent a node in your linked list. Remember that to do this, you can't declare the class as public, but you can include it in the same file as MyLinkedList. Also, since you'll need to be modifying these nodes, you might want to consider creating private methods in MyLinkedList that return a reference to a node instead of the data inside the node.

Testing

You should be able to re-use the tests you wrote in Lab 1 for MyArrayList. Just make changes similar to 

    List<String> x = new MyLinkedList<String>();

Part 2 - Directory

For this part of the project, I want you to create a directory application that will let you have a personal list of email addresses as well as the ability to query the whole student directory.

DirectoryEntry

You first are going to create a class that can hold an entry and has methods that make it useful for searching. The fields that must be supported are:

  1. First name: a person's first name
  2. Middle name: a person's middle name
  3. Last name: a person's last name
  4. Nickname: a person's preferred name
  5. OCMR: mailbox number
  6. Email: their full email address
  7. Dorm: their residence hall

And you may add to these if you want. However, for the equals() method, these are the only fields that matter.

You can also optionally support listing of a student's major. Students can have up to 3 majors, and these are the last 3 fields in the data lines. If you do support using it, I'd suggest you allow for the equals to match in any position.

The equals() method

For the method with signature boolean equals(Object), I want you to apply the following rules:

  1. Matches must be made in case-insensitive fashion. However, the case that is displayed to the user must allow for mixed case. (I.e., don't just turn everything into lower case)

    "Benjamin" matches "BeNjAmIn" but prints differently

  2. A blank string (i.e., "") should match anything. So, if there is no nickname entered, you should allow any nickname to match.
  3. A string that ends in '%' should be used to match from the beginning up to, but not including the '%' [see String.startsWith()], all other strings should match for the full string. For example 
            "Ben"  doesn't match "Benjamin"
        "Ben%" matches       "Benjamin"

Programming Hints

You should notice that you are performing the same non-standard string comparison for each of the fields. It might make sense to write one method that compares 2 strings and then just use that. Cutting and pasting will likely lead to difficult to track down errors.

A toString() method that matches the input format wouldn't be a bad idea.

Directory

Now create a class Directory.java that will act as your interface to manipulating these DirectoryEntry objects (which you'll be storing in MyLinkedLists).

Command line arguments

If an argument is provided, use it as the source file for your data. If not, just use "directory.txt". 

    % java Directory <data file>

If none is specified, use "directory.txt" for the directory. 

    % java Directory

The directory file should be considered a read-only list similar to your phone book -- don't add or remove from it.

Input file format

Entries are to be stored between runs of the program in flat text files. The format of the files is one entry per line with fields separated by ':' characters. 

    First:Middle:Last:NickName:Email:OCMR:Dorm:Major1:Major2:Major3:

For splitting the line, you might want to look at String.indexOf() methods or String.split().

Note that there will be many entries with blank values such as no dorm or middle name listed. I found using split(":",-1) to work fairly well and it would have empty strings in blank areas like we want.

Commands to be supported

Your Directory program should support the following operations. You may implement additional functions for consideration for extra credit.

You may use any interface that you'd like. You could have a set of numbered menu choices, or you could have user input commands on a command line. The general idea is that the user can continue to narrow down the list of students with a sequence of searches. So you could find out how many people's have a last name beginning with "Z" live in Dascomb, or how many people have "A" as their middle initial.

After each operation, print out how many items are in the list.

  1. Print out a help message to the user explaining your commands.

  2. Save personal list to a file -- only save when the user requests it. Ask the user for a file name and then dump the current list to that file.

    Here's how to create a PrintWriter

    PrintWriter outFile=new PrintWriter(
                    new BufferedWriter(
                    new FileWriter("personal.txt")));

    and now you can use 'outFile' just like 'System.out' 

    outFile.println("This line will be in personal.txt");
outFile.print("this has no newline");

    Note: when you are done writing to your file, you need to close it. Normally, this is done when your program exits, but students have been reporting problems with this. 

    outFile.close();
  3. Revert back to the original list -- you can just read it back in from the file on disk.
  4. Search the directory
  5. Display the full list of directory entries with index numbers

Extra features

Additional features you might consider adding:

Programming hints

Recall that you are implementing MyLinkedList so that it has a subset of the java.util.LinkedList methods. This means that you can build and test your Directory application separate from the MyLinkedList program. However, you need to first write the DirectoryEntry class that you will be using.

Sample runs

  1. lab4-run1.txt in which I search the class
  2. lab4-run2.txt in which I investigate the mystery of "Ben"

handin

Look through your programs and make sure you've included your name at the top of all of them.

README file

You need to create a file called "README" that contains the following information:

  1. Your name and your partner's name
  2. Any known problems or assumptions made in your classes or program
  3. Anything you've implemented for extra credit

If you have suggestions for improvements to this lab, feel free to add them to this file too.

Honor code

If you adhered to the honor code in this assignment, add the following statement to your README file:

I have adhered to the Honor Code in this assignment.

handin

You now just need to electronically handin all your files. Assignment is 4.

Don't forget to run lshand and verify that things were submitted.

Lab Goals

This lab is intended to:

Last Modified: March 01, 2009 - Benjamin A. KupermanVI Powered