Commit of patch #1715313 ("CORE: STL like algorithm implementation").

svn-id: r26929

5 files changed, 330 insertions, 55 deletions

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<class In, class Out>
+Out copy(In first, In last, Out dst) {
+	while (first != last)
+		*dst++ = *first++;
+	return dst;
+}
+
+template<class In, class Out>
+Out copy_backward(In first, In last, Out dst) {
+	while (first != last)
+		*--dst = *--last;
+	return dst;
+}
+
+template<class In, class Out, class Op>
+Out copy_if(In first, In last, Out dst, Op op) {
+	while (first != last) {
+		if (op(*first))
+			*dst++ = *first;
+		++first;
+	}
+	return dst;
+}
+
+template<class In, class T>
+In find(In first, In last, const T &v) {
+	while (first != last) {
+		if (*first == v)
+			return first;
+		++first;
+	}
+	return last;
+}
+
+template<class In, class Pred>
+In find_if(In first, In last, Pred p) {
+	while (first != last) {
+		if (p(*first))
+			return first;
+		++first;
+	}
+	return last;
+}
+
+template<class In, class Op>
+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<class T>
+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<T>& 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<T>& 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 <class T>
-struct EqualTo {
-  bool operator()(const T& x, const T& y) const { return x == y; }
+template<class Arg, class Result>
+struct UnaryFunction {
+	typedef Arg ArgumenType;
+	typedef Result ResultType;
 };
 
-template <class T>
-struct Less {
-  bool operator()(const T& x, const T& y) const { return x < y; }
+template<class Arg1, class Arg2, class Result>
+struct BinaryFunction {
+	typedef Arg1 FirstArgumentType;
+	typedef Arg2 SecondArgumentType;
+	typedef Result ResultType;
 };
 
+template<class T>
+struct EqualTo : public BinaryFunction<T, T, bool> {
+	bool operator()(const T& x, const T& y) const { return x == y; }
+};
+
+template<class T>
+struct Less : public BinaryFunction<T, T, bool> {
+	bool operator()(const T& x, const T& y) const { return x < y; }
+};
+
+template<class Op>
+class Binder1st : public UnaryFunction<typename Op::SecondArgumentType, typename Op::ResultType> {
+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<class Op, class T>
+inline Binder1st<Op> bind1st(const Op &op, const T &t) {
+	return Binder1st<Op>(op, t);
+}
+
+template<class Op>
+class Binder2nd : public UnaryFunction<typename Op::FirstArgumentType, typename Op::ResultType> {
+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<class Op, class T>
+inline Binder2nd<Op> bind2nd(const Op &op, const T &t) {
+	return Binder2nd<Op>(op, t);
+}
+
+template<class Arg, class Result>
+class PointerToUnaryFunc : public UnaryFunction<Arg, Result> {
+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 Arg1, class Arg2, class Result>
+class PointerToBinaryFunc : public BinaryFunction<Arg1, Arg2, Result> {
+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<class Arg, class Result>
+inline PointerToUnaryFunc<Arg, Result> ptr_fun(Result (*func)(Arg)) {
+	return PointerToUnaryFunc<Arg, Result>(func);
+}
+
+template<class Arg1, class Arg2, class Result>
+inline PointerToBinaryFunc<Arg1, Arg2, Result> ptr_fun(Result (*func)(Arg1, Arg2)) {
+	return PointerToBinaryFunc<Arg1, Arg2, Result>(func);
+}
+
+template<class Result, class T>
+class MemFunc0 : public UnaryFunction<T*, Result> {
+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 Result, class T>
+class ConstMemFunc0 : public UnaryFunction<T*, Result> {
+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 Result, class Arg, class T>
+class MemFunc1 : public BinaryFunction<T*, Arg, Result> {
+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 Result, class Arg, class T>
+class ConstMemFunc1 : public BinaryFunction<T*, Arg, Result> {
+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<class Result, class T>
+inline MemFunc0<Result, T> mem_fun(Result (T::*f)()) {
+	return MemFunc0<Result, T>(f);
+}
+
+template<class Result, class T>
+inline ConstMemFunc0<Result, T> mem_fun(Result (T::*f)() const) {
+	return ConstMemFunc0<Result, T>(f);
+}
+
+template<class Result, class Arg, class T>
+inline MemFunc1<Result, Arg, T> mem_fun(Result (T::*f)(Arg)) {
+	return MemFunc1<Result, Arg, T>(f);
+}
+
+template<class Result, class Arg, class T>
+inline ConstMemFunc1<Result, Arg, T> mem_fun(Result (T::*f)(Arg) const) {
+	return ConstMemFunc1<Result, Arg, T>(f);
+}
+
+template<class Cont>
+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<class Cont>
+BackInsertIterator<Cont> back_inserter(Cont &c) {
+	return BackInsertIterator<Cont>(c);
+}
+
+template<class Cont>
+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<class Cont>
+FrontInsertIterator<Cont> front_inserter(Cont &c) {
+	return FrontInsertIterator<Cont>(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 <typename T>
-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<T>        iterator;
-	typedef Iterator<const T>  const_iterator;
+	typedef Iterator<T>			iterator;
+	typedef Iterator<const T>	const_iterator;
+
+	typedef T value_type;
 
 public:
 	List() {