Question: Implement the code that is currently marked as TODO. At the moment I have a general idea of what to do but would also love
Implement the code that is currently marked as "TODO". At the moment I have a general idea of what to do but would also love to see what other people can come up with. Doing something with the DEBUG is not required and is only a test to help us if we are not sure where errors are.
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:
* Don't change the first line of any method given below.
* The names and types of the methods should not change.
*
* 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 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.
* 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
}
// a person "exists" after they are added using addPerson
// addPerson does nothing if p already exists
public void addPerson (Person p) {
if (DEBUG) { StdOut.format ("P %s ", p); }
// TODO
}
// addFriendship does nothing if p1 and p2 are already friends or if one does not exist
public void addFriendship (Person p1, Person p2) {
if (DEBUG) { StdOut.format ("F %s %s ", p1, p2); }
// TODO
}
// removeFriendship does nothing if p1 and p2 are not friends or if one does not exist
public void removeFriendship (Person p1, Person p2) {
if (DEBUG) { StdOut.format ("U %s %s ", p1, p2); }
// TODO
}
// 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); }
// TODO
return false;
}
//
The "lookupFriends" method returns an Iterable with the friends of p.
lookupFriends returns null or empty iterable if p does not exists
public Iterable lookupFriends (Person p) {
if (DEBUG) { StdOut.format ("L %s ", p); }
// TODO
return null;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help