Merge pull request #688 from blorente/master

COMMON:String::replace and Common::replace functionality added.

5 files changed, 261 insertions, 29 deletions

diff --git a/common/algorithm.h b/common/algorithm.h
index cbd6eae708..13cdd9f991 100644
--- a/common/algorithm.h
+++ b/common/algorithm.h
@@ -270,5 +270,26 @@ T gcd(T a, T b) {
 #pragma warning(pop)
 #endif
 
+/**
+ * Replacement algorithm for iterables.
+ *
+ * Replaces all occurrences of "original" in [begin, end) with occurrences of "replaced".
+ * 
+ * @param[in, out] begin: First element to be examined.
+ * @param[in] end: Last element in the seubsection. Not examined.
+ * @param[in] original: Elements to be replaced.
+ * @param[in] replaced: Element to replace occurrences of "original".
+ *
+ * @note Usage examples and unit tests may be found in "test/common/algorithm.h"
+ */
+template<class It, class Dat>
+void replace(It begin, It end, const Dat &original, const Dat &replaced) {
+	for (; begin != end; ++begin) {
+        if (*begin == original) {
+            *begin = replaced;
+        }
+    }
+}
+
 } // End of namespace Common
 #endif
diff --git a/common/str.cpp b/common/str.cpp
index ae3a965c70..c41e958349 100644
--- a/common/str.cpp
+++ b/common/str.cpp
@@ -75,7 +75,7 @@ void String::initWithCStr(const char *str, uint32 len) {
 }
 
 String::String(const String &str)
-    : _size(str._size) {
+	: _size(str._size) {
 	if (str.isStorageIntern()) {
 		// String in internal storage: just copy it
 		memcpy(_storage, str._storage, _builtinCapacity);
@@ -91,7 +91,7 @@ String::String(const String &str)
 }
 
 String::String(char c)
-    : _size(0), _str(_storage) {
+	: _size(0), _str(_storage) {
 
 	_storage[0] = c;
 	_storage[1] = 0;
@@ -132,24 +132,19 @@ void String::ensureCapacity(uint32 new_size, bool keep_old) {
 	if (!isShared && new_size < curCapacity)
 		return;
 
-	if (isShared && new_size < _builtinCapacity) {
-		// We share the storage, but there is enough internal storage: Use that.
-		newStorage = _storage;
-		newCapacity = _builtinCapacity;
-	} else {
-		// We need to allocate storage on the heap!
-
-		// Compute a suitable new capacity limit
-		// If the current capacity is sufficient we use the same capacity
-		if (new_size < curCapacity)
-			newCapacity = curCapacity;
-		else
-			newCapacity = MAX(curCapacity * 2, computeCapacity(new_size+1));
-
-		// Allocate new storage
-		newStorage = new char[newCapacity];
-		assert(newStorage);
-	}
+	// We need to allocate storage on the heap!
+
+	// Compute a suitable new capacity limit
+	// If the current capacity is sufficient we use the same capacity
+	if (new_size < curCapacity)
+		newCapacity = curCapacity;
+	else
+		newCapacity = MAX(curCapacity * 2, computeCapacity(new_size+1));
+
+	// Allocate new storage
+	newStorage = new char[newCapacity];
+	assert(newStorage);
+	
 
 	// Copy old data if needed, elsewise reset the new storage.
 	if (keep_old) {
@@ -444,6 +439,58 @@ uint String::hash() const {
 	return hashit(c_str());
 }
 
+void String::replace(uint32 pos, uint32 count, const String &str) {
+	replace(pos, count, str, 0, str._size);
+}
+
+void String::replace(uint32 pos, uint32 count, const char *str) {
+	replace(pos, count, str, 0, strlen(str));
+}
+
+void String::replace(iterator begin, iterator end, const String &str) {
+	replace(begin - _str, end - begin, str._str, 0, str._size);
+}
+
+void String::replace(iterator begin, iterator end, const char *str) {
+	replace(begin - _str, end - begin, str, 0, strlen(str));
+}
+
+void String::replace(uint32 posOri, uint32 countOri, const String &str,
+					 uint32 posDest, uint32 countDest) {
+	replace(posOri, countOri, str._str, posDest, countDest);
+}
+
+void String::replace(uint32 posOri, uint32 countOri, const char *str,
+					 uint32 posDest, uint32 countDest) {
+
+	ensureCapacity(_size + countDest - countOri, true);
+
+	// Prepare string for the replaced text.
+	if (countOri < countDest) {
+		uint32 offset = countDest - countOri; ///< Offset to copy the characters
+		uint32 newSize = _size + offset;
+		_size = newSize;
+
+		// Push the old characters to the end of the string
+		for (uint32 i = _size; i >= posOri + countDest; i--) 
+			_str[i] = _str[i - offset];
+
+	} else if (countOri > countDest){
+		uint32 offset = countOri - countDest; ///< Number of positions that we have to pull back
+
+		// Pull the remainder string back
+		for (uint32 i = posOri + countDest; i < _size; i++) 
+			_str[i] = _str[i + offset];	
+
+		_size -= offset; 
+	}
+
+	// Copy the replaced part of the string
+	for (uint32 i = 0; i < countDest; i++) 
+		_str[posOri + i] = str[posDest + i];
+
+}
+
 // static
 String String::format(const char *fmt, ...) {
 	String output;
diff --git a/common/str.h b/common/str.h
index 1b41c481c7..9ada8aaaa0 100644
--- a/common/str.h
+++ b/common/str.h
@@ -46,6 +46,17 @@ namespace Common {
 class String {
 public:
 	static const uint32 npos = 0xFFFFFFFF;
+
+	typedef char          value_type;
+	/**
+	 * Unsigned version of the underlying type. This can be used to cast
+	 * individual string characters to bigger integer types without sign
+	 * extension happening.
+	 */
+	typedef unsigned char unsigned_type;
+	typedef char *        iterator;
+	typedef const char *  const_iterator;
+
 protected:
 	/**
 	 * The size of the internal storage. Increasing this means less heap
@@ -222,6 +233,38 @@ public:
 	void trim();
 
 	uint hash() const;
+	 
+	/**@{
+	 * Functions to replace some amount of chars with chars from some other string.
+	 *
+	 * @note The implementation follows that of the STL's std::string:
+	 *       http://www.cplusplus.com/reference/string/string/replace/        
+	 *
+	 * @param pos Starting position for the replace in the original string.
+	 * @param count Number of chars to replace from the original string.
+	 * @param str Source of the new chars.
+	 * @param posOri Same as pos
+	 * @param countOri Same as count
+	 * @param posDest Initial position to read str from.
+	 * @param countDest Number of chars to read from str. npos by default.
+	 */ 
+	// Replace 'count' bytes, starting from 'pos' with str.
+	void replace(uint32 pos, uint32 count, const String &str);
+	// The same as above, but accepts a C-like array of characters.
+	void replace(uint32 pos, uint32 count, const char *str);
+	// Replace the characters in [begin, end) with str._str.
+	void replace(iterator begin, iterator end, const String &str);
+	// Replace the characters in [begin, end) with str.
+	void replace(iterator begin, iterator end, const char *str);
+	// Replace _str[posOri, posOri + countOri) with
+	// str._str[posDest, posDest + countDest)
+	void replace(uint32 posOri, uint32 countOri, const String &str,
+					uint32 posDest, uint32 countDest);
+	// Replace _str[posOri, posOri + countOri) with
+	// str[posDest, posDest + countDest)
+	void replace(uint32 posOri, uint32 countOri, const char *str,
+					uint32 posDest, uint32 countDest);
+	/**@}*/ 
 
 	/**
 	 * Print formatted data into a String object. Similar to sprintf,
@@ -238,15 +281,6 @@ public:
 	static String vformat(const char *fmt, va_list args);
 
 public:
-	typedef char          value_type;
-	/**
-	 * Unsigned version of the underlying type. This can be used to cast
-	 * individual string characters to bigger integer types without sign
-	 * extension happening.
-	 */
-	typedef unsigned char unsigned_type;
-	typedef char *        iterator;
-	typedef const char *  const_iterator;
 
 	iterator begin() {
 		// Since the user could potentially
diff --git a/test/common/algorithm.h b/test/common/algorithm.h
index ccf6469f67..eeed59d821 100644
--- a/test/common/algorithm.h
+++ b/test/common/algorithm.h
@@ -25,6 +25,34 @@ class AlgorithmTestSuite : public CxxTest::TestSuite {
 		return true;
 	}
 
+	/**
+	 * Auxiliary function to check the equality of two generic collections (A and B), from one_first to one_last.
+	 *
+	 * @note: It assumes that other has at least (one_last - one-first) lenght, starting from other_first. 
+	 * 
+	 * @param one_first: The first element of the first collection to be compared.
+	 * @param one_last: The last element of the first collection to be compared.
+	 * @param other_first: The first element of the collection to be compared.
+	 * @return true if, for each index i in [one_first, one_last), A[i] == B[i], false otherwise.
+	 */
+	template<typename It>
+	bool checkEqual(It one_first, It one_last, It other_first) {
+		if (one_first == one_last) 
+			return true;
+
+		// Check whether two containers have the same items in the same order,
+		// starting from some iterators one_first and other_first
+		// 
+		// It iterates through the containers, comparing the elements one by one.
+		// If it finds a discrepancy, it returns false. Otherwise, it returns true.
+
+		for (; one_first != one_last; ++one_first, ++other_first) 
+			if (*one_first != *other_first) 			
+				return false;
+		
+		return true;
+	}
+
 	struct Item {
 		int value;
 		Item(int v) : value(v) {}
@@ -97,4 +125,32 @@ public:
 		Common::sort(list.begin(), list.end());
 		TS_ASSERT_EQUALS(checkSort(list.begin(), list.end(), Common::Less<Item>()), true);
 	}
+	
+	void test_string_replace() {
+
+		Common::String original = "Hello World";
+		Common::String expected = "Hells Wsrld";
+
+		Common::replace(original.begin(), original.end(), 'o', 's');
+		
+		TS_ASSERT_EQUALS(original, expected);		
+	}
+
+	void test_container_replace() {
+		
+		Common::List<int> original;
+		Common::List<int> expected;
+		for (int i = 0; i < 6; ++i) {
+			original.push_back(i);
+			if (i == 3) {
+				expected.push_back(5);
+			} else {
+				expected.push_back(i);
+			}
+		}
+
+		Common::replace(original.begin(), original.end(), 3, 5);
+		
+		TS_ASSERT_EQUALS(checkEqual(original.begin(), original.end(), expected.begin()), true);
+	}
 };
diff --git a/test/common/str.h b/test/common/str.h
index 3ab5d828c1..461b26088a 100644
--- a/test/common/str.h
+++ b/test/common/str.h
@@ -419,4 +419,78 @@ class StringTestSuite : public CxxTest::TestSuite
 		TS_ASSERT_EQUALS(scumm_strnicmp("abCd", "ABCde", 4), 0);
 		TS_ASSERT_LESS_THAN(scumm_strnicmp("abCd", "ABCde", 5), 0);
 	}
+
+	void test_replace() {
+		// Tests created with the results of the STL std::string class
+
+		// --------------------------
+		// Tests without displacement
+		// --------------------------
+		Common::String testString = Common::String("This is the original string.");
+
+		// Positions and sizes as parameters, string as replacement
+		testString.replace(12, 8, Common::String("newnewne"));
+		TS_ASSERT_EQUALS(testString, Common::String("This is the newnewne string."));
+
+		// The same but with char*
+		testString.replace(0, 4, "That");
+		TS_ASSERT_EQUALS(testString, Common::String("That is the newnewne string."));
+
+		// Using iterators (also a terribly useless program as a test).
+		testString.replace(testString.begin(), testString.end(), "That is the supernew string.");
+		TS_ASSERT_EQUALS(testString, Common::String("That is the supernew string."));        
+       		
+		// With sub strings of character arrays.
+		testString.replace(21, 6, "That phrase is new.", 5, 6);
+		TS_ASSERT_EQUALS(testString, Common::String("That is the supernew phrase."));
+
+		// Now with substrings.		
+		testString.replace(12, 2, Common::String("That hy is new."), 5, 2);
+		TS_ASSERT_EQUALS(testString, Common::String("That is the hypernew phrase."));
+		
+		// --------------------------
+		// Tests with displacement
+		// --------------------------
+		testString = Common::String("Hello World");
+
+		// Positions and sizes as parameters, string as replacement
+		testString.replace(6, 5, Common::String("friends"));
+		TS_ASSERT_EQUALS(testString, Common::String("Hello friends"));
+
+		// The same but with char*
+		testString.replace(0, 5, "Good");
+		TS_ASSERT_EQUALS(testString, Common::String("Good friends"));
+
+		// Using iterators (also a terribly useless program as a test)
+		testString.replace(testString.begin() + 4, testString.begin() + 5, " coffee ");
+		TS_ASSERT_EQUALS(testString, Common::String("Good coffee friends"));  
+
+		// With sub strings of character arrays
+		testString.replace(4, 0, "Lorem ipsum expresso dolor sit amet", 11, 9);
+		TS_ASSERT_EQUALS(testString, Common::String("Good expresso coffee friends"));
+		
+		// Now with substrings	
+		testString.replace(5, 9, Common::String("Displaced ristretto string"), 10, 10);
+		TS_ASSERT_EQUALS(testString, Common::String("Good ristretto coffee friends"));
+        
+        // -----------------------
+        // Deep copy compliance
+        // -----------------------
+        
+        // Makes a deep copy without changing the length of the original
+        Common::String s1 = "TestTestTestTestTestTestTestTestTestTestTest";
+        Common::String s2(s1);
+        TS_ASSERT_EQUALS(s1, "TestTestTestTestTestTestTestTestTestTestTest");
+        TS_ASSERT_EQUALS(s2, "TestTestTestTestTestTestTestTestTestTestTest");
+        s1.replace(0, 4, "TEST");
+        TS_ASSERT_EQUALS(s1, "TESTTestTestTestTestTestTestTestTestTestTest");
+        TS_ASSERT_EQUALS(s2, "TestTestTestTestTestTestTestTestTestTestTest");
+
+        // Makes a deep copy when we shorten the string
+    	Common::String s3 = "TestTestTestTestTestTestTestTestTestTestTest";
+		Common::String s4(s3);
+		s3.replace(0, 32, "");
+		TS_ASSERT_EQUALS(s3, "TestTestTest");
+		TS_ASSERT_EQUALS(s4, "TestTestTestTestTestTestTestTestTestTestTest");
+	}
 };