weighted_random_access_iterator_tag

[Peter]

This ticket relates to various issues of how we should design things so that our algorithms can have different implementations for weighted and unweighted iterators, respectively.

[Markus Ringnér]

Well, iterator_traits need to return different tags for different types of iterators (that is how the partial template specializations of algorithms are called in the standard library). We need different tags for weighted and unweighted iterators to allow for our different algorithms. This could easily be solved with adding a separate structure of tags, together with a separate trait, and letting our iterators have a sixth typedef in addition to the 5 required by std::iterator. Using std was just a temporary way to do this so I could check in the distance functionality to get feedback.

[Peter]

I think we should add a new tag weighted or non-weighted. It goes under the rule that each tag should be responsible for one thing and one thing only.

Using a traits class (again) we can make all iterators be tagged as non-weighted and then specialize for our IteratorWeighted? to be tagged as weighted.

[Markus Ringnér]

Thinking about it again I disagree with creating a separate trait. Here is what I want to do:

1) weighted_random_access_iterator_tag should be in namespace utility and not in namespace std.

2) IteratorWeighted? should have an weighted_random_access_iterator_tag as iterator_category.

3) weighted_random_access_iterator_tag should be derived from std::random_access_iterator_tag

The first item means std is not contaminated and the original concern of this ticket is resolved.

This second item means there is only one tag but is it responsible for more than one thing? This single tag tells us which algorithms can be applied to an iterator. Is that being responsible for more than one thing? I guess one can argue both ways. However it is the second thing that will allow our algoritms to only have two partial template specializations, one for weighted and one for unweighted, and still support std iterators. Without using only single trait I think we will be back in having to implement many functions for each algorithm: for our iterators and std::iterators separately. This bloating is what we tried to avoid when going to iterators in the first place.

The third thing only means that when std algorithms are applied to IteratorWeighted? the fastest implementations are used.

[Markus Ringnér]

In [890] I changed according to the suggestion above. If this is ok then this ticket can be closed.

[Markus Ringnér]

Replying to markus:

In [890] I changed according to the suggestion above. If this is ok then this ticket can be closed.

Sorry! It should be [898] !!!!

[Peter]

This is fine with me. Some comment though

1. Good. Writing code in std is purely EVIL, and also ILLEGAL and that is never a good combination. If there is other examples of this in yat, it should be removed.

2-3) This is fine with me. For now, I don't think the double roles of weighted_random_access_iterator_tag should be a problem. However, I would like to point out that there are other solutions for this. We could have used the same pattern std uses for setting value in a iterator being a simple pointer. Pointers can not have typedefs like that, so how to do? Well instead of using iterator::value they use iterator_traits<iterator>::value, which typically just calls iterator::value. But for pointers there is a specialization, something like this

iterator_traits<T*> {
typedef T value
}

That is worth an invitation to Stockholms Stadshus.

[Markus Ringnér]

3 is not needed if we split the double roles.

If we split and want to avoid bloating one would have to write a trait that returns "unweighted_tag" for std iterators. I am sure it can be solved, but do not see the connection from your specialization above.

[Peter]

We do not have access to std and can thereby not setting typedefs in std::iterators. My point was that it is the same thing as when std had not access to set typedefs in "C pointers". The solution was to go via an iterator_traits class. We could use the same pattern.

But I closed this ticket and think this is fine.

[Peter]

I am not sure this discussion is finished.

The problem is that if we have two partial template specializations: one for weighted_random_access_iterator_tag and one for std::random_access_iterator_tag that means if std::list::iterator is passed it will not compile. But there is no reason to limit our stuff to random access iterators, or is there? We are not using random access, at least not in Pearson and Euclidean.

[Markus Ringnér]

So then I vote that the two specializations for Pearson and Euclidean should be for utility::weighted_random_access_iterator_tag and a lower std-tag. The inheritance structure is random_access_iterator_tag <- bidirectional_iterator_tag <- forward_iterator_tag <- input_iterator_tag.

1.) How low can we go with Pearson and Euclidean? forward_iterator_tag?

2.) Do we want to go as low as possible if this means making very many specializations to support all containers for some other future distance measure?

On the other hand I guess most distances are between pairs with the same index, meaning forward_iterator_tag should make it.

[Peter]

Clever. Yes, I think forward_iterator will do it. I picture we are only talking about read-only iterator here, and then iterating from start to end should be enough.

[Markus Ringnér]

We should try to remember that when going to forward_iterator support, vector_distance is an even more stupid name than originally.

[Markus Ringnér]

In [900] I changed to forward_iterator_tag (to get functionality with std::list bidirectional_iterator_tag would have been enough). Some thoughts:

1) For distance measures we should make two specializations (to support the same functionality for all measures; a design not a C++ requirement).

2) The forward_iterator_tag version will work for all higher level containers so the only reason to implement more than two specializations for a distance measure is if one can make a faster distance algorithm for containers with more iterator capabilities. Hence such additions will only affect run-time performance and not functionality.

3) I do not know if one should be too concerned with the possibility to get crazy results when weighted and non-weighted are mixed, and instead document the requirements (this is similar to the std algorithms I think?). Anyway, one can also send in iterators to strings: the euclidean distance between "olle" and "olle" is 0, but between (1,2,1) and "olle" I got roughly 200. So documenting the requirements will be "crucial" anyway.

[Markus Ringnér]

3) I do not know if one should be too concerned with the possibility to get crazy results when weighted and non-weighted are mixed, and instead document the requirements (this is similar to the std algorithms I think?). Anyway, one can also send in iterators to strings: the euclidean distance between "olle" and "olle" is 0, but between (1,2,1) and "olle" I got roughly 200. So documenting the requirements will be "crucial" anyway.

See comments regarding the Boost Concept Check Library in ticket:250 for my view on this issue.

[Markus Ringnér]

One potential advantage with reusing iterator_category as a common tag to also store weighted_random_access_iterator_tag, is that this means we could make special implementations of the std algorithms that works for our weighted iterator.

However, I am not sure this would work unless one illegally puts these specializations in namespace std, in which case this should not be exploited.

[Markus Ringnér]

(I mistakenly put this in the description earlier).

So let us address the last issue in this ticket (if we agree that concept checking is for later and instead document the requirements). If we want to make a separate tag for weighted/unweighted that is not mixed with the std iterator category one could do as outlined here.

We could do as follows:

struct unweighted_type {
  typedef unweighted_type weighted;
};
		
struct weighted_type {
  typedef weighted_type weighted;
};
		

// All iterators should default to unweighted type ...
template <class T>
struct weighted_traits {
  typedef unweighted_type weighted;
};

// but specialized to return weighted type for some things
template <class U, class V>
struct weighted_traits<yat::utility::IteratorWeighted<U,V> > {
  typedef weighted_type weighted;
  // of course there could be a typedef in IteratorWeighted
  // set to weighted_type that is returned here
};


And a distance function could use  iterator_traits<Iter>::weighted()
to call distance function specialized on weighted_type and unweighted_type for two different implementations.

I have tested this and it works. weighted_traits is a stupid name as it should really be named iterator_traits so my vote goes for having utility::iterator_traits that for our additional traits. What do you think? Should I do this and finally close this ticket again?

[Markus Ringnér]

The disadvantage with this separation is that if we come up with new weighted iterator classes then one has to make additional specializations of the weighted_traits. But I think this is acceptable (one weighted iterator should be enough?).

The opposite is worse: If we make the default weighted_trait look for a typedef in our iterator classes, one would have to make specialisations for all possible iterators in std so they become unweighted. The example Peter provided above only required one additional specialization on T* to support all ordinary pointers, but there is no corresponding simple thing discriminating std iterators from our iterators as far as I can tell.

[Peter]

No no don't make non-weighted iterator become a special case. That would be crazy!

In the long run I dont think one iterator will be enough though. In the future I can see the need (or advantage) for having an iterator for our 2D containers as well. For those one could iterate over elements, over row vectors, and column vectors.

[Peter]

In [908] implemented weighted_traits.

[Peter]

In [909] using weighted_iterator_traits, closes #251