From ad03c72bdb4eef62cbc05e432d7b49d3d2cd2038 Mon Sep 17 00:00:00 2001 From: Johannes Schickel Date: Wed, 23 May 2007 12:02:31 +0000 Subject: Commit of patch #1715313 ("CORE: STL like algorithm implementation"). svn-id: r26929 --- common/algorithm.h | 103 +++++++++++++++++++++++ common/array.h | 34 +++----- common/func.h | 240 ++++++++++++++++++++++++++++++++++++++++++++++------- common/hash-str.h | 2 + common/list.h | 6 +- 5 files changed, 330 insertions(+), 55 deletions(-) create mode 100644 common/algorithm.h (limited to 'common') diff --git a/common/algorithm.h b/common/algorithm.h new file mode 100644 index 0000000000..616dc67317 --- /dev/null +++ b/common/algorithm.h @@ -0,0 +1,103 @@ +/* ScummVM - Scumm Interpreter + * Copyright (C) 2007 The ScummVM project + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * $URL$ + * $Id$ + */ + +#ifndef COMMON_ALGORITHM_H +#define COMMON_ALGORITHM_H + +#include "common/scummsys.h" + +namespace Common { + +template +Out copy(In first, In last, Out dst) { + while (first != last) + *dst++ = *first++; + return dst; +} + +template +Out copy_backward(In first, In last, Out dst) { + while (first != last) + *--dst = *--last; + return dst; +} + +template +Out copy_if(In first, In last, Out dst, Op op) { + while (first != last) { + if (op(*first)) + *dst++ = *first; + ++first; + } + return dst; +} + +template +In find(In first, In last, const T &v) { + while (first != last) { + if (*first == v) + return first; + ++first; + } + return last; +} + +template +In find_if(In first, In last, Pred p) { + while (first != last) { + if (p(*first)) + return first; + ++first; + } + return last; +} + +template +Op for_each(In first, In last, Op f) { + while (first != last) f(*first++); + return f; +} + +// Simple sort function, modelled after std::sort. +// Use it like this: sort(container.begin(), container.end()). +// Also work on plain old int arrays etc. +template +void sort(T first, T last) { + if (first == last) + return; + + // Simple selection sort + T i(first); + for (; i != last; ++i) { + T minElem(i); + T j(i); + ++j; + for (; j != last; ++j) + if (*j < *minElem) + minElem = j; + if (minElem != i) + SWAP(*minElem, *i); + } +} + +} // end of namespace Common +#endif + diff --git a/common/array.h b/common/array.h index d0be7fa194..97ee6abdf4 100644 --- a/common/array.h +++ b/common/array.h @@ -23,6 +23,7 @@ #define COMMON_ARRAY_H #include "common/scummsys.h" +#include "common/algorithm.h" namespace Common { @@ -37,14 +38,15 @@ public: typedef T *iterator; typedef const T *const_iterator; + typedef T value_type; + public: Array() : _capacity(0), _size(0), _data(0) {} Array(const Array& array) : _capacity(0), _size(0), _data(0) { _size = array._size; _capacity = _size + 32; _data = new T[_capacity]; - for (int i = 0; i < _size; i++) - _data[i] = array._data[i]; + copy(array._data, array._data + _size, _data); } ~Array() { @@ -59,21 +61,14 @@ public: void push_back(const Array& array) { ensureCapacity(_size + array._size); - for (int i = 0; i < array._size; i++) - _data[_size++] = array._data[i]; + copy(array._data, array._data + array._size, _data + _size); + _size += array._size; } void insert_at(int idx, const T& element) { assert(idx >= 0 && idx <= _size); ensureCapacity(_size + 1); - // The following loop is not efficient if you can just memcpy things around. - // e.g. if you have a list of ints. But for real objects (String...), memcpy - // usually isn't correct (specifically, for any class which has a non-default - // copy behaviour. E.g. the String class uses a refCounter which has to be - // updated whenever a String is copied. - for (int i = _size; i > idx; i--) { - _data[i] = _data[i-1]; - } + copy_backward(_data + idx, _data + _size, _data + _size + 1); _data[idx] = element; _size++; } @@ -81,8 +76,7 @@ public: T remove_at(int idx) { assert(idx >= 0 && idx < _size); T tmp = _data[idx]; - for (int i = idx; i < _size - 1; i++) - _data[i] = _data[i+1]; + copy(_data + idx + 1, _data + _size, _data + idx); _size--; return tmp; } @@ -108,8 +102,7 @@ public: _size = array._size; _capacity = _size + 32; _data = new T[_capacity]; - for (int i = 0; i < _size; i++) - _data[i] = array._data[i]; + copy(array._data, array._data + _size, _data); return *this; } @@ -149,11 +142,7 @@ public: } bool contains(const T &key) const { - for (const_iterator i = begin(); i != end(); ++i) { - if (*i == key) - return true; - } - return false; + return find(begin(), end(), key) != end(); } @@ -168,8 +157,7 @@ protected: if (old_data) { // Copy old data - for (int i = 0; i < _size; i++) - _data[i] = old_data[i]; + copy(old_data, old_data + _size, _data); delete [] old_data; } } diff --git a/common/func.h b/common/func.h index b644f6569b..19d0ceafec 100644 --- a/common/func.h +++ b/common/func.h @@ -26,16 +26,219 @@ namespace Common { -template -struct EqualTo { - bool operator()(const T& x, const T& y) const { return x == y; } +template +struct UnaryFunction { + typedef Arg ArgumenType; + typedef Result ResultType; }; -template -struct Less { - bool operator()(const T& x, const T& y) const { return x < y; } +template +struct BinaryFunction { + typedef Arg1 FirstArgumentType; + typedef Arg2 SecondArgumentType; + typedef Result ResultType; }; +template +struct EqualTo : public BinaryFunction { + bool operator()(const T& x, const T& y) const { return x == y; } +}; + +template +struct Less : public BinaryFunction { + bool operator()(const T& x, const T& y) const { return x < y; } +}; + +template +class Binder1st : public UnaryFunction { +private: + Op _op; + typename Op::FirstArgumentType _arg1; +public: + Binder1st(const Op &op, const typename Op::FirstArgumentType &arg1) : _op(op), _arg1(arg1) {} + + typename Op::ResultType operator()(typename Op::SecondArgumentType v) const { + return _op(_arg1, v); + } +}; + +template +inline Binder1st bind1st(const Op &op, const T &t) { + return Binder1st(op, t); +} + +template +class Binder2nd : public UnaryFunction { +private: + Op _op; + typename Op::SecondArgumentType _arg2; +public: + Binder2nd(const Op &op, const typename Op::SecondArgumentType &arg2) : _op(op), _arg2(arg2) {} + + typename Op::ResultType operator()(typename Op::FirstArgumentType v) const { + return _op(v, _arg2); + } +}; + +template +inline Binder2nd bind2nd(const Op &op, const T &t) { + return Binder2nd(op, t); +} + +template +class PointerToUnaryFunc : public UnaryFunction { +private: + Result (*_func)(Arg); +public: + typedef Result (*FuncType)(Arg); + + PointerToUnaryFunc(const FuncType &func) : _func(func) {} + Result operator()(Arg v) const { + return _func(v); + } +}; + +template +class PointerToBinaryFunc : public BinaryFunction { +private: + Result (*_func)(Arg1, Arg2); +public: + typedef Result (*FuncType)(Arg1, Arg2); + + PointerToBinaryFunc(const FuncType &func) : _func(func) {} + Result operator()(Arg1 v1, Arg2 v2) const { + return _func(v1, v2); + } +}; + +template +inline PointerToUnaryFunc ptr_fun(Result (*func)(Arg)) { + return PointerToUnaryFunc(func); +} + +template +inline PointerToBinaryFunc ptr_fun(Result (*func)(Arg1, Arg2)) { + return PointerToBinaryFunc(func); +} + +template +class MemFunc0 : public UnaryFunction { +private: + Result (T::*_func)(); +public: + typedef Result (T::*FuncType)(); + + MemFunc0(const FuncType &func) : _func(func) {} + Result operator()(T *v) const { + return (v->*_func)(); + } +}; + +template +class ConstMemFunc0 : public UnaryFunction { +private: + Result (T::*_func)() const; +public: + typedef Result (T::*FuncType)() const; + + ConstMemFunc0(const FuncType &func) : _func(func) {} + Result operator()(T *v) const { + return (v->*_func)(); + } +}; + +template +class MemFunc1 : public BinaryFunction { +private: + Result (T::*_func)(Arg); +public: + typedef Result (T::*FuncType)(Arg); + + MemFunc1(const FuncType &func) : _func(func) {} + Result operator()(T *v1, Arg v2) const { + return (v1->*_func)(v2); + } +}; + +template +class ConstMemFunc1 : public BinaryFunction { +private: + Result (T::*_func)(Arg) const; +public: + typedef Result (T::*FuncType)(Arg) const; + + ConstMemFunc1(const FuncType &func) : _func(func) {} + Result operator()(T *v1, Arg v2) const { + return (v1->*_func)(v2); + } +}; + +template +inline MemFunc0 mem_fun(Result (T::*f)()) { + return MemFunc0(f); +} + +template +inline ConstMemFunc0 mem_fun(Result (T::*f)() const) { + return ConstMemFunc0(f); +} + +template +inline MemFunc1 mem_fun(Result (T::*f)(Arg)) { + return MemFunc1(f); +} + +template +inline ConstMemFunc1 mem_fun(Result (T::*f)(Arg) const) { + return ConstMemFunc1(f); +} + +template +class BackInsertIterator { +private: + Cont *_container; + +public: + BackInsertIterator(Cont &c) : _container(&c) {} + + BackInsertIterator &operator =(const typename Cont::value_type &v) { + _container->push_back(v); + return *this; + } + + BackInsertIterator &operator *() { return *this; } + BackInsertIterator &operator ++() { return *this; } + BackInsertIterator operator ++(int) { return *this; } +}; + +template +BackInsertIterator back_inserter(Cont &c) { + return BackInsertIterator(c); +} + +template +class FrontInsertIterator { +private: + Cont *_container; + +public: + FrontInsertIterator(Cont &c) : _container(&c) {} + + FrontInsertIterator &operator =(const typename Cont::value_type &v) { + _container->push_front(v); + return *this; + } + + FrontInsertIterator &operator *() { return *this; } + FrontInsertIterator &operator ++() { return *this; } + FrontInsertIterator operator ++(int) { return *this; } +}; + +template +FrontInsertIterator front_inserter(Cont &c) { + return FrontInsertIterator(c); +} + /** * Base template for hash functor objects, used by HashMap. * This needs to be specialized for every type that you need to hash. @@ -61,30 +264,7 @@ GENERATE_TRIVIAL_HASH_FUNCTOR(unsigned long); #undef GENERATE_TRIVIAL_HASH_FUNCTOR - -// Simple sort function, modelled after std::sort. -// Use it like this: sort(container.begin(), container.end()). -// Also work on plain old int arrays etc. -template -void sort(T first, T last) { - if (first == last) - return; - - // Simple selection sort - T i(first); - for (; i != last; ++i) { - T minElem(i); - T j(i); - ++j; - for (; j != last; ++j) - if (*j < *minElem) - minElem = j; - if (minElem != i) - SWAP(*minElem, *i); - } -} - - } // End of namespace Common #endif + diff --git a/common/hash-str.h b/common/hash-str.h index bb61e3091d..99ebf99a10 100644 --- a/common/hash-str.h +++ b/common/hash-str.h @@ -29,6 +29,8 @@ namespace Common { uint hashit(const char *str); uint hashit_lower(const char *str); // Generate a hash based on the lowercase version of the string +inline uint hashit(const String &str) { return hashit(str.c_str()); } +inline uint hashit_lower(const String &str) { return hashit_lower(str.c_str()); } // FIXME: The following functors obviously are not consistently named diff --git a/common/list.h b/common/list.h index da20f22cf1..68a464d194 100644 --- a/common/list.h +++ b/common/list.h @@ -111,8 +111,10 @@ public: NodeBase *_anchor; public: - typedef Iterator iterator; - typedef Iterator const_iterator; + typedef Iterator iterator; + typedef Iterator const_iterator; + + typedef T value_type; public: List() { -- cgit v1.2.3