yat/utility/sort_index.h

Code
Comments
Other
Rev Date Author Line
1491 11 Sep 08 peter 1 #ifndef _theplu_yat_utility_sort_index_
3237 24 May 14 peter 2 #define _theplu_yat_utility_sort_index_
1491 11 Sep 08 peter 3
1491 11 Sep 08 peter 4 // $Id$
1491 11 Sep 08 peter 5
1491 11 Sep 08 peter 6 /*
3550 03 Jan 17 peter 7   Copyright (C) 2008, 2010, 2014, 2015, 2016 Peter Johansson
1491 11 Sep 08 peter 8
1491 11 Sep 08 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
1491 11 Sep 08 peter 10
1491 11 Sep 08 peter 11   The yat library is free software; you can redistribute it and/or
1491 11 Sep 08 peter 12   modify it under the terms of the GNU General Public License as
1491 11 Sep 08 peter 13   published by the Free Software Foundation; either version 3 of the
1491 11 Sep 08 peter 14   License, or (at your option) any later version.
1491 11 Sep 08 peter 15
1491 11 Sep 08 peter 16   The yat library is distributed in the hope that it will be useful,
1491 11 Sep 08 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
1491 11 Sep 08 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1491 11 Sep 08 peter 19   General Public License for more details.
1491 11 Sep 08 peter 20
1491 11 Sep 08 peter 21   You should have received a copy of the GNU General Public License
1491 11 Sep 08 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
1491 11 Sep 08 peter 23 */
1491 11 Sep 08 peter 24
2202 21 Feb 10 peter 25 #include <boost/concept_check.hpp>
3285 11 Jul 14 peter 26 #include <boost/iterator/iterator_categories.hpp>
3285 11 Jul 14 peter 27 #include <boost/iterator/iterator_concepts.hpp>
3285 11 Jul 14 peter 28 #include <boost/iterator/iterator_traits.hpp>
2202 21 Feb 10 peter 29
1492 12 Sep 08 peter 30 #include <algorithm>
3237 24 May 14 peter 31 #include <functional>
1492 12 Sep 08 peter 32 #include <iterator>
1491 11 Sep 08 peter 33 #include <vector>
1491 11 Sep 08 peter 34
1491 11 Sep 08 peter 35 namespace theplu {
1491 11 Sep 08 peter 36 namespace yat {
1491 11 Sep 08 peter 37 namespace utility {
1491 11 Sep 08 peter 38
1491 11 Sep 08 peter 39   /**
1491 11 Sep 08 peter 40      Create a vector \a sort_index containing the indeces of elements
1491 11 Sep 08 peter 41      in a range [first, last). The elements of \a sort_index give the
1491 11 Sep 08 peter 42      index of the range element which would have been stored in that
1491 11 Sep 08 peter 43      position if the range had been sorted in place. The first element
1491 11 Sep 08 peter 44      of \a sort_index gives the index of the least element in the
1491 11 Sep 08 peter 45      range, and the last element of \a sort_index gives the index of
1491 11 Sep 08 peter 46      the greatest element in the range. The function will not affect
3392 16 Mar 15 peter 47      the range, i.e., InputIterator can be read-only.
1495 12 Sep 08 peter 48
3237 24 May 14 peter 49      Type Requirements:
3237 24 May 14 peter 50      - \c InputIterator is a model of \input_iterator
3237 24 May 14 peter 51      - \c InputIterator::value_type is
3237 24 May 14 peter 52      <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
3237 24 May 14 peter 53      LessThan Comparable</a>
3285 11 Jul 14 peter 54      - Either \c InputIterator::value_type is <a
3285 11 Jul 14 peter 55      href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
3285 11 Jul 14 peter 56      Default Constructible</a> or \c InputIterator is
3285 11 Jul 14 peter 57      \random_access_traversal_iterator.
3392 16 Mar 15 peter 58      - \c InputIterator::value_type is
3392 16 Mar 15 peter 59      <a href=http://www.sgi.com/tech/stl/Assignable.html>Assignable</a>
1495 12 Sep 08 peter 60
3237 24 May 14 peter 61      \since New in yat 0.5. In versions prior 0.13 function was restricted to
3238 24 May 14 peter 62      \forward_iterator with \c value_type convertible to \c double.
1491 11 Sep 08 peter 63   */
3237 24 May 14 peter 64   template<typename InputIterator>
3237 24 May 14 peter 65   void sort_index(InputIterator first, InputIterator last,
1491 11 Sep 08 peter 66                   std::vector<size_t>& sort_index);
1491 11 Sep 08 peter 67
1491 11 Sep 08 peter 68   /**
3237 24 May 14 peter 69      Same as sort_index(InputIterator, InputIterator,std::vector<size_t>&),
3237 24 May 14 peter 70      but objects are compared with \c comp rather than with \c operator<.
1495 12 Sep 08 peter 71
3237 24 May 14 peter 72      Type Requirements:
3237 24 May 14 peter 73      - \c InputIterator is a model of \input_iterator
3285 11 Jul 14 peter 74      - Either \c InputIterator::value_type is <a
3285 11 Jul 14 peter 75      href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
3285 11 Jul 14 peter 76      Default Constructible</a> or \c InputIterator is
3285 11 Jul 14 peter 77      \random_access_traversal_iterator.
3285 11 Jul 14 peter 78      - Either \c InputIterator::value_type is
3285 11 Jul 14 peter 79      <a href=http://www.sgi.com/tech/stl/Assignable.html>
3285 11 Jul 14 peter 80      Assignable</a> or \c InputIterator is
3285 11 Jul 14 peter 81      \random_access_traversal_iterator.
3237 24 May 14 peter 82      - \c Compare is a model of
3237 24 May 14 peter 83      <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
3237 24 May 14 peter 84      Strict Weak Ordering</a>
3238 24 May 14 peter 85      - \c Compare is
3285 11 Jul 14 peter 86      <a href="http://www.sgi.com/tech/stl/CopyConstructible.html">
3285 11 Jul 14 peter 87      Copy Constructible</a>
3237 24 May 14 peter 88      - \c InputIterator::value_type is convertible to \c Compare's
3237 24 May 14 peter 89        argument type
1491 11 Sep 08 peter 90
3237 24 May 14 peter 91      \since New in yat 0.13
3237 24 May 14 peter 92    */
3237 24 May 14 peter 93   template<typename InputIterator, class Compare>
3237 24 May 14 peter 94   void sort_index(InputIterator first, InputIterator last,
3237 24 May 14 peter 95                   std::vector<size_t>& sort_index, Compare comp);
1495 12 Sep 08 peter 96
1491 11 Sep 08 peter 97
3237 24 May 14 peter 98   /// \cond IGNORE_DOXYGEN
1495 12 Sep 08 peter 99
3237 24 May 14 peter 100   // private stuff
3237 24 May 14 peter 101   namespace detail {
1491 11 Sep 08 peter 102
3237 24 May 14 peter 103     template<typename InputIterator, class Compare>
3237 24 May 14 peter 104     void sort_index(InputIterator first, InputIterator last,
3237 24 May 14 peter 105                     std::vector<size_t>& idx, Compare comp,
3542 23 Dec 16 peter 106                     std::input_iterator_tag);
1491 11 Sep 08 peter 107
3237 24 May 14 peter 108     // Specialization for random access iterator
3237 24 May 14 peter 109     template<typename RandomAccessIterator, class Compare>
3237 24 May 14 peter 110     void sort_index(RandomAccessIterator first, RandomAccessIterator last,
3237 24 May 14 peter 111                     std::vector<size_t>& idx, Compare comp,
3542 23 Dec 16 peter 112                     std::random_access_iterator_tag);
1491 11 Sep 08 peter 113
3237 24 May 14 peter 114     template<typename RandomAccessIterator, class Compare>
3237 24 May 14 peter 115     class sort_index_Compare
3237 24 May 14 peter 116     {
3237 24 May 14 peter 117     public:
3237 24 May 14 peter 118       sort_index_Compare(RandomAccessIterator it, Compare comp)
3285 11 Jul 14 peter 119         : data_(it), compare_(comp)
3285 11 Jul 14 peter 120       {
3285 11 Jul 14 peter 121         using boost_concepts::ReadableIterator;
3285 11 Jul 14 peter 122         BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIterator>));
3285 11 Jul 14 peter 123         using boost_concepts::RandomAccessTraversal;
3285 11 Jul 14 peter 124         BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIterator>));
3285 11 Jul 14 peter 125         typedef
3285 11 Jul 14 peter 126           typename boost::iterator_reference<RandomAccessIterator>::type T;
3285 11 Jul 14 peter 127         BOOST_CONCEPT_ASSERT((boost::BinaryPredicate<Compare, T, T>));
3285 11 Jul 14 peter 128       }
3237 24 May 14 peter 129
3237 24 May 14 peter 130       bool operator()(size_t i, size_t j) const
3237 24 May 14 peter 131       { return compare_(data_[i], data_[j]); }
3237 24 May 14 peter 132
3237 24 May 14 peter 133     private:
3237 24 May 14 peter 134       RandomAccessIterator data_;
3237 24 May 14 peter 135       Compare compare_;
3237 24 May 14 peter 136     };
3237 24 May 14 peter 137
3237 24 May 14 peter 138   } // end of namespace detail
3237 24 May 14 peter 139
3237 24 May 14 peter 140   /// \endcond
3237 24 May 14 peter 141
3237 24 May 14 peter 142
3237 24 May 14 peter 143   //////////////  template implementation ///////////////////////////
3237 24 May 14 peter 144
3237 24 May 14 peter 145   template<typename InputIterator>
3237 24 May 14 peter 146   void sort_index(InputIterator first, InputIterator last,
3237 24 May 14 peter 147                   std::vector<size_t>& idx)
1492 12 Sep 08 peter 148   {
3285 11 Jul 14 peter 149     typedef typename boost::iterator_value<InputIterator>::type T;
3285 11 Jul 14 peter 150     // we use std::less<T>
3237 24 May 14 peter 151     BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
3237 24 May 14 peter 152     sort_index(first, last, idx, std::less<T>());
1492 12 Sep 08 peter 153   }
1492 12 Sep 08 peter 154
3237 24 May 14 peter 155
3237 24 May 14 peter 156   template<typename InputIterator, class Compare>
3237 24 May 14 peter 157   void sort_index(InputIterator first, InputIterator last,
3237 24 May 14 peter 158                   std::vector<size_t>& idx, Compare comp)
3237 24 May 14 peter 159   {
3237 24 May 14 peter 160     BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
3542 23 Dec 16 peter 161     typename std::iterator_traits<InputIterator>::iterator_category category;
3542 23 Dec 16 peter 162     detail::sort_index(first, last, idx, comp, category);
3237 24 May 14 peter 163   }
3237 24 May 14 peter 164
3237 24 May 14 peter 165
3237 24 May 14 peter 166   // implementation of private functions
3237 24 May 14 peter 167   namespace detail {
3237 24 May 14 peter 168
3237 24 May 14 peter 169     // general implementation. copy range to a std::vector and call
3237 24 May 14 peter 170     // random access version.
3237 24 May 14 peter 171     template<typename InputIterator, class Compare>
3237 24 May 14 peter 172     void sort_index(InputIterator first, InputIterator last,
3237 24 May 14 peter 173                     std::vector<size_t>& idx, Compare comp,
3542 23 Dec 16 peter 174                     std::input_iterator_tag tag)
3237 24 May 14 peter 175     {
3285 11 Jul 14 peter 176       typedef typename boost::iterator_value<InputIterator>::type T;
3285 11 Jul 14 peter 177       // two concepts for vector<T>
3285 11 Jul 14 peter 178       BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
3285 11 Jul 14 peter 179       BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
3237 24 May 14 peter 180       std::vector<T> vec(first, last);
3237 24 May 14 peter 181       sort_index(vec.begin(), vec.end(), idx, comp,
3542 23 Dec 16 peter 182                  std::random_access_iterator_tag());
3237 24 May 14 peter 183     }
3237 24 May 14 peter 184
3285 11 Jul 14 peter 185
3285 11 Jul 14 peter 186     // Specialization for random access traversal
3237 24 May 14 peter 187     template<typename RandomAccessIterator, class Compare>
3237 24 May 14 peter 188     void sort_index(RandomAccessIterator first, RandomAccessIterator last,
3237 24 May 14 peter 189                     std::vector<size_t>& idx, Compare comp,
3542 23 Dec 16 peter 190                     std::random_access_iterator_tag tag)
3237 24 May 14 peter 191     {
3237 24 May 14 peter 192       sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
3237 24 May 14 peter 193       // Peter would like to use boost::iota here, but that is only
3237 24 May 14 peter 194       // available in boost v1.50 and newer, which is too recent at
3237 24 May 14 peter 195       // time of writing.
3237 24 May 14 peter 196       size_t n = last-first;
3237 24 May 14 peter 197       idx.clear();
3237 24 May 14 peter 198       idx.reserve(n);
3237 24 May 14 peter 199       for (size_t i=0; i<n; ++i)
3237 24 May 14 peter 200         idx.push_back(i);
3237 24 May 14 peter 201       std::sort(idx.begin(), idx.end(), compare);
3237 24 May 14 peter 202     }
3237 24 May 14 peter 203
3237 24 May 14 peter 204   } // end of namespace detail
3237 24 May 14 peter 205
1491 11 Sep 08 peter 206 }}} // of namespace utility, yat, and theplu
1491 11 Sep 08 peter 207
1491 11 Sep 08 peter 208 #endif

Generated on Sat Oct 14 02:25:52 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)