yat  0.14.5pre
sort_index.h
1 #ifndef _theplu_yat_utility_sort_index_
2 #define _theplu_yat_utility_sort_index_
3 
4 // $Id: sort_index.h 3550 2017-01-03 05:41:02Z peter $
5 
6 /*
7  Copyright (C) 2008, 2010, 2014, 2015, 2016 Peter Johansson
8 
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10 
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15 
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23 */
24 
25 #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>
29 
30 #include <algorithm>
31 #include <functional>
32 #include <iterator>
33 #include <vector>
34 
35 namespace theplu {
36 namespace yat {
37 namespace utility {
38 
64  template<typename InputIterator>
65  void sort_index(InputIterator first, InputIterator last,
66  std::vector<size_t>& sort_index);
67 
93  template<typename InputIterator, class Compare>
94  void sort_index(InputIterator first, InputIterator last,
95  std::vector<size_t>& sort_index, Compare comp);
96 
97 
99 
100  // private stuff
101  namespace detail {
102 
103  template<typename InputIterator, class Compare>
104  void sort_index(InputIterator first, InputIterator last,
105  std::vector<size_t>& idx, Compare comp,
106  std::input_iterator_tag);
107 
108  // Specialization for random access iterator
109  template<typename RandomAccessIterator, class Compare>
110  void sort_index(RandomAccessIterator first, RandomAccessIterator last,
111  std::vector<size_t>& idx, Compare comp,
112  std::random_access_iterator_tag);
113 
114  template<typename RandomAccessIterator, class Compare>
115  class sort_index_Compare
116  {
117  public:
118  sort_index_Compare(RandomAccessIterator it, Compare comp)
119  : data_(it), compare_(comp)
120  {
121  using boost_concepts::ReadableIterator;
122  BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIterator>));
123  using boost_concepts::RandomAccessTraversal;
124  BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIterator>));
125  typedef
126  typename boost::iterator_reference<RandomAccessIterator>::type T;
127  BOOST_CONCEPT_ASSERT((boost::BinaryPredicate<Compare, T, T>));
128  }
129 
130  bool operator()(size_t i, size_t j) const
131  { return compare_(data_[i], data_[j]); }
132 
133  private:
134  RandomAccessIterator data_;
135  Compare compare_;
136  };
137 
138  } // end of namespace detail
139 
141 
142 
144 
145  template<typename InputIterator>
146  void sort_index(InputIterator first, InputIterator last,
147  std::vector<size_t>& idx)
148  {
149  typedef typename boost::iterator_value<InputIterator>::type T;
150  // we use std::less<T>
151  BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
152  sort_index(first, last, idx, std::less<T>());
153  }
154 
155 
156  template<typename InputIterator, class Compare>
157  void sort_index(InputIterator first, InputIterator last,
158  std::vector<size_t>& idx, Compare comp)
159  {
160  BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
161  typename std::iterator_traits<InputIterator>::iterator_category category;
162  detail::sort_index(first, last, idx, comp, category);
163  }
164 
165 
166  // implementation of private functions
167  namespace detail {
168 
169  // general implementation. copy range to a std::vector and call
170  // random access version.
171  template<typename InputIterator, class Compare>
172  void sort_index(InputIterator first, InputIterator last,
173  std::vector<size_t>& idx, Compare comp,
174  std::input_iterator_tag tag)
175  {
176  typedef typename boost::iterator_value<InputIterator>::type T;
177  // two concepts for vector<T>
178  BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
179  BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
180  std::vector<T> vec(first, last);
181  sort_index(vec.begin(), vec.end(), idx, comp,
182  std::random_access_iterator_tag());
183  }
184 
185 
186  // Specialization for random access traversal
187  template<typename RandomAccessIterator, class Compare>
188  void sort_index(RandomAccessIterator first, RandomAccessIterator last,
189  std::vector<size_t>& idx, Compare comp,
190  std::random_access_iterator_tag tag)
191  {
192  sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
193  // Peter would like to use boost::iota here, but that is only
194  // available in boost v1.50 and newer, which is too recent at
195  // time of writing.
196  size_t n = last-first;
197  idx.clear();
198  idx.reserve(n);
199  for (size_t i=0; i<n; ++i)
200  idx.push_back(i);
201  std::sort(idx.begin(), idx.end(), compare);
202  }
203 
204  } // end of namespace detail
205 
206 }}} // of namespace utility, yat, and theplu
207 
208 #endif
void sort_index(InputIterator first, InputIterator last, std::vector< size_t > &sort_index)
Definition: sort_index.h:146

Generated on Tue Sep 26 2017 02:33:29 for yat by  doxygen 1.8.5