source: trunk/yat/utility/sort_index.h

Last change on this file was 3550, checked in by Peter, 5 years ago

Update copyright years. Happy New Year

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 7.0 KB
Line 
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
35namespace theplu {
36namespace yat {
37namespace utility {
38
39  /**
40     Create a vector \a sort_index containing the indeces of elements
41     in a range [first, last). The elements of \a sort_index give the
42     index of the range element which would have been stored in that
43     position if the range had been sorted in place. The first element
44     of \a sort_index gives the index of the least element in the
45     range, and the last element of \a sort_index gives the index of
46     the greatest element in the range. The function will not affect
47     the range, i.e., InputIterator can be read-only.
48
49     Type Requirements:
50     - \c InputIterator is a model of \input_iterator
51     - \c InputIterator::value_type is
52     <a href=http://www.sgi.com/tech/stl/LessThanComparable.html>
53     LessThan Comparable</a>
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     - \c InputIterator::value_type is
59     <a href=http://www.sgi.com/tech/stl/Assignable.html>Assignable</a>
60
61     \since New in yat 0.5. In versions prior 0.13 function was restricted to
62     \forward_iterator with \c value_type convertible to \c double.
63  */
64  template<typename InputIterator>
65  void sort_index(InputIterator first, InputIterator last,
66                  std::vector<size_t>& sort_index);
67
68  /**
69     Same as sort_index(InputIterator, InputIterator,std::vector<size_t>&),
70     but objects are compared with \c comp rather than with \c operator<.
71
72     Type Requirements:
73     - \c InputIterator is a model of \input_iterator
74     - Either \c InputIterator::value_type is <a
75     href=http://www.sgi.com/tech/stl/DefaultConstructible.html>
76     Default Constructible</a> or \c InputIterator is
77     \random_access_traversal_iterator.
78     - Either \c InputIterator::value_type is
79     <a href=http://www.sgi.com/tech/stl/Assignable.html>
80     Assignable</a> or \c InputIterator is
81     \random_access_traversal_iterator.
82     - \c Compare is a model of
83     <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
84     Strict Weak Ordering</a>
85     - \c Compare is
86     <a href="http://www.sgi.com/tech/stl/CopyConstructible.html">
87     Copy Constructible</a>
88     - \c InputIterator::value_type is convertible to \c Compare's
89       argument type
90
91     \since New in yat 0.13
92   */
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
98  /// \cond IGNORE_DOXYGEN
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
140  /// \endcond
141
142
143  //////////////  template implementation ///////////////////////////
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
Note: See TracBrowser for help on using the repository browser.