- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Utils/Lang/String.cpp

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00009 // Organization:        Model-based Embedded and Robotic Systems Group
    00010 //                                      Massachusetts Institute of Technology
    00011 //
    00013
    00014 #include "String.h"
    00015 #if (defined(__APPLE__) || (defined(__MWERKS__) && defined(__MACOS__)))
    00016 #include <sys/malloc.h>
    00017 #else
    00018 #include <malloc.h>
    00019 #endif
    00020 #include <cstring>
    00021 #include <cstdio>
    00022 #include <stdexcept>
    00023 #include <limits.h>
    00024 #include <stdarg.h>
    00025 #include <cassert>
    00026 using namespace std;
    00027
    00028 using namespace Mers::Utils::Lang;
    00029
    00031 // Construction/Destruction
    00033
    00034 const String::size_type String::npos = -1;
    00035
    00037
    00038 String::String() : BaseModelObject(BaseModelObject::oString)
    00039 {
    00040         array = NULL;
    00041         curSize = 0;
    00042         maxSize = 0;
    00043         if(FAILED(grow(1))){
    00044                 return;
    00045         }else{
    00046                 array[curSize] = '\0';
    00047         }
    00048 }
    00049
    00051
    00052 String::String(const char * s) : BaseModelObject(BaseModelObject::oString)
    00053 {
    00054         array = NULL;
    00055         curSize = 0;
    00056         maxSize = 0;
    00057         assign(s);
    00058 }
    00059
    00061
    00062 String::String(const char * s, String::size_type n)
    00063 : BaseModelObject(BaseModelObject::oString)
    00064 {
    00065         array = NULL;
    00066         curSize = 0;
    00067         maxSize = 0;
    00068         assign(s, n);
    00069 }
    00070
    00072
    00073 String::String(const String& rhs) : BaseModelObject(BaseModelObject::oString)
    00074 {
    00075         array = NULL;
    00076         curSize = 0;
    00077         maxSize = 0;
    00078         assign(rhs);
    00079 }
    00080
    00082
    00083 String::String(const String& rhs, String::size_type pos, String::size_type n)
    00084 : BaseModelObject(BaseModelObject::oString)
    00085 {
    00086         array = NULL;
    00087         curSize = 0;
    00088         maxSize = 0;
    00089         assign(rhs, pos, n);
    00090 }
    00091
    00093
    00094 String::String(String::size_type n, char c)
    00095 : BaseModelObject(BaseModelObject::oString)
    00096 {
    00097         array = NULL;
    00098         curSize = 0;
    00099         maxSize = 0;
    00100         assign(n, c);
    00101 }
    00102
    00104
    00105 //String(String::const_iterator first, String::const_iterator last)
    00106 //{
    00107 //}
    00108
    00110
    00111 #ifndef MERS_STRING_ONLY
    00112
    00113 String::String(const std::string& rhs) : BaseModelObject(BaseModelObject::oString)
    00114 {
    00115         array = NULL;
    00116         curSize = 0;
    00117         maxSize = 0;
    00118         operator=(rhs);
    00119 }
    00120
    00121 #endif
    00122
    00124
    00125 String::~String()
    00126 {
    00127         destroy();
    00128 }
    00129
    00131
    00132 String& String::operator=(const String& rhs)
    00133 {
    00134         return assign(rhs);
    00135 }
    00136
    00138
    00139 String& String::operator=(const char * s)
    00140 {
    00141         return assign(s);
    00142 }
    00143
    00145
    00146 String& String::operator=(char c)
    00147 {
    00148         return assign(1, c);
    00149 }
    00150
    00152
    00153 BaseModelObject * String::duplicate() const
    00154 {
    00155         return new String(*this);
    00156 }
    00157
    00159
    00160 bool String::operator ==(const String &rhs) const
    00161 {
    00162         return compare(rhs) == 0;
    00163 }
    00164
    00166
    00167 bool String::operator ==(const char * rhs) const
    00168 {
    00169         return compare(rhs) == 0;
    00170 }
    00171
    00173
    00174 bool String::operator !=(const String &rhs) const
    00175 {
    00176         return compare(rhs) != 0;
    00177 }
    00178
    00180
    00181 bool String::operator !=(const char * rhs) const
    00182 {
    00183         return compare(rhs) != 0;
    00184 }
    00185
    00187
    00188 //String::iterator String::begin()
    00189 //{
    00190 //}
    00191
    00193
    00194 //String::const_iterator String::begin() const
    00195 //{
    00196 //}
    00197
    00199
    00200 //String::iterator String::end()
    00201 //{
    00202 //}
    00203
    00205
    00206 //String::const_iterator String::end() const
    00207 //{
    00208 //}
    00209
    00211
    00212 //String::reverse_iterator String::rbegin()
    00213 //{
    00214 //}
    00215
    00217
    00218 //String::const_reverse_iterator String::rbegin() const
    00219 //{
    00220 //}
    00221
    00223
    00224 //String::reverse_iterator String::rend()
    00225 //{
    00226 //}
    00227
    00229
    00230 //String::const_reverse_iterator String::rend() const
    00231 //{
    00232 //}
    00233
    00235
    00236 String::reference String::at(String::size_type pos)
    00237 {
    00238         if(pos >= 0 && pos < curSize)
    00239                 return array[pos];
    00240         else{
    00241                 char buf[80];
    00242
    00243                 sprintf(buf, "Error, string array bounds out of range: %d not in [0-%d]\n",
    00244                         pos, curSize-1);
    00245
    00246                 fprintf(stderr, "%s", buf);
    00247                 if(array){
    00248                         fprintf(stderr, "%s", buf);
    00249                         fprintf(stderr, "String: %s", array);
    00250                 }
    00251
    00252                 throw out_of_range(buf);
    00253                 return array[curSize];
    00254         }
    00255 }
    00256
    00258
    00259 String::const_reference String::at(String::size_type pos) const
    00260 {
    00261         if(pos >= 0 && pos < curSize)
    00262                 return array[pos];
    00263         else{
    00264                 char buf[80];
    00265
    00266                 sprintf(buf, "Error, string array bounds out of range: %d not in [0-%d]\n",
    00267                         pos, curSize);
    00268
    00269                 fprintf(stderr, "%s", buf);
    00270                 if(array){
    00271                         fprintf(stderr, "String: %s", array);
    00272                 }
    00273
    00274                 throw out_of_range(buf);
    00275         }
    00276 }
    00277
    00279
    00280 String::reference String::operator[](String::size_type pos)
    00281 {
    00282         return at(pos);
    00283 }
    00284
    00286
    00287 String::const_reference String::operator[](String::size_type pos) const
    00288 {
    00289         return at(pos);
    00290 }
    00291
    00293
    00294 const char * String::c_str() const
    00295 {
    00296         return array;
    00297 }
    00298
    00300
    00301 const char * String::data() const
    00302 {
    00303         return array;
    00304 }
    00305
    00307
    00308 String::size_type String::length() const
    00309 {
    00310         return curSize;
    00311 }
    00312
    00314
    00315 String::size_type String::size() const
    00316 {
    00317         return curSize;
    00318 }
    00319
    00321
    00322 String::size_type String::max_size() const
    00323 {
    00324         return INT_MAX;
    00325 }
    00326
    00328
    00329 void String::resize(String::size_type n, char c)
    00330 {
    00331         if(n < 0)
    00332                 n = 0;
    00333         if(n == curSize){
    00334                 return;
    00335         }else if(n < curSize){
    00336                 curSize = n;
    00337                 array[curSize] = '\0';
    00338                 return;
    00339         } // n > size
    00340         if(n + 1 >= maxSize){
    00341                 if(FAILED(grow(n + 1))){
    00342                         return;
    00343                 }
    00344         }
    00345         while(curSize < n)
    00346                 array[curSize++] = c;
    00347         array[curSize] = '\0';
    00348 }
    00349
    00351
    00352 String::size_type String::capacity() const
    00353 {
    00354         return maxSize - 1;
    00355 }
    00356
    00358
    00359 void String::reserve(String::size_type n)
    00360 {
    00361         if(n < 0)
    00362                 n = 0;
    00363         if(n + 1 >= maxSize){
    00364                 if(FAILED(grow(n + 1))){
    00365                         return;
    00366                 }
    00367                 // in case the array is just now being allocated
    00368                 array[curSize] = '\0';
    00369         }
    00370 }
    00371
    00373
    00374 bool String::empty() const
    00375 {
    00376         return curSize == 0;
    00377 }
    00378
    00380
    00381 String& String::append(const String& str)
    00382 {
    00383         return append(str.array, str.curSize);
    00384 }
    00385
    00387
    00388 String& String::append(const String& str, String::size_type pos, String::size_type n)
    00389 {
    00390         if(n == npos)
    00391                 n = str.curSize - pos;
    00392         else if(pos + n > str.curSize){
    00393                 n = str.curSize - pos;
    00394         }
    00395         if(n <= 0)
    00396                 return *this;
    00397
    00398         if(pos < 0 || pos > str.curSize)
    00399                 return *this;
    00400
    00401         return append(str.array + pos, n);
    00402 }
    00403
    00405
    00406 String& String::append(const char * s, String::size_type n)
    00407 {
    00408         if(n < 0)
    00409                 n = 0;
    00410         if(curSize + n + 1 >= maxSize){
    00411                 if(FAILED(grow(curSize + n + 1))){
    00412                         return *this;
    00413                 }
    00414         }
    00415         strncpy(array + curSize, s, n);
    00416         curSize += n;
    00417         array[curSize] = '\0';
    00418         return *this;
    00419 }
    00420
    00422
    00423 String& String::append(const char * s)
    00424 {
    00425         return append(s, strlen(s));
    00426 }
    00427
    00429
    00430 String& String::append(String::size_type n, char c)
    00431 {
    00432         if(curSize + n + 1 >= maxSize){
    00433                 if(FAILED(grow(curSize + n + 1))){
    00434                         return *this;
    00435                 }
    00436         }
    00437         while(n > 0){
    00438                 array[curSize++] = c;
    00439                 n--;
    00440         }
    00441         array[curSize] = '\0';
    00442         return *this;
    00443 }
    00444
    00446
    00447 //String& String::append(String::const_iterator first, String::const_iterator last)
    00448 //{
    00449 //}
    00450
    00452
    00453 String& String::assign(const String& str)
    00454 {
    00455         return assign(str.array, str.curSize);
    00456 }
    00457
    00459
    00460 String& String::assign(const String& str, String::size_type pos, String::size_type n)
    00461 {
    00462         if(n == npos)
    00463                 n = str.curSize - pos;
    00464         else if(pos + n > str.curSize){
    00465                 n = str.curSize - pos;
    00466         }
    00467         if(n <= 0)
    00468                 return *this;
    00469
    00470         if(pos < 0 || pos > str.curSize)
    00471                 return *this;
    00472
    00473         return assign(str.array + pos, n);
    00474 }
    00475
    00477
    00478 String& String::assign(const char * s, String::size_type n)
    00479 {
    00480         curSize = 0;
    00481
    00482         if(n < 0)
    00483                 n = 0;
    00484
    00485         if(n + 1 >= maxSize){
    00486                 if(FAILED(grow(n + 1))){
    00487                         return *this;
    00488                 }
    00489         }
    00490         strncpy(array, s, n);
    00491         curSize = n;
    00492         array[curSize] = '\0';
    00493         return *this;
    00494 }
    00495
    00497
    00498 String& String::assign(const char * s)
    00499 {
    00500         return assign(s, strlen(s));
    00501 }
    00502
    00504
    00505 String& String::assign(String::size_type n, char c)
    00506 {
    00507         curSize = 0;
    00508
    00509         if(n + 1 >= maxSize){
    00510                 if(FAILED(grow(n + 1))){
    00511                         return *this;
    00512                 }
    00513         }
    00514         while(n > 0){
    00515                 array[curSize++] = c;
    00516                 n--;
    00517         }
    00518         array[curSize] = '\0';
    00519         return *this;
    00520 }
    00521
    00523
    00524 //String& String::assign(String::const_iterator first, String::const_iterator last)
    00525 //{
    00526 //}
    00527
    00529
    00530 String& String::insert(String::size_type p0, const String& str)
    00531 {
    00532         return insert(p0, str.array, str.curSize);
    00533 }
    00534
    00536
    00537 String& String::insert(String::size_type p0, const String& str,
    00538                                            String::size_type pos, String::size_type n)
    00539 {
    00540         if(n == npos)
    00541                 n = str.curSize - pos;
    00542         else if(pos + n > str.curSize){
    00543                 n = str.curSize - pos;
    00544         }
    00545         if(n <= 0)
    00546                 return *this;
    00547
    00548         if(pos < 0 || pos > str.curSize)
    00549                 return *this;
    00550
    00551         return insert(p0, str.array + pos, n);
    00552 }
    00553
    00555
    00556 String& String::insert(String::size_type p0, const char * s, String::size_type n)
    00557 {
    00558         if(p0 == npos || p0 == curSize){
    00559                 return append(s, n);
    00560         }else if(p0 < 0){
    00561                 fprintf(stderr, "Error, insertion point is before string: %d\n", p0);
    00562                 return *this;
    00563         }else if(p0 > curSize){
    00564                 fprintf(stderr, "Error, insertion point is after string: %d not in [0-%d]\n",
    00565                         p0, curSize);
    00566                 return *this;
    00567         }
    00568
    00569         if(n < 0)
    00570                 n = 0;
    00571         if(curSize + n + 1 >= maxSize){
    00572                 if(FAILED(grow(curSize + n + 1))){
    00573                         return *this;
    00574                 }
    00575         }
    00576
    00577         memmove(array + n + p0, array + p0, curSize - p0);
    00578         strncpy(array + p0, s, n);
    00579         curSize += n;
    00580         array[curSize] = '\0';
    00581         return *this;
    00582 }
    00583
    00585
    00586 String& String::insert(String::size_type p0, const char * s)
    00587 {
    00588         return insert(p0, s, strlen(s));
    00589 }
    00590
    00592
    00593 String& String::insert(String::size_type p0, String::size_type n, char c)
    00594 {
    00595         if(p0 == npos || p0 == curSize){
    00596                 return append(n, c);
    00597         }else if(p0 < 0){
    00598                 fprintf(stderr, "Error, insertion point is before string: %d\n", p0);
    00599                 return *this;
    00600         }else if(p0 > curSize){
    00601                 fprintf(stderr, "Error, insertion point is after string: %d not in [0-%d]\n",
    00602                         p0, curSize);
    00603                 return *this;
    00604         }
    00605
    00606         if(curSize + n + 1 >= maxSize){
    00607                 if(FAILED(grow(curSize + n + 1))){
    00608                         return *this;
    00609                 }
    00610         }
    00611         memmove(array + n + p0, array + p0, curSize - p0);
    00612         while(n > 0){
    00613                 array[curSize++] = c;
    00614                 n--;
    00615         }
    00616         array[curSize] = '\0';
    00617         return *this;
    00618 }
    00619
    00621
    00622 //String::iterator String::insert(String::iterator it, char c)
    00623 //{
    00624 //}
    00625
    00627
    00628 //void String::insert(String::iterator it, String::size_type n, char c)
    00629 //{
    00630 //}
    00631
    00633
    00634 //void String::insert(String::iterator it, String::const_iterator first, String::const_iterator last)
    00635 //{
    00636 //}
    00637
    00639
    00640 String& String::erase(String::size_type p0, String::size_type n)
    00641 {
    00642         if(p0 == npos){
    00643                 p0 = curSize;
    00644         }else if(p0 < 0){
    00645                 if(n != npos)
    00646                         n += p0;
    00647                 p0 = 0;
    00648         }
    00649
    00650         if(n == npos)
    00651                 n = curSize;
    00652
    00653         if(p0 == curSize){
    00654                 // if we're deleteing at the end, we're already done (nothing to delete)
    00655                 return *this;
    00656         }else if(p0 > curSize){
    00657                 fprintf(stderr, "Error, deletion start point is after string: %d not in [0-%d]\n",
    00658                         p0, curSize);
    00659                 return *this;
    00660         }
    00661
    00662         if(p0 + n >= curSize){
    00663                 // delete everything after p0
    00664                 curSize = p0;
    00665                 array[curSize] = '\0';
    00666                 return *this;
    00667         }
    00668         if(n <= 0){ // nothing to do
    00669                 return *this;
    00670         }
    00671
    00672         memmove(array + p0, array + p0 + n, curSize - n - p0);
    00673         curSize -= n;
    00674         array[curSize] = '\0';
    00675         return *this;
    00676 }
    00677
    00679
    00680 //String::iterator String::erase(String::iterator it)
    00681 //{
    00682 //}
    00683
    00685
    00686 //String::iterator String::erase(String::iterator first, String::iterator last)
    00687 //{
    00688 //}
    00689
    00691
    00692 String& String::replace(String::size_type p0, String::size_type n0, const String& str)
    00693 {
    00694         return replace(p0, n0, str.array, str.curSize);
    00695 }
    00696
    00698
    00699 String& String::replace(String::size_type p0, String::size_type n0, const String& str,
    00700                                                 String::size_type pos, String::size_type n)
    00701 {
    00702         if(n == npos)
    00703                 n = str.curSize - pos;
    00704         else if(pos + n > str.curSize){
    00705                 n = str.curSize - pos;
    00706         }
    00707         if(n <= 0)
    00708                 return erase(p0, n0);
    00709
    00710         if(pos < 0 || pos > str.curSize)
    00711                 return erase(p0, n0);
    00712
    00713         return replace(p0, n0, str.array + pos, n);
    00714 }
    00715
    00717
    00718 String& String::replace(String::size_type p0, String::size_type n0, const char * s,
    00719                                                 String::size_type n)
    00720 {
    00721         // we could be more efficient here and overwite the first min(n0, str.curSize)
    00722         // caracters and then erase/insert the rest
    00723         erase(p0, n0);
    00724         return insert(p0, s, n);
    00725 }
    00726
    00728
    00729 String& String::replace(String::size_type p0, String::size_type n0, const char * s)
    00730 {
    00731         return replace(p0, n0, s, strlen(s));
    00732 }
    00733
    00735
    00736 String& String::replace(String::size_type p0, String::size_type n0, String::size_type n, char c)
    00737 {
    00738         // we could be more efficient here and overwite the first min(n0, str.curSize)
    00739         // caracters and then erase/insert the rest
    00740         erase(p0, n0);
    00741         return insert(p0, n, c);
    00742 }
    00743
    00745
    00746 //String& String::replace(String::iterator first0, String::iterator last0, const String& str)
    00747 //{
    00748 //}
    00749
    00751
    00752 //String& String::replace(String::iterator first0, String::iterator last0, const char * s, String::size_type n)
    00753 //{
    00754 //}
    00755
    00757
    00758 //String& String::replace(String::iterator first0, String::iterator last0, const char * s)
    00759 //{
    00760 //}
    00761
    00763
    00764 //String& String::replace(String::iterator first0, String::iterator last0, String::size_type n, char c)
    00765 //{
    00766 //}
    00767
    00769
    00770 //String& String::replace(String::iterator first0, String::iterator last0, String::const_iterator first, String::const_iterator last)
    00771 //{
    00772 //}
    00773
    00775
    00776 String::size_type String::copy(char * s, String::size_type n, String::size_type pos) const
    00777 {
    00778         if(pos < 0 || pos > curSize){
    00779                 fprintf(stderr, "Error, start position out of range: %d not in [0-%d]\n",
    00780                         pos, curSize);
    00781                 return 0;
    00782         }
    00783         if(n > curSize - pos + 1)
    00784                 n = curSize - pos + 1;
    00785         strncpy(s, array + pos, n - 1);
    00786         // null terminate
    00787         s[n - 1] = '\0';
    00788         // return number of characters copied, including '\0'
    00789         return n;
    00790 }
    00791
    00793
    00794 void String::swap(String& str)
    00795 {
    00796         char * sTmp = array;
    00797         array = str.array;
    00798         str.array = sTmp;
    00799
    00800         size_type iTmp = curSize;
    00801         curSize = str.curSize;
    00802         str.curSize = iTmp;
    00803
    00804         iTmp = maxSize;
    00805         maxSize = str.maxSize;
    00806         str.maxSize = iTmp;
    00807 }
    00808
    00810
    00811 String::size_type String::find(const String& str, String::size_type pos) const
    00812 {
    00813         return find(str.array, pos, str.curSize);
    00814 }
    00815
    00817
    00818 String::size_type String::find(const char * s, String::size_type pos,
    00819                                                            String::size_type n) const
    00820 {
    00821         if(pos < 0 || pos > curSize){
    00822                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    00823                         pos, curSize);
    00824                 return npos;
    00825         }
    00826
    00827         //naive string-matching algorithm O((curSize - n + 1) * n) time
    00828         //but O(1) space
    00829         //Other options:
    00830         // Knuth-Morris-Pratt: O(curSize + n) time, O(n) space  (faster on average)
    00831         // Boyer-Moore:        O((curSize - n + 1) * n + 256) time, O(n + 256) space
    00832         //       (fastest on average, for longer search strings)
    00833         size_type i, j;
    00834         char const * atrace = array + pos;
    00835
    00836         for(j = 0; j <= curSize - pos - n; j++, atrace++){
    00837                 for(i = 0; i < n; i++){
    00838                         if(*(s + i) != *(atrace + i))
    00839                                 break;
    00840                 }
    00841                 if(i == n)
    00842                         return j;
    00843         }
    00844         return npos;
    00845 }
    00846
    00848
    00849 String::size_type String::find(const char * s, String::size_type pos) const
    00850 {
    00851         return find(s, pos, strlen(s));
    00852 }
    00853
    00855
    00856 String::size_type String::find(char c, String::size_type pos) const
    00857 {
    00858         if(pos < 0 || pos > curSize){
    00859                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    00860                         pos, curSize);
    00861                 return npos;
    00862         }
    00863
    00864         size_type j;
    00865         char const * atrace = array + pos;
    00866
    00867         for(j = 0; j < curSize - pos; j++, atrace++){
    00868                 if(c == *atrace)
    00869                         return j;
    00870         }
    00871         return npos;
    00872 }
    00873
    00875
    00876 String::size_type String::rfind(const String& str, String::size_type pos) const
    00877 {
    00878         return rfind(str.array, pos, str.curSize);
    00879 }
    00880
    00882
    00883 String::size_type String::rfind(const char * s, String::size_type pos, String::size_type n) const
    00884 {
    00885         if(pos == npos){
    00886                 pos = curSize;
    00887         }else if(pos < 0 || pos > curSize){
    00888                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    00889                         pos, curSize);
    00890                 return npos;
    00891         }
    00892
    00893         // we aren't going to find anything before n characters
    00894         // before the end of the list
    00895         if(pos > curSize - n)
    00896                 pos = curSize - n;
    00897
    00898         //naive string-matching algorithm O((curSize - n + 1) * n) time
    00899         //but O(1) space
    00900         //Other options:
    00901         // Knuth-Morris-Pratt: O(curSize + n) time, O(n) space  (faster on average)
    00902         // Boyer-Moore:        O((curSize - n + 1) * n + 256) time, O(n + 256) space
    00903         //       (fastest on average, for longer search strings)
    00904         size_type i, j;
    00905         char const * atrace = array + pos;
    00906
    00907         for(j = pos ; j >= 0; j--, atrace--){
    00908                 for(i = 0; i < n; i++){
    00909                         if(*(s + i) != *(atrace + i))
    00910                                 break;
    00911                 }
    00912                 if(i == n)
    00913                         return j;
    00914         }
    00915         return npos;
    00916 }
    00917
    00919
    00920 String::size_type String::rfind(const char * s, String::size_type pos) const
    00921 {
    00922         return rfind(s, pos, strlen(s));
    00923 }
    00924
    00926
    00927 String::size_type String::rfind(char c, String::size_type pos) const
    00928 {
    00929         if(pos == npos){
    00930                 pos = curSize;
    00931         }else if(pos < 0 || pos > curSize){
    00932                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    00933                         pos, curSize);
    00934                 return npos;
    00935         }
    00936
    00937         // we aren't going to find anything before n characters
    00938         // before the end of the list
    00939         if(pos > curSize - 1)
    00940                 pos = curSize - 1;
    00941
    00942         //naive string-matching algorithm O((curSize - n + 1) * n) time
    00943         //but O(1) space
    00944         //Other options:
    00945         // Knuth-Morris-Pratt: O(curSize + n) time, O(n) space  (faster on average)
    00946         // Boyer-Moore:        O((curSize - n + 1) * n + 256) time, O(n + 256) space
    00947         //       (fastest on average, for longer search strings)
    00948         size_type j;
    00949         char const * atrace = array + pos;
    00950
    00951         for(j = pos ; j >= 0; j--, atrace--){
    00952                 if(c == *(atrace))
    00953                         return j;
    00954         }
    00955         return npos;
    00956 }
    00957
    00959
    00960 String::size_type String::find_first_of(const String& str, String::size_type pos) const
    00961 {
    00962         return find_first_of(str.array, pos, str.curSize);
    00963 }
    00964
    00966
    00967 String::size_type String::find_first_of(const char * s, String::size_type pos, String::size_type n) const
    00968 {
    00969         if(pos < 0 || pos > curSize){
    00970                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    00971                         pos, curSize);
    00972                 return npos;
    00973         }
    00974
    00975         size_type i, j;
    00976         char const * atrace = array + pos;
    00977
    00978         for(j = 0; j <= curSize - pos - n; j++, atrace++){
    00979                 for(i = 0; i < n; i++){
    00980                         if(*(s + i) == *atrace)
    00981                                 return j;
    00982                 }
    00983         }
    00984         return npos;
    00985 }
    00986
    00988
    00989 String::size_type String::find_first_of(const char * s, String::size_type pos) const
    00990 {
    00991         return find_first_of(s, pos, strlen(s));
    00992 }
    00993
    00995
    00996 String::size_type String::find_first_of(char c, String::size_type pos) const
    00997 {
    00998         if(pos < 0 || pos > curSize){
    00999                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01000                         pos, curSize);
    01001                 return npos;
    01002         }
    01003
    01004         size_type j;
    01005         char const * atrace = array + pos;
    01006
    01007         for(j = 0; j <= curSize - pos - 1; j++, atrace++){
    01008                 if(c == *atrace)
    01009                         return j;
    01010         }
    01011         return npos;
    01012 }
    01013
    01015
    01016 String::size_type String::find_last_of(const String& str, String::size_type pos) const
    01017 {
    01018         return find_last_of(str.array, pos, str.curSize);
    01019 }
    01020
    01022
    01023 String::size_type String::find_last_of(const char * s, String::size_type pos, String::size_type n) const
    01024 {
    01025         if(pos == npos){
    01026                 pos = curSize;
    01027         }else if(pos < 0 || pos > curSize){
    01028                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01029                         pos, curSize);
    01030                 return npos;
    01031         }
    01032
    01033         // we aren't going to find anything before n characters
    01034         // before the end of the list
    01035         if(pos > curSize - 1)
    01036                 pos = curSize - 1;
    01037
    01038         size_type i, j;
    01039         char const * atrace = array + curSize - pos;
    01040
    01041         for(j = curSize - pos ; j >= 0; j--, atrace--){
    01042                 for(i = 0; i < n; i++){
    01043                         if(*(s + i) == *atrace)
    01044                                 return j;
    01045                 }
    01046         }
    01047         return npos;
    01048 }
    01049
    01051
    01052 String::size_type String::find_last_of(const char * s, String::size_type pos) const
    01053 {
    01054         return find_last_of(s, pos, strlen(s));
    01055 }
    01056
    01058
    01059 String::size_type String::find_last_of(char c, String::size_type pos) const
    01060 {
    01061         if(pos == npos){
    01062                 pos = curSize;
    01063         }else if(pos < 0 || pos > curSize){
    01064                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01065                         pos, curSize);
    01066                 return npos;
    01067         }
    01068
    01069         // we aren't going to find anything before n characters
    01070         // before the end of the list
    01071         if(pos > curSize - 1)
    01072                 pos = curSize - 1;
    01073
    01074         size_type j;
    01075         char const * atrace = array + curSize - pos;
    01076
    01077         for(j = curSize - pos ; j >= 0; j--, atrace--){
    01078                 if(c == *atrace)
    01079                         return j;
    01080         }
    01081         return npos;
    01082 }
    01083
    01085
    01086 String::size_type String::find_first_not_of(const String& str, String::size_type pos) const
    01087 {
    01088         return find_first_not_of(str.array, pos, str.curSize);
    01089 }
    01090
    01092
    01093 String::size_type String::find_first_not_of(const char * s, String::size_type pos, String::size_type n) const
    01094 {
    01095         if(pos < 0 || pos > curSize){
    01096                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01097                         pos, curSize);
    01098                 return npos;
    01099         }
    01100
    01101         size_type i, j;
    01102         char const * atrace = array + pos;
    01103
    01104         for(j = 0; j <= curSize - pos - n; j++, atrace++){
    01105                 for(i = 0; i < n; i++){
    01106                         if(*(s + i) == *atrace)
    01107                                 break;
    01108                 }
    01109                 if(i != n)
    01110                         return j;
    01111         }
    01112         return npos;
    01113 }
    01114
    01116
    01117 String::size_type String::find_first_not_of(const char * s, String::size_type pos) const
    01118 {
    01119         return find_first_not_of(s, pos, strlen(s));
    01120 }
    01121
    01123
    01124 String::size_type String::find_first_not_of(char c, String::size_type pos) const
    01125 {
    01126         if(pos < 0 || pos > curSize){
    01127                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01128                         pos, curSize);
    01129                 return npos;
    01130         }
    01131
    01132         size_type j;
    01133         char const * atrace = array + pos;
    01134
    01135         for(j = 0; j <= curSize - pos - 1; j++, atrace++){
    01136                 if(c != *atrace)
    01137                         return j;
    01138         }
    01139         return npos;
    01140 }
    01141
    01143
    01144 String::size_type String::find_last_not_of(const String& str, String::size_type pos) const
    01145 {
    01146         return find_last_not_of(str.array, pos, str.curSize);
    01147 }
    01148
    01150
    01151 String::size_type String::find_last_not_of(const char * s, String::size_type pos, String::size_type n) const
    01152 {
    01153         if(pos == npos){
    01154                 pos = curSize;
    01155         }else if(pos < 0 || pos > curSize){
    01156                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01157                         pos, curSize);
    01158                 return npos;
    01159         }
    01160
    01161         // we aren't going to find anything before n characters
    01162         // before the end of the list
    01163         if(pos > curSize - 1)
    01164                 pos = curSize - 1;
    01165
    01166         size_type i, j;
    01167         char const * atrace = array + curSize - pos;
    01168
    01169         for(j = curSize - pos ; j >= 0; j--, atrace--){
    01170                 for(i = 0; i < n; i++){
    01171                         if(*(s + i) == *atrace)
    01172                                 break;
    01173                 }
    01174                 if(i != n)
    01175                         return j;
    01176         }
    01177         return npos;
    01178 }
    01179
    01181
    01182 String::size_type String::find_last_not_of(const char * s, String::size_type pos) const
    01183 {
    01184         return find_last_not_of(s, pos, strlen(s));
    01185 }
    01186
    01188
    01189 String::size_type String::find_last_not_of(char c, String::size_type pos) const
    01190 {
    01191         if(pos == npos){
    01192                 pos = curSize;
    01193         }else if(pos < 0 || pos > curSize){
    01194                 fprintf(stderr, "Find position out of range: %d not in [0-%d]\n",
    01195                         pos, curSize);
    01196                 return npos;
    01197         }
    01198
    01199         // we aren't going to find anything before n characters
    01200         // before the end of the list
    01201         if(pos > curSize - 1)
    01202                 pos = curSize - 1;
    01203
    01204         size_type j;
    01205         char const * atrace = array + curSize - pos;
    01206
    01207         for(j = curSize - pos ; j >= 0; j--, atrace--){
    01208                 if(c != *atrace)
    01209                         return j;
    01210         }
    01211         return npos;
    01212 }
    01213
    01215
    01216 String String::substr(String::size_type pos, String::size_type n) const
    01217 {
    01218         return String(*this, pos, n);
    01219 }
    01220
    01222
    01223 int String::compare(const String& str) const
    01224 {
    01225         return strcmp(array, str.array);
    01226 }
    01227
    01229
    01230 int String::compare(String::size_type p0, String::size_type n0, const String& str)
    01231 {
    01232         return compare(p0, n0, str.array, 0, str.curSize);
    01233 }
    01234
    01236
    01237 int String::compare(String::size_type p0, String::size_type n0, const String& str,
    01238                                         String::size_type pos, String::size_type n)
    01239 {
    01240         if(pos < 0 || pos > str.curSize){
    01241                 fprintf(stderr, "Error, position not in range for comparison: %d not in [0-%d]\n",
    01242                         pos, str.curSize);
    01243                 throw out_of_range("Position offset out of bounds for comparison\n");
    01244                 return 0;
    01245         }
    01246
    01247         if(n == npos)
    01248                 n = str.curSize - pos;
    01249         else if(pos + n > str.curSize){
    01250                 n = str.curSize - pos;
    01251         }
    01252
    01253         if(p0 < 0 || p0 > curSize){
    01254                 fprintf(stderr, "Error, position not in range for comparison: %d not in [0-%d]\n",
    01255                         p0, curSize);
    01256                 throw out_of_range("Position offset out of bounds for comparison\n");
    01257                 return 0;
    01258         }
    01259
    01260         if(n0 == npos)
    01261                 n0 = curSize - p0;
    01262         else if(p0 + n0 > curSize){
    01263                 n0 = curSize - p0;
    01264         }
    01265
    01266         if(n <= 0){
    01267                 if(n0 <= 0)
    01268                         // two zero length segments are always equal
    01269                         return 0;
    01270         }
    01271
    01272         size_type np;
    01273         if(n0 < n)
    01274                 np = n0;
    01275         else
    01276                 np = n;
    01277
    01278         int res = strncmp(array + p0, str.array + pos, np);
    01279         if(res != 0)
    01280                 return res;
    01281         else if(n0 < n)
    01282                 return -1;
    01283         else if(n0 > n)
    01284                 return 1;
    01285         else
    01286                 return 0;
    01287 }
    01288
    01290
    01291 int String::compare(const char * s) const
    01292 {
    01293         return strcmp(array, s);
    01294 }
    01295
    01297
    01298 int String::compare(String::size_type p0, String::size_type n0, const char * s) const
    01299 {
    01300         size_type n;
    01301
    01302         n = strlen(s);
    01303
    01304         if(p0 < 0 || p0 > curSize){
    01305                 fprintf(stderr, "Error, position not in range for comparison: %d not in [0-%d]\n",
    01306                         p0, curSize);
    01307                 throw out_of_range("Position offset out of bounds for comparison\n");
    01308                 return 0;
    01309         }
    01310
    01311         if(n0 == npos)
    01312                 n0 = curSize - p0;
    01313         else if(p0 + n0 > curSize){
    01314                 n0 = curSize - p0;
    01315         }
    01316
    01317         if(n <= 0){
    01318                 if(n0 <= 0)
    01319                         // two zero length segments are always equal
    01320                         return 0;
    01321         }
    01322
    01323         size_type np;
    01324         if(n0 < n)
    01325                 np = n0;
    01326         else
    01327                 np = n;
    01328
    01329         int res = strncmp(array + p0, s, np);
    01330         if(res != 0)
    01331                 return res;
    01332         else if(n0 < n)
    01333                 return -1;
    01334         else if(n0 > n)
    01335                 return 1;
    01336         else
    01337                 return 0;
    01338 }
    01339
    01341
    01342 int String::compare(String::size_type p0, String::size_type n0, const char * s, String::size_type pos) const
    01343 {
    01344         return compare(p0, n0, s + pos);
    01345 }
    01346
    01348
    01349 #ifndef EMBEDDED
    01350
    01351 void String::print(ostream &out) const
    01352 {
    01353         // we ouptut only if we're not ""
    01354         if(array)
    01355                 out << array;
    01356 }
    01357
    01358 #endif
    01359
    01361
    01362 void String::destroy()
    01363 {
    01364         if(array){
    01365                 free(array);
    01366                 array = NULL;
    01367         }
    01368         curSize = 0;
    01369         maxSize = 0;
    01370 }
    01371
    01373
    01374 int String::grow(String::size_type newMaxSize)
    01375 {
    01376         char * newArray;
    01377
    01378         // make sure we grow to a proper size (handle 0 special case)
    01379         if(newMaxSize == 0)
    01380                 newMaxSize = 1;
    01381
    01382         // create the replacement array
    01383         assert( array != (char *)0xcccccccc );
    01384         newArray = (char *) realloc(array, newMaxSize * sizeof(char));
    01385         if(NULL != newArray)
    01386         {
    01387                 array = newArray;
    01388                 maxSize = newMaxSize;
    01389                 return 0;
    01390         }else{
    01391                 // allocation failed, return an error
    01392                 fprintf(stderr, "Failed to grow the string to %d elements", newMaxSize);
    01393                 return 1;
    01394         }
    01395 }
    01396
    01398
    01399 int String::shrink()
    01400 {
    01401         char * newArray;
    01402         size_type newMaxSize;
    01403
    01404         // make sure we dont shrink below 2 (we could allow down to 1)
    01405         if(maxSize > 2)
    01406                 newMaxSize = maxSize >> 1;
    01407         else
    01408                 return 0;
    01409
    01410         // allocate the new smaller array
    01411         assert( array != (char *)0xcccccccc );
    01412         newArray = (char *) realloc(array, newMaxSize * sizeof(char));
    01413         if(NULL != newArray)
    01414         {
    01415                 array = newArray;
    01416                 maxSize = newMaxSize;
    01417                 return 0;
    01418         }else{
    01419                 // couldn't create the smaller array (no big deal)
    01420                 fprintf(stderr, "Warning, failed to shrink the string to %d elements", newMaxSize);
    01421                 return -1;
    01422         }
    01423 }
    01424
    01426
    01427 String::size_type String::trimLeft( void )
    01428 {
    01429         size_type i;
    01430         for ( i=0; i<curSize && ( array[ i ] == ' ' || array[ i ] == '\t' ); i++ ) {}
    01431         erase( 0, i ); // erase(p0,n) removes n chars starting at pos p0
    01432         return i;
    01433 }
    01434
    01436
    01437 String::size_type String::trimRight( void )
    01438 {
    01439         size_type i;
    01440         size_type origSize = curSize;
    01441         for ( i=curSize-1; i>=0 && ( array[ i ] == ' ' || array[ i ] == '\t' ); i-- ) {}
    01442         erase( i+1 ); // erase(p0,n) removes n chars starting at pos p0
    01443         return origSize - curSize;
    01444 }
    01445
    01447
    01448 String::size_type String::trim( void )
    01449 {
    01450         return trimLeft() + trimRight();
    01451 }
    01452
    01454
    01455 /*static*/ String
    01456 String::format(const char *formatStr, ...)
    01457 {
    01458         const int MAX_SIZE = 256;
    01459         char buffer[MAX_SIZE+1] = {0};
    01460         va_list ap;
    01461
    01462         va_start(ap, formatStr);
    01463 #ifdef _MSC_VER // VC++
    01464         _vsnprintf(buffer, MAX_SIZE, formatStr, ap);
    01465 #else // GCC
    01466         vsnprintf(buffer, MAX_SIZE, formatStr, ap);
    01467 #endif
    01468         va_end(ap);
    01469         buffer[MAX_SIZE] = 0;  // Make doubly sure buffer is 0-terminated.
    01470
    01471         return String(buffer);
    01472 }