Code Dive: Custom iterators in Hellenica (Part 1)

Recently I've been digging around in some code I wrote a long while back, and it reminded me of one handy feature of C# that I thought worth explaining here. It's been too long since we've had a hearty code post! There's a bit of background info I'll need to go over to make sure everyone's on the same page, so I've broken things up into two separate posts. This week I'll explain the C# feature, and next week I'll go over an example of its use in Hellenica.

When you write game code, or any kind of code really, you often spend a good deal of time iterating through collections of things. Usually this is something simple like a list of values, and it's easy enough to write code to step through them.

If you wanted to print out each of these values in order, you could write code like this:

foreach (int value in superImportantValues)

{
    print(value);

}

This would output:

12345678

Sometimes your data isn't so simply organized, however. Usually the code we write needs to perform some task under a specific set of constraints; perhaps we need it to run a specific operation very quickly for a large set of data, or maybe we need it to be able to do many things but only within a very small amount of memory.

Programmers have devised a number of special structures and techniques to store and interact with collections of data in ways that address these constraints. Consider this tree structure:

These are still the same super important values from our list earlier, but now the conceptual model used to represent the collection is very different. This specific structure is handy for quickly searching for a specific value, but it's not as clear how we might step through and add up the total of each of the values in this... thing.

It would be great if there were a simple way to iterate over these values just like I did in the previous list example without having to add complexity to my code every time I wanted to do so. In C#, there is a built-in type called IEnumerator<T> that allows you to define an iterator over any sort of complex collection of items, so long as you can tell the compiler how to do it. Here's what that might look like for this type of data structure:

IEnumerator<int> in_order_tree_traversal(Node root)
{
    Node current_node = root;
    Stack<Node> node_stack = new Stack<Node>();

    while (node_stack.Count > 0 || current_node != null)
    {
        if (current_node == null)
        {
            current_node = node_stack.Pop();

            yield return current_node.value;

            current_node = current_node.right;
        }
        else if (current_node.left != null)
        {
            node_stack.Push(current_node);
            current_node = current_node.left;
        }
        else
        {
            yield return current_node.value;

            current_node = current_node.right;
        }
    }
}

I claim that this function will climb around that tree from above and return each of our super important values in order. The specifics of the algorithm aren't vital to this discussion, but feel free to dig through it if you're interested.

I do want to draw your attention to the bolded statements in the code, though.

The first is IEnumerator<int> in the function definition at the top. This tells us that calling this function in_order_traversal will return to us an object that will enumerate a collection of integer values. Sounds promising so far!

The second are the yield return statements, of which there are two in the example. This is the C# secret sauce. These are the guys that tell the program, "Hey! We found another value that you might care about!" When execution hits one of these statements, it returns the value just like a normal function, but importantly, the state of the function is preserved -- local variables, the next instruction, everything. So, when we come back and ask for another value, the process can start up right where it left off.

It might help to see how to use this IEnumerator<int> thing. Here's an example similar to our previous one:

IEnumerator<int> superImportantValues = in_order_traversal(superImportantTree);
while (superImportantValues.MoveNext())
{
    print(superImportantValues.Current);
}

Pretty cool! Even though the user code looks fairly similar, internally we're now climbing all over a complex tree structure instead of just walking through a linear list. Let's look at what's going on here:

IEnumerator<int> superImportantValues = in_order_traversal(superImportantTree);

First, we're calling our new function and getting an object of type IEnumerator<int>. This is just a thing we can use to iterate over a collection of integer values.

while (superImportantValues.MoveNext())
{

Next, we use MoveNext() to find the next value in our tree by running our code until it hits another yield return statement. (If we reach the end of our iterator function without finding a yield return statement, MoveNext() will return false, signaling to us that we've seen all of the values.)

    print(superImportantValues.Current);

Lastly, we use .Current to look at the last value that our iterator found. We can keep referencing .Current to access the same value until we call MoveNext() again.

Still with me? That's one example of how to use yield return statements and the IEnumerator<T> type. All in all, a pretty convenient way to write a custom iterator for a collection of data.

Perhaps more interestingly, there's no limitation to the kind of collection you can iterate over. That collection could even be something you generate on the fly instead of something stored in memory. Next week, I'll go over one way we use this idea in Hellenica to do some of our combat calculations!