Assignment 3: Heatmap for GPS Track

Objectives

to use an ADT implemented with opaque structs
to implement an ADT using opaque structs
to use dynamically allocated memory

Introduction

A heatmap is a graphical representation of a 2-D array using different colors to represent different ranges of values. Heatmaps are useful in a variety of applications, including web usability, sports analytics, and many geographic applications.

Our application is search-and-rescue: given a GPS track, we want to see where in the search area the track hasn't been as often so that we can focus future search efforts on those locations.

Assignment

There are two parts to this assignment:

implement the track ADT according to the specification in /c/cs223/hw3/Required/track.h; and
write a program called Heatmap that reads a GPS track and writes an ASCII-art heatmap to standard output.

Implementing the `track` ADT

A GPS track is a collection of trackpoints each containing a location and timestamp. Trackpoints within tracks are ordered by increasing timestamp and can be organized into multiple segments within the same track (a tracking device might, for example, start a new segment each time the user pauses the device, starts a new lap, or when the devices loses the signal from the satellites).

The header file /c/cs223/hw3/Required/track.h specifies the functions you must implement for the track abstract data type (ADT), which models as GPS track. You may not change the header file, which defines the public interface to the ADT (but you can implement additional functions that will not be visible to other modules in your implementation file). The /c/cs223/hw3/Required directory also contains the required header and implementation files for location and trackpoint structs and you may not change those either.

In addition, there are efficiency requirements for each function:

track_create must run in $O(1)$ worst-case time;
track_destroy must run in $O(n)$ worst-case time;
track_count_segments, track_count_points, and track_get_point must run in worst-case $O(1)$ time;
track_get_lengths must run in worst-case $O(m)$ time;
track_add_point and track_start_segment must run in amortized $O(1)$ time (so any sequence of $k$ such operations must take $O(k)$ time total in the worst case);
track_merge_segments must run in worst-case $O(n)$ time; and
track_heatmap must run in worst-case $O(n^2)$ time, assuming that each trackpoint is in the same cell as the previous one (for the start of a segment, "the previous one" is the last trackpoint on the previous segment) or in an adjacent cell – given a regular time interval between trackpoints, this assumption bounds the speed of the tracked object. (Without that assumption, the time bound is $O(n^2 + m)$ where $m$ is the total number of cells in the heatmap.)

All time bounds assume that $n$ is the number of total points in the track and $m$ is the number of segments, and that malloc and free work in $O(1)$ time (note that this assumption does not extends to calloc, realloc or similar functions).

Your ADT will be tested with a series of unit tests that test individual functions. An incomplete suite of unit tests is implemented in /c/cs223/hw3/Required/track_unit.c, which will be replaced with a complete test suite for the private test script. The public and private unit test modules will each contain a main function that will be linked with your track implementation to produce an executable called Unit that executes the unit tests. Examine the public track_unit.c to see how the individual tests work. All unit tests must pass with no errors reported from valgrind.

Note that although you may not use all of the functions provided by the track ADT when writing the Heatmap program, you must implement all of them for this part of the assignment.

Writing the `Heatmap` program

Use your track ADT implementation to write a program that produces heatmaps for search-and-rescue operations. The size of the geographic regions represented by each cell in the heatmap and which characters used to represent which values will be specified as command-line arguments. The trackpoints will be read from standard input.

The command-line arguments will be in the following order:

the width, in degrees of longitude, of each cell in the heatmap, which will be positive and in a format readable by atof;
the height, in degrees of latitude, of each cell in the heatmap, which will be positive and in a format readable by atof;
a non-empty string of characters used to represent ranges of values in the heatmap, with the character used to represent the lowest range of values first and the character used to represent the highest range last; and
a positive integer $n$ in a format readable by atoi that defines the ranges of values represented by each character, so that if the length of the string of characters is $m$ then the ranges are $kn, \ldots, (k+1)n-1$ for k = $0, \ldots, m-2$, and $(m-1)n, \ldots, \infty$.

Standard input will contain one trackpoint per line, with a single blank line before the second and subsequent track segments. The latitude and longitude for each trackpoint will be given in degrees in a format readable by atof and the values will satisfy the preconditions of trackpoint_create. The time will be given as the number of milliseconds since January 1, 1970 in a format readable by atol. All three fields will be separated by single space characters, with no leading or trailing whitespace (aside from the newline that marks the end of the line). The trackpoints will be given in order of increasing timestamp. There will be a single empty line used to delimit segments within the track, and if there is more than one segment they will all be non-empty.

The output should be a heatmap representing all trackpoints and all segments read from standard input, as specified by the heatmap function in the track ADT, using the cell width and height given on the command line. Each row of the heatmap should be written to standard output on a separate line, with the first character written corresponding to the first column of the first row of the heatmap. Each integer value in the heatmap should be replaced with a single character as determined by the last two command-line arguments, with no space between characters in the same row. There should be no other output to standard output or standard error.

Your Heatmap program must not produce any errors when run with Valgrind, nor may it otherwise crash or hang in an infinite loop, including when there are any memory allocation errors and when the command-line arguments are invalid.

Example

[jrg94@termite code]$ for N in `seq 1 13`; do ./Unit $N; done
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
[jrg94@termite code]$ ./Heatmap 1.0 1.0 .xX* 1 < /c/cs223/hw3/Tests/heatmap_2x2.in
*.
xX
[jrg94@termite code]$ ./Heatmap 0.03125 0.03125 .xX* 1 < /c/cs223/hw3/Tests/grid_walk_6_4.in
xxxxX
xxxxX
XXXX*
[jrg94@termite code]$ ./Heatmap 0.003 0.002 .:xX# 10 < /c/cs223/hw3/Tests/east_rock.in
.........X#......
.........#X......
.........#x......
.........#.......
....Xxx####......
....x..#.###.....
....x.....###....
....#......#x....
:XX#X......x.....
x...........#.xX.
x...........XXx:x
X...............x
.X..............x
x#.............X.
#.......#......x.
#.......Xx#....X.
.X#x:...X.:...X..
...##XxX#..#X#x..

Submissions

Submit your makefile, log file, and source code necessary to build the executables Heatmap and Unit using your makefile. Your makefile should have rules with each of those executables as their targets as well as a default (first) rule that builds both targets. Your makefile should assume that the files from /c/cs223/hw3/Required have been copied into the current directory but not that they are still in their original locations, and you should not submit those files.