Changeset 3237 for trunk/yat/utility/sort_index.h

Timestamp:

May 24, 2014, 7:49:24 AM (9 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

File:

• trunk/yat/utility/sort_index.h (modified) (3 diffs)

trunk/yat/utility/sort_index.h

@@ -1 +1 @@
 #ifndef _theplu_yat_utility_sort_index_
-#define _theplu_yat_utility_sort_index_ 
+#define _theplu_yat_utility_sort_index_
 
 // $Id$
 
 /*
-  Copyright (C) 2008, 2010 Peter Johansson
+  Copyright (C) 2008, 2010, 2014 Peter Johansson
 
   This file is part of the yat library, http://dev.thep.lu.se/yat
@@ -23 +23 @@
 */
 
-#include "StrideIterator.h"
-
 #include <boost/concept_check.hpp>
 
 #include <algorithm>
+#include <functional>
 #include <iterator>
 #include <vector>
@@ -45 +44 @@
      the range, i.e., ForwardIterator can be read-only.
 
-     \since New in yat 0.5
+     Type Requirements:
+     - \c InputIterator is a model of \input_iterator
+     - \c InputIterator::value_type is
+     <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
+     LessThan Comparable</a>
+
+     \since New in yat 0.5. In versions prior 0.13 function was restricted to
+     \forward_iterator and \c value_type of \c double.
   */
-  template<typename ForwardIterator>
-  void sort_index(ForwardIterator first, ForwardIterator last, 
-                  std::vector<size_t>& sort_index);
-    
-    
-  /**
-     Specialization for StrideIterator<double*>
-
-     \since New in yat 0.5
-  */
-  void sort_index(StrideIterator<double*> first, 
-                  StrideIterator<double*> last, 
+  template<typename InputIterator>
+  void sort_index(InputIterator first, InputIterator last,
                   std::vector<size_t>& sort_index);
 
   /**
-     Specialization for StrideIterator<const double*>
+     Same as sort_index(InputIterator, InputIterator,std::vector<size_t>&),
+     but objects are compared with \c comp rather than with \c operator<.
 
-     \since New in yat 0.5
-  */
-  void sort_index(StrideIterator<const double*> first, 
-                  StrideIterator<const double*> last, 
-                  std::vector<size_t>& sort_index);
+     Type Requirements:
+     - \c InputIterator is a model of \input_iterator
+     - \c Compare is a model of
+     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
+     Strict Weak Ordering</a>
+     - \c InputIterator::value_type is convertible to \c Compare's
+       argument type
 
-  /**
-     Specialization for std::vector<double>::iterator
-
-     \since New in yat 0.5
-  */
-  void sort_index(std::vector<double>::iterator first, 
-                  std::vector<double>::iterator last, 
-                  std::vector<size_t>& sort_index);
-
-  /**
-     Specialization for std::vector<double>::const_iterator
-
-     \since New in yat 0.5
-  */
-  void sort_index(std::vector<double>::const_iterator first, 
-                  std::vector<double>::const_iterator last, 
-                  std::vector<size_t>& sort_index);
+     \since New in yat 0.13
+   */
+  template<typename InputIterator, class Compare>
+  void sort_index(InputIterator first, InputIterator last,
+                  std::vector<size_t>& sort_index, Compare comp);
 
 
-  //  template implementation
+  /// \cond IGNORE_DOXYGEN
 
-  template<typename ForwardIterator>
-  void sort_index(ForwardIterator first, ForwardIterator last, 
-                  std::vector<size_t>& result)
+  // private stuff
+  namespace detail {
+
+    template<typename InputIterator, class Compare>
+    void sort_index(InputIterator first, InputIterator last,
+                    std::vector<size_t>& idx, Compare comp,
+                    std::input_iterator_tag);
+
+    // Specialization for random access iterator
+    template<typename RandomAccessIterator, class Compare>
+    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
+                    std::vector<size_t>& idx, Compare comp,
+                    std::random_access_iterator_tag);
+
+
+    template<typename RandomAccessIterator, class Compare>
+    class sort_index_Compare
+    {
+    public:
+      sort_index_Compare(RandomAccessIterator it, Compare comp)
+        : data_(it), compare_(comp) {}
+
+      bool operator()(size_t i, size_t j) const
+      { return compare_(data_[i], data_[j]); }
+
+    private:
+      RandomAccessIterator data_;
+      Compare compare_;
+    };
+
+  } // end of namespace detail
+
+  /// \endcond
+
+
+  //////////////  template implementation ///////////////////////////
+
+  template<typename InputIterator>
+  void sort_index(InputIterator first, InputIterator last,
+                  std::vector<size_t>& idx)
   {
-    BOOST_CONCEPT_ASSERT((boost::ForwardIterator<ForwardIterator>));
-    std::vector<double> vec;
-    vec.reserve(std::distance(first, last));
-    std::copy(first, last, 
-              std::back_insert_iterator<std::vector<double> >(vec));
-    sort_index(vec.begin(), vec.end(), result);
+    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
+    typedef typename std::iterator_traits<InputIterator>::value_type T;
+    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
+    sort_index(first, last, idx, std::less<T>());
   }
+
+
+  template<typename InputIterator, class Compare>
+  void sort_index(InputIterator first, InputIterator last,
+                  std::vector<size_t>& idx, Compare comp)
+  {
+    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
+    
+    typedef typename std::iterator_traits<InputIterator> traits;
+    typedef typename traits::iterator_category category;
+    detail::sort_index(first, last, idx, comp, category());
+  }
+
+
+  // implementation of private functions
+  namespace detail {
+
+    // general implementation. copy range to a std::vector and call
+    // random access version.
+    template<typename InputIterator, class Compare>
+    void sort_index(InputIterator first, InputIterator last,
+                    std::vector<size_t>& idx, Compare comp,
+                    std::input_iterator_tag tag)
+    {
+      typedef typename std::iterator_traits<InputIterator>::value_type T;
+      std::vector<T> vec(first, last);
+      sort_index(vec.begin(), vec.end(), idx, comp,
+                 std::random_access_iterator_tag());
+    }
+
+    // Specialization for random access iterator
+    template<typename RandomAccessIterator, class Compare>
+    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
+                    std::vector<size_t>& idx, Compare comp,
+                    std::random_access_iterator_tag tag)
+    {
+      sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
+      // Peter would like to use boost::iota here, but that is only
+      // available in boost v1.50 and newer, which is too recent at
+      // time of writing.
+      size_t n = last-first;
+      idx.clear();
+      idx.reserve(n);
+      for (size_t i=0; i<n; ++i)
+        idx.push_back(i);
+      std::sort(idx.begin(), idx.end(), compare);
+    }
+
+  } // end of namespace detail
 
 }}} // of namespace utility, yat, and theplu