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) f(*first++);
145 return f;
146 }
147
148 template<typename T>
distance(T * first,T * last)149 unsigned int distance(T *first, T *last) {
150 return last - first;
151 }
152
153 template<typename T>
distance(T first,T last)154 unsigned int distance(T first, T last) {
155 unsigned int n = 0;
156 while (first != last) {
157 ++n;
158 ++first;
159 }
160 return n;
161 }
162
163 template<typename T>
sortChoosePivot(T * first,T * last)164 T *sortChoosePivot(T *first, T *last) {
165 return first + distance(first, last) / 2;
166 }
167
168 template<typename T>
sortChoosePivot(T first,T last)169 T sortChoosePivot(T first, T last) {
170 unsigned int n = distance(first, last);
171 n /= 2;
172 while (n--)
173 ++first;
174 return first;
175 }
176
177 template<typename T, class StrictWeakOrdering>
sortPartition(T first,T last,T pivot,StrictWeakOrdering & comp)178 T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
179 --last;
180 if (pivot != last)
181 SWAP(*pivot, *last);
182
183 T sorted;
184 for (sorted = first; first != last; ++first) {
185 if (!comp(*last, *first)) {
186 if (first != sorted)
187 SWAP(*first, *sorted);
188 ++sorted;
189 }
190 }
191
192 if (last != sorted)
193 SWAP(*last, *sorted);
194 return sorted;
195 }
196
197 /**
198 * Simple sort function, modeled after std::sort.
199 * It compares data with the given comparator object comp.
200 *
201 * Like std::sort this is not guaranteed to be stable.
202 *
203 * Two small quotes from wikipedia about stability:
204 *
205 * Stable sorting algorithms maintain the relative order of records with
206 * equal keys.
207 *
208 * Unstable sorting algorithms may change the relative order of records with
209 * equal keys, but stable sorting algorithms never do so.
210 *
211 * For more information on that topic check out:
212 * http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
213 *
214 * NOTE: Actually as the time of writing our implementation is unstable.
215 */
216 template<typename T, class StrictWeakOrdering>
sort(T first,T last,StrictWeakOrdering comp)217 void sort(T first, T last, StrictWeakOrdering comp) {
218 if (first == last)
219 return;
220
221 T pivot = sortChoosePivot(first, last);
222 pivot = sortPartition(first, last, pivot, comp);
223 sort<T, StrictWeakOrdering>(first, pivot, comp);
224 sort<T, StrictWeakOrdering>(++pivot, last, comp);
225 }
226
227 /**
228 * Simple sort function, modeled after std::sort.
229 */
230 template<typename T>
sort(T * first,T * last)231 void sort(T *first, T *last) {
232 sort(first, last, Less<T>());
233 }
234
235 template<class T>
sort(T first,T last)236 void sort(T first, T last) {
237 sort(first, last, Less<typename T::ValueType>());
238 }
239
240 // MSVC is complaining about the minus operator being applied to an unsigned type
241 // We disable this warning for the affected section of code
242 #if defined(_MSC_VER)
243 #pragma warning(push)
244 #pragma warning(disable: 4146)
245 #endif
246
247 /**
248 * Euclid's algorithm to compute the greatest common divisor.
249 */
250 template<class T>
gcd(T a,T b)251 T gcd(T a, T b) {
252 // Note: We check for <= instead of < to avoid spurious compiler
253 // warnings if T is an unsigned type, i.e. warnings like "comparison
254 // of unsigned expression < 0 is always false".
255 if (a <= 0)
256 a = -a;
257 if (b <= 0)
258 b = -b;
259
260 while (a > 0) {
261 T tmp = a;
262 a = b % a;
263 b = tmp;
264 }
265
266 return b;
267 }
268
269 #if defined(_MSC_VER)
270 #pragma warning(pop)
271 #endif
272
273 /**
274 * Replacement algorithm for iterables.
275 *
276 * Replaces all occurrences of "original" in [begin, end) with occurrences of "replaced".
277 *
278 * @param[in, out] begin: First element to be examined.
279 * @param[in] end: Last element in the seubsection. Not examined.
280 * @param[in] original: Elements to be replaced.
281 * @param[in] replaced: Element to replace occurrences of "original".
282 *
283 * @note Usage examples and unit tests may be found in "test/common/algorithm.h"
284 */
285 template<class It, class Dat>
replace(It begin,It end,const Dat & original,const Dat & replaced)286 void replace(It begin, It end, const Dat &original, const Dat &replaced) {
287 for (; begin != end; ++begin) {
288 if (*begin == original) {
289 *begin = replaced;
290 }
291 }
292 }
293
294 } // End of namespace Common
295 #endif
296