001package algs34;
002
003import java.util.*;
004import stdlib.*;
005
006/*
007 * Complete the methods of MyFB so that it works.
008 * Each method must work in the worst case time given below (assuming uniform hashing and ignoring string lengths):
009 *
010 *   addPerson must take constant time
011 *
012 *   addFriendship must take constant time
013 *
014 *   queryFriendship must take constant time
015 *
016 *   removeFriendship should take constant time
017 *
018 *   lookupFriends should take time proportional to the number of
019 *   friends that the named person has (or less)
020 *
021 * Your solution should use a single field of type
022 *
023 *   HashMap<Person,HashSet<Person>>
024 *
025 * You will need to add hashCode and equals methods to the Person class.
026 * Follow the suggestions from Joshua Bloch, given in items 7 and 8 here:
027 *
028 *   http://fpl.cs.depaul.edu/jriely/ds2/extras/Chapter3.pdf
029 *
030 * Don't change the first line of any method given below.
031 * The names and types of the methods should not change.
032 * I will run you MyFB class using my own main method.
033 *
034 * You can add more classes too.  Just put them all in this file, inside MyFB.
035 * Any classes you add should be "static" and not "public".
036 * You can import/use any file in the java APIs.
037 * You can import/use any file in the algs packages.
038 *
039 * You do not need to implement a hash table for this assignment.
040 * You can use java.util.HashMap, java.util.HashSet, or the implementations in algs34.
041 *
042 * You do not need to implement a iterable object.
043 * You can use algs13.Queue.
044 * Also note that all of the Map implementations we have looked at create an iterable
045 *   object via the keys() method.
046 *
047 *
048 * Here is an example session:
049 *
050 *   INPUT           OUTPUT
051 *
052 *   p sa 8
053 *   p li 7
054 *   p he 9
055 *   p tu 5
056 *   f li 7 tu 5
057 *   f li 7 he 9
058 *   f tu 5 sa 8
059 *   l tu 5          li 7 sa 8
060 *   l sa 8          tu 5
061 *   u li 7 tu 5
062 *   l tu 5          sa 8
063 *   q li 7 he 9     yes
064 *   q he 9 li 7     yes
065 *   q he 9 li 23    no
066 *   q he 9 he 9     no
067 *
068 * Note that friendship is symmetric and irreflexive.
069 * So if a/b are friends, then so are b/a.
070 * And no one is their own friend.
071 *
072 * Put the following in a file "input.txt" to run this test:
073p sa 8
074p li 7
075p he 9
076p tu 5
077f li 7 tu 5
078f li 7 he 9
079f tu 5 sa 8
080l tu 5
081l sa 8
082u li 7 tu 5
083l tu 5
084q li 7 he 9
085q he 9 li 7
086q he 9 li 23
087q he 9 he 9
088 */
089public class MyFB {
090        public static boolean DEBUG = true;
091        public static Person makePerson (In in) {
092                try {
093                        String name = in.readString ();
094                        int age = in.readInt ();
095                        return makePerson (name, age);
096                } catch (java.util.InputMismatchException e) {
097                        StdOut.println ("Input format error");
098                        return null;
099                }
100        }
101        public static Person makePerson (String name, int age) {
102                return new Person (name, age);
103        }
104        static class Person {
105                String name;
106                int age;
107                public Person (String name, int age) {
108                        this.name = name;
109                        this.age = age;
110                }
111                public String toString () {
112                        return name + " " + age;
113                }
114                @Override
115                public boolean equals (Object obj) {
116                        return true;
117                }
118                @Override
119                public int hashCode () {
120                        return 1293879128;
121                }
122                
123        }
124        public static void main (String[] args) {
125                Trace.showBuiltInObjects (true);
126                //Trace.run ();
127                Person x = makePerson ("xi", 1);
128                Person y = makePerson ("xi", 1);
129                StdOut.println (x.hashCode());
130                StdOut.println (y.hashCode());
131        }
132        
133        HashMap<Person,HashSet<Person>> map = new HashMap<>();
134
135        // a person "exists" after they are added using addPerson
136        // addPerson does nothing if p already exists
137        public void addPerson (Person p) {
138                // TODO
139                if (DEBUG) { StdOut.format ("P %s: %s\n", p, map); }
140        }
141        // addFriendship does nothing if p1 and p2 are already friends or if one does not exist
142        public void addFriendship (Person p1, Person p2) {
143                // TODO
144                if (DEBUG) { StdOut.format ("F %s %s: %s\n", p1, p2, map); }
145        }
146        // removeFriendship does nothing if p1 and p2 are not friends or if one does not exist
147        public void removeFriendship (Person p1, Person p2) {
148                // TODO
149                if (DEBUG) { StdOut.format ("U %s %s: %s\n", p1, p2, map); }
150        }
151        // queryFriendship returns false if p1 and p2 are not friends or if one does not exist
152        public boolean queryFriendship (Person p1, Person p2) {
153                if (DEBUG) { StdOut.format ("Q %s %s: ", p1, p2); }
154                // TODO
155                return false;
156        }
157        // lookupFriends returns null or empty iterable if p does not exists
158        public Iterable<Person> lookupFriends (Person p) {
159                if (DEBUG) { StdOut.format ("L %s:", p); }
160                // TODO
161                return null;
162        }
163
164        public static void main2 (String[] args) {
165                Trace.showBuiltInObjects (true);
166                //Trace.run ();
167                /*
168                 * The first line below causes "in" to read from the console. You can
169                 * change this to read from a file, by using something like the line
170                 * below, where "input.txt" is a file you create in your eclipse
171                 * workspace. The file should be in the same folder that contains "src"
172                 * "bin" and "lib":
173                 */
174
175                //In[] inputFiles = new In[] { new In () }; // from console
176                //In[] inputFiles = new In[] { new In ("input.txt") }; // from file
177                In[] inputFiles = new In[] { new In ("input.txt"), new In () }; // from file, then console
178                MyFB fb = new MyFB ();
179                StdOut.println ("Enter one of the following:");
180                StdOut.println ("  P name age -- add person");
181                StdOut.println ("  F name1 age1 name2 age2 -- add friendship");
182                StdOut.println ("  U name1 age1 name2 age2 -- remove friendship");
183                StdOut.println ("  Q name1 age1 name2 age2 -- query friendship");
184                StdOut.println ("  L name age -- lookup friends");
185                StdOut.println ("  R -- restart");
186                StdOut.println ("  X -- exit");
187                for (In in : inputFiles) {
188                        while (in.hasNextLine ()) {
189                                //StdOut.println (fb. ...); // while debugging, print debugging info here!  You can print maps, sets, lists.
190                                String action;
191                                try {
192                                        action = in.readString ();
193                                } catch (NoSuchElementException e) { continue; }
194                                switch (action) {
195                                case "P":
196                                case "p": {
197                                        Person p = makePerson (in);
198                                        fb.addPerson (p);
199                                        break;
200                                }
201                                case "F":
202                                case "f": {
203                                        Person p1 = makePerson (in);
204                                        Person p2 = makePerson (in);
205                                        fb.addFriendship (p1, p2);
206                                        break;
207                                }
208                                case "U":
209                                case "u": {
210                                        Person p1 = makePerson (in);
211                                        Person p2 = makePerson (in);
212                                        fb.removeFriendship (p1, p2);
213                                        //Trace.draw ();
214                                        break;
215                                }
216                                case "Q":
217                                case "q": {
218                                        Person p1 = makePerson (in);
219                                        Person p2 = makePerson (in);
220                                        boolean result = fb.queryFriendship (p1, p2);
221                                        StdOut.println (result ? "Yes" : "No");
222                                        break;
223                                }
224                                case "L":
225                                case "l": {
226                                        Person p = makePerson (in);
227                                        Iterable<Person> result = fb.lookupFriends (p);
228                                        if (result != null) {
229                                                for (Person friend : result) {
230                                                        StdOut.print (friend);
231                                                        StdOut.print (" ");
232                                                }
233                                        }
234                                        StdOut.println ();
235                                        break;
236                                }
237                                case "R":
238                                case "r":
239                                        fb = new MyFB ();
240                                        break;
241                                case "X":
242                                case "x":
243                                        System.exit (0);
244                                }
245                        }
246                }
247        }
248}