ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

algorithm.h

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
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 // Our 'specialized' 'fill' template for char, signed char and unsigned char arrays.
00078 // Since C++ doesn't support partial specialized template functions (currently) we
00079 // are going this way...
00080 // With this we assure the usage of memset for those, which should be
00081 // faster than a simple loop like for the generic 'fill'.
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 // MSVC is complaining about the minus operator being applied to an unsigned type
00242 // We disable this warning for the affected section of code
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     // Note: We check for <= instead of < to avoid spurious compiler
00254     // warnings if T is an unsigned type, i.e. warnings like "comparison
00255     // of unsigned expression < 0 is always false".
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 } // End of namespace Common
00296 #endif


Generated on Sat Feb 16 2019 05:00:44 for ResidualVM by doxygen 1.7.1
curved edge   curved edge