www.mooseframework.org
IndirectSort.h
Go to the documentation of this file.
1 /****************************************************************/
2 /* DO NOT MODIFY THIS HEADER */
3 /* MOOSE - Multiphysics Object Oriented Simulation Environment */
4 /* */
5 /* (c) 2010 Battelle Energy Alliance, LLC */
6 /* ALL RIGHTS RESERVED */
7 /* */
8 /* Prepared by Battelle Energy Alliance, LLC */
9 /* Under Contract No. DE-AC07-05ID14517 */
10 /* With the U. S. Department of Energy */
11 /* */
12 /* See COPYRIGHT for full restrictions */
13 /****************************************************************/
14 
15 #ifndef INDIRECTSORT_H
16 #define INDIRECTSORT_H
17 
18 #include <functional>
19 #include <vector>
20 #include <algorithm>
21 #include <iterator> // std::iterator_traits
22 
23 namespace Moose
24 {
25 
26 // The indirect (or index) comparison functor is templated on a random
27 // access iterator type, and a user comparison function. This class
28 // is to be constructed with a random access iterator which points to
29 // the beginning of the container whose values are to be indirectly
30 // sorted. This class is not to be used directly by the user.
31 template <class RandomAccessIterator, class UserComparisonFunctor>
33 {
34  // ctor
35  indirect_comparator(RandomAccessIterator r, UserComparisonFunctor c)
37  {
38  }
39 
40  // comparison operator - calls the user's comparison function on
41  // v[lhs] and v[rhs]
42  bool operator()(size_t lhs, size_t rhs)
43  {
44  // Note: operator[] is defined for random access iterators!
46  }
47 
48 private:
49  // data
50  RandomAccessIterator _random_access_iterator;
51  UserComparisonFunctor _user_comp;
52 };
53 
54 // This is a common initialization function called by the indirect_sort's.
55 // Should not be called directly by users...
56 template <class RandomAccessIterator>
57 void
58 initialize_indirect_sort(RandomAccessIterator beg,
59  RandomAccessIterator end,
60  std::vector<size_t> & b)
61 {
62  // enough storage for all the indices
63  b.resize(std::distance(beg, end));
64 
65  // iota
66  for (size_t i = 0; i < b.size(); ++i)
67  b[i] = i;
68 }
69 
70 // A generic indirect sort function templated on the iterator type. Uses
71 // std::less<T> for the comparisons.
72 template <class RandomAccessIterator>
73 void
74 indirectSort(RandomAccessIterator beg, RandomAccessIterator end, std::vector<size_t> & b)
75 {
76  // Space in b
77  initialize_indirect_sort(beg, end, b);
78 
79  // Typedef for less typing. Note: use of std::iterator_traits means this should work with
80  // naked pointers too...
81  typedef std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>
82  LessThanComparator;
83 
84  // Construct comparator object
86 
87  // Sort the indices, based on the data
88  std::sort(b.begin(), b.end(), ic);
89 }
90 
91 // A generic indirect sort function templated on the iterator type *and* the comparison functor
92 // to be used for the ordering.
93 template <class RandomAccessIterator, class UserComparisonFunctor>
94 void
95 indirectSort(RandomAccessIterator beg,
96  RandomAccessIterator end,
97  std::vector<size_t> & b,
98  UserComparisonFunctor user_comp)
99 {
100  // Space in b
101  initialize_indirect_sort(beg, end, b);
102 
103  // Construct comparator object
105 
106  // Sort the indices, based on the data
107  std::sort(b.begin(), b.end(), ic);
108 }
109 
112 template <typename T>
113 void
114 applyIndices(T & container, const std::vector<size_t> & indices)
115 {
116  T tmp;
117  tmp.resize(container.size());
118  for (size_t i = 0; i < indices.size(); i++)
119  tmp[i] = container[indices[i]];
120  std::swap(tmp, container);
121 }
122 
123 } // namespace Moose
124 
125 #endif // INDIRECTSORT_H
RandomAccessIterator _random_access_iterator
Definition: IndirectSort.h:50
void indirectSort(RandomAccessIterator beg, RandomAccessIterator end, std::vector< size_t > &b)
Definition: IndirectSort.h:74
bool operator()(size_t lhs, size_t rhs)
Definition: IndirectSort.h:42
void initialize_indirect_sort(RandomAccessIterator beg, RandomAccessIterator end, std::vector< size_t > &b)
Definition: IndirectSort.h:58
void applyIndices(T &container, const std::vector< size_t > &indices)
Uses indices created by the indirectSort function to sort the given container (which must support ran...
Definition: IndirectSort.h:114
indirect_comparator(RandomAccessIterator r, UserComparisonFunctor c)
Definition: IndirectSort.h:35
X_global swap(X_sys)
UserComparisonFunctor _user_comp
Definition: IndirectSort.h:51
Definition: Moose.h:84