use new iterator concepts

[Peter]

Reading about the new iterator concepts ​http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/new-iter-concepts.html

it's obvious that we should replace the c++98 style categories with this new style. It will be more useful and backward compatible. Several things:

1. we should replace usage of std::iterator::tags with boost::iterator_traversal_tags e.g. boost::forward_traversal_tag instead std::forward_iterator_tag. This includes both
   1. declarations of iterators as well as
   2. specializations in algorithms
2. ​Concept Checks should be replaced with more specific ​Iterator Concepts provided by Boost::Iterator.
3. In tests use ​boost iterator archetypes

[Peter]

(In [3273]) refs #803. Extend iterator tests using boost concepts. For DataIterator? and WeightIterator? always make value_type double. Remove tests that DataIterator? and WeightIterator? are RandomAccessIterator? since they are not (always); instead check that they are readable and random access traversal iterators.

[Peter]

(In [3274]) refs #803. record r3273 in NEWS

[Peter]

(In [3278]) use boost concept requirements in random namespace. refs #803

[Peter]

(In [3279]) use boost_concepts requirements in random namespace. refs #803

[Peter]

(In [3285]) refs #803. Use boost concepts in sort_index. Make requirements more accurate especially when iterator is random access and value_type doesn't need to be, e.g., default constructible.

[Peter]

(In [3289]) refs #803. use boost concepts in Spearman.

[Peter]

(In [3290]) refs #803. Correct docs and reflect that random access iterators are needed. Change test and concept schecks to use boost concepts.

[Peter]

(In [3314]) new test class: weighted_iterator_archetype. refs #803

[Peter]

(In [3315]) added inclusion of boost iterator_facade header. refs #803.

[Peter]

(In [3322]) change name of test function to more descriptive 'avoid_compiler_warning'; test weighted_iterator_traits; refs #803

[Peter]

(In [3379]) avoid using weighted_iterator_archetype with incrementable_traversal_tag. note, should reflect this in docs and concept checks in library as well. refs #803

[Peter]

(In [3385]) refs #803

[Peter]

(In [3387]) refs #803. MergeIterator?

[Peter]

(In [3388]) document requirements in MergeIterator?. refs #803

[Peter]

(In [3391]) document requirements in SmithWaterman?. refs #803

[Peter]

(In [3392]) refs #803. sort_index

[Peter]

(In [3393]) refs #803

The std::random_access_iterator promises that iterator provides random traversal and that reference_type is an lvalue (i.e. not proxy). If reference_type is a proxy, it is therefore incorrect to tag the iterator with std::random_access_iterator. To reflect that we do the following two changes:

1) Container2DIterator now carries tag boost::random_access_traversal_tag rather than std::random_access_iterator. This means that in std:: speak a Container2DIterator is a random access iterator, if reference is an lvalue and an input iterator otherwise.

2) The BASE of StrideIterator? is no longer required to be a random access iterator, instead we require random access traversal. Therefore, StrideIterator? now uses the default tag rather than std::iterator_traits<BASE>::iterator_category. This means that the traversal tag is boost::random_access_traversal_tag (as BASE is required to provide random access traversal), and in std:: speak the same rule applies as for Container2DIterator.

3) The concept check for Container2D now requires that iterators ::const_iterator, ::const_row_iterator, ::const_column_iterator are readable iterator (the random access requirement is removed).

[Peter]

According to comment in ​boost ticket:1296 these the standard has lifted the reference requirement on forward iterators so there is no reason to mess around with traversal categories etc. Need to look into the details, but probably means that most of changes within this ticket should be reverted. At least docs should not mention these concepts and then concept_check should not use them either.

[Peter]

I got this reply on the ​boost list basically saying that is not true (yet), but that some people (read Eric Niebler) is lobbying for a change.

For yat that means, I'll go ahead with the change as outlined (in my head).

[Peter]

0.13 is already delayed and I don't think this ticket should block the release.

[Peter]

(In [3459]) utility::WeightedIterator? is now always tagged as std::input_iterator_tag. Previously it was inheriting the tag from DataIterator?, but did not implement what was promised in the tag - particuarly not having lvalue access. It continuous to support more advanced (e.g. random access) traversal if supported by underlying iterators and whether this is supported can be assessed with boost meta functions boost::iterator_traversal<>::type (see boost docs).

refs #803

[Peter]

(In [3460]) prefer boost:: traits (rather than std::), clarify that iterators must be readable. refs #803.

[Peter]

(In [3490]) extend spaces for sort_index (refs #803).

[Peter]

(In [3499]) extend test. refs #803

[Peter]

(In [3506]) refs #803. require readable iterator rather than input iterator.

[Peter]

(In [3507]) refs #865 and refs #803. Concept checks for binary_weight.

[Peter]

(In [3509]) concept checks in MergeIterator?. refs #803

[Peter]

(In [3510]) doc type requirements. refs #803

[Peter]

(In [3511]) Reduce requirement on Percentiler (and functions that use Percentiler: percentiler2, median, mad) so it only require iterators to be random access traversal and not std::random_access_iterator. The letter requiring reference to be lvalue. refs #803.

[Peter]

(In [3512]) TukeyWeight? same requirement as mad. refs #803

[Peter]

(In [3514]) refs #803. relax requirement for Smoother so it works with input_iterator as well.

[Peter]

(In [3517]) Use boost iterator concepts (refs #803); avoid two loops in dna_reverse_comlement_copy.

[Peter]

(In [3518]) refs #803; let std::random_shuffle do the concept check

[Peter]

(In [3521]) refs #803

In WeightIterator? and DataIterator? require that BASE models concept DataIterator? directly (rather than implicit requirements).

[Peter]

(In [3522]) refs #803. In Histogram no need to require forrward iterator but allow all data iterator as long as they are single_pass_iterator.

[Peter]

(In [3523]) refs #803. use new iterator concepts. Require forward traversal and readable iterator rather than std::forward_iterator

[Peter]

(In [3527]) refs #803. use new iterator concept in Averager

[Peter]

(In [3528]) refs #803. use new iterator concept in AveragerWeighted?

[Peter]

(In [3529]) refs #803. use new iterator concept in AveragerPair?

[Peter]

(In [3530]) refs #803. use new iterator concept in AveragerPairWeighted?

[Peter]

(In [3541]) refs #803; use boost iterator concepts in Centralizer and Zscore

[Peter]

(In [3542]) fix sort_index so it works with iterators that are boost::random_access_traversal_tag but not std::random_access_iterator_tag. refs #803

[Peter]

(In [3543]) refs #803. use boost iterator categories in normalizer::Spearman

[Peter]

(In [3544]) refs #803. use boost iterator categories in normalizer::Gauss

[Peter]

(In [3547]) refs #803; use boost iterator concepts in qQuantileNormalizer.