Direct links to MP 3.1 and MP 3.2

Solo MP

This MP, as well as all other MPs in CS 225, are to be completed without a partner.

You are welcome to get help on the MP from course staff, via open lab hours, or Piazza!

Goals

In this MP (machine problem) you will:

Checking Out the Code

From your CS 225 git directory, run the following on EWS:

git fetch release
git merge release/mp3 -m "Merging initial mp3 files"

If you’re on your own machine, you may need to run:

git fetch release
git merge --allow-unrelated-histories release/mp3 -m "Merging initial mp3 files"

Upon a successful merge, your MP2 files are now in your mp3 directory.

Background Information: Template Classes

Identical to what you saw in lecture, template classes provide the ability to create generic container classes. In this MP, you will be writing a List class.

template <typename T>
class List {
    // implementation
};

This simply says that our class List has a parametrized type that we will call T. Similarly, the constructor will look like this:

template <typename T>
List<T>::List() {
    // implementation
}

We need the template <typename T> or template <class T> above all of our functions—it becomes part of the function signature. The keywords class and typename can be interchanged.

Template classes need access to the implementation for compilation. Every time a different class is used as the template, the code must be compiled to support containing it. For example, if you want to make a List<int>, the compiler must take the generic List<T> implementation code and replace all the Ts with ints inside it, and compile the result (this process is called template instantiation). Our solution to this is to #include "list-inl.h" at the bottom of our list.h file. This ensures that whenever a client includes our header file, he/she also gets the implementation as well for compilation purposes (there are other solutions, but this is how we will solve it in this course).

Background Information: Linked Lists

The interface of this List class is slightly different from what you have seen in lecture. This List has no sentinel nodes; the first node’s prev pointer, and the last node’s next pointer, are both NULL. In lieu of these sentinels, we keep a pointer head to the first node, and a pointer tail to the last node in the List. (In an empty list, both head and tail are NULL.) The List class also has an integer member variable, length, which represents the number of nodes in the List; you will need to maintain this variable.

Background Information: Iterators

We use iterators to figure out where we currently are in the list, what is the next/previous node, and to access the data. Iterator class has one member variable, namely a pointer to the node in the list. Some of the core functionality includes moving the pointer, getting current location, and checking the location of the iterator.

MP 3.1: A Linked List Implementation

In your mp3 folder, you will find that the List class is split into four .h files:

You should leave ‘list-given-inl.h’ as it is. We have provided you with a skeleton for the rest of the functions needed for this part of the MP, but you will need to write the implementations. They are designed to force you to write pointer manipulation code. You will write code for the functions, which are declared in list.h but not defined in list-inl.h. You must add your implementation to the file list-inl.h. Also, you will need to implement three functions in list-iter.h

See the Doxygen for MP 3 for details of the List class.

Notes on testing

There are two ways to test this MP:

  1. Using make to make main.cpp into ./mp3, which allows you to write your own lists to test.
  2. Using make test to make ./test, which allows you to run the automated tests.

You’re free to run Valgrind (or other tools) on the executables:

valgrind ./mp3
valgrind ./test
valgrind ./test "List::reverse"

MP 3.1.1: Iterator

In order to provide the client code with the ability to read the data from the list in a uniform way, we need to have an iterator. We have provided a list iterator class list-iter.h which has some functionality implemented. You will need to add the following implementations:

MP 3.1.2: ~List() and clear()

Since the List class has dynamic memory associated with it, we need to define all of the Rule of Three. We have provided you with the Copy Constructor and overloaded operator=.

MP 3.1.3: Insertion

MP 3.1.3.a: The insertFront Function

(See the Doxygen for insertFront.)

Example

For example, if insertFront is called on the list of integers

< 5 4 7 >

with the parameter 6, then the resultant list should be

< 6 5 4 7 >

MP 3.1.3.b: The insertBack Function

(See the Doxygen for insertBack.)

Example

For example, if insertBack is called on the list of integers

< 5 4 7 >

with the parameter 6, then the resultant list should be

< 5 4 7 6 >

Testing Your insert Functions

Once you have completed insertFront and insertBack, you should compile and test them:

make test
./test "List::insertFront"
./test "List::insertBack"

MP 3.1.4: Pointer Manipulation

MP 3.1.4.a: The reverse Helper Function

(See the Doxygen for reverse.)

In list-inl.h you will see that a public reverse method is already defined and given to you. You are to write the helper function that the method calls.

Example

For example, if we have a list of integers

< 1 2 3 4 5 6 7 >

(with head pointing at 1 and tail pointing at 7) and call the public function reverse()

The resulting list should be

< 7 6 5 4 3 2 1 >

(with head pointing at 7 and tail pointing at 1)

Your helper function should be as general as possible! In other words, do not assume your reverse() helper function is called only to reverse the entire list—it may be called to reverse only parts of a given list.

Additionally, the pointers startPoint and endPoint that are parameters to this function should at its completion point to the beginning and end of the new, reversed sublist.

We highly recommend you write this function iteratively. It is possible that you may run out of stack space if you write this function recursively.

MP 3.1.4.b: The reverseNth Function

(See the Doxygen for reverseNth.)

Example

For example, if reverseNth is called on the list of integers

< 1 2 3 4 5 6 7 8 9 >

then the call to reverseNth(3) should result in

< 3 2 1 6 5 4 9 8 7 >

For the list of integers

< 1 2 3 4 5 6 >

the call to reverseNth(4) should result in

< 4 3 2 1 6 5 >
Hint

You should try to use your reverse() helper function here.

Testing Your reverse Functions

Once you have completed reverse and reverseNth, you should compile and test them.

make test
./test "List::reverse"
./test "List::reverseNth #1"
./test "List::reverseNth #2"

MP 3.1.4.c: The waterfall Function

(See the Doxygen for waterfall.)

Example

For example, if waterfall is called on the list of integers

< 1 2 3 4 5 6 7 8 >

then the call to waterfall() should result in

< 1 3 5 7 2 6 4 8 >

(Do you see the pattern here?)

Step-by-Step Example

We will look again at the list

< 1 2 3 4 5 6 7 8 >

When we call waterfall, this is how it should look step-by-step:

< 1 2 3 4 5 6 7 8 > - Skip the 1
  ^             ^
curr           tail

< 1 3 4 5 6 7 8 2 > - Remove the 2 and move it at the end
    ^           ^
  curr         tail

< 1 3 5 6 7 8 2 4 > - Skip the 3, and move the 4 to the end
      ^         ^
    curr       tail

< 1 3 5 7 8 2 4 6 > - Skip the 5 and move the 6 to the end
        ^       ^
      curr     tail

< 1 3 5 7 2 4 6 8 > - Skip the 7 and move the 8 to the end
          ^     ^
        curr   tail

< 1 3 5 7 2 6 8 4 > - We have moved past the original tail of the list.
            ^   ^       This is okay! Skip the 2 and move the 4 to the end,
          curr tail     now for the second time!

< 1 3 5 7 2 6 4 8 > Skip the 6 and move the 8 to the end, now for the second time!
              ^ ^
           curr tail

We are done now because we skip over the 4 and get to the tail of the list. The 8 stays in place, and we have finished. If you were keeping track of moves, you would notice that a number (they happen to be in order here for convenience) gets moved the same amount of times as it is divisible by 2! Technically this might not be true for the 8, but we could have moved it that last time, it just would have stayed where it was (remove it from the tail and put it back to the tail). Kinda neat, huh?

Testing Your waterfall Function

Once you have completed waterfall, you should compile and test it.

make test
./test "List::waterfall"

MP 3.1.5: Testing

Compile your code using the following command:

make test

After compiling, you can run all of the MP 3.1 tests at once with the following command:

./test [part=1]
Notes
  • These tests are deliberately insufficient. We strongly recommend augmenting these tests with your own.
  • Be sure to think carefully about edge cases and reasonable behavior of each of the functions when called on an empty list, or when given an empty list as a parameter.
  • It is highly advised to test with lists of integers before testing with lists of HSLAPixels.
  • Printing out a list both forward and backwards is one way to check whether you have the double-linking correct, not just forward linking. Printing the size may also help debug other logical errors.

DOUBLE CHECK that you can confidently answer “no” to the following questions:

  • Did I allocate new memory in functions that disallow it?
  • Did I modify the data entry of any ListNode?
  • Do I leak memory?

MP 3.1: Extra Credit Submission

For extra credit, you can submit the code you have implemented and tested for part one of MP 3. Follow the instructions in the MP 3 Submission section for handing in your code.

MP 3.2: Sorting

You will be implementing the helper functions for one more member function of the List template class: sort. This is designed to help you practice pointer manipulation and solve an interesting algorithm problem. In the process of solving this problem, you will implement several helper functions along the way—we have provided public interfaces for these helper functions to help you test your code.

MP 3.2.1: The split Helper Function

(See the Doxygen for split.)

Example

For example, if split is called on the list of integers

list1 = < 1 2 3 4 5 >

then after calling list2 = list1.split(2) the lists will look like

list1 == < 1 2 >
list2 == < 3 4 5 >

Testing Your split Function

Once you have completed split, you should compile and test it.

make test
./test "List::split"

You should see images actual-split_*.png created in the working directory (these are generated by repeatedly splitting split.png). Compare them against expected-split_*.png.

MP 3.2.2: The merge Helper Function

(See the Doxygen for merge.)

Example

For example, if we have the following lists

list1 = < 1 3 4 6 >
list2 = < 2 5 7 >

then after calling list1.mergeWith(list2) the lists will look like

list1 == < 1 2 3 4 5 6 7 >
list2 == < >

Testing Your merge Function

Once you have completed merge, you should compile and test it.

make test
./test "List::merge"

You should see the image actual-merge.png created in the working directory if your program terminates properly. This is generated by merging the images tests/merge1.png and tests/merge2.png. Compare this against expected-merge.png.

MP 3.2: The mergesort Helper Function

(See the Doxygen for mergesort.)

Example

For example, if sort is called on the list of integers

< 6 1 5 8 4 3 7 2 9 >

the resulting list should be

< 1 2 3 4 5 6 7 8 9 >

Merge Sort — Algorithm Details

Merge Sort is a recursive sorting algorithm that behaves as follows:

In other words, Merge Sort operates on the principle of breaking the problem into smaller and smaller pieces, and merging the sorted, smaller lists together to finally end up at a completely sorted list.

MP 3.2: Testing

Compile your code using the following command:

make test

After compiling, you can run the MP 3.2 tests at once with the following command:

./test [part=2]
Hint: Comparing similar images

Occasionally diff may tell you that the 2 images differ, but you cannot easily tell the difference with the naked eye. In these scenarios, there is a great tool on ews machines called compare which can help you.

compare out.png out_01.png out_difference.png

This command will create a new image called out_difference.png where any differing pixels will be bright red.

Notes
  • These tests are deliberately insufficient. We strongly recommend augmenting these tests with your own.
  • Be sure to think carefully about reasonable behavior of each of the functions when called on an empty list, or when given an empty list as a parameter.
  • It is highly advised to test with lists of integers before testing with lists of HSLAPixels.
  • Printing out a list both forward and backwards is one way to check whether you have the double-linking correct, not just forward linking. Printing the size may also help debug other logical errors.

DOUBLE CHECK that you can confidently answer “no” to the following questions:

  • Did I allocate new memory in functions that disallow it?
  • Did I modify the data entry of any ListNode?
  • Do I leak memory?

MP 3: Submission

Our grading system will checkout your most recent (pre-deadline) commit for grading. Therefore, to hand in your code, all you have to do is commit it to your Subversion repository.

Be sure your working directory is the mp3 folder that was created when you checked out the code. To hand in your code, you first need to add the new files you created to the working copy of your repository by typing:

To commit your changes to the repository type:

git add -u
git commit -m "<your message>"
git push origin master
Guide: How to submit CS 225 work using git

Grading Information

The following files are used to grade MP 3:

All other files including any testing files you have added will not be used for grading.

Good Luck!