CSE 143 Spring 2001 Homework 1 Due: Electronic submission by 10 pm, Wednesday April 4.  Paper receipt and written report due in quiz section on Thursday April 5.

Overview

You've been hired as a contractor to implement a small geography database.  The main idea is to read a file containing a lists of places and their locations, then answer questions about distances to various places.

As with all assignments, please read the instructions all the way through before beginning.  Read them once again before you turn in your assignment, to be sure you've left nothing out.

Concepts

The purpose of this assignment is to review some ideas from previous courses and explore basic parts of C++.

• Review of fundamental programming concepts (things you should be familiar with from CSE142)
• functions
• conditional and loop statements
• data structures, including nested arrays and structs
• concepts involving files (open, read, write, close)
• Source file organization (.cpp and .h files)
• C++ strings
• C++ stream I/O and files 
• C++ reference parameters

Program Specification

The program should operate in two phases:

1. When it starts, it should open a file named "places.txt" in the current directory, read the contents of that file, and store the information in a suitable data structure.  Details of the file format are given below.
2. After reading the file, the program should repeatedly ask the user to enter a place name (like Ballard or Redmond), look for that name in the data structure initialized in step 1, and report the distance to that place (if found), or report that the given name did not appear in the data.  Specific details are given below.

File Format

The file contains three pieces of information for each place: the x and y distances of the place measured in miles from the Center of the Universe, and the place name (a string).  The Center of the Universe has x and y coordinates 0.0.  The file might contain a place name with coordinates (0.0,0.0) or there might be no place with those coordinates.  The x coordinate gives the east-west distance from the Center of the Universe; positive distances are east and negative distances are west.  The y coordinate gives the north-south distance; positive distances are north, negative ones are south.

To keep things simple, place names are restricted to be a single string.  So, for example, NewYork is a valid place name; New York (with the embedded blank), is not.

The end of the file is indicated by an entry with a place name of "." (a single period).  This end marker will have x and y coordinates, but the values of these are not specified - they may be any value, positive or negative.

You may assume that there are at most 30 places in the input file (not including the end marker with the period as a place name).  You should also assume that the input file contains clean data, i.e., you do not need to check for input errors like incorrectly formatted numbers, duplicate place names, etc.

Example:  Here is a sample places.txt file giving distances to various Seattle neighborhoods.  (These numbers are a guesstimate by the course staff and may not correspond to reality.)

-1.7	1.1	Ballard
1.0	2.0	GreenLake
2.0	0.5	UDistrict
0.0	0.0	Fremont
-2.5	-1.0	Magnolia
-1.0	-1.3	QueenAnn
2.4	-2.0	CapitolHill
0.5	-2.8	Belltown
8.5	-2.0	Bellevue
11.0	2.5	Redmond
28.0	-49.0	MtRainier
17.42	0.0	.

Interaction

Once the program has read the places.txt file, it should prompt the user to enter place names, look up the place name, and print the following:

• If the place did not appear in the input data file, print a suitable message.
• If the place is the Center of the Universe (distance is 0.0), print a suitable message.
• Otherwise, print the distance between the place and the Center of the Universe.

The place name must exactly match the name in the database, including capitalization.

When the user is done, she should enter a single period (".") to indicate that the program should terminate execution.

Distances should be computed as floating-point numbers, not integers.  The number of decimal places to print on a distance is not specified - feel free to use the default precision provided by C++ output streams.

Example:  Here is a sample of what the interaction should look like, using the Seattle neighborhood data given above. User input is underlined and in italics, like this.

Enter place name: Ballard
Ballard is 2.03 miles from the Center of the Universe
Enter place name: redmond
Never heard of redmond
Enter place name: MtRainier
MtRanier is 56.44 miles from the Center of the Universe
Enter place name: Fremont
Fremont is the Center of the Universe
Enter place name: Pullman
Never heard of Pullman
Enter place name: .

Implementation Requirements

A primary purpose of this assignment, besides learning basic C++, is for you to gain experience designing a program, including data structures, breaking the code apart into functions in some sensible way, and so forth.  But there are a few specific implementation requirements - things you must do as specified here.

You should split your code into a couple of different source files, and partition your code into files so that related code is together.  In particular, you will need a data structure to hold the place/location information. You will also need various functions to manipulate this data structure, for example, adding new information to it, locating the distance information given a particular place name, etc.

You must separate your source code so that the functions that process the internal details of the place data structure are in a separate source (.cpp) file from the main program.  You will also need an associated header (.h) file containing declarations of the data structure(s) and function prototypes for the routines in this source file.  The source (.cpp) file containing the main program should #include the header file to access the data structure definitions and function prototypes.  The main program must call appropriate functions to manipulate the place/location information - it should not access the internal details itself.

Other Implementation Requirements

• Use C++ stream I/O (cin, cout, ifstream, etc.).  Do not use printf/scanf/fscanf or other C library functions for I/O.
• Use the C++ string library (#include <string>), not the C library functions strcpy, strcmp, and so forth.
• Use C++ reference parameters as needed.  Do not use explicit pointers.
• Your code should be clear and readable.  See the style guide for detailed suggestions.

Implementation Hints

• Remember to use #include "file.h" to include header files that you write and that are in your project folder.  The angle brackets in #include <library> are used to indicate libraries that are part of Visual C++ or other implementations.
• Be sure that you don't hard-code the sample data in the program.  For instance, don't assume that Fremont is always the Center of the Universe.  A different data file might specify that the location with coordinates 0.0, 0.0 is Manhattan, which some people consider to be the Center of (their) Universe.

Testing

Part of your job as a programmer is to verify that your code works by running appropriate tests.  That means more than just trying it with the example data given above.  You need to invent test data that will check your program under various conditions.  For example, your tests should check that the program works properly if

• The places.txt file contains no data (just two numbers and the "." that signals the end of input data)
• The file contains information about exactly 30 places (the maximum possible)
• The user asks for the distance to the first place on the list, the last one, or one in between, or one that doesn't exist.

As part of the report you turn in with this assignment (see below), you will need to describe how you tested the program and why you believe that your tests demonstrate that it works properly.

Sample Program

There is no sample program for this assignment; you should create a program that works as specified.  In cases where the specification is not clear, you may need to make some reasonable assumptions.  Also, feel free to discuss issues about the specifications on the course newsgroup, in sections, with your colleagues, etc.

Help!!! Where to I start?

In any non-trivial project, programming or otherwise, the job can often seem overwhelming at first - too many things to do all at once and no clear idea where to start.  An important skill to develop is to figure out what you can do first, without having to finish other things.  Here are some suggestions.

1. The place to start is not, I repeat not at the computer keyboard.  You have to do some thinking and planning before you start writing code.  Premature use of the computer is guaranteed, I repeat guaranteed to waste huge amounts of your time.
2. Start by planning, on paper, the data structures and functions you will need.  Write down fairly detailed data structure declarations.  Draw pictures.  Figure out what the functions need to do and what their parameters should be - but don't spend much time on implementation details now.
3. Figure out how you will test your code.  As you design data structures and specify functions, think about how they could fail(!) if you make a mistake.  Design a test that will catch that bug if it happens.  Write it down now, not later.
4. Only when you've gotten this far should you start writing detailed code on the computer.  You should develop the code bit-by-bit, getting some parts working, then add more until you have everything done.  You might try first getting the data structure definitions right, then implement the code to read the data from the file and store it in the data structure.  Inspect the data structure with the debugger or by printing it out at this point to verify that things are working so far.  Then add code to interact with the user, reading place names and printing distances.  Keep testing as you go.

Time spent planning and thinking at the beginning of the project will be more than repaid by time saved that would otherwise be needed to debug and fix problems.

Report

When you turn in your program, you must also turn in a short report that discusses the following issues:

1. Planning - How did you plan your code design for this problem.  What kinds of data structures and functions seemed necessary?
2. Implementation - Describe the implementation.  What data structures did you use?   How did you structure the code?  Were there any significant differences between the original design and the final program?  If there were major changes, why were they needed?
3. Testing - Describe the test cases you chose.  Describe the kinds of bugs you found using tests.  If some of your test cases still don't work, or there are parts of the program that are incomplete, describe that.  Attach some of your test cases and results to support your claims.
4. What did you learn from completing this project?  This could include things you learned about program specification and design, C++ language issues, developing test cases, debugging, etc.

This report need not be long, but it should be complete enough to give us a good picture of what you accomplished.

Electronic Submission

When you've finished your program, turn it in using this turnin form. Print out the receipt that appears, staple it and your report together, and hand it in during quiz section.