Changeset 3237


Ignore:
Timestamp:
May 24, 2014, 7:49:24 AM (7 years ago)
Author:
Peter
Message:

re-write sort_index so it's not limited to ranges of double but work on any value_type than is less than comparable. Also provide a variant that takes a compare functor, similarly to std::sort

Location:
trunk/yat/utility
Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/yat/utility/Makefile.am

    r3212 r3237  
    4242  yat/utility/OptionSwitch.cc \
    4343  yat/utility/PCA.cc \
    44   yat/utility/sort_index.cc \
    4544  yat/utility/split.cc \
    4645  yat/utility/stl_utility.cc \
  • trunk/yat/utility/sort_index.h

    r2202 r3237  
    11#ifndef _theplu_yat_utility_sort_index_
    2 #define _theplu_yat_utility_sort_index_ 
     2#define _theplu_yat_utility_sort_index_
    33
    44// $Id$
    55
    66/*
    7   Copyright (C) 2008, 2010 Peter Johansson
     7  Copyright (C) 2008, 2010, 2014 Peter Johansson
    88
    99  This file is part of the yat library, http://dev.thep.lu.se/yat
     
    2323*/
    2424
    25 #include "StrideIterator.h"
    26 
    2725#include <boost/concept_check.hpp>
    2826
    2927#include <algorithm>
     28#include <functional>
    3029#include <iterator>
    3130#include <vector>
     
    4544     the range, i.e., ForwardIterator can be read-only.
    4645
    47      \since New in yat 0.5
     46     Type Requirements:
     47     - \c InputIterator is a model of \input_iterator
     48     - \c InputIterator::value_type is
     49     <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
     50     LessThan Comparable</a>
     51
     52     \since New in yat 0.5. In versions prior 0.13 function was restricted to
     53     \forward_iterator and \c value_type of \c double.
    4854  */
    49   template<typename ForwardIterator>
    50   void sort_index(ForwardIterator first, ForwardIterator last,
    51                   std::vector<size_t>& sort_index);
    52    
    53    
    54   /**
    55      Specialization for StrideIterator<double*>
    56 
    57      \since New in yat 0.5
    58   */
    59   void sort_index(StrideIterator<double*> first,
    60                   StrideIterator<double*> last,
     55  template<typename InputIterator>
     56  void sort_index(InputIterator first, InputIterator last,
    6157                  std::vector<size_t>& sort_index);
    6258
    6359  /**
    64      Specialization for StrideIterator<const double*>
     60     Same as sort_index(InputIterator, InputIterator,std::vector<size_t>&),
     61     but objects are compared with \c comp rather than with \c operator<.
    6562
    66      \since New in yat 0.5
    67   */
    68   void sort_index(StrideIterator<const double*> first,
    69                   StrideIterator<const double*> last,
    70                   std::vector<size_t>& sort_index);
     63     Type Requirements:
     64     - \c InputIterator is a model of \input_iterator
     65     - \c Compare is a model of
     66     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
     67     Strict Weak Ordering</a>
     68     - \c InputIterator::value_type is convertible to \c Compare's
     69       argument type
    7170
    72   /**
    73      Specialization for std::vector<double>::iterator
    74 
    75      \since New in yat 0.5
    76   */
    77   void sort_index(std::vector<double>::iterator first,
    78                   std::vector<double>::iterator last,
    79                   std::vector<size_t>& sort_index);
    80 
    81   /**
    82      Specialization for std::vector<double>::const_iterator
    83 
    84      \since New in yat 0.5
    85   */
    86   void sort_index(std::vector<double>::const_iterator first,
    87                   std::vector<double>::const_iterator last,
    88                   std::vector<size_t>& sort_index);
     71     \since New in yat 0.13
     72   */
     73  template<typename InputIterator, class Compare>
     74  void sort_index(InputIterator first, InputIterator last,
     75                  std::vector<size_t>& sort_index, Compare comp);
    8976
    9077
    91   //  template implementation
     78  /// \cond IGNORE_DOXYGEN
    9279
    93   template<typename ForwardIterator>
    94   void sort_index(ForwardIterator first, ForwardIterator last,
    95                   std::vector<size_t>& result)
     80  // private stuff
     81  namespace detail {
     82
     83    template<typename InputIterator, class Compare>
     84    void sort_index(InputIterator first, InputIterator last,
     85                    std::vector<size_t>& idx, Compare comp,
     86                    std::input_iterator_tag);
     87
     88    // Specialization for random access iterator
     89    template<typename RandomAccessIterator, class Compare>
     90    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
     91                    std::vector<size_t>& idx, Compare comp,
     92                    std::random_access_iterator_tag);
     93
     94
     95    template<typename RandomAccessIterator, class Compare>
     96    class sort_index_Compare
     97    {
     98    public:
     99      sort_index_Compare(RandomAccessIterator it, Compare comp)
     100        : data_(it), compare_(comp) {}
     101
     102      bool operator()(size_t i, size_t j) const
     103      { return compare_(data_[i], data_[j]); }
     104
     105    private:
     106      RandomAccessIterator data_;
     107      Compare compare_;
     108    };
     109
     110  } // end of namespace detail
     111
     112  /// \endcond
     113
     114
     115  //////////////  template implementation ///////////////////////////
     116
     117  template<typename InputIterator>
     118  void sort_index(InputIterator first, InputIterator last,
     119                  std::vector<size_t>& idx)
    96120  {
    97     BOOST_CONCEPT_ASSERT((boost::ForwardIterator<ForwardIterator>));
    98     std::vector<double> vec;
    99     vec.reserve(std::distance(first, last));
    100     std::copy(first, last,
    101               std::back_insert_iterator<std::vector<double> >(vec));
    102     sort_index(vec.begin(), vec.end(), result);
     121    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
     122    typedef typename std::iterator_traits<InputIterator>::value_type T;
     123    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
     124    sort_index(first, last, idx, std::less<T>());
    103125  }
     126
     127
     128  template<typename InputIterator, class Compare>
     129  void sort_index(InputIterator first, InputIterator last,
     130                  std::vector<size_t>& idx, Compare comp)
     131  {
     132    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
     133   
     134    typedef typename std::iterator_traits<InputIterator> traits;
     135    typedef typename traits::iterator_category category;
     136    detail::sort_index(first, last, idx, comp, category());
     137  }
     138
     139
     140  // implementation of private functions
     141  namespace detail {
     142
     143    // general implementation. copy range to a std::vector and call
     144    // random access version.
     145    template<typename InputIterator, class Compare>
     146    void sort_index(InputIterator first, InputIterator last,
     147                    std::vector<size_t>& idx, Compare comp,
     148                    std::input_iterator_tag tag)
     149    {
     150      typedef typename std::iterator_traits<InputIterator>::value_type T;
     151      std::vector<T> vec(first, last);
     152      sort_index(vec.begin(), vec.end(), idx, comp,
     153                 std::random_access_iterator_tag());
     154    }
     155
     156    // Specialization for random access iterator
     157    template<typename RandomAccessIterator, class Compare>
     158    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
     159                    std::vector<size_t>& idx, Compare comp,
     160                    std::random_access_iterator_tag tag)
     161    {
     162      sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
     163      // Peter would like to use boost::iota here, but that is only
     164      // available in boost v1.50 and newer, which is too recent at
     165      // time of writing.
     166      size_t n = last-first;
     167      idx.clear();
     168      idx.reserve(n);
     169      for (size_t i=0; i<n; ++i)
     170        idx.push_back(i);
     171      std::sort(idx.begin(), idx.end(), compare);
     172    }
     173
     174  } // end of namespace detail
    104175
    105176}}} // of namespace utility, yat, and theplu
Note: See TracChangeset for help on using the changeset viewer.