In the map data file, must the street segments be listed in an order that forms one contiguous stretch of roadway?
No. The segments listed after the street name in the file may be in any order and might not form just one contiguous stretch. For example, consider this hypothetical street (near Paris, judging by the coordinates):
Rue Exemple 45.000 3.000 45.000 3.001 0 Rue Exemple 45.000 3.001 45.001 3.002 0 Rue Exemple 45.001 3.003 45.001 3.004 0 Rue Exemple 45.001 3.004 45.000 3.005 0
This describes a street with two discontiguous stretches, one from (45.000,3.000) east to (45.000,3.001) then northeast to (45.001,3.002) and one from (45.001,3.003) east to (45.001,3.004) southeast to (45.000,3.005). But the file might just as well list the segments in a different order or the endpoints of a segment in the opposite order; the same information is conveyed:
Rue Exemple 45.000 3.000 45.000 3.001 0 Rue Exemple 45.001 3.004 45.001 3.003 0 Rue Exemple 45.000 3.001 45.001 3.002 0 Rue Exemple 45.001 3.004 45.000 3.005 0
It still specifies two discontiguous stretches, one consisting of two segments connected at (45.000,3.001) and one consisting of two segments connected at (45.001,3.004).
For the most straighforward implementation of GeoDatabase that we can think of, the code works the same for either of these arrangements and results in the same information being stored as a GeoDatabase's data.
Is it correct to say that we must NOT use containers defined in
<map>, <set>, <unordered_map>,
or <unordered_set> in our implementations of
HashMap and GeoDatabase, but we ARE allowed to use
them for Router and TourGenerator, and we ARE allowed to
use vector, list, stack, queue, and
priority_queue for any of the five classes?
Yes.
I've traced through my code to insert something into a HashMap, and it seems to be doing the right things, but the new association doesn't stay in my HashMap. How could that be?
Perhaps it doesn't stay because it never was there to begin with. Think about this:
int a[10]; a[2] = 42; int x = a[2]; x = 86; cout << a[2] << endl; // writes 42. Why didn't 86 "stay" there? int& y = a[2]; y = 99; cout << a[2] << endl; // writes 99. Why does 99 stay there?
If the street map data file contains more than one point of
interest with the same name (e.g., Northern Cafe|lat1
long1 and Northern Cafe|lat2
long2), what should I do?
Associate that name with just one of the indicated coordinate pairs (e.g., lat2 long2)—it's your choice which one, so depending on how your code is written for the normal case of no duplicate names, it might just naturally save only the first one you encounter when processing the file, or perhaps the only last one you encounter). The mapdata.txt file we give you has three instances of that situation.
My program seems to run correctly, but runs awfully slowly, and I know it's not because of bad algorithms (O(N2) instead of O(N), etc.). How can I speed it up?
Especially if it's Visual C++, it may be that you're building in the Debug configuration, which inserts code to check for many STL usage errors. These are helpful during debugging, but can slow things down. Follow the instructions in Homework 4, problem 7 to build an optimized version.
Do we know enough from this class to do a complexity analysis of A* or simulated annealing?
No. If one of those is an approach you took, then in your report, for the functions for which you implemented A* or simulated annealing, say so and instead of telling us the big-O for that function, briefly describe the data structures you used.
If a street segment from point A to point B has a PoI associated with it, I compute a midpoint M between A and B, and add a segment named "a path" connecting the PoI to M. I also connect M to A and B. Should A also be directly connected to B?
Yes.