QuestionQuestion

Transcribed TextTranscribed Text

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<Person,HashSet<Person>> * * You will need to add hashCode and equals methods to the Person class. * To increase the avalance effect, consider a hash function that utilizes * primes, for example: * * public int hashCode() { * int result = 17; * result = 37*result + var1; * result = 37*result + var2; * result = 37*result + var3; * return result; * } * * 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 an 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 john 8 * p mike 7 * p sara 9 * p jane 5 * f mike 7 jane 5 * f mike 7 sara 9 * f jane 5 john 8 * l jane 5 mike 7 john 8 * l john 8 jane 5 * u mike 7 jane 5 * l jane 5 john 8 * q mike 7 sara 9 yes * q sara 9 mike 7 yes * q sara 9 mike 23 no * q sara 9 sara 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 john 8 p mike 7 p sara 9 p jane 5 f mike 7 jane 5 f mike 7 sara 9 f jane 5 john 8 l jane 5 l john 8 u mike 7 jane 5 l jane 5 q mike 7 sara 9 q sara 9 mike 7 q sara 9 mike 23 q sara 9 sara 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; } @Override public boolean equals (Object obj) { // TODO return true; } @Override public int hashCode () { // TODO return 1293879128; } } HashMap<Person,HashSet<Person>> map = new HashMap<>(); // a person "exists" after they are added using addPerson // addPerson does nothing if p already exists public void addPerson (Person p) { // TODO if (DEBUG) { StdOut.format ("P %s: %s\n", 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) { // TODO if (DEBUG) { StdOut.format ("F %s %s: %s\n", 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) { // TODO if (DEBUG) { StdOut.format ("U %s %s: %s\n", 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); } // TODO return false; } // lookupFriends returns null or empty iterable if p does not exists public Iterable<Person> lookupFriends (Person p) { if (DEBUG) { StdOut.format ("L %s:", p); } // TODO return null; } public static void hashTest () { Trace.showBuiltInObjects (true); //Trace.run (); Person x = makePerson ("bob", 27); Person y = makePerson ("bob", 27); Boolean eq = x.equals(y); Boolean hash = x.hashCode() == y.hashCode(); StdOut.println(x.toString() + " ("+x.hashCode()+") == " + y.toString() + " ("+y.hashCode()+")"); StdOut.println( " Equal Test: " + (eq ? "equal" : "not equal") ); StdOut.println( " Hash Test: " + (hash ? "equal" : "not equal") ); x = makePerson ("mike", 27); y = makePerson ("john", 29); eq = x.equals(y); hash = x.hashCode() == y.hashCode(); StdOut.println(x.toString() + " ("+x.hashCode()+") == " + y.toString() + " ("+y.hashCode()+")"); StdOut.println( " Equal Test: " + (eq ? "equal" : "not equal") ); StdOut.println( " Hash Test: " + (hash ? "equal" : "not equal") ); } public static void main (String[] args) { Trace.showBuiltInObjects (true); //Trace.run (); hashTest(); /* * 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 ("\n"); 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\n\n"); for (In in : inputFiles) { while (in.hasNextLine ()) { String action; try { action = in.readString (); } catch (NoSuchElementException e) { continue; } //StdOut.println (action); // while debugging, print debugging info here! You can print maps, sets, lists. 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<Person> 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); } } } } }

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

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<Person,HashSet<Person>>
*
* You will need to add hashCode and equals methods to the Person class.
* To increase the avalance effect, consider a hash function that utilizes
* primes, for example:
*
* public int hashCode() {
*   int result = 17;
*   result = 37*result + var1;
*   result = 37*result + var2;
*   result = 37*result + var3;
*   return result;
* }
*
* 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 an 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 john 8
*   p mike 7
*   p sara 9
*   p jane 5
*   f mike 7 jane 5
*   f mike 7 sara 9
*   f jane 5 john 8
*   l jane 5            mike 7 john 8
*   l john 8            jane 5
*   u mike 7 jane 5
*   l jane 5            john 8
*   q mike 7 sara 9      yes
*   q sara 9 mike 7      yes
*   q sara 9 mike 23    no
*   q sara 9 sara 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.
*...

By purchasing this solution you'll be able to access the following files:
Solution.java and Solution.txt.

$60.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats