The STL library provides sorted associative containers, which are a solution to this problem. With these containers, insertion, deletion, and lookup are all fast operations--they work in time proportional to the logarithm of the size of the container. These containers are implemented with balanced binary search trees, which, as we've seen in Chapter 4 of the textbook, does support these operations with a logarithmic bound on their computing time. In this project, you are to write a couple of short programs that construct tables of (key, data) pairs. One program should use of the STL associative containers, map. However, it's possible to do better than logarithmic time for insertion, deletion, and lookup, on average, by using a hash table, which is another type of associative container. Hash tables have average case constant time bounds on insertion, deletion, and lookup. Their disadvantage is that their worst case behavior can be very bad compared to balanced binary search trees--linear time instead of logarithmic. Achieving the optimal constant time behavior requires careful choice of the hash function and other parameters. In this project you will experiment with these factors and make some measurements of the performance of your programs using timing functions that are provided in another of the standard C/C++ libraries, time.h.
The program operates in either a verbose mode, in which it outputs a commentary on the events and its actions, or a silent mode, in which it only prints overall statistics at the end of its operation.
In verbose mode, the program's response to a connection event is either "n2 is busy" or "At time t connected call from n1 to n2", where n1 is the calling number, n2 is the called number and t is the time at which the event was processed. The "busy" response occurs if there is already a connection involving the called number. Otherwise, in either mode, an entry is made in the table with n1 as the key and (n2, t) as the associated data, and another entry with n2 as the key and (n1, t) as the associated data.
The response to a disconnection event with number n is "At time t disconnected call between n1 and n2, duration: d" where n1 or n2 is n, t is the time at which the event was processed, and d is the difference between t and the start time of the connection. There is no action taken if there is no call in progress with n1 or n2 equal to n (i.e., the event is ignored). But if there is such a call in progress, it is removed from the table by deleting both of the entries involving phone number n.
A random connection event is generated by using a random number generator to generate two 7-digit numbers and a start time for the call. This information is packaged in the event and it is placed in the event queue, which is set up as a priority queue in which earliest (smallest) times have the highest priority. When the connection event is later removed from the queue, a disconnection event is constructed for it with its time set to the current time plus a randomly generated duration, and this event is entered in the queue.
After the prescribed number of events has been processed, the program should display (on cout) a line that tells the number of calls completed and the average duration of the completed calls and the average number of active connections (calls that are still in progress are ignored in this summary). Finally, it should display the amount of time taken to process all of the events. This (real, not simulated) time can be computed using the function clock from time.h:
clock_t start, duration; ... start = clock(); ... code to be timed duration = (double)(clock() - start)/CLOCKS_PER_SEC; cout << "Time used: " << duration << " seconds\n";The type clock_t and the factor CLOCKS_PER_SEC are also defined in time.h.
map<string, pair<string, float> >That is, it associates a pair consisting of a string and a float with each key of type string, and the ordering of the keys is computed using the usual < operator on stringss. In the map, each entry is of the form pair(n1, pair(n2, t)).
For the hash table version, you must also implement a hash table class. In
there is already a hash table class, implemented using separate chaining. (It is similar to the hash table class in the Chapter 5 online notes, but the interface is extended and modified some to make it more similar to the the STL map interface.) You must implement your hash table with exactly the same public interface, but using open addressing with quadratic probing instead of separate chaining. (See Section 5.4.2 in the textbook, where some of the implementation is given.)http://www.cs.rpi.edu/courses/fall99/dsa/projdir/project3/hash.h
As mentioned, the public interface of this hash table class is designed to be very similar to that of the STL map class--more precisely, it is very similar to the partial specialization
template <class ElementType> map<string, ElementType>i.e., the keys must be strings. This similarity means that very few changes to your phone company simulation program should be required to change it from the map version to the hash table version. For simplicity, the given hash table class omits some features of the map class; for example, it defines iterator and const_iterator types but doesn't provide them with all of the usual iterator operations. This isn't a problem for the phone company simulation, because it doesn't need full-blown iterators. Note that GNU C++ does provide a set of hashed associative containers (hash_set, hash_multiset, hash_map, hash_multimap) that have full-blown iterators and are as fully compatible with the sorted associated containers as possible. (These containers were actually developed by the generic programming project headed by Alexander Stepanov at Silicon Graphics; they are not part of the C++ standard library but are part of SGI's version of STL. For purposes of this project you are not permitted to use any of SGI's hash tables. In fact, they don't meet the project specification, because they are implemented with separate chaining.)
You can also find two compiled versions of the program (both using a map) in
called jog (SUN version) or jog.exe (Windows PC version). Try them out with various command-line parameters to give you still more information about what is expected.http://www.cs.rpi.edu/courses/fall99/projects/project3/programs/