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 * @defgroup common_alg Algorithms
34 * @ingroup common
35 *
36 * @brief Templates for algorithms used to manipulate data.
37 *
38 * @{
39 */
40
41 /**
42 * @name Copy templates
43 * @{
44 */
45
46 /**
47 * Copy data from the range [first, last) to [dst, dst + (last - first)).
48 *
49 * The function requires the range [dst, dst + (last - first)) to be valid.
50 * It also requires dst not to be in the range [first, last).
51 */
52 template<class In, class Out>
copy(In first,In last,Out dst)53 Out copy(In first, In last, Out dst) {
54 while (first != last)
55 *dst++ = *first++;
56 return dst;
57 }
58
59 /**
60 * Copy data from the range [first, last) to [dst - (last - first), dst).
61 *
62 * The function requires the range [dst - (last - first), dst) to be valid.
63 * It also requires dst not to be in the range [first, last).
64 *
65 * Unlike copy, copy_backward copies the data from the end to the beginning.
66 */
67 template<class In, class Out>
copy_backward(In first,In last,Out dst)68 Out copy_backward(In first, In last, Out dst) {
69 while (first != last)
70 *--dst = *--last;
71 return dst;
72 }
73
74 /**
75 * Copy data from the range [first, last) to [dst, dst + (last - first)).
76 *
77 * The function requires the range [dst, dst + (last - first)) to be valid.
78 * It also requires dst not to be in the range [first, last).
79 *
80 * Unlike copy or copy_backward, it does not copy all data. It only copies
81 * a data element when operator() of the op parameter returns true for the
82 * passed data element.
83 */
84 template<class In, class Out, class Op>
copy_if(In first,In last,Out dst,Op op)85 Out copy_if(In first, In last, Out dst, Op op) {
86 while (first != last) {
87 if (op(*first))
88 *dst++ = *first;
89 ++first;
90 }
91 return dst;
92 }
93
94 /**
95 * @}
96 */
97
98 /**
99 * @name Fill templates
100 * @{
101 */
102
103 /**
104 * A 'fill' template for signed char arrays.
105 *
106 * Since C++ does not currently support partial specialized template functions,
107 * this solution is implemented.
108 * With this template, the usage of memset is assured, which is
109 * faster than a simple loop like for the generic 'fill'.
110 */
111 template<class Value>
fill(signed char * first,signed char * last,Value val)112 signed char *fill(signed char *first, signed char *last, Value val) {
113 memset(first, (val & 0xFF), last - first);
114 return last;
115 }
116
117 /**
118 * A 'fill' template for unsigned char arrays.
119 *
120 * Since C++ does not currently support partial specialized template functions,
121 * this solution is implemented.
122 * With this template, the usage of memset is assured, which is
123 * faster than a simple loop like for the generic 'fill'.
124 */
125 template<class Value>
fill(unsigned char * first,unsigned char * last,Value val)126 unsigned char *fill(unsigned char *first, unsigned char *last, Value val) {
127 memset(first, (val & 0xFF), last - first);
128 return last;
129 }
130
131 /**
132 * A 'fill' template for char arrays.
133 *
134 * Since C++ does not currently support partial specialized template functions,
135 * this solution is implemented.
136 * With this template, the usage of memset is assured, which is
137 * faster than a simple loop like for the generic 'fill'.
138 */
139 template<class Value>
fill(char * first,char * last,Value val)140 char *fill(char *first, char *last, Value val) {
141 memset(first, (val & 0xFF), last - first);
142 return last;
143 }
144
145 /**
146 * @}
147 */
148
149 /**
150 * @name Range templates
151 * @{
152 */
153
154 /**
155 * Set all elements in the range [first, last) to val.
156 */
157 template<class In, class Value>
fill(In first,In last,const Value & val)158 In fill(In first, In last, const Value &val) {
159 while (first != last)
160 *first++ = val;
161 return first;
162 }
163
164 /**
165 * Find the first data value in the range [first, last) matching v.
166 * For data comparison, it uses operator == of the data elements.
167 */
168 template<class In, class T>
find(In first,In last,const T & v)169 In find(In first, In last, const T &v) {
170 while (first != last) {
171 if (*first == v)
172 return first;
173 ++first;
174 }
175 return last;
176 }
177
178 /**
179 * Find the first data value in the range [first, last), for which
180 * the specified predicate p returns true.
181 */
182 template<class In, class Pred>
find_if(In first,In last,Pred p)183 In find_if(In first, In last, Pred p) {
184 while (first != last) {
185 if (p(*first))
186 return first;
187 ++first;
188 }
189 return last;
190 }
191
192 /**
193 * Apply the function f on all elements from the range [first, last).
194 * The processing order is from beginning to end.
195 */
196 template<class In, class Op>
for_each(In first,In last,Op f)197 Op for_each(In first, In last, Op f) {
198 while (first != last)
199 f(*first++);
200 return f;
201 }
202
203 /**
204 * @}
205 */
206
207 template<typename T>
distance(T * first,T * last)208 unsigned int distance(T *first, T *last) {
209 return last - first;
210 }
211
212 template<typename T>
distance(T first,T last)213 unsigned int distance(T first, T last) {
214 unsigned int n = 0;
215 while (first != last) {
216 ++n;
217 ++first;
218 }
219 return n;
220 }
221
222 template<typename T>
sortChoosePivot(T * first,T * last)223 T *sortChoosePivot(T *first, T *last) {
224 return first + distance(first, last) / 2;
225 }
226
227 template<typename T>
sortChoosePivot(T first,T last)228 T sortChoosePivot(T first, T last) {
229 unsigned int n = distance(first, last);
230 n /= 2;
231 while (n--)
232 ++first;
233 return first;
234 }
235
236 template<typename T, class StrictWeakOrdering>
sortPartition(T first,T last,T pivot,StrictWeakOrdering & comp)237 T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
238 --last;
239 if (pivot != last)
240 SWAP(*pivot, *last);
241
242 T sorted;
243 for (sorted = first; first != last; ++first) {
244 if (!comp(*last, *first)) {
245 if (first != sorted)
246 SWAP(*first, *sorted);
247 ++sorted;
248 }
249 }
250
251 if (last != sorted)
252 SWAP(*last, *sorted);
253 return sorted;
254 }
255
256 /**
257 * @name Sorting templates
258 * @{
259 */
260
261 /**
262 * Simple sorting function, modeled after std::sort.
263 *
264 * This function compares data with the given comparator object comp.
265 *
266 * Like std::sort, this is not guaranteed to be stable.
267 *
268 * Two quotes from Wikipedia about stability:
269 *
270 * Stable sorting algorithms maintain the relative order of records with
271 * equal keys.
272 *
273 * Unstable sorting algorithms may change the relative order of records with
274 * equal keys, but stable sorting algorithms never do so.
275 *
276 * For more information, see:
277 * http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
278 *
279 * @note Currently, this implementation is unstable.
280 *
281 * @param[in] first First element to sort.
282 * @param[in] last Last element to sort.
283 * @param[in] comp Comparator object.
284 */
285
286 template<typename T, class StrictWeakOrdering>
sort(T first,T last,StrictWeakOrdering comp)287 void sort(T first, T last, StrictWeakOrdering comp) {
288 if (first == last)
289 return;
290
291 T pivot = sortChoosePivot(first, last);
292 pivot = sortPartition(first, last, pivot, comp);
293 sort<T, StrictWeakOrdering>(first, pivot, comp);
294 sort<T, StrictWeakOrdering>(++pivot, last, comp);
295 }
296
297 /**
298 * Simple sorting function, modeled after std::sort.
299 *
300 * @param[in] first First element to sort.
301 * @param[in] last Last element to sort.
302 */
303 template<typename T>
sort(T * first,T * last)304 void sort(T *first, T *last) {
305 sort(first, last, Less<T>());
306 }
307
308 /**
309 * Simple sorting function, modeled after std::sort.
310 *
311 * @param[in] first First element to sort.
312 * @param[in] last Last element to sort.
313 */
314
315 template<class T>
sort(T first,T last)316 void sort(T first, T last) {
317 sort(first, last, Less<typename T::ValueType>());
318 }
319
320 /**
321 * @}
322 */
323
324 // MSVC is complaining about the minus operator being applied to an unsigned type
325 // We disable this warning for the affected section of code
326 #if defined(_MSC_VER)
327 #pragma warning(push)
328 #pragma warning(disable: 4146)
329 #endif
330
331 /**
332 * Euclidean algorithm to compute the greatest common divisor.
333 */
334 template<class T>
gcd(T a,T b)335 T gcd(T a, T b) {
336 // Note: We check for <= instead of < to avoid spurious compiler
337 // warnings if T is an unsigned type, i.e. warnings like "comparison
338 // of unsigned expression < 0 is always false".
339 if (a <= 0)
340 a = -a;
341 if (b <= 0)
342 b = -b;
343
344 while (a > 0) {
345 T tmp = a;
346 a = b % a;
347 b = tmp;
348 }
349
350 return b;
351 }
352
353 #if defined(_MSC_VER)
354 #pragma warning(pop)
355 #endif
356
357 /**
358 * Get the next highest power of 2.
359 */
360 template<class T>
nextHigher2(T v)361 T nextHigher2(T v) {
362 if (v == 0)
363 return 1;
364 v--;
365 v |= v >> 1;
366 v |= v >> 2;
367 v |= v >> 4;
368 v |= v >> 8;
369 v |= v >> 16;
370 return ++v;
371 }
372
373 /**
374 * Replacement algorithm for iterables.
375 *
376 * Replaces all occurrences of "original" in [begin, end) with occurrences of "replaced".
377 *
378 * @param[in,out] begin First element to be examined.
379 * @param[in] end Last element in the subsection. Not examined.
380 * @param[in] original Elements to be replaced.
381 * @param[in] replaced Element to replace occurrences of @p original.
382 *
383 * @note Usage examples and unit tests may be found in "test/common/algorithm.h"
384 */
385 template<class It, class Dat>
replace(It begin,It end,const Dat & original,const Dat & replaced)386 void replace(It begin, It end, const Dat &original, const Dat &replaced) {
387 for (; begin != end; ++begin) {
388 if (*begin == original) {
389 *begin = replaced;
390 }
391 }
392 }
393
394 /** @} */
395
396 } // End of namespace Common
397
398 #endif
399