Contact List Application

There are many faculty and staff on campus who you might want to interact with, but finding everyone can be a challenge! In this part of the lab, we will create an application that creates a list of contact information for each faculty and staff member in the College including their office number, then we will use that list to allow users to look up peoples’ office numbers based on their names.

To make the application as fast as possible with lists, we will maintain the list in sorted order (based on peoples’ names), then use the binary search algorithm to find a person, based on the input from a user.

Contact Information

For each faculty and staff member in the College directory, we will maintain a Contact object, where the Contact class simply has two instance variables: name, storing the person’s full name (recorded as <last name>, <first name>, e.g., Eck, Adam) and office, storing the location of their office (e.g., King 125B). We have provided you with a FacultyStaff.txt file in your GitHub repository that contains all of this information.

Selection Sort Algorithm

To keep our list of Contacts sorted, we will use the selection sort algorithm. Its pseudocode is:

  1. Loop through each index i of your list of Contacts from 0 to size() - 1 [inclusive]
    • a. Find the Contact with the earliest name in alphabetical order from index i to the end of the list of Contacts.
    • b. Swap the Contact at position i with the Contact found in Step (1a) above.
Hint

Our sorting algorithm compares the names of different Contacts, but we cannot simply use the < operator to decide if one name String is earlier in alphabetical order than another String (like we could in Python and some other languages). Instead, in Java, we use the compareTo(String other) method for String objects – calling s1.compareTo(s2):

  • returns a negative integer (less than 0) if s1 is earlier in alphabetical order than s2
  • returns 0 if s1 and s2 are the same String
  • returns a positive integer (greater than 0) if s1 is later in alphabetical order than s2

Binary Search Algorithm

If our list is in sorted order, then we can quickly find an item using an algorithm called binary search. The iterative (i.e., non-recursive) version of that algorithm (similar to the GuessingGame in Lab 1) works as follows:

  1. Get an input name from the user that we are searching for
  2. Set min equal to 0 and max equal to the size() of the list
  3. Loop as long as min <= max and we have not found the user’s input name
    • a. Get the Contact in the middle of the list between min and max
    • b. Check if the name of the Contact from Step (3a) starts with the input name the user is searching for from Step 1 (using the startsWith(String prefix) method of the String class). If yes, return this Contact
    • c. If the input name the user is searching for is earlier in alphabetical order than name of the Contact from Step (3a), then search earlier in the list by assigning max to be one index before the middle index computed in Step (3a)
    • d. Otherwise, if the input name the user is searching for is later in alphabetical order than name of the Contact from Step (3a), then search later in the list by assigning min to be one index after the middle index computed in Step (3a)
    • e. If min == max but no name starts with the input name, then the search fails to find and should return null.

Steps 3c and 3d cut the remaining list to search in half each time, drastically reducing the total number of comparisons needed to find a name in the list when compared to starting at the beginning and looking at each Contact until the one wanted by the user is found.

Application Instructions

We have provided you with a class Contact that you can use to store the name and office location for each faculty and staff member in the FacultyStaff.txt file.

Inside your GitHub repository, open the file called ContactApp.java in Visual Studio Code. In this file, create a new class ContactApp. Within this class, you should implement a program that accomplishes the following:

  1. Read in the contact information for each person from the FacultyStaff.txt file and save them to a MyArrayList of Contacts. That MyArrayList should be the only instance variable of the ContactApp class.
Hint

Each line of the FacultyStaff.txt file represents a different faculty or staff person. Each line is formatted as “name” tab “office location”. You can parse each line String by using the split method of the String class:

String[] splitLine = line.split("\t");

where the name will be in the first index of splitLine and the office will be in the second index of splitLine. Here, “\t” represents a tab in the String.

README

To earn full credit, you should use your MyArrayList to complete this part of the lab. However, if your MyArrayList is not quite working, you can still earn partial credit by using Java’s built in ArrayList class since one of the goals of this part is to gain practice using array lists to solve interesting real-world problems.

  1. Use the selection sort algorithm described above to sort the Contacts in the MyArrayList so that the Contacts are in alphabetical order by the name of each Contact
  2. Repeatedly ask the user for people to lookup in the MyArrayList of Contacts until the user chooses to end the program by typing the input exit.
    • a. The program should use the binary search algorithm described above to find the Contact whose name starts with the input given by the user. If a Contact is found, you should print their office location followed by their name in parentheses. For example: King 125B (Eck, Adam)
    • b. If no such Contact can be found by binary search, then the program should print a message saying the requested person cannot be found.

You should create methods for each of these major components of your program. The logical flow of your program (e.g., calling the methods in the correct order) should be implemented in the public static void main(String[] args) method of your class.

README

Since our binary search pseudocode above instructs to check whether a Contact’s name starts with the input from the user, the name found by our application might not be exactly the name the user was looking for. For example, there are 8 names in the FacultyStaff.txt file that start with Ch, so if the user searches for Ch, the application will print the first name it finds that starts with Ch (which may not be the first in alphabetical order given that the algorithm starts searching in the middle of the list of Contacts).

You should find that the longer the user’s search String, the more likely your application is to find the requested person (instead of someone with a similar name).

Example Program Output

To help with debugging, here are some possible outputs of your program:

What name would you like to search for? (Type exit to quit) Eck
The office found is: King Building 125B (Eck, Adam)


What name would you like to search for? (Type exit to quit) Hoyle
The office found is: Rice Hall 108 (Hoyle, Roberto)


What name would you like to search for? (Type exit to quit) Draper
The office found is: King Building 125A (Draper, Lucas)


What name would you like to search for? (Type exit to quit) Wang
The office found is: King Building 223D (Wang, Emily)


What name would you like to search for? (Type exit to quit) Levinson
The office found is: King Building 139C (Levinson, Howard)


What name would you like to search for? (Type exit to quit) Nobody
Sorry, but we could not find the name: Nobody


What name would you like to search for? (Type exit to quit) exit

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.