Complex iterators in C

cc99iterator

Part of my current project involves iterating over sequences that don't necessarily exist. For example, I have something similar to a relational database in memory, so say I have three arrays

typedef struct { size_t car_index, size_t part_index } car_part_t;

car_ * cars;
part_t * parts;
car_part * car_parts;

I want to be able to iterate over all the parts in a given car, for example. I specifically want the part and not the car_part. My current solution is

typedef struct {
    size_t car_index;
    size_t part_index;
    size_t m_car_part_index; // keeps progress
} car_part_iterator_t;

and to have two functions

car_part_iterator_t car_part_first(size_t car_index);

which returns an iterator set up such that it.part_index is the index of the part in parts, it.car_index is the car selected by the first parameter, and it.m_car_part_index is a 'private' variable used to track progress in the car_parts list.

I then have a similar function for getting the next one

bool car_part_next(car_part_iterator_t * it);

which moves to the next car part, and returns if the iterator is still valid. Finally for completeness I have

bool car_part_valid(car_part_iterator it);

to check if the current iterator is still valid. So it can be used in a for loop like

for (car_part_iterator_t it = car_part_first(car_index);
    car_part_valid(it); car_part_next(&it))
{
    // use it.part_index ...
}

To me, this sounds like a good solution that I came to after some trial and error. I also experimented with a function that returns an iterator before the first result, so the next` function would return the first result, for use in while loops.

Is this a good pattern? I assume a known one. Does it have a name? Are there pitfalls I'm not seeing?

notes:

On SO the generality of this was questioned (ie it can be made more general), but as it stands I'm not too bothered about that.

It was also pointed out that the valid function isn't strictly needed for the loop, but it allows for a more natural for loop, and is also sometimes useful outside of loops.

Best Answer

Is this a good pattern?

Yes, in general.

I can't see how it interacts with your data in detail, but it works well in lots of places, and is probably fine here too.

I assume a known one. Does it have a name?

It's just the iterator pattern. It may be more complex than a linked-list or array iterator, but it's not so obviously different to a tree iterator.

Are there pitfalls I'm not seeing?

Well, your current implementation seems to depend on global state. Generalizing this aspect is probably a good idea.

Lastly, when you said the sequence might not exist, I was expecting to see an iterator lazily generating the values. Since that isn't the case here, what do you actually mean?

Related Solutions

Iterators – Advantages of Next-Iterator Over This-Iterator

I think an advantage of C#/.NET's MoveNext() model over Java's hasNext() model is that the former implies that some work may be done. The hasNext() method implies a simple state check. But what if you are iterating a lazy stream, and you have to go out to a database to determine whether there are any results? In that case, the first call to hasNext() may be a long blocking operation. The naming of the hasNext() method can be very misleading as to what's actually going on.

For a real world example, this design issue bit me when implementing Microsoft's Reactive Extensions (Rx) APIs in Java. Specifically, for the iterator created by IObservable.asIterable() to function properly, the hasNext() method would have to block and wait for the next item/error/completion notification to arrive. That's hardly intuitive: the name implies a simple state check. Contrast that to the C# design, where MoveNext() would have to block, which is not an altogether unexpected result when you are dealing with a lazily evaluated stream.

My point is this: the "next-iterator" model is preferable to the "this-iterator" model because the "this-iterator" model is often a lie: you may be required to pre-fetch the next element in order to check the state of the iterator. A design which communicates that possibility clearly is preferable, in my opinion. Yes, Java's naming conventions do follow the "next" model, but the behavioral implications are similar to those of the "this-iterator" model.

Clarification: Perhaps contrasting Java and C# was a poor choice, because Java's model is deceptive. I consider the most important distinction in the models presented by the OP to be that the "this-iterator" model decouples the "is valid" logic from the "retrieve current/next element" logic, while an ideal "next-iterator" implementation combines these operations. I feel it is appropriate to combine them because, in some cases, determining whether the iterator's state is valid requires prefetching the next element, so that possibility should be made as explicit as possible.

I do not see a significant design difference between:

while (i.isValid()) { // do we have an element?  (implied as fast, non-blocking)
    doSomething(i.current()); // retrieve the element (may be slow!)
    i.next();
}
// ...and:
while (i.hasNext()) { // do we have an element?  (implied as fast, non-blocking)
    doSomething(i.next()); // retrieve the element (may be slow!)
}

But I do see a meaningful difference here:

while (i.hasNext()) { // do we have an element?  (implied as fast, non-blocking)
    doSomething(i.next()); // retrieve the element (may be slow!)
}
// ...and:
while (i.moveNext()) { // fetch the next element if it exists (may be slow!)
    doSomething(i.current()); // get the element  (implied as fast, non-blocking)
}

In both the isValid() and hasNext() examples, the operation that is implied to be a fast and non-blocking state check may in fact be a slow, blocking operation. In the moveNext() example, most of the work is being done in the method you'd expect, regardless of whether you are dealing with an eagerly or lazily evaluated stream.

Design Patterns – What Makes the Iterator a Design Pattern?

Most of the patterns from the GoF book have the following things in common:

they solve basic design problems, using object-oriented means
people often face these kind problems in arbitrary programs, indepently from the domain or business
they are recipes for making the code more reusable, often by making it more SOLID
they present canonic solutions to these problems

The problems solved by these patterns are so basic that many developers understand them mainly as workarounds for missing programming language features, which is IMHO a valid point of view (note that the GoF book is from 1995, where Java and C++ did not offer so many features as today).

The iterator pattern fits well into this description: it solves a basic problem which occurs very often, independently from any specific domain, and as you wrote by yourself it is a good example for "separation of concerns". As you surely know, direct iterator support is something you find in a lot of contempary programming languages today.

Now compare this to the problems you picked:

writing to a file - that is IMHO simply not "basic" enough. It is a very specific problem. Nor is there a good, canonic solution - there are lots of different approaches how to write to a file, and no clear "best practice".
Painter, Encoder: whatever you have in mind with that, those problems look even less basic to me, and not even domain independent.
having the "power" function available for different kind of objects: at a first glance, that could be worth beeing a pattern, but your proposed solution does not convince me - it looks more like an attempt to shoehorn the power function into something similar to the iterator pattern. I implemented a lot of code with engineering calculations, but I cannot remember a situation where an approach similar to your power function object would have helped me (however, iterators is something I have to deal with on a daily basis).

Moreover, I do not see anything in your power function example which could not be interpreted as an application of the strategy pattern or the command pattern, which means those basic parts are already in the GoF book. A better solution might contain either operator overloading or extension methods, but those are things are subject to language features, and that is exactly what the "OO means" used by the "Gang" could not provide.

Best Answer

Related Solutions

Iterators – Advantages of Next-Iterator Over This-Iterator

Design Patterns – What Makes the Iterator a Design Pattern?

Related Topic