Unlike previous assignments, on this assignment *you may work in
pairs*. If you choose to work with a partner, the handin procedures
are as follows:

- Only
*one*of your pair should hand in the assignment, the other person should leave his/her handin directory*empty*. - The handin should
*clearly*state the name and andrew-ID of the other person (so that we can be sure to give that person credit!) You will both receive the same grade.

**Guidelines for working in pairs:** If you choose to work in
pairs, you may split up the effort as you wish. However, each person
should contribute some significant part of the work, and you should
say how you decided to split things up in your handin. (E.g., I did
part X, my partner did part Y, and we did part Z together.) Here are some
suggestions for splitting up work (some of these will make more sense
*after* you've read the rest of the handout):

- One person can be in charge of creating the priority queue and
the other person can be in charge of writing the code that uses the
priority queue. The person creating the pqueue can, for starters,
whip up a simple but slow implementation using an unsorted array or a
linked list. This can then be used by the other partner while the
faster but more complicated heap-based implementation is being
developed. Remember, the point of an ``abstract data type'' (like a
priority queue) is that you can separate the interface from the
implementation.
- The part of the code that handles the input from the user
(deciding if the user has typed in a place name or a street address,
and checking for partial matches, etc.) is pretty much independent of the
rest and either partner can be in charge of that. While that is being
developed, you can still work on Tasks 2 and 3 but only allowing the
user to type in street addresses like on assignment 6.
- The part of your code that handles the output of Task 3 is also pretty much independent from the rest - you just need to decide in advance what the interface between your routines will be.

This assignment consists of three tasks. The Task 1 is worth 20 points, Tasks 2 is worth 60 points, and task 3 is worth 20 points. 40 out of the 60 points for Task 2 are for getting a working heap-based implementation of a priority queue.

<address> is <N1> feet from intersection <I1> and <N2> feet from intersection <I2>.If it was a place name, the program responds by saying

<place name> is at <address> <address> is <N1> feet from intersection <I1> and <N2> feet from intersection <I2>.(The actual syntax is not important, and you can provide more information if your choose.) Furthermore, if the thing the user entered is ambiguous, the program should list the possible choices just like on Task 1 of assignment 6. You can run the executable we have provided for specific examples.

The way you will estimate the distance of the address to each intersection is by interpolation. For instance, if the block has street numbers 5100 to 5199, and is 550 feet long, then:

- Address 5100 is 0 feet from the first intersection and 550 feet from the second.
- Address 5101 is 5 feet (5.556 but let's round down) from the first and 545 feet from the second.
- Address 5130 is 166 feet from the first and 384 feet from the second.
- Address 5199 is 550 feet from the first and 0 feet from the second.

As a special case, if the minimum and maximum street addresses on the block are the same, then say that the address is halfway between the two.

Note: one thing you will need to do is to determine if the user is
giving you a place name or a street address. One way to do that is to
read in a string, and then see if the string begins with a digit. If
it does not begin with a digit, then this string is a place name (you
can assume that no place names begin with digits). Otherwise, if the string
*does* begin with a digit, then this means the string is a street
number and you want to read in a second string to get the street name.
One thing you will need to do is to convert your first string into a
number. A convenient way to do that is to use the `atoi`
function defined in `<stdlib.h>`. E.g.,
`street_number = atoi(string);`
where `street_number` is an `int` and `string` is a
character array. You can also use `sscanf`.

Enter a place name or street address: Blu Blum's_Barbeque is at address 355 S_Highland_Ave Enter a place name or street address: Bru Bruce's_Beach_Party is at address 711 Copeland_St Starting at 355 S_Highland_Ave, go to intersection 179, then on Elwood_St to intersection 192, then on Elwood_St to intersection 206, then on Elwood_St to intersection 217, then on Elwood_St to intersection 227, then on Elwood_St to intersection 268, then on Elwood_St to intersection 284, then on Elwood_St to intersection 295, then on Summerlea_St to intersection 275, then on Elmer_St to intersection 294, then on Elmer_St to intersection 314, then on Elmer_St to intersection 320, then on Elmer_St to intersection 330, then on Elmer_St to intersection 340, then on Elmer_St to intersection 348, then on Elmer_St to intersection 354, then on Elmer_St to intersection 359, then on Elmer_St to intersection 365, then on Copeland_St to 711 Copeland_St Total distance traveled: 3578 feet.(Your code may produce a total distance that differs by a foot or so from our code depending on how you do the rounding of Task 1.)

You may wish to treat the case in which the start and end are on the same block as a special case. For instance:

Enter a place name or street address: Ali Ali_Baba is at address 404 S_Craig_St Enter a place name or street address: Sta Star_Of_India is at address 412 S_Craig_St Just walk down the block!

Your program should run in time *O(m* log*m)* where
*m* is the total
number of edges in your graph. In order to do this, your program
should use a heap-based implementation of a priority queue. This
priority queue should allow one to `insert` an item with a
priority value, to perform a `remove_min` operation to remove the item
with the smallest priority value, and perhaps to perform a `
decrease_value` operation to
decrease the priority value of some item already inside the pqueue as
well. (The last feature is not necessary - it depends on your search
routine).

Your program should use interpolation (as in Task 1) to figure out the distances from the start and end locations to the ends of their respective blocks.

A programming hint: if you put print statements into your insert and remove functions that let you know what you're inserting and what you're removing, it will help you debug your code. Also, you will need to decide on an interface between your path-finding code and your path-printing code. One nice way to do this is to have your path-finding code return its parent array, where you may wish to have each element of this array contain more information than just the parent.

A good test case on the small database is to start at 5070
Forbes and go to 5300 Wilkins, and then try from 5080 Forbes to 5300
Wilkins. These should take different routes.

Enter a place name or street address: Blu Blum's_Barbeque is at address 355 S_Highland_Ave Enter a place name or street address: Bru Bruce's_Beach_Party is at address 711 Copeland_St Starting at 355 S_Highland_Ave head in the direction of increasing street number Go for 367 feet Turn right onto Elwood_St Go for 1604 feet Turn right onto Summerlea_St Go for 156 feet Turn left onto Elmer_St Go for 1394 feet Turn left onto Copeland_St Go for 57 feet and stop at number 711 Total distance traveled: 3578 feet.This is a bit trickier than it looks. For instance, how can you tell if you are making a right turn or a left turn? Below is a fragment of code that you can use or modify that will help you do that.

/* Suppose that xcoords is an array of all the x coordinates and ycoords is an array of all the y coordinates. This routine, given a start, middle, and end intersection (e.g., 284, 295, and 275) figures out what kind of turn (right or left) was made at the middle intersection. Here's the idea: we want to tell if the angle between two vectors is < or > 180 degrees. So, rotate the first vector by 90 degrees and then see if the dot prodoct is postive. */ char *which_way(int start, int middle, int end) { /* these are the rotated ones (which is why they look weird) */ int x0 = ycoords[middle] - ycoords[start]; int y0 = xcoords[start] - xcoords[middle]; int x1 = xcoords[end] - xcoords[middle]; int y1 = ycoords[end] - ycoords[middle]; int result = x0*x1 + y0*y1; if (result > 0) return "right"; else return "left"; }

For debugging purposes you might want to make your code output the intersections numbers too, while you're getting it working. We have placed executables into the assign7 directory that you can use to help you test out your program.

Good luck!