Line data Source code
1 : /*
2 : * Copyright (c) 2011-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Martin Rupp
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #include <utility>
34 :
35 : #ifndef __H__SORT_UTIL__
36 : #define __H__SORT_UTIL__
37 :
38 : /// \addtogroup ugbase_common_util
39 : /// \{
40 :
41 : template<typename TIndex, typename TValue>
42 0 : struct SortStruct
43 : {
44 0 : SortStruct() { }
45 : SortStruct(TIndex &i, TValue &v) : index(i), value(v) { }
46 :
47 : void set_value(TValue &val)
48 : {
49 : value = val;
50 : }
51 :
52 : TValue &get_value()
53 : {
54 : return value;
55 : }
56 :
57 : bool operator < (const SortStruct<TIndex, TValue> &other) const
58 : {
59 0 : return value < other.value;
60 : }
61 :
62 : TIndex index;
63 : TValue value;
64 : };
65 :
66 :
67 :
68 : template<typename TCompareValues, bool bReverse>
69 : class CompareIndicesByClass
70 : {
71 : public:
72 : CompareIndicesByClass(const TCompareValues &compareValues) : m_compareValues(compareValues) { }
73 :
74 : template<typename TIndex>
75 : bool operator () (const TIndex &i, const TIndex &j) const
76 : {
77 : if(bReverse)
78 : return m_compareValues[i] > m_compareValues[j];
79 : else
80 : return m_compareValues[i] < m_compareValues[j];
81 : }
82 : private:
83 : const TCompareValues &m_compareValues;
84 : };
85 :
86 : template<typename TCompareValues, typename TCompare>
87 : class CompareIndicesByClass2
88 : {
89 : public:
90 : CompareIndicesByClass2(const TCompareValues &compareValues, TCompare comp) : m_compareValues(compareValues), m_comp(comp) { }
91 :
92 : template<typename TIndex>
93 : bool operator () (const TIndex &i, const TIndex &j) const
94 : {
95 : return m_comp(m_compareValues[i], m_compareValues[j]);
96 : }
97 : private:
98 : const TCompareValues &m_compareValues;
99 : TCompare m_comp;
100 : };
101 :
102 : ////////////////////////////////////////////////////////////////////////////////////////////////
103 : // CompareIndicesBy
104 : /**
105 : * Allows sorting of indices by their values in another array.
106 : * example:
107 : * int v[] = {1, 3, 2};
108 : int pivot[] = {5, 2, 3, 1};
109 : sort(v, v+3, CompareIndicesBy(pivot));
110 : for(size_t i=0; i<3; i++)
111 : cout << v[i] << " = " << pivot[v[i]] << endl;
112 : */
113 : template<typename TCompareValues>
114 : inline CompareIndicesByClass<TCompareValues, false> CompareIndicesBy(const TCompareValues &values)
115 : {
116 : return CompareIndicesByClass<TCompareValues, false>(values);
117 : }
118 :
119 : template<typename TCompareValues>
120 : inline CompareIndicesByClass<TCompareValues, true> CompareIndicesReversedBy(const TCompareValues &values)
121 : {
122 : return CompareIndicesByClass<TCompareValues, true>(values);
123 : }
124 :
125 : /**
126 : * Allows sorting of indices by their values in another array with a comp function
127 : */
128 : template<typename TCompareValues, typename TCompare>
129 : inline CompareIndicesByClass2<TCompareValues, TCompare> CompareIndicesBy(const TCompareValues &values, TCompare comp)
130 : {
131 : return CompareIndicesByClass2<TCompareValues, TCompare>(values, comp);
132 : }
133 :
134 :
135 : /**
136 : * example:
137 : * std::vector<size_t> v; // = { 45, 3, 6, 4, 9};
138 : * ind = GetSortedIndices(ind, v);
139 : * then v[ ind[0] ] <= v[ ind[1] ] <= ... <= v [ ind[v.size() -1] ]; ,
140 : * and here ind = 1, 3, 2, 4, 0, because e.g. v[ind[0]] = v[1] = 3.
141 : * @param values array where indices should be sorted after
142 : * @return the indices list sorted with respect to the ordering in values
143 : */
144 : template<typename TCompareValues>
145 : void GetSortedIndices(std::vector<size_t> &indices, const TCompareValues &values, bool bReverse=false)
146 : {
147 : indices.resize(values.size());
148 : for(size_t i=0; i<indices.size(); i++) indices[i] = i;
149 : if(bReverse)
150 : std::sort(indices.begin(), indices.end(), CompareIndicesByClass<TCompareValues, true>(values));
151 : else
152 : std::sort(indices.begin(), indices.end(), CompareIndicesByClass<TCompareValues, false>(values));
153 : }
154 :
155 : /**
156 : * example:
157 : * std::vector<const char*> v; // some strings
158 : * GetSortedIndices(ind, v, boolstrcmp);
159 : * then v[ ind[0] ] <= v[ ind[1] ] <= ... <= v [ ind[v.size() -1] ]; ,
160 : * @param indices array with indices
161 : * @param values array where indices should be sorted after
162 : * @param comp compare function
163 : */
164 : template<typename TCompareValues, typename TCompare>
165 : void GetSortedIndices(std::vector<size_t> &indices, const TCompareValues &values, TCompare comp)
166 : {
167 : indices.resize(values.size());
168 : for(size_t i=0; i<indices.size(); i++) indices[i] = i;
169 : std::sort(indices.begin(), indices.end(), CompareIndicesByClass2<TCompareValues, TCompare>(values, comp));
170 : }
171 :
172 : template<typename TCompareValues, typename TCompare>
173 : std::vector<size_t> GetSortedIndices(const TCompareValues &values, TCompare comp)
174 : {
175 : std::vector<size_t> indices(values.size());
176 : GetSortedIndices(indices, values, comp);
177 : return indices;
178 : }
179 :
180 : template<typename TCompareValues>
181 : std::vector<size_t> GetSortedIndices(const TCompareValues &values)
182 : {
183 : std::vector<size_t> indices(values.size());
184 : GetSortedIndices(indices, values);
185 : return indices;
186 : }
187 :
188 :
189 :
190 : inline bool boolstrcmp(const char *a, const char *b)
191 : {
192 : return strcmp(a, b) < 0;
193 : }
194 :
195 : inline bool boolstrcmpReversed(const char *a, const char *b)
196 : {
197 : return strcmp(a, b) > 0;
198 : }
199 :
200 : // end group ugbase_common_util
201 : /// \}
202 :
203 : #endif
204 :
205 :
|
