Java Question Given a series of user actions in the social network that is initially empty, recommend new possible friendships after one user friends another user. For example, if Alice, Bob, and Carol are all network members, and Alice and Bob are friends. If Bob and Carol become friends, then your program should recommend that Alice and Carol should become friends. For example, given the user actions the resulting recommendations would be:

Alice joins Carol joins Bob joins Bob friends Alice Bob friends Carol Dave joins Dave friends Bob end

Figure 2: Sample user actions.

Alice and Carol should be friends Alice and Dave should be friends Carol and Dave should be friends

Your task is to create a program that reads in the user actions and generates the friend recommendations. Write a program called Friend.java that reads in the user actions from the console (System.in) and outputs the corresponding friend recommendations. Your Friend class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method:

public ArrayList compute( Scanner input );

This method must perform the required computation.

Input The compute() method takes a Scanner object, which contains one or more lines. Each line, except the last one, contains a user action. There are four user actions:

A joins : means that new user A has joins the network. A friends B : means that user A and B are now friends. A unfriends B : means that user A and B are no longer friends. A leaves : means that user A has left the network (deleted their account).

where A and B are names of users. The user names are single words with no white spaces within them. The last line of input is simply the word \end". See Figure 2 for an example. Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line.

Semantics The social network is initially empty. All user actions are on the same network. Only users that are not part of the social network can join. I.e., each user will have a unique name. Users can leave the network and then rejoin. When a user leaves the network, the user and all his/her friendships are deleted from the network. If a user rejoins the network, it's as if he/she is joining for the first time. All friendships are symmetrical. I.e., "A friends B" is the same as "B friends A". No recommendation should be generated for users who are already friends.

Output The method compute( Scanner input ) should return an ArrayList of Strings denoting the friend recommendations in the same order as the user actions that caused them. A recommendation is of the form

A and B should be friends

where A and B are user names and must be in alphabetical order. For example, this recommendation is correct: "Alice and Bob should be friends", while this one is not: "Bob and Alice should be friends". If more than one recommendation is generated by a single user action, the recommendations should be ordered alphabetically.

Hint

Use a 1-pass algorithm: Simply check for friendships after processing each user action.

Compute Method Tester Interface Class

import java.util.ArrayList; import java.util.Scanner; public interface Tester { // This method takes a Scanner object contianint the input // and returns an ArrayList object containing the output. // // Parameters: // Scanner input: is a Scanner object that is a stream of text // containing the input to your program. // // Returns: an ArrayList of Strings. Each string is a line of output // from your program. public ArrayList compute( Scanner log ); } 

Junit Test Class

import static org.junit.jupiter.api.Assertions.*; import java.util.ArrayList; import java.util.Scanner; import org.junit.jupiter.api.Test; class FriendTest { private static String testInput0 = "end"; private static String [] testOutput0 = {}; private static String testInput1 = "Alice joins " + "Carol joins " + "Bob joins " + "Bob friends Alice " + "Bob friends Carol " + "Alice leaves " + "Bob leaves " + "Carol leaves " + "end"; private static String [] testOutput1 = { "Alice and Carol should be friends" }; private static String testInput2 = "Alice joins " + "Carol joins " + "Bob joins " + "Bob friends Alice " + "Bob friends Carol " + "Bob unfriends Carol " + "Bob friends Carol " + "Alice leaves " + "Bob leaves " + "Carol leaves " + "end"; private static String [] testOutput2 = { "Alice and Carol should be friends", "Alice and Carol should be friends" }; private static String testInput3 = "Alice joins " + "Carol joins " + "Bob joins " + "Bob friends Alice " + "Bob friends Carol " + "Dave joins " + "Dave friends Bob " + "Alice leaves " + "Bob leaves " + "Carol leaves " + "Dave leaves " + "end"; private static String [] testOutput3 = { "Alice and Carol should be friends", "Alice and Dave should be friends", "Carol and Dave should be friends" }; private static String testInput4 = "Alice joins " + "Carol joins " + "Bob joins " + "Bob friends Alice " + "Bob friends Carol " + "Dave joins " + "Dave friends Bob " + "Carol leaves " + "Carol joins " + "Carol friends Alice " + "Alice leaves " + "Bob leaves " + "Carol leaves " + "Dave leaves " + "end"; private static String [] testOutput4 = { "Alice and Carol should be friends", "Alice and Dave should be friends", "Carol and Dave should be friends", "Bob and Carol should be friends" }; private static String testInput5 = "Alice joins " + "Carol joins " + "Bob joins " + "Bob friends Alice " + "Bob friends Carol " + "Dave joins " + "Dave friends Bob " + "Eve joins " + "Eve friends Bob " + "Dave leaves " + "Dave joins " + "Dave friends Bob " + "Dave unfriends Bob " + "Dave friends Bob " + "Fred joins " + "Alice friends Fred " + "Bob friends Fred " + "Carol friends Fred " + "Bob leaves " + "Fred leaves " + "Alice friends Carol " + "Alice leaves " + "Carol leaves " + "Dave leaves " + "end"; private static String [] testOutput5 = { "Alice and Carol should be friends", "Alice and Dave should be friends", "Carol and Dave should be friends", "Alice and Eve should be friends", "Carol and Eve should be friends", "Dave and Eve should be friends", "Alice and Dave should be friends", "Carol and Dave should be friends", "Dave and Eve should be friends", "Alice and Dave should be friends", "Carol and Dave should be friends", "Dave and Eve should be friends", "Bob and Fred should be friends", "Carol and Fred should be friends", "Dave and Fred should be friends", "Eve and Fred should be friends", "Alice and Carol should be friends" }; private static Scanner mkTest( String input ) { return new Scanner( input ); } private static ArrayList mkOutput( String [] output ) { ArrayList al = new ArrayList(); for( String s : output ) { al.add( s ); } return al; } private static boolean doTest( String input, String [] output ) { Tester t = new Friend(); ArrayList al = t.compute( mkTest( input ) ); System.out.println( "Input: " ); System.out.println( input ); System.out.println( "Generated output" ); for( String s : al ) { System.out.println( s ); } System.out.println( "Expected output" ); for( String s : output ) { System.out.println( s ); } System.out.println( "---------------------------------------------------" ); return al != null && al.equals( mkOutput( output ) ); } @Test void testEmpty() { assertTrue( doTest( testInput0, testOutput0 ), "Empty test" ); } @Test void test1() { assertTrue( doTest( testInput1, testOutput1 ), "Basic recommendation" ); } @Test void test2() { assertTrue( doTest( testInput2, testOutput2 ), "Repeat recommendation" ); } @Test void test3() { assertTrue( doTest( testInput3, testOutput3 ), "Multiple recommendation" ); } @Test void test4() { assertTrue( doTest( testInput4, testOutput4 ), "Lots of users leave" ); } @Test void test5() { assertTrue( doTest( testInput5, testOutput5 ), "Lots of recommendations" ); } }