Standard Iterator Categories for RangeSetBase

[mgsutton]

Hi Folks, Would it make sense to add stl iterator_categories (and all the other sundry stl iterator typedefs) for the RangeSetBase class? There are times when I would like to use stl algorithms on some entitie of the mesh, like:

std::transform(begin(mesh.faces()), end(mesh.faces()),...)

But, it seems we need category support for that. My guess is that std::forward_iterator_tag would be the most likely candidate, but maybe std::bidirectional_iterator_tag would work too?

Ultimately, I would like to be able to use the parallel version of the stl algorithms, which I currently do in some code. But, I end up first copying the entity handles to a std::vector with a range based for loop, and then use that sequence as my iteration range for the algorithm. From a performance standpoint, the penalty of copying is probably in the noise for cases where parallelizing things is a benefit, but it still seems wasteful. I only bring that up because I don't quite know all the details for how the parallel versions of the std algorithms partition things, etc... Therefore, I don't know how smart/safe/etc... a given iterator/container pair need to actually be to work correctly in the parallel versions of the algorithms. A vector of handles seems to work fine, but obviously that is the least restrictive container/iterator type.

As a last thought, this may also play into enhancing general const-correctness for the overall api as well. However, I seem to gather from #66 it is not as trival as sprinkling const everywhere.

[nmwsharp]

At the high level I think this sounds great, and would be very happy to see changes like this! I'm not too knowledgable about the different tags and categories, but I think forward and bidirectional should both be easy (whereas random access is not easy).

I have a vague memory that when I initially set up the iterator classes, there was a blocker that made it difficult to satisfy the stl iterator requirements. Perhaps that the stl iterators expect a it++ operator, but "incrementing" an element doesn't really make sense. I suppose there's no real downside to implementing an increment operator like face++ etc, but it's something we should think carefully about.

For const-correctness, yes please! The more const the better! Const containers eluded me initially as mentioned in #66, but I'm sure it's doable. And more generally, there are likely other places a const can be dropped in. Even if it requires some redesign, those redesigns are usually good improvements. A related thought: I'm always deeply curious about inlining/optimization, and when we pay a price for using Vertex handle objects rather than raw indices. It would be really awesome to find places where adding a const helps the compiler find optimizations like it would with raw indices.... but this is far beyond my own low-level C++ skills!

[mgsutton]

Hey Nicholas, I think I see your concerns. I certainly don't know all of the design decsions that went into the library, so please don't construe this as some sort of veiled criticism. It is a very impressive piece of work. I have seen in other libraries an api pattern where they expose an entity (face, edge...) and then they expose entirely separate entity_iterators. Then, to the set of entity_iterators, they add an entire set of const_entity_iterators. And then after that, they might need special iterator types for things like circulators or other kinds of "topologically smart" iterators (and their const variety). So, the down side is you end up with like MN classes just to support N entities, where M isn't necessarily tiny. The upside is that you get a clear separation of concerns, so your notion of iterating a face is replaced with iterating some kind of iterator. Finally, I think (blindly hope) that if you implement it well, the compilers can reduce it all down to just the bare index manipulations. Obviously, though, any change like this would be very wide sweeping, and way more than my original suggestion. And, regarding my original suggestion, I agree that it needs more thought. It really might not be a very good idea to continue further down the path of bluring the lines between what is an iterator and what is an entity. Or, maybe I'm just completely misunderstanding the whole design as it current stands!

[nmwsharp]

Design comments are very welcome! As with all projects the library is far from perfect, and these conversations can always influence future changes :)

Actually, thinking about this some more, what we implement is very similar to the common paradigm you describe. Geometry-central does already define set types and iterator logic for each kind of traversal.

The classes are declared in halfedge_element_types.h, with the logic in halfedge_element_types.ipp. However, just looking at those it's not clear that they fulfill the iterator paradigm, because they are actually just template substitutions for the RangeIterator and NavigationIterator defined in element_iterators.h. There you'll find exactly the usual ++ and * operators one would expect (though we lack const versions of these as, you mention).

Soooooo.... perhaps I need to think a bit more about what the actual blocker is to using these as STL iterators. There's even a comment about STL iterators from past-me at the top of element_iterators.h, but I don't really understand what past-me was saying there. It seems like just exposing RangeIteratorBase<F>::begin()/end() might be enough to get rolling with STL.

[mgsutton]

Yeah. In years past I used to rely pretty heavily on boost for random stuff until it just became way too heavy to be of use. Having said that, are you familar with boost's iterator_facade template? It might help guide how to write a STL friendly iterator in terms of the necessary type traits, etc... Honestly, I think all the type trait decorations are primarily what's missing, but I could be wrong. I do now see your comment in element_iterators.h, but I'm not sure I'm following what you were getting when you said that an iterator expects a container to have one set of data over which to iterate? I don't think the iterator concepts are quite that restrictive. I don't even think you need a container to have an iterator. As long as end() is reachable from begin()', and you have an increment, I think you're mostly good. But, maybe you were refering to the idea that a mesh has lots of different kinds of entities, so it can expose a singlebegin()/end()` pair?

[nmwsharp]

Yeah, let's assume that that comment in the source code is a stale comment and not true :)

Just adding type traits sounds reasonable to me! And as long as it works, I don't really think there's really any downside either.