From a19b50ddf26ac4e36b3e86f781ef7c2ae5fc69fd Mon Sep 17 00:00:00 2001 From: Borja Lorente Escobar Date: Wed, 2 Mar 2016 17:07:50 +0100 Subject: COMMON: Add replace functions to Common and String. COMMON: Add replacement to common/algorithm.h COMMON: Intermediate commit to show doubts. COMMON: Basic String::replace() methods implemented. COMMON: Fix typo in the algorithm.h documentation. COMMON: Fix documentation of String::replace() COMMON: Fix formatting issues in method signatures. COMMON: Add assert and reformat loops in str and algorithm. COMMON: Fix typo in comment. COMMON: Fix style in string test cases. COMMON: Add Doxygen documentation to algorithm and String. COMMON: Add Doxygen documentation to algorithm and String. COMMON: Add Doxygen documentation to algorithm. COMMON: Fix style in algorithm comments. COMMON: Add Doxygen comments to String. COMMON: Add Doxygen comments to algorithm test function. COMMON: Add String support for substring replace. COMMON: Fix string replace to comply with STL COMMON: Fix documentation on string replace COMMON: Fix style in string replace COMMON: Fix unwanted reference problem in String::replace(). COMMON: Fix indentation in comments for replace COMMON: Fix indentation in replace COMMON: Fix comments in String::replace to match implementation. COMMON: Remove assert to allow for not-null-terminated character arrays COMMON: Add new test for String::replace COMMON: Fix broken comments on String::replace COMMON: Fix sharing bug on ensureCapacity COMMON: Remove superfluous call to makeUnique() --- common/algorithm.h | 21 ++++++++++++ common/str.cpp | 87 +++++++++++++++++++++++++++++++++++++------------ common/str.h | 52 ++++++++++++++++++++++++----- test/common/algorithm.h | 56 +++++++++++++++++++++++++++++++ test/common/str.h | 74 +++++++++++++++++++++++++++++++++++++++++ 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 +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 + 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()), 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 original; + Common::List 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"); + } }; -- cgit v1.2.3