CS31: Lab 2

This lab should be done with your assigned partner:

Lab 2 Goals:

Practice with C programming basics: declaring vars, types, arrays, functions
Writing C code and functions that use statically declared arrays
Practice writing and using C functions. Pass by value: basic types and array parameters.
C I/O: scanf, printf, and using a file reading library.
More practice with top-down design.
Using a Makefile.
Practice with using a git repo to share code with a partner.

The expectation is that you and your partner are working together side by side in the lab for most, if not all, of the time you work on a lab assignments. You and your partner should work on all aspects of the project together: initial top-down design, incremental testing and debugging, and final stress testing and code review. There may be short periods of time where you each go off and impelement some small part independently. However, you should frequently come back together, talk through your changes, push and pull each others code from the repo and try out your merged code together. Taking time to design a plan for your solution together and to do incremental implementation and testing together may seem like it is a waste of time, but in the long run it will save you a lot of time by making it less likely that you have design or logic errors in your solution, and by having a partner to help track down bugs and to help come up with solutions to problems.

Partnerships where partners work mostly independently rarely work out well and rarely result in complete, correct and robust solutions. Partnerships where partners work side-by-side for all or most of the time tend to work out very well.

You and your partner are equally responsible for scheduling times when you can meet to work together, and for making time available in your schedule for working together.

Lab 2 Starting Point Code

Both you and your partner should do:

Get your Lab2 ssh-URL from the GitHub server for our class: CS31-F17
On the CS system, cd into your cs31/labs subdirectory
```
cd ~/cs31/labs
```
Clone a local copy of your shared repo in your private cs31/labs subdirectory:
```
git clone [your_Lab2_URL]
```

If all was successful, you should see the following files when you run ls:

ls
  Makefile       README.md   floats2.txt  floatsbig.txt  readfile.h
  QUESTIONNAIRE  floats.txt  floats3.txt  readfile.c     sorter.c

If this didn't work, or for more detailed instructions see the the Using git page.

As you and your partner work on your joint solution, you will want to push and pull changes from the master into your local repo.

We will do this together in Wednesday lab:
Try out git push and pull before working on lab 2 code:

Both of you add some minor change to the program like printing out your name in the main function.
Both compile and run and make sure your change doesn't break the code.
Both do a git add and a git commit.
One of you try doing a git push.
Then the other try doing a git pull (you should see your partner's code). Compile run and test it out. Now do a git add, git commit, git push.
Now, first pusher do git pull to pull changes into their local.

Also, it is good practice to do a make clean before doing a git add and commit: you do not want to add to the repo any files that are built by gcc (e.g. executable files). Included in your Lab2 git repo is a .gitignore file telling git to ignore these files, so you likely won't add these types of files by accident. However, if you have other gcc generated binaries in your repo, please be careful about this.

Lab Overview

You will implement program that sorts floating point numbers using a sorting algorithm of your choice in C. Your program will read a collection of unsorted floats from a file, store those floats in an array, provide some information about the floats to the user, sort them from smallest to largest (i.e., ascending order), and print them out in sorted form to the user.

Lab 1 Starting Point Code

Makefile: Use it to compile your code (and to clean it up).
```
make
make clean
```
We will look at writing Makefiles later in the semester. You're welcome to look at its contents now, but you do not need to edit it for this lab.

readfile.h and readfile.c:These files contain a library for reading from files. You should make calls to functions in this library in your program. The instructions for using this library are explained below. Later in the semester you will write your own library code, but for this assignment you will just use this readfile library code that is already written for you.
You should not modify any code in these two files.

sorter.c: the file into which you will add your C solution and comments. The starting point code includes one helper function:
- get_filename_from_commandline: takes the storage space for a string and the command line arguments and initializes the string storage space with the filename from the command line argument. You should not change this function, but feel free to change where it gets called in your program.

floats.txt, floats2.txt, floats3.txt, and floatsbig.txt: example input files to your program. These are provided for your convenience to help you test your program. You will likely want to create other test files to more extensively test your program before you consider it finished.

To compile your program, run make, which will use the Makefile to build your program (and link in the provided readfile library). Running make will show you the compiler output, which you should examine for errors and warnings. There is one unused variable warning with the starting point code that will go away when you write code that uses this variable.

  $ make
  gcc -g -Wall -Wvla -Werror -Wno-error=unused-variable -c readfile.c
  gcc -g -Wall -Wvla -Werror -Wno-error=unused-variable -o sorter sorter.c  readfile.o
  sorter.c: In function 'main':
  sorter.c:30:9: warning: unused variable 'values' [-Wunused-variable]
   float values[ARRAYSIZE];

Program Start-up

Your program will take one command line argument: the name of the input file containing floating point values to sort, one on each line. It should read values from the file (using the provided library), print the unsorted values, sort them, and print out the sorted result back to the user. Here is an example of how you invoke the program:

  $ ./sorter floats.txt

File Format

The input file format consists of several lines of an ASCII text file. A properly formatted file will contain a short header, consisting of a single line with one integer and two floats on it. These numbers represent the total number of floats in the file (i.e., the number of subsequent lines), as well as the minimum and maximum to-be-sorted float value in the file. These numbers will be written like this:

For example, here is the header of a valid input file:

  4 0.0 9.0

This header indicates that the file contains a total of 4 floats that need to be sorted. The smallest float value in the file will be 0.0, and the largest will be 9.0. You may not need to know the minimum and maximum values to successfully sort the values, but you will need to inform the user about the range of values being sorted.

Included with the starting point code are a few sample test files you can use to test your code. Every line after the first line in the file will contain a single floating point number. These are the float values that must be sorted. For example, a file containing the header we just saw might look like this (after the first line):

File I/O

For this assignment we'll use functions from the provided readfile library (in the files readfile.c and readfile.h). You should not change any code in these files. The readfile.h file contains function prototypes for the readfile library. There are function comments in this file that describe each function and a high-level comment that describes how to use the library.

Here are the general rules for how to use these functions:

Open a file by calling: open_file(), passing in the name of the file to open as a string. The return value of open_file() tells you whether or not the file was opened successfully. It returns 0 if the file is successfully opened, and -1 if the file cannot be opened. You should always check the return value of this function and respond appropriately!

Call the read_int(), read_string(), read_float() functions to read values from the file into your program's variables, where the name of the function you call determines the resulting type of the return value. Like open_file(), these functions return 0 on success, and you should always check their return value. If you've reached the end of the file, they will return -1.

These functions take arguments much like scanf does: they need to know the memory location of where to put the value read in.

For example:
```
  int x;
  float f;
  char s[20];
  ...
  /* These functions return 0 on success or -1 if read fails or
   * if there is nothing left to read (end-of-file has been reached). */
  ret = read_float(&f); 
  ret = read_int(&x)
  ret = read_string(s)
```

Close the file when you're done with it: close_file().

If you are curious, the implementation of these functions is in readfile.c. You can take a look and see how it uses the C FILE * interface and fscanf functions for reading. We will use this interface directly later in the semester. For now, we're hiding it under a layer of abstraction.

Requirements

Your program's output should look like this: output from an example run. It doesn't show every possible run or error handling, but should give you some idea of what a correct program will look like. To make my job of grading easier, please make your output match the example as closely as possible.

For full credit, your solution should meet the following requirements:

As in the example above, you program should print the following four items in a human-readable way:
1. The name of the file.
2. The header contents of the file (number of values, max/min values).
3. The values in their original, unsorted order.
4. The values in sorted order, from smallest to largest.

You should store the set of floating point values only once (e.g., keep only one array, don't copy all the values to a second array). You may assume that there will never be more than 1000 values to sort, and you can use any sorting algorithm you like, it doesn't need to be fancy. You should not attempt to use merge sort, as we haven't yet discussed all the C functionality that you'll need to implement it.

Your program should exit gracefully if you detect an error that's not your code's fault (for example, if it was given the name of an invalid input file). Be sure to check those return values!

You should implement a helper function that takes the array and its size, checks to see if the array is in sorted order, and returns a value specifiying if it is sorted or not. This will be particularly useful for correctness testing of your sorting function for runs on large input files.

It should be evident that you applied top-down design when constructing your submission. In addition to main(), you should have at least three non-trivial functions, each with a specific role. (See the Implementation Recommendations section below for suggestions.)

Do not wrap lines in your C code files: all lines of code in your program should be less than 80 characters long (including white space characters). Hit return and continue on the statement (nicely indented) on the next line.

Your code should be commented, modular, robust, and use meaningful variable and function names. This includes having a top-level comment describing your program and listing your and your partner's names and the date. Every function should include a brief description of its behavior, a description of its parameter values and a description of its possible return values.
Look at my C style Guide For example of good comments, how not to wrap lines and some tips for breaking up long statements into multiple lines of C code, good indenting style, and suggetions for good function and variable naming in your programs.

Your program should not use global variables. If a function needs a value from the caller, then that value should be passed in as a parameter. If a function needs to store variables, then those should be declared as local variables inside the function. If you don't know what a global variable is, no problem, you won't make the mistake of using one!

The code you submit should have no "TODO" comments left in it. These are notes to you in the starting point code. You should replace them with actual code and/or comments that you add.

Your code should compile cleanly with no errors or warnings and should not crash unexpectedly during execution.

Implementation Recommendations

The following is the suggested way to implement the lab and fulfill the requirements. If you intend to significantly deviate from this design, please let me know so that I can do a basic sanity check of your proposed changes.

Store the floating point values in an array of C float types.

Write a function that knows how to print the contents of an array of floating point values. You'll use this twice: once to print the original unsorted values, and later, to print the sorted values.

Write a sort function that takes in an array of floating point values (and the size of the array), sorting the array values such that the original array is in sorted order after the call completes. You will likely find it useful for your sort function to call a helper function that you define to swap the contents of an array, given two indices and the array.

Tips

Before even starting to write code, you and your partner should use top-down design to break your program into manageable functionality.

Test your code in small increments. It's much easier to localize a bug when you've only changed a few lines.

Many of the functions that you'll write to deal with arrays will need to know the size (length) of the array. Unlike Python, C does NOT keep that information around (there is no len() function). If a function needs to know the array length, you should probably make that a parameter to the function.

When printing floating point values, you can make the output more readable by limiting the number of digits that get printed after the decimal point. For example, using %.2f in the format string for printf() will limit the printed float to two digits after the decimal.

For values that will never change in your program, you can compile in constants using #defines.

Use CNTRL-C to kill a running program stuck in an infinite loop.

Post on Piazza, attend ninja sessions, and/or come to office hours if you have questions!

To debug programs with command line options in gdb, include the command line arugments when you start the program with the gdb run command:
```
gdb ./sorter
(gdb) break main
(gdb) run floats.txt
```

Lab Questionnaire

With every lab assignment is a file named QUESTIONNAIRE for you to fill out (with vim or another Unix editor) and submit with your lab solution. In this file you will answer some questions about the lab assignment. You should fill this out and submit it with your lab solution.

Submit

Before the Due Date

Only one of you or your partner needs to push your solution from one of your local repos to the GitHub remote repo. (It doesn't hurt if you both push, but the last pushed version before the due date is the one we will grade, so be careful that you are pushing the version you want to submit for grading):

From one of your local repos (in your ~you/cs31/labs/Lab2-partner1-partner2 subdirectory)

git push

Troubleshooting

If git push fails, then there are likely local changes you haven't committed. Commit those first, then try pushing again:

git add sorter.c
git add QUESTIONNAIRE
git commit
git push

Another likely source of a failed push is that your partner pushed, and you have not pulled their changes. Do a git pull. Compile and test that your code still works. Then you can add, commit, and push.

If that doesn't work, take a look at the "Troubleshooting" section of the Using git page. You may need to pull and merge some changes from master into your local. If so, this indicates that your partner pushed changes that you have not yet merged into your local. Anytime you pull into your local, you need to check that your code still works before submitting.

CS31 Lab 2: C Warm-up: Sorting