source: trunk/yat/utility/sort_index.h @ 3417

Last change on this file since 3417 was 3417, checked in by Peter, 4 years ago

updating copyright statements

  • 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 3417 2015-05-25 01:35:59Z peter $
5
6/*
7  Copyright (C) 2008, 2010, 2014, 2015 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                    boost::single_pass_traversal_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                    boost::random_access_traversal_tag);
113
114
115    template<typename RandomAccessIterator, class Compare>
116    class sort_index_Compare
117    {
118    public:
119      sort_index_Compare(RandomAccessIterator it, Compare comp)
120        : data_(it), compare_(comp)
121      {
122        using boost_concepts::ReadableIterator;
123        BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIterator>));
124        using boost_concepts::RandomAccessTraversal;
125        BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIterator>));
126        typedef
127          typename boost::iterator_reference<RandomAccessIterator>::type T;
128        BOOST_CONCEPT_ASSERT((boost::BinaryPredicate<Compare, T, T>));
129      }
130
131      bool operator()(size_t i, size_t j) const
132      { return compare_(data_[i], data_[j]); }
133
134    private:
135      RandomAccessIterator data_;
136      Compare compare_;
137    };
138
139  } // end of namespace detail
140
141  /// \endcond
142
143
144  //////////////  template implementation ///////////////////////////
145
146  template<typename InputIterator>
147  void sort_index(InputIterator first, InputIterator last,
148                  std::vector<size_t>& idx)
149  {
150    typedef typename boost::iterator_value<InputIterator>::type T;
151    // we use std::less<T>
152    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<T>));
153    sort_index(first, last, idx, std::less<T>());
154  }
155
156
157  template<typename InputIterator, class Compare>
158  void sort_index(InputIterator first, InputIterator last,
159                  std::vector<size_t>& idx, Compare comp)
160  {
161    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
162    typename boost::iterator_traversal<InputIterator>::type traversal;
163    detail::sort_index(first, last, idx, comp, traversal);
164  }
165
166
167  // implementation of private functions
168  namespace detail {
169
170    // general implementation. copy range to a std::vector and call
171    // random access version.
172    template<typename InputIterator, class Compare>
173    void sort_index(InputIterator first, InputIterator last,
174                    std::vector<size_t>& idx, Compare comp,
175                    boost::single_pass_traversal_tag tag)
176    {
177      typedef typename boost::iterator_value<InputIterator>::type T;
178      // two concepts for vector<T>
179      BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<T>));
180      BOOST_CONCEPT_ASSERT((boost::SGIAssignable<T>));
181      std::vector<T> vec(first, last);
182      sort_index(vec.begin(), vec.end(), idx, comp,
183                 boost::random_access_traversal_tag());
184    }
185
186
187    // Specialization for random access traversal
188    template<typename RandomAccessIterator, class Compare>
189    void sort_index(RandomAccessIterator first, RandomAccessIterator last,
190                    std::vector<size_t>& idx, Compare comp,
191                    boost::random_access_traversal_tag tag)
192    {
193      sort_index_Compare<RandomAccessIterator, Compare> compare(first, comp);
194      // Peter would like to use boost::iota here, but that is only
195      // available in boost v1.50 and newer, which is too recent at
196      // time of writing.
197      size_t n = last-first;
198      idx.clear();
199      idx.reserve(n);
200      for (size_t i=0; i<n; ++i)
201        idx.push_back(i);
202      std::sort(idx.begin(), idx.end(), compare);
203    }
204
205  } // end of namespace detail
206
207}}} // of namespace utility, yat, and theplu
208
209#endif
Note: See TracBrowser for help on using the repository browser.