Please see the general programming webpage for details about the programming environment for this course, guidelines for programming style, and details on electronic submission of assignments.

Collaboration Policy

For this assignment, you must work individually in regard to the design and implementation of your project.

Please make sure you adhere to the policies on academic integrity in this regard.

Contents:

• Overview
• Limitations
• Files We Are Providing
• Using Our Driver
• Files to Submit
  • Source Code
  • Readme File
• Grading Standards

Overview

Our goal for this assignment is to manipulate list of integers and iterators for those lists. Given two lists, both of which are known to be sorted in non-decreasing order, your goal is to efficiently merge the elements from the second list into the first list, while ensuring that the combined result is still sorted. Because the two original lists are internally sorted, the merging process can be completed in linear time.

The source code for the entire project is already complete, with the exception of a single routine that we ask you to implement.

/**
 * Given two distinct lists, each of which are assumed to be sorted in
 * non-decreasing order, this function mutates the primary list so as
 * to include all elements of the secondary list while maintaining the
 * non-decreasing invariant.
 */
void merge(list& primary, const list& secondary)

Before writing your code, think about how you will accomplish the task. It may help to consider the process you might use if doing this with lists written on paper. You might imagine placing one finger at the beginning of the first list and one finger at the beginning of the second list. Now, you should be able to advance the fingers in a way, ensuring that items are copied from the second list into the proper place in the first list as you go. To implement this strategy, the iterator classes can be used to represent the idea of a finger moving through a list.

Advice: if you are having trouble, always consider that a problem can be fixed by simplifying your code rather than complicating it. There exists a remarkably simple solution to this assignment. In fact, the merging process is described on page 491 of the text, due to its role in the larger context of designing an algorithm for sorting elements. You may skim that material from the book for general guidelines regarding the merging process, but the implementation details for this assignment vary greatly from the coverage in the book. In particular, the description in the book creates a third list as the result, rather than mutating one of the original lists. Furthermore, the book bases its description on their Sequence ADT rather than the stl::list interface.

Limitations

Our goal for this assignment is to have you get used to using the standard library list class and its iterator and const_iterator classes for low-level manipulations of a list. The list class includes some higher-level functionality including, as it happens, a function to merge a second list into a first. Needless to say, you are not allowed to use that method for this assignment (nor should you be using the sort method). You should be primarily relying on the insert method to add individual elements to your list.

Files We Are Providing

All such files can be downloaded here.

• Merger.cpp
  This is the one file which you surely must modify It contains a stub for the merge function, yet without any code.

• MergeTest.cpp
  This file provides a main driver to be used in testing your program. You will not need to modify or examine this code. The use of the driver is discussed later in this assignment description.

• makefile
  This makefile should allow you to rebuild your project by simply typing 'make' rather than in invoking the compiler directly.

Using Our Driver

The executable MergeTest is a driver which will handle reading the input, creating the initial lists, calling your routine, and then outputting the merged result.

You will need to design your own input; in particular, I recommend constructing a simpler merging example when starting the project, since you may need to debug initially and may not want to run the full test code. Your full test code should consider several variations and ways to "trick" the merger code, so be sure to test exhaustively and think about how things could be broken!

The expected format for input is as follows:

• Each line is to contain a single integer.
• The end of a particular list is indicated by 1000.
• The final end of data is indicated by -1.
• All other integer values must be between 0 and 999.
• Each individual list must have elements entered in non-decreasing order.
• Duplicate values may appear in one or both of the lists. In this case, the final merged list will contain multiple copies of those particular values.
• The file is at most 100 lines.

You will notice that this format allows you to specify a test file which involves many different merges, as demonstrated in the following example of a properly formatted input file.

5
9
12
1000
4
10
11
15
1000
3
4
1000
1000
1
5
5
8
1000
2
8
10
1000
-1

The driver will create the two lists A = {5, 9, 12} and B = {4, 10, 11, 15}, and then invoke merge(A,B). Hopefully this results in A = {4, 5, 9, 10, 11, 12, 15}.

After that, it will create two lists A = {3, 4} and B = { }, and again call merge(A,B) (which hopefully results in A = {3, 4}).

Then it will merge {1, 5, 5, 8} and {2, 8, 10}, hopefully producing the list {1, 2, 5, 5, 8, 8, 10}. After this, it exits.

By default, the driver reads input from the keyboard. However, if you would like to have the driver read input from a text file, give the filename as a single argument when starting the program (as was done in an earlier programming assignment)

The driver will output the sorted result. Your code is expected to succesfully sort all the inputs given in our test file.

Files to Submit

• Merger.cpp

• Test Input
  Please submit a single file, inputfile, which we will use as sample input when testing all of the students' submissions. The file format for inputfiles is based on use with our driver Your input file may use at most 100 lines (although you may certainly specify multiple merges within the 100 line limit). In order to make sure that your inputfile follows the proper format, we strongly recommend that you make sure that your inputfile is accepted by the driver. We also recommend you think about how your program could be defeated, and make sure to test several options.

• Readme File
  A brief summary of your program, and any further comments you wish to make to the grader.

Grading Standards

The assignment is worth 10 points. Eight points will be awarded based on our own evaluation of your assignment and the readme file. One additional point will be awarded fractionally based on how well your program performs on other students' test inputs. The final point will be awarded fractionally based on how well your test input fools other students' flawed programs.