Description
Overview: In the not–to–distant future, you will be writing a program to create an index on a binary file. I
could just give you the binary file, or merge the two assignments, but creating the binary file from a formatted
text file makes for a nice “shake off the rust” assignment, plus it provides a gentle (?) introduction to binary
file processing.
A basic binary file contains information in the same format in which the information is held in memory. (In
a standard text file, all information is stored as ASCII or UNICODE characters.) As a result, binary files
are generally faster and easier for a program to read and write than are text files. When your data is wellstructured, doesn’t need to be read directly by people and doesn’t need to be ported to a different type of
system, binary files are usually the best way to store information.
For this program, we have lines of data items that we need to store, and each line’s items need to be stored
as a group (in a database, such a group of fields is called a record). Making this happen in Java requires a bit
of effort; Java wasn’t originally designed for this sort of task. By comparison, “systems” languages like C can
interact more directly with the operating system to provide more convenient file I/O. On the class web page
you’ll find a sample Java binary file I/O program, which should help get you started.
Assignment: To discourage procrastination, this assignment is in two parts, Part A and Part B:
Part A Available from lectura is a file named jan2018ontime.csv (see also the Data section, below). This
is a CSV (Comma–Separated Value) text file consisting of 570,119 lines of 19 values each about airline flights
in January of 2018.
Using Java 1.8, write a program named Prog1A.java that creates a binary version of the text file’s content
that is sorted (using a stable sort) in ascending order by the fifth field of each record (the ‘FL NUM’ field).
Additional details:
• For an input file named file.csv, name the binary file file.bin. (That is, keep the file name, but
change the extension.) Don’t put a path on it; just create it in the current directory.
• Field types are limited to int , double, and String. Follow the lead of the data. For example, if values
of a field are in quotes, assume that the field is a string (and don’t store the quote characters).
• For each column, all values must consume the same quantity of bytes. This is easy for numeric columns,
but for alphanumeric columns we don’t want to waste storage by choosing a huge maximum length.
Instead, you need to determine the number of characters in each field’s longest value, and use that as
the length of each value in that field. This must be done for each execution of the program. (Why?
Your program needs to work on other flight data files, too. You may assume that the field order, types,
and quantity will not change.) When necessary, pad strings on the right with spaces to reach the needed
length(s). (For example, “abc “, where ” ” represents the space character.
• Because the maximum lengths of the text fields can be different for different input files, you will need to
store these lengths in the binary file so that your Part B program can access them. One possibility is to
store the maximum lengths at the end of the binary file (after the last data record).
Repeating the info at the top of this handout: Part A is due in just one week; start today!
(Continued…)
DRAFT
Part B Write another complete, well-documented Java 1.8 program named Prog1B.java that performs both
of the following tasks, in this order:
1. Reads and prints to the screen the UNIQUE CARRIER, FL NUM, ORIGIN, and DEST field values of
the first five records of data, the middle three records (or middle four records, if the quantity of records
is even), and the last five records of data in the binary file. Conclude the output with the total number
of records in the binary file, on a new line.
2. Using one or more FL NUM values given by the user, locates within the binary file (using interpolation
search; see below), and displays to the screen, the same four field values of all records having the given
FL NUM value.
Some output details:
• Display the data one record per line, with a single space between the field values.
• seek() the Java API and ye shall find a method that will help you read the middle and last records of
the binary file.
• Use a loop to prompt the user for the FL NUM values. Terminate the program when a zero is entered.
Data: Write your programs to accept the complete data file pathname as a command line argument (for
Prog1A, that will be the pathname of the data file, and for Prog1B, the pathname of binary file created
by Prog1A). The complete lectura pathname of our data file is /home/cs460/fall18/jan2018ontime.csv.
Prog1A (when running on lectura, of course) can read the file directly from that directory; just provide that
path when you run your program. (That is, there’s no reason to waste disk space by making a copy of the file
in your account.)
Each of the lines in the file contains 19 fields (columns) of information. Here is one of them:
2018-01-01,”EV”,20366,”N604QX”,”2853″,”SAF”,”DFW”,””,,,””,””,,””,,1.00,”A”,,551.00,
Some file information:
• The field names can be found in the first line of the file. Because that line contains metadata, its content
must not be stored in the binary file.
• In some records, such as this sample, some field values are missing (see the adjacent commas?). However,
the binary file requires values to maintain the common record length. For missing numeric fields, store
-1. For missing strings, store a string containing the appropriate quantity of spaces.
• Please keep in mind that we have not combed through the data to see that it is all formatted perfectly.
This is completely intentional. Corrupt data is a huge problem in data management. We hope that this
file holds a few surprises. We want you to think about how to deal with malformed data, and to ask
questions of us as necessary.
Output: Output details for each program are stated in the Assignment section, above. Please ask (preferably
on Piazza) if you need additional details.
Hand In: You are required to submit your completed program files using the turnin facility on lectura. The
submission folder is cs460p1. Instructions are available from the document of submission instructions linked
to the class web page. In particular, because we will be grading your program on lectura, it needs to run
on lectura, so be sure to test it on lectura. Feel free to split up your code over additional files if doing so is
appropriate to achieve acceptable code modularity. Submit all files as-is, without packaging or compression.
(Continued…)
2
DRAFT
Want to Learn More?
• https://www.bts.gov/topics/airlines-and-airports-0 — The provided sample data was downloaded from the U.S. Department of Transportation’s Bureau of Transportation Statistics web site. Other
fields are available. If you’re curious: Click the “On-Time” drop down, and choose “Airline On-Time
Performance Databases”. On the next page, click “Download”. On the following page, select the desired
fields and click “Download” to create CSV.
Other Requirements and Hints:
• Don’t “hard–code” values in your program if you can avoid it. For example, don’t assume a certain
number of records in the input file or the binary file. Your program should automatically adapt to simple
changes, such as more or fewer lines in a file, or changes to the file names and paths. For example, we
may test your program with a file of just two records, or even no records. We expect that your program
will handle such situations gracefully.
• Once in a while, a student will think that “create a binary file” means “convert all the data into the
characters ‘0’ and ‘1’.” Don’t do that! The binary I/O functions in Java will read/write the data in
binary format automatically. See the example program on the class web page.
• Try this: Comment your code according to the style guidelines as you write the code (not an hour before
the due date and time!). Explaining in words what your code must accomplish before you write that
code is likely to result in better code. The requirements and some examples are available from:
http://u.arizona.edu/~mccann/style.html
• You can make debugging easier by using only a few lines of data from the data file for your initial testing.
Try running the program on the complete file only when you can process a few reduced data files.
• Late days can be used on each part of the assignment, if necessary, but we are limiting you to at most
two late days on Part A. For example, you could burn one late day by turning in Part A 18 hours late,
and three more by turning in Part B two and a half days late. Of course, it’s best if you don’t use any.
• Finally: Start early! File processing can be tricky.
Interpolation Search
Interpolation Search is an enhanced binary search. To be most effective, these conditions must exist: (1) The
data is stored in a direct-access data structure (such as a binary file of uniformly-sized records), (2) the data
is in sorted order by the search key, (3) the data is uniformly distributed, and (4) there’s a lot of data. In such
situations, the reduction in quantity of probes over binary search is likely to be particularly beneficial given
the inherent delay that exists in file accesses. Our data falls short on (3) and (4), but that’s OK; the search
will still work.
Interpolation Search is just like binary search, with one change: Instead of probing the data at the midpoint
(one-half of low index plus high index), we use the following probe index calculation:
probe index = low index +
target − key[low index]
key[high index] − key[low index] · (high index − low index)
For example, consider a binary file of 60,000 records (indices 0 through 59,999), with keys that range from
100 through 150,000, and a target of 125,000. Thus, low index = 0, high index = 59999, key[low index]
= 100, key[high index] = 150000, and target = 125000. Our first probe into the file would be into record
number 0 + l
125000−100
150000−100 · (59999 − 0)m
= 49993.
3
