Opened 5 years ago

Closed 2 years ago

#803 closed request (fixed)

use new iterator concepts

Reported by: Peter Owned by: Peter
Priority: major Milestone: yat 0.14
Component: utility Version: trunk
Keywords: Cc:

Description (last modified by 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

Change History (48)

comment:1 Changed 5 years ago by Peter

Description: modified (diff)

comment:2 Changed 5 years ago by Peter

Status: newassigned

comment:3 Changed 5 years ago by 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.

comment:4 Changed 5 years ago by Peter

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

comment:5 Changed 5 years ago by Peter

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

comment:6 Changed 5 years ago by Peter

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

comment:7 Changed 5 years ago by 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.

comment:8 Changed 5 years ago by Peter

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

comment:9 Changed 5 years ago by Peter

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

comment:10 Changed 5 years ago by Peter

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

comment:11 Changed 5 years ago by Peter

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

comment:12 Changed 5 years ago by Peter

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

comment:13 Changed 4 years ago by 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

comment:14 Changed 4 years ago by Peter

(In [3385]) refs #803

comment:15 Changed 4 years ago by Peter

comment:16 Changed 4 years ago by Peter

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

comment:17 Changed 4 years ago by Peter

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

comment:18 Changed 4 years ago by Peter

(In [3392]) refs #803. sort_index

comment:19 Changed 4 years ago by 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).

comment:20 Changed 4 years ago by 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.

comment:21 Changed 4 years ago by 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).

comment:22 Changed 4 years ago by Peter

Milestone: yat 0.13yat 0.14

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

comment:23 Changed 3 years ago by 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

comment:24 Changed 3 years ago by Peter

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

comment:25 Changed 3 years ago by Peter

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

comment:26 Changed 3 years ago by Peter

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

comment:27 Changed 3 years ago by Peter

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

comment:28 Changed 3 years ago by Peter

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

comment:29 Changed 3 years ago by Peter

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

comment:30 Changed 3 years ago by Peter

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

comment:31 Changed 3 years ago by 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.

comment:32 Changed 3 years ago by Peter

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

comment:33 Changed 3 years ago by Peter

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

comment:34 Changed 3 years ago by Peter

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

comment:35 Changed 3 years ago by Peter

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

comment:36 Changed 3 years ago by Peter

(In [3521]) refs #803

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

comment:37 Changed 3 years ago by 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.

comment:38 Changed 3 years ago by Peter

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

comment:39 Changed 3 years ago by Peter

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

comment:40 Changed 3 years ago by Peter

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

comment:41 Changed 3 years ago by Peter

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

comment:42 Changed 3 years ago by Peter

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

comment:43 Changed 3 years ago by Peter

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

comment:44 Changed 3 years ago by 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

comment:45 Changed 3 years ago by Peter

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

comment:46 Changed 3 years ago by Peter

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

comment:47 Changed 2 years ago by Peter

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

comment:48 Changed 2 years ago by Peter

Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.