Changeset 3285


Ignore:
Timestamp:
Jul 11, 2014, 12:59:46 PM (9 years ago)
Author:
Peter
Message:

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.

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/test/utility.cc

    r3255 r3285  
    3535
    3636#include <boost/concept_archetype.hpp>
     37#include <boost/iterator/iterator_archetypes.hpp>
    3738
    3839#include <cassert>
    … …  
    533534  // do not run compiler tests
    534535  if (false) {
    535     std::vector<size_t> vec;
    536536    // value type must be possible to store in a vector so has to be
    537537    // default constructible and assignable
    … …  
    541541    boost::input_iterator_archetype<value_type> iter;
    542542    utility::sort_index(iter, iter, vec);
     543
    543544    // try with a random access container as well
    544     std::vector<value_type> vec2;
    545     utility::sort_index(vec2.begin(), vec2.end(), vec);
     545    typedef boost::iterator_archetypes::readable_iterator_t access_type;
     546    typedef boost::random_access_traversal_tag traversal_type;
     547    typedef boost::copy_constructible_archetype<
     548      boost::less_than_comparable_archetype<> > value_type2;
     549    boost::iterator_archetype<value_type2, access_type, traversal_type> iter2;
     550    utility::sort_index(iter2, iter2, vec);
    546551  }
    547552  // same thing with four argument version
    548553  if (false) {
    549     std::vector<size_t> vec;
    550554    // value type must be possible to store in a vector so has to be
    551555    // default constructible and assignable
    … …  
    555559    boost::input_iterator_archetype<value_type> iter;
    556560
    557     // Create a binary predicate that is assignable and default constructible
    558     boost::default_constructible_archetype<
    559       boost::sgi_assignable_archetype<
    560         boost::binary_predicate_archetype<
    561           value_type, value_type> > > comp;
     561    // Create a binary predicate that is copy constructible
     562    boost::copy_constructible_archetype<
     563        boost::binary_predicate_archetype<value_type, value_type>
     564      > comp;
    562565
    563566    utility::sort_index(iter, iter, vec, comp);
    564     // try with a random access container as well
    565     std::vector<value_type> vec2;
    566     utility::sort_index(vec2.begin(), vec2.end(), vec, comp);
     567
     568    // try with a random access iterator as well
     569    typedef boost::iterator_archetypes::readable_iterator_t access_type;
     570    typedef boost::random_access_traversal_tag traversal_type;
     571    typedef boost::copy_constructible_archetype<> value_type2;
     572    boost::iterator_archetype<value_type2, access_type, traversal_type> iter2;
     573    // Create a binary predicate that is copy constructible
     574    boost::copy_constructible_archetype<
     575        boost::binary_predicate_archetype<value_type2, value_type2>
     576      > comp2;
     577    utility::sort_index(iter2, iter2, vec, comp2);
    567578  }
    568579}

  • trunk/yat/utility/sort_index.h

    r3238 r3285  
    2424
    2525#include <boost/concept_check.hpp>
     26#include <boost/iterator/iterator_categories.hpp>
     27#include <boost/iterator/iterator_concepts.hpp>
     28#include <boost/iterator/iterator_traits.hpp>
    2629
    2730#include <algorithm>
    … …  
    4952     <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
    5053     LessThan Comparable</a>
    51      - \c InputIterator::value_type is
    52      <a href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
    53      Default Constructible</a> and
     54     - Either \c InputIterator::value_type is <a
     55     href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     56     Default Constructible</a> or \c InputIterator is
     57     \random_access_traversal_iterator.
     58     - Either \c InputIterator::value_type is
    5459     <a href=http://www.sgi.com/tech/stl/Assignable.html>
    55      Assignable</a>
     60     Assignable</a> or \c InputIterator is
     61     \random_access_traversal_iterator.
    5662
    5763     \since New in yat 0.5. In versions prior 0.13 function was restricted to
    … …  
    6874     Type Requirements:
    6975     - \c InputIterator is a model of \input_iterator
     76     - Either \c InputIterator::value_type is <a
     77     href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
     78     Default Constructible</a> or \c InputIterator is
     79     \random_access_traversal_iterator.
     80     - Either \c InputIterator::value_type is
     81     <a href=http://www.sgi.com/tech/stl/Assignable.html>
     82     Assignable</a> or \c InputIterator is
     83     \random_access_traversal_iterator.
    7084     - \c Compare is a model of
    7185     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
    7286     Strict Weak Ordering</a>
    7387     - \c Compare is
    74      <a href="http://www.sgi.com/tech/stl/Assignable.html">
    75      Assignable</a>
    76      - \c InputIterator::value_type is
    77      <a href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
    78      Default Constructible</a> and
    79      <a href=http://www.sgi.com/tech/stl/Assignable.html>
    80      Assignable</a>
     88     <a href="http://www.sgi.com/tech/stl/CopyConstructible.html">
     89     Copy Constructible</a>
    8190     - \c InputIterator::value_type is convertible to \c Compare's
    8291       argument type
    … …  
    97106    void sort_index(InputIterator first, InputIterator last,
    98107                    std::vector<size_t>& idx, Compare comp,
    99                     std::input_iterator_tag);
     108                    boost::single_pass_traversal_tag);
    100109
    101110    // Specialization for random access iterator
    … …  
    103112    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
    104113                    std::vector<size_t>& idx, Compare comp,
    105                     std::random_access_iterator_tag);
     114                    boost::random_access_traversal_tag);
    106115
    107116
    … …  
    111120    public:
    112121      sort_index_Compare(RandomAccessIterator it, Compare comp)
    113         : data_(it), compare_(comp) {}
     122        : data_(it), compare_(comp)
     123      {
     124        using boost_concepts::ReadableIterator;
     125        BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIterator>));
     126        using boost_concepts::RandomAccessTraversal;
     127        BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIterator>));
     128        typedef
     129          typename boost::iterator_reference<RandomAccessIterator>::type T;
     130        BOOST_CONCEPT_ASSERT((boost::BinaryPredicate<Compare, T, T>));
     131      }
    114132
    115133      bool operator()(size_t i, size_t j) const
    … …  
    132150                  std::vector<size_t>& idx)
    133151  {
    134     BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    135     typedef typename std::iterator_traits<InputIterator>::value_type T;
    136     BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
    137     BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
     152    typedef typename boost::iterator_value<InputIterator>::type T;
     153    // we use std::less<T>
    138154    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
    139155    sort_index(first, last, idx, std::less<T>());
    … …  
    146162  {
    147163    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    148     typedef typename std::iterator_traits<InputIterator> traits;
    149     typedef typename std::iterator_traits<InputIterator>::value_type T;
    150     BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
    151     BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
    152     BOOST_CONCEPT_ASSERT((boost::Assignable<Compare>));
    153 
    154     typedef typename traits::iterator_category category;
    155     detail::sort_index(first, last, idx, comp, category());
     164    typename boost::iterator_traversal<InputIterator>::type traversal;
     165    detail::sort_index(first, last, idx, comp, traversal);
    156166  }
    157167
    … …  
    165175    void sort_index(InputIterator first, InputIterator last,
    166176                    std::vector<size_t>& idx, Compare comp,
    167                     std::input_iterator_tag tag)
     177                    boost::single_pass_traversal_tag tag)
    168178    {
    169       typedef typename std::iterator_traits<InputIterator>::value_type T;
     179      typedef typename boost::iterator_value<InputIterator>::type T;
     180      // two concepts for vector<T>
     181      BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
     182      BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
    170183      std::vector<T> vec(first, last);
    171184      sort_index(vec.begin(), vec.end(), idx, comp,
    172                  std::random_access_iterator_tag());
     185                 boost::random_access_traversal_tag());
    173186    }
    174187
    175     // Specialization for random access iterator
     188
     189    // Specialization for random access traversal
    176190    template<typename RandomAccessIterator, class Compare>
    177191    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
    178192                    std::vector<size_t>& idx, Compare comp,
    179                     std::random_access_iterator_tag tag)
     193                    boost::random_access_traversal_tag tag)
    180194    {
    181195      sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
Note: See TracChangeset for help on using the changeset viewer.