Java Social Network Edgelist II This project will extend the midterm project to further analyze the Twitter data. For this application responsiveness is very important, so runtime should be minimized even at the expense of increased memory usage. This is a common situation in real-world applications. Specifically, you need to create two new methods: Collection getFollowing(TwitterUser user) TwitterUser getByPopularity(int x) In the midterm you read in a data file (social_network.edgelist) that indicated whom a user is following. The getFollowing method should do the reverse -- it should return a collection of the people who are following the user. The object that you return can be any type of Java Collection that we have studied: list, queue, set, map, etc. Choose whichever is most appropriate. The getByPopularity method should return the xth TwitterUser (starting from zero) when the users have been sorted by the following criteria: Number of followers (largest to smallest) If two users have the same number of followers, sort by the number of people that user is following (largest to smallest) If two users have the same number of followers and are following the same number of people, sort by user id (smallest to largest) Note that since user id is unique, these criteria impose a total rather than partial ordering on the TwitterUser objects (in other words, there will never be any "ties"). The time complexity of both of these methods must be constant, i.e. O(1). In order to achieve this, you will likely need to create additional data structures in the TwitterUser class, the driver program, or both. Keep in mind that it is ok if reading in the data files and initializing all of the TwitterUser objects is slow (within reason). It is also fine if these objects take up a lot of space in memory, as long as the program can execute on a standard desktop computer. For each method, write a comment (in your code, right before the method implementations) that describes the changes you have made to your project since the midterm in order to implement the method. Additionally, modify your driver program to test the operation of the two new methods. You will be graded according to the following requirements: • The getFollowing method returns the correct results • The getFollowing method has a constant time complexity • The comment explaining the getFollowing method is complete and clearly written • The getByPopularity method returns the correct results • The getByPopularity method has a constant time complexity • The comment explaining the getByPopularity method is complete and clearly written • The driver program tests the execution of both methods • The program compiles • The program runs • The program is clearly written and follows standard coding conventions link to edgelist file is here - https://drive.google.com/file/d/1QjROviv0yGnr469ifMB0sdjvRNduXGLJ/view My code so far.... it doesn't sort in order of largest to smallest followers and I seem to be getting duplicates. Thanks for looking and thanks for the help! import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Hashtable; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Stack; public class Driver { static ArrayList users = new ArrayList(); static Scanner input = new Scanner(System.in); public static void main(String[] args) { String filename; String line; int userID, followID, depth; TwitterUser userObj, followObj, cloneTestObj; /* * Reading file and pulling in data */ /**/ System.out.print("\nEnter the filename holding the user data: "); // filename = input.nextLine();//*/ filename = "social_network.edgelist"; //filename = "finalTestList.edgelist"; long startTime = System.currentTimeMillis(); long endTime; System.out.println("\nTesting the file input: "); try { BufferedReader file = new BufferedReader(new FileReader(filename)); System.out.println("\tReading data from the file..."); Stack followers = new Stack(); HashSet hashSet = new HashSet(1000000); while ((line = file.readLine()) != null && !line.isEmpty()) { String[] ids = line.split(" "); userID = Integer.parseInt(ids[0]); followID = Integer.parseInt(ids[1]); hashSet.add(new TwitterUser(userID)); hashSet.add(new TwitterUser(followID)); // Followers begin followers.push(new Integer[] { userID, followID }); // Followers end } endTime = System.currentTimeMillis(); System.out.println("\tFinished adding " + hashSet.size() + " users in " + (int) ((endTime - startTime) / 1000) + " seconds."); file.close(); // Map all TwitterUsers to their ID in HashMap HashMap hashMap = new HashMap(); for (TwitterUser t : hashSet) { hashMap.put(t.getID(), t); } file = new BufferedReader(new FileReader(filename)); startTime = System.currentTimeMillis(); int counter = 0; System.out.println("\n\tFriending..."); while ((line = file.readLine()) != null && !line.isEmpty()) { String[] ids = line.split(" "); userID = Integer.parseInt(ids[0]); followID = Integer.parseInt(ids[1]); userObj = hashMap.get(userID); followObj = hashMap.get(followID); userObj.followUser(followObj); counter++; } file.close(); endTime = System.currentTimeMillis(); System.out.println("\tFinished all " + counter + " friending operations in " + (int) ((endTime - startTime) / 1000) + " seconds."); // Transfer HashMap values to ArrayList of TwitterUsers for (TwitterUser t : hashMap.values()) { users.add(t); } // Followers begin mapFollowers(followers); // Followers end } catch (FileNotFoundException e) { System.out.println("\n\tThe filename \"" + filename + "\" was not found. Exiting program."); System.exit(1); } catch (IOException i) { System.out.println("\tIOException: "); i.printStackTrace(); } /** * System.out.println("\n\tUsers:"); for (TwitterUser t: users) { * System.out.println("\tUser " + t); }/ **/ /* * Unit test of the getNeighborhood function */ System.out .print("\nTest for the getNeighborhood(user, depth) function:" + "\n\tEnter the user you would like to test: "); userID = input.nextInt(); userObj = getUser(userID); System.out .print("\tEnter the depth you would like to go to in your neighborhood: "); depth = input.nextInt(); while (depth userObj.getFollowing().size())) { System.out .print("\tPlease enter a positive number less than or equal to " + userObj.getFollowing().size() + ": "); depth = input.nextInt(); } userObj.getNeighborhood(userObj, depth); /* * Clone method test */ final int TEST_USER = 0; System.out.println("\nTesting the clone() function for deep copy:"); userObj = getUser(TEST_USER); System.out.println("\tCloning User " + userObj + "."); cloneTestObj = (TwitterUser) userObj.clone(); System.out.println("\tUser " + userObj + " successfully cloned."); System.out.println("\tUser 0's following list: " + userObj.getFollowing() + "\n\tClone's following list: " + cloneTestObj.getFollowing()); System.out.print("\tClearing the clone's following list."); cloneTestObj.clearFollowing(); System.out.println("\n\tUser 0's following list: " + userObj.getFollowing() + "\n\tClone's following list: " + cloneTestObj.getFollowing()); // Followers test begin System.out.print("\nTest for the followers function:" + "\n\tEnter the user you would like see list of followers: "); userID = input.nextInt(); test_getFollowing(getUser(userID)); // Followers test end // Popularity test begin System.out .print("\nTest for the followers getByPopularity function:" + "\n\tEnter the user index for which you would like to see popularity: "); int idx = input.nextInt(); TwitterUser u = getByPopularity(idx); System.out.print("\nThe " + idx + "th popular user is :" + u.getID() + " number of followers " + u.getFollowers().size()); // Popularity test end System.out.println("\n\nExiting."); } public static TwitterUser getUser(int userID) { TwitterUser temp; temp = new TwitterUser(userID); while (!users.contains(temp)) { System.out.print("\tInvalid user ID. Enter a valid user id: "); userID = input.nextInt(); temp.setUserID(userID); } return users.get(users.indexOf(temp)); } // Followers && Popularity begin /** * Walk through the list of users and find match * * @param followers * */ private static void mapFollowers(Stack followers) { while (!followers.isEmpty()) { Integer[] anEntry = followers.pop(); Integer aUserId = anEntry[1]; List f = findFollowersForUser( (Stack) followers.clone(), aUserId); System.err.println("User " + aUserId + " has " + f.size() + " followers."); TwitterUser aUser = getUser(aUserId); aUser.setFollowers(f); } } /** * given a userID id find all followers in stack * * @param sList * @param id * @return a list of followers */ private static List findFollowersForUser(Stack sList, Integer id) { List f = new ArrayList(); while (!sList.isEmpty()) { Integer[] ids = sList.pop(); if (id - ids[1] == 0) { f.add(ids[0]); // System.err.println(ids[0] +" : "+ ids[1]); } } return f; } public static void test_getFollowing(TwitterUser user) { Collection followerUsers = user.getFollowing(user); List followers = new ArrayList(); for (TwitterUser aUser : followerUsers) { followers.add(aUser.getID()); } System.out.println("User " + user.getID() + " has " + followers + " followers. "); } private static TwitterUser getByPopularity(int idx) { Collections.sort(users, new UserComparator()); return users.get(idx); } // Followers && Popularity end } import java.util.ArrayList; import java.util.Collection; import java.util.List; public class TwitterUser implements Comparable, Cloneable { private int id; private ArrayList following = new ArrayList(); public TwitterUser() { } public TwitterUser(int userID) { id = userID; } public void getNeighborhood(TwitterUser user, int depth) { System.out.println("\tUser " + user + ", Friends: " + user.getFollowing()); if (depth // do nothing } else { for (int i = 0; i TwitterUser temp = following.get(i); getNeighborhood(temp, 0); } } } public void followUser(TwitterUser user) { if (!following.contains(user)) { following.add(user); } } public void clearFollowing() { following.clear(); } public ArrayList getFollowing() { ArrayList copy = new ArrayList(); for (TwitterUser t : following) { copy.add(t); } return copy; } public int getID() { return id; } public void setUserID(int newId) { id = newId; } @Override public int compareTo(TwitterUser t) { if (id > t.getID()) { return 1; } else if (id return -1; } else { return 0; } } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + id; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; TwitterUser other = (TwitterUser) obj; if (id != other.id) return false; return true; } public Object clone() { try { TwitterUser clonedUser = (TwitterUser) super.clone(); clonedUser.following = (ArrayList) following.clone(); return clonedUser; } catch (CloneNotSupportedException e) { return null; } } public String toString() { return Integer.toString(id); } // Followers begin /* * * return a collection of the people who are following the user */ public Collection getFollowing(TwitterUser user) { Collection tUser = new ArrayList(); if (user.getID() == 415) { System.out.print("\nuser id: " + user.getID()); } for (Integer t : user.getFollowers()) { tUser.add(new TwitterUser(t)); } return tUser; } private List followers = new ArrayList(); public void setFollowers(List f) { for (Integer i : f) { if (!followers.contains(i)) followers.add(i); } } public List getFollowers() { return followers; } // Followers end } import java.util.Comparator; public class UserComparator implements Comparator { @Override public int compare(TwitterUser o1, TwitterUser o2) { int res = 0; // 3. If two users have the same number of followers and are following // the same number of people, sort by user id (smallest to largest) if ((o1.getFollowers().size() == o2.getFollowers().size()) && (o1.getFollowing().size() == o2.getFollowing().size())) res = (o1.getID() // 2. If two users have the same number of followers, sort by the number // of people that user is following (largest to smallest) if (o1.getFollowers().size() == o2.getFollowers().size()) res = o1.getFollowing().size() > o2.getFollowing().size() ? 1 : 0; // 1. Number of followers (largest to smallest) if (o1.getFollowers().size() > o2.getFollowers().size()) res = 1; return res; } }