package algs34;

import java.util.*;

import stdlib.*;

/*

* Complete the methods of MyFB so that it works.

* Each method must work in the worst case time given below (assuming uniform hashing and ignoring string lengths):

*

* addPerson must take constant time

*

* addFriendship must take constant time

*

* queryFriendship must take constant time

*

* removeFriendship should take constant time

*

* lookupFriends should take time proportional to the number of

* friends that the named person has (or less)

*

* Your solution should use a single field of type

*

* HashMap>

*

* You will need to add hashCode and equals methods to the Person class.

* Follow the suggestions from Joshua Bloch, given in items 7 and 8 here:

*

* http://fpl.cs.depaul.edu/jriely/ds2/extras/Chapter3.pdf

*

* Don't change the first line of any method given below.

* The names and types of the methods should not change.

* I will run you MyFB class using my own main method.

*

* You can add more classes too. Just put them all in this file, inside MyFB.

* Any classes you add should be "static" and not "public".

* You can import/use any file in the java APIs.

* You can import/use any file in the algs packages.

*

* You do not need to implement a hash table for this assignment.

* You can use java.util.HashMap, java.util.HashSet, or the implementations in algs34.

*

* You do not need to implement a iterable object.

* You can use algs13.Queue.

* Also note that all of the Map implementations we have looked at create an iterable

* object via the keys() method.

*

*

* Here is an example session:

*

* INPUT OUTPUT

*

* p sa 8

* p li 7

* p he 9

* p tu 5

* f li 7 tu 5

* f li 7 he 9

* f tu 5 sa 8

* l tu 5 li 7 sa 8

* l sa 8 tu 5

* u li 7 tu 5

* l tu 5 sa 8

* q li 7 he 9 yes

* q he 9 li 7 yes

* q he 9 li 23 no

* q he 9 he 9 no

*

* Note that friendship is symmetric and irreflexive.

* So if a/b are friends, then so are b/a.

* And no one is their own friend.

*

* Put the following in a file "input.txt" to run this test:

p sa 8

p li 7

p he 9

p tu 5

f li 7 tu 5

f li 7 he 9

f tu 5 sa 8

l tu 5

l sa 8

u li 7 tu 5

l tu 5

q li 7 he 9

q he 9 li 7

q he 9 li 23

q he 9 he 9

*/

public class MyFB {

public static boolean DEBUG = true;

public static Person makePerson(In in) {

try {

String name = in.readString();

int age = in.readInt();

return makePerson(name, age);

} catch (java.util.InputMismatchException e) {

StdOut.println("Input format error");

return null;

}

}

public static Person makePerson(String name, int age) {

return new Person(name, age);

}

static class Person {

String name;

int age;

public Person(String name, int age) {

this.name = name;

this.age = age;

}

public String toString() {

return name + " " + age;

}

// TODO

}

HashMap> map = new HashMap<>();

// a person "exists" after they are added using addPerson

// addPerson does nothing if p already exists

public void addPerson(Person p) {

if (map.containsValue(p)) {

return;

}

if (!map.containsValue(p)) {

HashSet set1 = new HashSet();

set1.add(p);

map.put(p, set1);

}

if (DEBUG) {

StdOut.format("P %s: %s ", p, map);

}

}

// addFriendship does nothing if p1 and p2 are already friends or if one

// does not exist

public void addFriendship(Person p1, Person p2) {

if (p1.equals(p2)) {

return;

}

if (!map.containsKey(p1) || !map.containsKey(p2)) {

return;

}

if (map.containsKey(p1) && map.containsKey(p2)) {

HashSet s1 = map.get(p1);

HashSet s2 = map.get(p2);

s1.add(p2);

s2.add(p1);

map.put(p1, s1);

map.put(p2, s2);

}

if (DEBUG) {

StdOut.format("F %s %s: %s ", p1, p2, map);

}

}

// removeFriendship does nothing if p1 and p2 are not friends or if one does

// not exist

public void removeFriendship(Person p1, Person p2) {

if (p1.equals(p2)) {

return;

}

if (!map.containsKey(p1) || !map.containsKey(p2)) {

return;

}

if (map.containsKey(p1) && map.containsKey(p2)) {

HashSet s1 = map.get(p1);

HashSet s2 = map.get(p2);

s1.remove(p2);

s2.remove(p1);

// map.remove(p2, s2);

map.remove(s1);

map.remove(p1);

}

if (DEBUG) {

StdOut.format("U %s %s: %s ", p1, p2, map);

}

}

// queryFriendship returns false if p1 and p2 are not friends or if one does

// not exist

public boolean queryFriendship(Person p1, Person p2) {

if (DEBUG) {

StdOut.format("Q %s %s: ", p1, p2);

}

if (!map.containsKey(p1) || !map.containsKey(p2)) {

return false;

} else {

return true;

}

}

// lookupFriends returns null or empty iterable if p does not exists

public Iterable lookupFriends(Person p) {

if (DEBUG) {

StdOut.format("L %s:", p);

}

if (!map.containsKey(p))

return null;

else {

// System.out.println(p);

HashSet s1 = map.get(p);

s1.remove(p);

return s1;

}

}

public static void main(String[] args) {

Trace.showBuiltInObjects(true);

// Trace.run ();

/*

* The first line below causes "in" to read from the console. You can

* change this to read from a file, by using something like the line

* below, where "input.txt" is a file you create in your eclipse

* workspace. The file should be in the same folder that contains "src"

* "bin" and "lib":

*/

// In[] inputFiles = new In[] { new In () }; // from console

// In[] inputFiles = new In[] { new In ("input.txt") }; // from file

In[] inputFiles = new In[] { new In("input.txt"), new In() }; // from

// file,

// then

// console

MyFB fb = new MyFB();

StdOut.println("Enter one of the following:");

StdOut.println(" P name age -- add person");

StdOut.println(" F name1 age1 name2 age2 -- add friendship");

StdOut.println(" U name1 age1 name2 age2 -- remove friendship");

StdOut.println(" Q name1 age1 name2 age2 -- query friendship");

StdOut.println(" L name age -- lookup friends");

StdOut.println(" R -- restart");

StdOut.println(" X -- exit");

for (In in : inputFiles) {

while (in.hasNextLine()) {

// StdOut.println (fb. ...); // while debugging, print debugging

// info here! You can print maps, sets, lists.

String action;

try {

action = in.readString();

} catch (NoSuchElementException e) {

continue;

}

switch (action) {

case "P":

case "p": {

Person p = makePerson(in);

fb.addPerson(p);

break;

}

case "F":

case "f": {

Person p1 = makePerson(in);

Person p2 = makePerson(in);

fb.addFriendship(p1, p2);

break;

}

case "U":

case "u": {

Person p1 = makePerson(in);

Person p2 = makePerson(in);

fb.removeFriendship(p1, p2);

// Trace.draw ();

break;

}

case "Q":

case "q": {

Person p1 = makePerson(in);

Person p2 = makePerson(in);

boolean result = fb.queryFriendship(p1, p2);

StdOut.println(result ? "Yes" : "No");

break;

}

case "L":

case "l": {

Person p = makePerson(in);

Iterable result = fb.lookupFriends(p);

if (result != null) {

for (Person friend : result) {

StdOut.print(friend);

StdOut.print(" ");

}

}

StdOut.println();

break;

}

case "R":

case "r":

fb = new MyFB();

break;

case "X":

case "x":

System.exit(0);

}

}

}

}

}