1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #ifndef COMMON_ALGORITHM_H
24 #define COMMON_ALGORITHM_H
25
26 #include "common/scummsys.h"
27 #include "common/func.h"
28 #include "common/util.h"
29
30 namespace Common {
31
32 /**
33 * Copies data from the range [first, last) to [dst, dst + (last - first)).
34 * It requires the range [dst, dst + (last - first)) to be valid.
35 * It also requires dst not to be in the range [first, last).
36 */
37 template<class In, class Out>
copy(In first,In last,Out dst)38 Out copy(In first, In last, Out dst) {
39 while (first != last)
40 *dst++ = *first++;
41 return dst;
42 }
43
44 /**
45 * Copies data from the range [first, last) to [dst - (last - first), dst).
46 * It requires the range [dst - (last - first), dst) to be valid.
47 * It also requires dst not to be in the range [first, last).
48 *
49 * Unlike copy copy_backward copies the data from the end to the beginning.
50 */
51 template<class In, class Out>
copy_backward(In first,In last,Out dst)52 Out copy_backward(In first, In last, Out dst) {
53 while (first != last)
54 *--dst = *--last;
55 return dst;
56 }
57
58 /**
59 * Copies data from the range [first, last) to [dst, dst + (last - first)).
60 * It requires the range [dst, dst + (last - first)) to be valid.
61 * It also requires dst not to be in the range [first, last).
62 *
63 * Unlike copy or copy_backward it does not copy all data. It only copies
64 * a data element when operator() of the op parameter returns true for the
65 * passed data element.
66 */
67 template<class In, class Out, class Op>
copy_if(In first,In last,Out dst,Op op)68 Out copy_if(In first, In last, Out dst, Op op) {
69 while (first != last) {
70 if (op(*first))
71 *dst++ = *first;
72 ++first;
73 }
74 return dst;
75 }
76
77 // Our 'specialized' 'fill' template for char, signed char and unsigned char arrays.
78 // Since C++ doesn't support partial specialized template functions (currently) we
79 // are going this way...
80 // With this we assure the usage of memset for those, which should be
81 // faster than a simple loop like for the generic 'fill'.
82 template<class Value>
fill(signed char * first,signed char * last,Value val)83 signed char *fill(signed char *first, signed char *last, Value val) {
84 memset(first, (val & 0xFF), last - first);
85 return last;
86 }
87
88 template<class Value>
fill(unsigned char * first,unsigned char * last,Value val)89 unsigned char *fill(unsigned char *first, unsigned char *last, Value val) {
90 memset(first, (val & 0xFF), last - first);
91 return last;
92 }
93
94 template<class Value>
fill(char * first,char * last,Value val)95 char *fill(char *first, char *last, Value val) {
96 memset(first, (val & 0xFF), last - first);
97 return last;
98 }
99
100 /**
101 * Sets all elements in the range [first, last) to val.
102 */
103 template<class In, class Value>
fill(In first,In last,const Value & val)104 In fill(In first, In last, const Value &val) {
105 while (first != last)
106 *first++ = val;
107 return first;
108 }
109
110 /**
111 * Finds the first data value in the range [first, last) matching v.
112 * For data comperance it uses operator == of the data elements.
113 */
114 template<class In, class T>
find(In first,In last,const T & v)115 In find(In first, In last, const T &v) {
116 while (first != last) {
117 if (*first == v)
118 return first;
119 ++first;
120 }
121 return last;
122 }
123
124 /**
125 * Finds the first data value in the range [first, last) for which
126 * the specified predicate p returns true.
127 */
128 template<class In, class Pred>
find_if(In first,In last,Pred p)129 In find_if(In first, In last, Pred p) {
130 while (first != last) {
131 if (p(*first))
132 return first;
133 ++first;
134 }
135 return last;
136 }
137
138 /**
139 * Applies the function f on all elements of the range [first, last).
140 * The processing order is from beginning to end.
141 */
142 template<class In, class Op>
for_each(In first,In last,Op f)143 Op for_each(In first, In last, Op f) {
144 while (first != last)
145 f(*first++);
146 return f;
147 }
148
149 template<typename T>
distance(T * first,T * last)150 unsigned int distance(T *first, T *last) {
151 return last - first;
152 }
153
154 template<typename T>
distance(T first,T last)155 unsigned int distance(T first, T last) {
156 unsigned int n = 0;
157 while (first != last) {
158 ++n;
159 ++first;
160 }
161 return n;
162 }
163
164 template<typename T>
sortChoosePivot(T * first,T * last)165 T *sortChoosePivot(T *first, T *last) {
166 return first + distance(first, last) / 2;
167 }
168
169 template<typename T>
sortChoosePivot(T first,T last)170 T sortChoosePivot(T first, T last) {
171 unsigned int n = distance(first, last);
172 n /= 2;
173 while (n--)
174 ++first;
175 return first;
176 }
177
178 template<typename T, class StrictWeakOrdering>
sortPartition(T first,T last,T pivot,StrictWeakOrdering & comp)179 T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
180 --last;
181 if (pivot != last)
182 SWAP(*pivot, *last);
183
184 T sorted;
185 for (sorted = first; first != last; ++first) {
186 if (!comp(*last, *first)) {
187 if (first != sorted)
188 SWAP(*first, *sorted);
189 ++sorted;
190 }
191 }
192
193 if (last != sorted)
194 SWAP(*last, *sorted);
195 return sorted;
196 }
197
198 /**
199 * Simple sort function, modeled after std::sort.
200 * It compares data with the given comparator object comp.
201 *
202 * Like std::sort this is not guaranteed to be stable.
203 *
204 * Two small quotes from wikipedia about stability:
205 *
206 * Stable sorting algorithms maintain the relative order of records with
207 * equal keys.
208 *
209 * Unstable sorting algorithms may change the relative order of records with
210 * equal keys, but stable sorting algorithms never do so.
211 *
212 * For more information on that topic check out:
213 * http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
214 *
215 * NOTE: Actually as the time of writing our implementation is unstable.
216 */
217 template<typename T, class StrictWeakOrdering>
sort(T first,T last,StrictWeakOrdering comp)218 void sort(T first, T last, StrictWeakOrdering comp) {
219 if (first == last)
220 return;
221
222 T pivot = sortChoosePivot(first, last);
223 pivot = sortPartition(first, last, pivot, comp);
224 sort<T, StrictWeakOrdering>(first, pivot, comp);
225 sort<T, StrictWeakOrdering>(++pivot, last, comp);
226 }
227
228 /**
229 * Simple sort function, modeled after std::sort.
230 */
231 template<typename T>
sort(T * first,T * last)232 void sort(T *first, T *last) {
233 sort(first, last, Less<T>());
234 }
235
236 template<class T>
sort(T first,T last)237 void sort(T first, T last) {
238 sort(first, last, Less<typename T::ValueType>());
239 }
240
241 // MSVC is complaining about the minus operator being applied to an unsigned type
242 // We disable this warning for the affected section of code
243 #if defined(_MSC_VER)
244 #pragma warning(push)
245 #pragma warning(disable: 4146)
246 #endif
247
248 /**
249 * Euclid's algorithm to compute the greatest common divisor.
250 */
251 template<class T>
gcd(T a,T b)252 T gcd(T a, T b) {
253 // Note: We check for <= instead of < to avoid spurious compiler
254 // warnings if T is an unsigned type, i.e. warnings like "comparison
255 // of unsigned expression < 0 is always false".
256 if (a <= 0)
257 a = -a;
258 if (b <= 0)
259 b = -b;
260
261 while (a > 0) {
262 T tmp = a;
263 a = b % a;
264 b = tmp;
265 }
266
267 return b;
268 }
269
270 #if defined(_MSC_VER)
271 #pragma warning(pop)
272 #endif
273
274 /**
275 * Get the next highest power of 2.
276 */
277 template<class T>
nextHigher2(T v)278 T nextHigher2(T v) {
279 if (v == 0)
280 return 1;
281 v--;
282 v |= v >> 1;
283 v |= v >> 2;
284 v |= v >> 4;
285 v |= v >> 8;
286 v |= v >> 16;
287 return ++v;
288 }
289
290 /**
291 * Replacement algorithm for iterables.
292 *
293 * Replaces all occurrences of "original" in [begin, end) with occurrences of "replaced".
294 *
295 * @param[in, out] begin: First element to be examined.
296 * @param[in] end: Last element in the seubsection. Not examined.
297 * @param[in] original: Elements to be replaced.
298 * @param[in] replaced: Element to replace occurrences of "original".
299 *
300 * @note Usage examples and unit tests may be found in "test/common/algorithm.h"
301 */
302 template<class It, class Dat>
replace(It begin,It end,const Dat & original,const Dat & replaced)303 void replace(It begin, It end, const Dat &original, const Dat &replaced) {
304 for (; begin != end; ++begin) {
305 if (*begin == original) {
306 *begin = replaced;
307 }
308 }
309 }
310
311 } // End of namespace Common
312 #endif
313