1 /* ScummVM Tools
2 *
3 * ScummVM Tools is the legal property of its developers, whose
4 * names are too numerous to list here. Please refer to the
5 * COPYRIGHT file distributed with this source distribution.
6 *
7 * Additionally this file is based on the ScummVM source code.
8 * Copyright information for the ScummVM source code is
9 * available in the COPYRIGHT file of the ScummVM source
10 * distribution.
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
16 *
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26
27 #ifndef COMMON_ALGORITHM_H
28 #define COMMON_ALGORITHM_H
29
30 #include "common/scummsys.h"
31 #include "common/func.h"
32
33 namespace Common {
34
35 /**
36 * Copies data from the range [first, last) to [dst, dst + (last - first)).
37 * It requires the range [dst, dst + (last - first)) to be valid.
38 * It also requires dst not to be in the range [first, last).
39 */
40 template<class In, class Out>
copy(In first,In last,Out dst)41 Out copy(In first, In last, Out dst) {
42 while (first != last)
43 *dst++ = *first++;
44 return dst;
45 }
46
47 /**
48 * Copies data from the range [first, last) to [dst - (last - first), dst).
49 * It requires the range [dst - (last - first), dst) to be valid.
50 * It also requires dst not to be in the range [first, last).
51 *
52 * Unlike copy copy_backward copies the data from the end to the beginning.
53 */
54 template<class In, class Out>
copy_backward(In first,In last,Out dst)55 Out copy_backward(In first, In last, Out dst) {
56 while (first != last)
57 *--dst = *--last;
58 return dst;
59 }
60
61 /**
62 * Copies data from the range [first, last) to [dst, dst + (last - first)).
63 * It requires the range [dst, dst + (last - first)) to be valid.
64 * It also requires dst not to be in the range [first, last).
65 *
66 * Unlike copy or copy_backward it does not copy all data. It only copies
67 * a data element when operator() of the op parameter returns true for the
68 * passed data element.
69 */
70 template<class In, class Out, class Op>
copy_if(In first,In last,Out dst,Op op)71 Out copy_if(In first, In last, Out dst, Op op) {
72 while (first != last) {
73 if (op(*first))
74 *dst++ = *first;
75 ++first;
76 }
77 return dst;
78 }
79
80 // Our 'specialized' 'set_to' template for char, signed char and unsigned char arrays.
81 // Since C++ doesn't support partial specialized template functions (currently) we
82 // are going this way...
83 // With this we assure the usage of memset for those, which should be
84 // faster than a simple loop like for the generic 'set_to'.
85 template<class Value>
set_to(signed char * first,signed char * last,Value val)86 signed char *set_to(signed char *first, signed char *last, Value val) {
87 memset(first, (val & 0xFF), last - first);
88 return last;
89 }
90
91 template<class Value>
set_to(unsigned char * first,unsigned char * last,Value val)92 unsigned char *set_to(unsigned char *first, unsigned char *last, Value val) {
93 memset(first, (val & 0xFF), last - first);
94 return last;
95 }
96
97 template<class Value>
set_to(char * first,char * last,Value val)98 char *set_to(char *first, char *last, Value val) {
99 memset(first, (val & 0xFF), last - first);
100 return last;
101 }
102
103 /**
104 * Sets all elements in the range [first, last) to val.
105 */
106 template<class In, class Value>
set_to(In first,In last,Value val)107 In set_to(In first, In last, Value val) {
108 while (first != last)
109 *first++ = val;
110 return first;
111 }
112
113 /**
114 * Finds the first data value in the range [first, last) matching v.
115 * For data comperance it uses operator == of the data elements.
116 */
117 template<class In, class T>
find(In first,In last,const T & v)118 In find(In first, In last, const T &v) {
119 while (first != last) {
120 if (*first == v)
121 return first;
122 ++first;
123 }
124 return last;
125 }
126
127 /**
128 * Finds the first data value in the range [first, last) for which
129 * the specified predicate p returns true.
130 */
131 template<class In, class Pred>
find_if(In first,In last,Pred p)132 In find_if(In first, In last, Pred p) {
133 while (first != last) {
134 if (p(*first))
135 return first;
136 ++first;
137 }
138 return last;
139 }
140
141 /**
142 * Applies the function f on all elements of the range [first, last).
143 * The processing order is from beginning to end.
144 */
145 template<class In, class Op>
for_each(In first,In last,Op f)146 Op for_each(In first, In last, Op f) {
147 while (first != last) f(*first++);
148 return f;
149 }
150
151 template<typename T>
distance(T * first,T * last)152 unsigned int distance(T *first, T *last) {
153 return last - first;
154 }
155
156 template<typename T>
distance(T first,T last)157 unsigned int distance(T first, T last) {
158 unsigned int n = 0;
159 while (first != last) {
160 ++n;
161 ++first;
162 }
163 return n;
164 }
165
166 template<typename T>
sortChoosePivot(T * first,T * last)167 T *sortChoosePivot(T *first, T *last) {
168 return first + distance(first, last) / 2;
169 }
170
171 template<typename T>
sortChoosePivot(T first,T last)172 T sortChoosePivot(T first, T last) {
173 unsigned int n = distance(first, last);
174 n /= 2;
175 while (n--)
176 ++first;
177 return first;
178 }
179
180 template<typename T, class StrictWeakOrdering>
sortPartition(T first,T last,T pivot,StrictWeakOrdering & comp)181 T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
182 --last;
183 SWAP(*pivot, *last);
184
185 T sorted;
186 for (sorted = first; first != last; ++first) {
187 if (!comp(*last, *first)) {
188 if (first != sorted)
189 SWAP(*first, *sorted);
190 ++sorted;
191 }
192 }
193
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 template<typename T, class StrictWeakOrdering>
sort(T first,T last,StrictWeakOrdering comp)203 void sort(T first, T last, StrictWeakOrdering comp) {
204 if (first == last)
205 return;
206
207 T pivot = sortChoosePivot(first, last);
208 pivot = sortPartition(first, last, pivot, comp);
209 sort<T, StrictWeakOrdering>(first, pivot, comp);
210 sort<T, StrictWeakOrdering>(++pivot, last, comp);
211 }
212
213 /**
214 * Simple sort function, modeled after std::sort.
215 */
216 template<typename T>
sort(T * first,T * last)217 void sort(T *first, T *last) {
218 sort(first, last, Common::Less<T>());
219 }
220
221 template<class T>
sort(T first,T last)222 void sort(T first, T last) {
223 sort(first, last, Common::Less<typename T::ValueType>());
224 }
225
226 } // End of namespace Common
227 #endif
228
229