00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef COMMON_ALGORITHM_H
00024 #define COMMON_ALGORITHM_H
00025
00026 #include "common/scummsys.h"
00027 #include "common/func.h"
00028 #include "common/util.h"
00029
00030 namespace Common {
00031
00037 template<class In, class Out>
00038 Out copy(In first, In last, Out dst) {
00039 while (first != last)
00040 *dst++ = *first++;
00041 return dst;
00042 }
00043
00051 template<class In, class Out>
00052 Out copy_backward(In first, In last, Out dst) {
00053 while (first != last)
00054 *--dst = *--last;
00055 return dst;
00056 }
00057
00067 template<class In, class Out, class Op>
00068 Out copy_if(In first, In last, Out dst, Op op) {
00069 while (first != last) {
00070 if (op(*first))
00071 *dst++ = *first;
00072 ++first;
00073 }
00074 return dst;
00075 }
00076
00077
00078
00079
00080
00081
00082 template<class Value>
00083 signed char *fill(signed char *first, signed char *last, Value val) {
00084 memset(first, (val & 0xFF), last - first);
00085 return last;
00086 }
00087
00088 template<class Value>
00089 unsigned char *fill(unsigned char *first, unsigned char *last, Value val) {
00090 memset(first, (val & 0xFF), last - first);
00091 return last;
00092 }
00093
00094 template<class Value>
00095 char *fill(char *first, char *last, Value val) {
00096 memset(first, (val & 0xFF), last - first);
00097 return last;
00098 }
00099
00103 template<class In, class Value>
00104 In fill(In first, In last, const Value &val) {
00105 while (first != last)
00106 *first++ = val;
00107 return first;
00108 }
00109
00114 template<class In, class T>
00115 In find(In first, In last, const T &v) {
00116 while (first != last) {
00117 if (*first == v)
00118 return first;
00119 ++first;
00120 }
00121 return last;
00122 }
00123
00128 template<class In, class Pred>
00129 In find_if(In first, In last, Pred p) {
00130 while (first != last) {
00131 if (p(*first))
00132 return first;
00133 ++first;
00134 }
00135 return last;
00136 }
00137
00142 template<class In, class Op>
00143 Op for_each(In first, In last, Op f) {
00144 while (first != last)
00145 f(*first++);
00146 return f;
00147 }
00148
00149 template<typename T>
00150 unsigned int distance(T *first, T *last) {
00151 return last - first;
00152 }
00153
00154 template<typename T>
00155 unsigned int distance(T first, T last) {
00156 unsigned int n = 0;
00157 while (first != last) {
00158 ++n;
00159 ++first;
00160 }
00161 return n;
00162 }
00163
00164 template<typename T>
00165 T *sortChoosePivot(T *first, T *last) {
00166 return first + distance(first, last) / 2;
00167 }
00168
00169 template<typename T>
00170 T sortChoosePivot(T first, T last) {
00171 unsigned int n = distance(first, last);
00172 n /= 2;
00173 while (n--)
00174 ++first;
00175 return first;
00176 }
00177
00178 template<typename T, class StrictWeakOrdering>
00179 T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
00180 --last;
00181 if (pivot != last)
00182 SWAP(*pivot, *last);
00183
00184 T sorted;
00185 for (sorted = first; first != last; ++first) {
00186 if (!comp(*last, *first)) {
00187 if (first != sorted)
00188 SWAP(*first, *sorted);
00189 ++sorted;
00190 }
00191 }
00192
00193 if (last != sorted)
00194 SWAP(*last, *sorted);
00195 return sorted;
00196 }
00197
00217 template<typename T, class StrictWeakOrdering>
00218 void sort(T first, T last, StrictWeakOrdering comp) {
00219 if (first == last)
00220 return;
00221
00222 T pivot = sortChoosePivot(first, last);
00223 pivot = sortPartition(first, last, pivot, comp);
00224 sort<T, StrictWeakOrdering>(first, pivot, comp);
00225 sort<T, StrictWeakOrdering>(++pivot, last, comp);
00226 }
00227
00231 template<typename T>
00232 void sort(T *first, T *last) {
00233 sort(first, last, Less<T>());
00234 }
00235
00236 template<class T>
00237 void sort(T first, T last) {
00238 sort(first, last, Less<typename T::ValueType>());
00239 }
00240
00241
00242
00243 #if defined(_MSC_VER)
00244 #pragma warning(push)
00245 #pragma warning(disable: 4146)
00246 #endif
00247
00251 template<class T>
00252 T gcd(T a, T b) {
00253
00254
00255
00256 if (a <= 0)
00257 a = -a;
00258 if (b <= 0)
00259 b = -b;
00260
00261 while (a > 0) {
00262 T tmp = a;
00263 a = b % a;
00264 b = tmp;
00265 }
00266
00267 return b;
00268 }
00269
00270 #if defined(_MSC_VER)
00271 #pragma warning(pop)
00272 #endif
00273
00286 template<class It, class Dat>
00287 void replace(It begin, It end, const Dat &original, const Dat &replaced) {
00288 for (; begin != end; ++begin) {
00289 if (*begin == original) {
00290 *begin = replaced;
00291 }
00292 }
00293 }
00294
00295 }
00296 #endif