Implementing IntList, Phase 3: The Insertification

Our goal in this part is just to design implement the insert_after function. This is actually pretty straightforward, since you already know how to add nodes to the front and back of the list.

The Specification

Our function is defined as follows:

list.insert_after(it, value)

Inserts a new element with the given value immediately after the position indicated by the iterator it. It returns an iterator referring to the newly inserted element.

• Note: It is forbidden to try to insert after the end() iterator. Remember that end() is not a valid position in the list, but rather a marker that indicates "just gone off the end". If you try to insert after end(), you're trying to insert insert after after the end, which doesn't make sense.
• Likewise, you cannot use insert_after on an empty list, since there is no valid position in an empty list.

This operation is required to run in constant time.

Your Task, Part 1: Planning the Implementation

Before you start writing code, you need to think carefully about how insert_after will work. In particular, you need to think about the edge cases, especially when the list has only one element. The code will have a lot in common with the code you wrote for push_back.

You will need to do the following:

• Think about how insert_after will work.

• Make sure you've thought about the three edge cases we saw in the invariants discussion (and in particular, whether something special needs to happen when the list moves between these cases):

  • When the list is empty (this is forbidden, but you could add an assert to check for it).
  • When the list has one element.
  • When the list has two or more elements.
  • Something else…?

• Capture evidence of your planning as a .jpg file (either a photo of your nodes, whiteboard session, or a screenshot of your digital drawing), adding it to the Planning folder in your repository as Phase_3.jpg.

Your Task, Part 2: Adding the Declaration

Now that you have a plan for your implementation, you need to add the declaration for the insert_after function to your IntList class. This declaration should include the function signature and a brief docstring explaining what the function does.

The type signature should look like this:

    const_iterator insert_after(const_iterator it, int value);

Your Task, Part 3: Writing Testcases for insert_after

Extend your testcases in intlist-test.cpp to test the insert_after function. Think about the edge cases you need to test, especially when the list has only one element.

You can check the syntax of your testcases by running make intlist-test.o. You won't be able to run them against IntList yet, since you haven't implemented it, but at least you can check for serious issues with the tests. You can't test against IntVector, since it doesn't have an insert_after function.

Your Task, Part 4: Implementing and Testing insert_after

Now that you have a plan and testcases, it's time to implement the insert_after function in intlist.cpp. Be sure to add a call to check_invariants() at the end of the function, to make sure you haven't accidentally violated any invariants.

Once it's written, run your testcases to check that it works correctly.

cs70-make -H intlist-test
./intlist-test

As usual, if things fail, you can use valgrind to help you find the problem and all the usual debugging advice applies.

Your Task, Part 5: Enhancing the Snake Game

Now that we have a working insert_after function, we can use it to enhance the Snake game. Open config.hpp and replace content in the marked section with this new content:

#define COORDLIST_USES_INTLIST 1
#define COORDLIST_PROVIDES_ITERATOR 1
#define COORDLIST_PROVIDES_INSERT_AFTER 1

Then run:

cs70-make -H snake
./snake

Hopefully the game will work (and show the desired effect the snake eats a $ mutagen). If it doesn't work, it may indicate that you have a bug in your IntList class not captured by your testcases. You may be able to get some insight by running the game under valgrind, but do not spend significant time trying to understand the internal logic of the Snake game. If you can't find anything obvious wrong with your IntList class, ask for help on Piazza, during grutoring hours, or during lab, but you can move on to the next part of the assignment without getting this part working.

(When logged in, completion status appears here.)