src/common/string.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        string.cpp
   3 // Purpose:     wxString class
   4 // Author:      Vadim Zeitlin, Ryan Norton
   5 // Modified by:
   6 // Created:     29/01/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
   9 //              (c) 2004 Ryan Norton <wxprojects@comcast.net>
  10 // Licence:     wxWindows licence
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
  14   #pragma implementation "string.h"
  15 #endif
  16
  17 /*
  18  * About ref counting:
  19  *  1) all empty strings use g_strEmpty, nRefs = -1 (set in Init())
  20  *  2) AllocBuffer() sets nRefs to 1, Lock() increments it by one
  21  *  3) Unlock() decrements nRefs and frees memory if it goes to 0
  22  */
  23
  24 // ===========================================================================
  25 // headers, declarations, constants
  26 // ===========================================================================
  27
  28 // For compilers that support precompilation, includes "wx.h".
  29 #include "wx/wxprec.h"
  30
  31 #ifdef __BORLANDC__
  32   #pragma hdrstop
  33 #endif
  34
  35 #ifndef WX_PRECOMP
  36   #include "wx/defs.h"
  37   #include "wx/string.h"
  38   #include "wx/intl.h"
  39   #include "wx/thread.h"
  40 #endif
  41
  42 #include <ctype.h>
  43 #include <string.h>
  44 #include <stdlib.h>
  45 #include <errno.h>
  46
  47 #ifdef __SALFORDC__
  48   #include <clib.h>
  49 #endif
  50
  51 // allocating extra space for each string consumes more memory but speeds up
  52 // the concatenation operations (nLen is the current string's length)
  53 // NB: EXTRA_ALLOC must be >= 0!
  54 #define EXTRA_ALLOC       (19 - nLen % 16)
  55
  56 // ---------------------------------------------------------------------------
  57 // static class variables definition
  58 // ---------------------------------------------------------------------------
  59
  60 #if !wxUSE_STL
  61   //According to STL _must_ be a -1 size_t
  62   const size_t wxStringBase::npos = (size_t) -1;
  63 #endif
  64
  65 // ----------------------------------------------------------------------------
  66 // static data
  67 // ----------------------------------------------------------------------------
  68
  69 #if wxUSE_STL
  70
  71 extern const wxChar WXDLLIMPEXP_BASE *wxEmptyString = _T("");
  72
  73 #else
  74
  75 // for an empty string, GetStringData() will return this address: this
  76 // structure has the same layout as wxStringData and it's data() method will
  77 // return the empty string (dummy pointer)
  78 static const struct
  79 {
  80   wxStringData data;
  81   wxChar dummy;
  82 } g_strEmpty = { {-1, 0, 0}, wxT('\0') };
  83
  84 // empty C style string: points to 'string data' byte of g_strEmpty
  85 extern const wxChar WXDLLIMPEXP_BASE *wxEmptyString = &g_strEmpty.dummy;
  86
  87 #endif
  88
  89 // ----------------------------------------------------------------------------
  90 // global functions
  91 // ----------------------------------------------------------------------------
  92
  93 #if wxUSE_STD_IOSTREAM
  94
  95 // MS Visual C++ version 5.0 provides the new STL headers as well as the old
  96 // iostream ones.
  97 //
  98 // ATTN: you can _not_ use both of these in the same program!
  99
 100 #include <iostream>
 101
 102 wxSTD istream& operator>>(wxSTD istream& is, wxString& WXUNUSED(str))
 103 {
 104 #if 0
 105   int w = is.width(0);
 106   if ( is.ipfx(0) ) {
 107     streambuf *sb = is.rdbuf();
 108     str.erase();
 109     while ( true ) {
 110       int ch = sb->sbumpc ();
 111       if ( ch == EOF ) {
 112         is.setstate(ios::eofbit);
 113         break;
 114       }
 115       else if ( isspace(ch) ) {
 116         sb->sungetc();
 117         break;
 118       }
 119
 120       str += ch;
 121       if ( --w == 1 )
 122         break;
 123     }
 124   }
 125
 126   is.isfx();
 127   if ( str.length() == 0 )
 128     is.setstate(ios::failbit);
 129 #endif
 130   return is;
 131 }
 132
 133 wxSTD ostream& operator<<(wxSTD ostream& os, const wxString& str)
 134 {
 135   os << str.c_str();
 136   return os;
 137 }
 138
 139 #endif // wxUSE_STD_IOSTREAM
 140
 141 // ----------------------------------------------------------------------------
 142 // private classes
 143 // ----------------------------------------------------------------------------
 144
 145 // this small class is used to gather statistics for performance tuning
 146 //#define WXSTRING_STATISTICS
 147 #ifdef  WXSTRING_STATISTICS
 148   class Averager
 149   {
 150   public:
 151     Averager(const wxChar *sz) { m_sz = sz; m_nTotal = m_nCount = 0; }
 152    ~Averager()
 153    { wxPrintf("wxString: average %s = %f\n", m_sz, ((float)m_nTotal)/m_nCount); }
 154
 155     void Add(size_t n) { m_nTotal += n; m_nCount++; }
 156
 157   private:
 158     size_t m_nCount, m_nTotal;
 159     const wxChar *m_sz;
 160   } g_averageLength("allocation size"),
 161     g_averageSummandLength("summand length"),
 162     g_averageConcatHit("hit probability in concat"),
 163     g_averageInitialLength("initial string length");
 164
 165   #define STATISTICS_ADD(av, val) g_average##av.Add(val)
 166 #else
 167   #define STATISTICS_ADD(av, val)
 168 #endif // WXSTRING_STATISTICS
 169
 170 #if !wxUSE_STL
 171
 172 // ===========================================================================
 173 // wxStringData class deallocation
 174 // ===========================================================================
 175
 176 #if defined(__VISUALC__) && defined(_MT) && !defined(_DLL)
 177 #  pragma message (__FILE__ ": building with Multithreaded non DLL runtime has a performance impact on wxString!")
 178 void wxStringData::Free()
 179 {
 180     free(this);
 181 }
 182 #endif
 183
 184 // ===========================================================================
 185 // wxStringBase
 186 // ===========================================================================
 187
 188 // takes nLength elements of psz starting at nPos
 189 void wxStringBase::InitWith(const wxChar *psz, size_t nPos, size_t nLength)
 190 {
 191   Init();
 192
 193   // if the length is not given, assume the string to be NUL terminated
 194   if ( nLength == npos ) {
 195     wxASSERT_MSG( nPos <= wxStrlen(psz), _T("index out of bounds") );
 196
 197     nLength = wxStrlen(psz + nPos);
 198   }
 199
 200   STATISTICS_ADD(InitialLength, nLength);
 201
 202   if ( nLength > 0 ) {
 203     // trailing '\0' is written in AllocBuffer()
 204     if ( !AllocBuffer(nLength) ) {
 205       wxFAIL_MSG( _T("out of memory in wxStringBase::InitWith") );
 206       return;
 207     }
 208     wxTmemcpy(m_pchData, psz + nPos, nLength);
 209   }
 210 }
 211
 212 // poor man's iterators are "void *" pointers
 213 wxStringBase::wxStringBase(const void *pStart, const void *pEnd)
 214 {
 215   InitWith((const wxChar *)pStart, 0,
 216            (const wxChar *)pEnd - (const wxChar *)pStart);
 217 }
 218
 219 wxStringBase::wxStringBase(size_type n, wxChar ch)
 220 {
 221   Init();
 222   append(n, ch);
 223 }
 224
 225 // ---------------------------------------------------------------------------
 226 // memory allocation
 227 // ---------------------------------------------------------------------------
 228
 229 // allocates memory needed to store a C string of length nLen
 230 bool wxStringBase::AllocBuffer(size_t nLen)
 231 {
 232   // allocating 0 sized buffer doesn't make sense, all empty strings should
 233   // reuse g_strEmpty
 234   wxASSERT( nLen >  0 );
 235
 236   // make sure that we don't overflow
 237   wxASSERT( nLen < (INT_MAX / sizeof(wxChar)) -
 238                    (sizeof(wxStringData) + EXTRA_ALLOC + 1) );
 239
 240   STATISTICS_ADD(Length, nLen);
 241
 242   // allocate memory:
 243   // 1) one extra character for '\0' termination
 244   // 2) sizeof(wxStringData) for housekeeping info
 245   wxStringData* pData = (wxStringData*)
 246     malloc(sizeof(wxStringData) + (nLen + EXTRA_ALLOC + 1)*sizeof(wxChar));
 247
 248   if ( pData == NULL ) {
 249     // allocation failures are handled by the caller
 250     return false;
 251   }
 252
 253   pData->nRefs        = 1;
 254   pData->nDataLength  = nLen;
 255   pData->nAllocLength = nLen + EXTRA_ALLOC;
 256   m_pchData           = pData->data();  // data starts after wxStringData
 257   m_pchData[nLen]     = wxT('\0');
 258   return true;
 259 }
 260
 261 // must be called before changing this string
 262 bool wxStringBase::CopyBeforeWrite()
 263 {
 264   wxStringData* pData = GetStringData();
 265
 266   if ( pData->IsShared() ) {
 267     pData->Unlock();                // memory not freed because shared
 268     size_t nLen = pData->nDataLength;
 269     if ( !AllocBuffer(nLen) ) {
 270       // allocation failures are handled by the caller
 271       return false;
 272     }
 273     wxTmemcpy(m_pchData, pData->data(), nLen);
 274   }
 275
 276   wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
 277
 278   return true;
 279 }
 280
 281 // must be called before replacing contents of this string
 282 bool wxStringBase::AllocBeforeWrite(size_t nLen)
 283 {
 284   wxASSERT( nLen != 0 );  // doesn't make any sense
 285
 286   // must not share string and must have enough space
 287   wxStringData* pData = GetStringData();
 288   if ( pData->IsShared() || pData->IsEmpty() ) {
 289     // can't work with old buffer, get new one
 290     pData->Unlock();
 291     if ( !AllocBuffer(nLen) ) {
 292       // allocation failures are handled by the caller
 293       return false;
 294     }
 295   }
 296   else {
 297     if ( nLen > pData->nAllocLength ) {
 298       // realloc the buffer instead of calling malloc() again, this is more
 299       // efficient
 300       STATISTICS_ADD(Length, nLen);
 301
 302       nLen += EXTRA_ALLOC;
 303
 304       pData = (wxStringData*)
 305           realloc(pData, sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 306
 307       if ( pData == NULL ) {
 308         // allocation failures are handled by the caller
 309         // keep previous data since reallocation failed
 310         return false;
 311       }
 312
 313       pData->nAllocLength = nLen;
 314       m_pchData = pData->data();
 315     }
 316   }
 317
 318   wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
 319
 320   // it doesn't really matter what the string length is as it's going to be
 321   // overwritten later but, for extra safety, set it to 0 for now as we may
 322   // have some junk in m_pchData
 323   GetStringData()->nDataLength = 0;
 324
 325   return true;
 326 }
 327
 328 wxStringBase& wxStringBase::append(size_t n, wxChar ch)
 329 {
 330     size_type len = length();
 331
 332     if ( !Alloc(len + n) || !CopyBeforeWrite() ) {
 333       wxFAIL_MSG( _T("out of memory in wxStringBase::append") );
 334     }
 335     GetStringData()->nDataLength = len + n;
 336     m_pchData[len + n] = '\0';
 337     for ( size_t i = 0; i < n; ++i )
 338         m_pchData[len + i] = ch;
 339     return *this;
 340 }
 341
 342 void wxStringBase::resize(size_t nSize, wxChar ch)
 343 {
 344     size_t len = length();
 345
 346     if ( nSize < len )
 347     {
 348         erase(begin() + nSize, end());
 349     }
 350     else if ( nSize > len )
 351     {
 352         append(nSize - len, ch);
 353     }
 354     //else: we have exactly the specified length, nothing to do
 355 }
 356
 357 // allocate enough memory for nLen characters
 358 bool wxStringBase::Alloc(size_t nLen)
 359 {
 360   wxStringData *pData = GetStringData();
 361   if ( pData->nAllocLength <= nLen ) {
 362     if ( pData->IsEmpty() ) {
 363       nLen += EXTRA_ALLOC;
 364
 365       wxStringData* pData = (wxStringData*)
 366           malloc(sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 367
 368       if ( pData == NULL ) {
 369         // allocation failure handled by caller
 370         return false;
 371       }
 372
 373       pData->nRefs = 1;
 374       pData->nDataLength = 0;
 375       pData->nAllocLength = nLen;
 376       m_pchData = pData->data();  // data starts after wxStringData
 377       m_pchData[0u] = wxT('\0');
 378     }
 379     else if ( pData->IsShared() ) {
 380       pData->Unlock();                // memory not freed because shared
 381       size_t nOldLen = pData->nDataLength;
 382       if ( !AllocBuffer(nLen) ) {
 383         // allocation failure handled by caller
 384         return false;
 385       }
 386       // +1 to copy the terminator, too
 387       memcpy(m_pchData, pData->data(), (nOldLen+1)*sizeof(wxChar));
 388       GetStringData()->nDataLength = nOldLen;
 389     }
 390     else {
 391       nLen += EXTRA_ALLOC;
 392
 393       pData = (wxStringData *)
 394         realloc(pData, sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 395
 396       if ( pData == NULL ) {
 397         // allocation failure handled by caller
 398         // keep previous data since reallocation failed
 399         return false;
 400       }
 401
 402       // it's not important if the pointer changed or not (the check for this
 403       // is not faster than assigning to m_pchData in all cases)
 404       pData->nAllocLength = nLen;
 405       m_pchData = pData->data();
 406     }
 407   }
 408   //else: we've already got enough
 409   return true;
 410 }
 411
 412 wxStringBase::iterator wxStringBase::begin()
 413 {
 414     if (length() > 0)
 415         CopyBeforeWrite();
 416     return m_pchData;
 417 }
 418
 419 wxStringBase::iterator wxStringBase::end()
 420 {
 421     if (length() > 0)
 422         CopyBeforeWrite();
 423     return m_pchData + length();
 424 }
 425
 426 wxStringBase::iterator wxStringBase::erase(iterator it)
 427 {
 428     size_type idx = it - begin();
 429     erase(idx, 1);
 430     return begin() + idx;
 431 }
 432
 433 wxStringBase& wxStringBase::erase(size_t nStart, size_t nLen)
 434 {
 435   wxASSERT(nStart <= length());
 436   size_t strLen = length() - nStart;
 437   // delete nLen or up to the end of the string characters
 438   nLen = strLen < nLen ? strLen : nLen;
 439   wxString strTmp(c_str(), nStart);
 440   strTmp.append(c_str() + nStart + nLen, length() - nStart - nLen);
 441
 442   swap(strTmp);
 443   return *this;
 444 }
 445
 446 wxStringBase& wxStringBase::insert(size_t nPos, const wxChar *sz, size_t n)
 447 {
 448   wxASSERT( nPos <= length() );
 449
 450   if ( n == npos ) n = wxStrlen(sz);
 451   if ( n == 0 ) return *this;
 452
 453   if ( !Alloc(length() + n) || !CopyBeforeWrite() ) {
 454     wxFAIL_MSG( _T("out of memory in wxStringBase::insert") );
 455   }
 456
 457   memmove(m_pchData + nPos + n, m_pchData + nPos,
 458           (length() - nPos) * sizeof(wxChar));
 459   memcpy(m_pchData + nPos, sz, n * sizeof(wxChar));
 460   GetStringData()->nDataLength = length() + n;
 461   m_pchData[length()] = '\0';
 462
 463   return *this;
 464 }
 465
 466 void wxStringBase::swap(wxStringBase& str)
 467 {
 468     wxChar* tmp = str.m_pchData;
 469     str.m_pchData = m_pchData;
 470     m_pchData = tmp;
 471 }
 472
 473 size_t wxStringBase::find(const wxStringBase& str, size_t nStart) const
 474 {
 475   wxASSERT( str.GetStringData()->IsValid() );
 476   wxASSERT( nStart <= length() );
 477
 478   //anchor
 479   const wxChar* p = (const wxChar*)wxTmemchr(c_str() + nStart,
 480                                             str.c_str()[0],
 481                                             length() - nStart);
 482
 483   if(!p)
 484       return npos;
 485
 486   while(p - c_str() + str.length() <= length() &&
 487         wxTmemcmp(p, str.c_str(), str.length()) )
 488   {
 489       //Previosly passed as the first argument to wxTmemchr,
 490       //but C/C++ standard does not specify evaluation order
 491       //of arguments to functions -
 492       //http://embedded.com/showArticle.jhtml?articleID=9900607
 493       ++p;
 494
 495       //anchor again
 496       p = (const wxChar*)wxTmemchr(p,
 497                                   str.c_str()[0],
 498                                   length() - (p - c_str()));
 499
 500       if(!p)
 501           return npos;
 502   }
 503
 504    return (p - c_str() + str.length() <= length()) ? p - c_str() : npos;
 505 }
 506
 507 size_t wxStringBase::find(const wxChar* sz, size_t nStart, size_t n) const
 508 {
 509   return find(wxStringBase(sz, n), nStart);
 510 }
 511
 512 size_t wxStringBase::find(wxChar ch, size_t nStart) const
 513 {
 514   wxASSERT( nStart <= length() );
 515
 516   const wxChar *p = (const wxChar*)wxTmemchr(c_str() + nStart, ch, length() - nStart);
 517
 518   return p == NULL ? npos : p - c_str();
 519 }
 520
 521 size_t wxStringBase::rfind(const wxStringBase& str, size_t nStart) const
 522 {
 523     wxASSERT( str.GetStringData()->IsValid() );
 524     wxASSERT( nStart == npos || nStart <= length() );
 525
 526     if ( length() >= str.length() )
 527     {
 528         // avoids a corner case later
 529         if ( length() == 0 && str.length() == 0 )
 530             return 0;
 531
 532         // "top" is the point where search starts from
 533         size_t top = length() - str.length();
 534
 535         if ( nStart == npos )
 536             nStart = length() - 1;
 537         if ( nStart < top )
 538             top = nStart;
 539
 540         const wxChar *cursor = c_str() + top;
 541         do
 542         {
 543             if ( wxTmemcmp(cursor, str.c_str(),
 544                         str.length()) == 0 )
 545             {
 546                 return cursor - c_str();
 547             }
 548         } while ( cursor-- > c_str() );
 549     }
 550
 551     return npos;
 552 }
 553
 554 size_t wxStringBase::rfind(const wxChar* sz, size_t nStart, size_t n) const
 555 {
 556     return rfind(wxStringBase(sz, n), nStart);
 557 }
 558
 559 size_t wxStringBase::rfind(wxChar ch, size_t nStart) const
 560 {
 561     if ( nStart == npos )
 562     {
 563         nStart = length();
 564     }
 565     else
 566     {
 567         wxASSERT( nStart <= length() );
 568     }
 569
 570     const wxChar *actual;
 571     for ( actual = c_str() + ( nStart == npos ? length() : nStart + 1 );
 572           actual > c_str(); --actual )
 573     {
 574         if ( *(actual - 1) == ch )
 575             return (actual - 1) - c_str();
 576     }
 577
 578     return npos;
 579 }
 580
 581 size_t wxStringBase::find_first_of(const wxChar* sz, size_t nStart) const
 582 {
 583     wxASSERT(nStart <= length());
 584
 585     size_t len = wxStrlen(sz);
 586
 587     size_t i;
 588     for(i = nStart; i < this->length(); ++i)
 589     {
 590         if (wxTmemchr(sz, *(c_str() + i), len))
 591             break;
 592     }
 593
 594     if(i == this->length())
 595         return npos;
 596     else
 597         return i;
 598 }
 599
 600 size_t wxStringBase::find_first_of(const wxChar* sz, size_t nStart,
 601                                    size_t n) const
 602 {
 603     return find_first_of(wxStringBase(sz, n), nStart);
 604 }
 605
 606 size_t wxStringBase::find_last_of(const wxChar* sz, size_t nStart) const
 607 {
 608     if ( nStart == npos )
 609     {
 610         nStart = length() - 1;
 611     }
 612     else
 613     {
 614         wxASSERT_MSG( nStart <= length(),
 615                         _T("invalid index in find_last_of()") );
 616     }
 617
 618     size_t len = wxStrlen(sz);
 619
 620     for ( const wxChar *p = c_str() + nStart; p >= c_str(); --p )
 621     {
 622         if ( wxTmemchr(sz, *p, len) )
 623             return p - c_str();
 624     }
 625
 626     return npos;
 627 }
 628
 629 size_t wxStringBase::find_last_of(const wxChar* sz, size_t nStart,
 630                                    size_t n) const
 631 {
 632     return find_last_of(wxStringBase(sz, n), nStart);
 633 }
 634
 635 size_t wxStringBase::find_first_not_of(const wxChar* sz, size_t nStart) const
 636 {
 637     if ( nStart == npos )
 638     {
 639         nStart = length();
 640     }
 641     else
 642     {
 643         wxASSERT( nStart <= length() );
 644     }
 645
 646     size_t len = wxStrlen(sz);
 647
 648     size_t i;
 649     for(i = nStart; i < this->length(); ++i)
 650     {
 651         if (!wxTmemchr(sz, *(c_str() + i), len))
 652             break;
 653     }
 654
 655     if(i == this->length())
 656          return npos;
 657      else
 658         return i;
 659 }
 660
 661 size_t wxStringBase::find_first_not_of(const wxChar* sz, size_t nStart,
 662                                        size_t n) const
 663 {
 664     return find_first_not_of(wxStringBase(sz, n), nStart);
 665 }
 666
 667 size_t wxStringBase::find_first_not_of(wxChar ch, size_t nStart) const
 668 {
 669     wxASSERT( nStart <= length() );
 670
 671     for ( const wxChar *p = c_str() + nStart; *p; p++ )
 672     {
 673         if ( *p != ch )
 674             return p - c_str();
 675     }
 676
 677     return npos;
 678 }
 679
 680 size_t wxStringBase::find_last_not_of(const wxChar* sz, size_t nStart) const
 681 {
 682     if ( nStart == npos )
 683     {
 684         nStart = length() - 1;
 685     }
 686     else
 687     {
 688         wxASSERT( nStart <= length() );
 689     }
 690
 691     size_t len = wxStrlen(sz);
 692
 693     for ( const wxChar *p = c_str() + nStart; p >= c_str(); --p )
 694     {
 695         if ( !wxTmemchr(sz, *p,len) )
 696              return p - c_str();
 697     }
 698
 699     return npos;
 700 }
 701
 702 size_t wxStringBase::find_last_not_of(const wxChar* sz, size_t nStart,
 703                                       size_t n) const
 704 {
 705     return find_last_not_of(wxStringBase(sz, n), nStart);
 706 }
 707
 708 size_t wxStringBase::find_last_not_of(wxChar ch, size_t nStart) const
 709 {
 710     if ( nStart == npos )
 711     {
 712         nStart = length() - 1;
 713     }
 714     else
 715     {
 716         wxASSERT( nStart <= length() );
 717     }
 718
 719     for ( const wxChar *p = c_str() + nStart; p >= c_str(); --p )
 720     {
 721         if ( *p != ch )
 722             return p - c_str();
 723     }
 724
 725     return npos;
 726 }
 727
 728 wxStringBase& wxStringBase::replace(size_t nStart, size_t nLen,
 729                                     const wxChar *sz)
 730 {
 731   wxASSERT_MSG( nStart <= length(),
 732                 _T("index out of bounds in wxStringBase::replace") );
 733   size_t strLen = length() - nStart;
 734   nLen = strLen < nLen ? strLen : nLen;
 735
 736   wxStringBase strTmp;
 737   strTmp.reserve(length()); // micro optimisation to avoid multiple mem allocs
 738
 739   if ( nStart != 0 )
 740     strTmp.append(c_str(), nStart);
 741   strTmp.append(sz);
 742   strTmp.append(c_str() + nStart + nLen);
 743
 744   swap(strTmp);
 745   return *this;
 746 }
 747
 748 wxStringBase& wxStringBase::replace(size_t nStart, size_t nLen,
 749                                     size_t nCount, wxChar ch)
 750 {
 751   return replace(nStart, nLen, wxStringBase(nCount, ch).c_str());
 752 }
 753
 754 wxStringBase& wxStringBase::replace(size_t nStart, size_t nLen,
 755                                     const wxStringBase& str,
 756                                     size_t nStart2, size_t nLen2)
 757 {
 758   return replace(nStart, nLen, str.substr(nStart2, nLen2));
 759 }
 760
 761 wxStringBase& wxStringBase::replace(size_t nStart, size_t nLen,
 762                                     const wxChar* sz, size_t nCount)
 763 {
 764   return replace(nStart, nLen, wxStringBase(sz, nCount).c_str());
 765 }
 766
 767 wxStringBase wxStringBase::substr(size_t nStart, size_t nLen) const
 768 {
 769   if ( nLen == npos )
 770     nLen = length() - nStart;
 771   return wxStringBase(*this, nStart, nLen);
 772 }
 773
 774 // assigns one string to another
 775 wxStringBase& wxStringBase::operator=(const wxStringBase& stringSrc)
 776 {
 777   wxASSERT( stringSrc.GetStringData()->IsValid() );
 778
 779   // don't copy string over itself
 780   if ( m_pchData != stringSrc.m_pchData ) {
 781     if ( stringSrc.GetStringData()->IsEmpty() ) {
 782       Reinit();
 783     }
 784     else {
 785       // adjust references
 786       GetStringData()->Unlock();
 787       m_pchData = stringSrc.m_pchData;
 788       GetStringData()->Lock();
 789     }
 790   }
 791
 792   return *this;
 793 }
 794
 795 // assigns a single character
 796 wxStringBase& wxStringBase::operator=(wxChar ch)
 797 {
 798   if ( !AssignCopy(1, &ch) ) {
 799     wxFAIL_MSG( _T("out of memory in wxStringBase::operator=(wxChar)") );
 800   }
 801   return *this;
 802 }
 803
 804 // assigns C string
 805 wxStringBase& wxStringBase::operator=(const wxChar *psz)
 806 {
 807   if ( !AssignCopy(wxStrlen(psz), psz) ) {
 808     wxFAIL_MSG( _T("out of memory in wxStringBase::operator=(const wxChar *)") );
 809   }
 810   return *this;
 811 }
 812
 813 // helper function: does real copy
 814 bool wxStringBase::AssignCopy(size_t nSrcLen, const wxChar *pszSrcData)
 815 {
 816   if ( nSrcLen == 0 ) {
 817     Reinit();
 818   }
 819   else {
 820     if ( !AllocBeforeWrite(nSrcLen) ) {
 821       // allocation failure handled by caller
 822       return false;
 823     }
 824     memcpy(m_pchData, pszSrcData, nSrcLen*sizeof(wxChar));
 825     GetStringData()->nDataLength = nSrcLen;
 826     m_pchData[nSrcLen] = wxT('\0');
 827   }
 828   return true;
 829 }
 830
 831 // ---------------------------------------------------------------------------
 832 // string concatenation
 833 // ---------------------------------------------------------------------------
 834
 835 // add something to this string
 836 bool wxStringBase::ConcatSelf(size_t nSrcLen, const wxChar *pszSrcData,
 837                               size_t nMaxLen)
 838 {
 839   STATISTICS_ADD(SummandLength, nSrcLen);
 840
 841   nSrcLen = nSrcLen < nMaxLen ? nSrcLen : nMaxLen;
 842
 843   // concatenating an empty string is a NOP
 844   if ( nSrcLen > 0 ) {
 845     wxStringData *pData = GetStringData();
 846     size_t nLen = pData->nDataLength;
 847     size_t nNewLen = nLen + nSrcLen;
 848
 849     // alloc new buffer if current is too small
 850     if ( pData->IsShared() ) {
 851       STATISTICS_ADD(ConcatHit, 0);
 852
 853       // we have to allocate another buffer
 854       wxStringData* pOldData = GetStringData();
 855       if ( !AllocBuffer(nNewLen) ) {
 856           // allocation failure handled by caller
 857           return false;
 858       }
 859       memcpy(m_pchData, pOldData->data(), nLen*sizeof(wxChar));
 860       pOldData->Unlock();
 861     }
 862     else if ( nNewLen > pData->nAllocLength ) {
 863       STATISTICS_ADD(ConcatHit, 0);
 864
 865       reserve(nNewLen);
 866       // we have to grow the buffer
 867       if ( capacity() < nNewLen ) {
 868           // allocation failure handled by caller
 869           return false;
 870       }
 871     }
 872     else {
 873       STATISTICS_ADD(ConcatHit, 1);
 874
 875       // the buffer is already big enough
 876     }
 877
 878     // should be enough space
 879     wxASSERT( nNewLen <= GetStringData()->nAllocLength );
 880
 881     // fast concatenation - all is done in our buffer
 882     memcpy(m_pchData + nLen, pszSrcData, nSrcLen*sizeof(wxChar));
 883
 884     m_pchData[nNewLen] = wxT('\0');          // put terminating '\0'
 885     GetStringData()->nDataLength = nNewLen; // and fix the length
 886   }
 887   //else: the string to append was empty
 888   return true;
 889 }
 890
 891 // ---------------------------------------------------------------------------
 892 // simple sub-string extraction
 893 // ---------------------------------------------------------------------------
 894
 895 // helper function: clone the data attached to this string
 896 bool wxStringBase::AllocCopy(wxString& dest, int nCopyLen, int nCopyIndex) const
 897 {
 898   if ( nCopyLen == 0 ) {
 899     dest.Init();
 900   }
 901   else {
 902     if ( !dest.AllocBuffer(nCopyLen) ) {
 903       // allocation failure handled by caller
 904       return false;
 905     }
 906     memcpy(dest.m_pchData, m_pchData + nCopyIndex, nCopyLen*sizeof(wxChar));
 907   }
 908   return true;
 909 }
 910
 911 #endif // !wxUSE_STL
 912
 913 #if !wxUSE_STL || !defined(HAVE_STD_STRING_COMPARE)
 914
 915 #if !wxUSE_STL
 916     #define STRINGCLASS wxStringBase
 917 #else
 918     #define STRINGCLASS wxString
 919 #endif
 920
 921 static inline int wxDoCmp(const wxChar* s1, size_t l1,
 922                           const wxChar* s2, size_t l2)
 923 {
 924     if( l1 == l2 )
 925         return wxTmemcmp(s1, s2, l1);
 926     else if( l1 < l2 )
 927     {
 928         int ret = wxTmemcmp(s1, s2, l1);
 929         return ret == 0 ? -1 : ret;
 930     }
 931     else
 932     {
 933         int ret = wxTmemcmp(s1, s2, l2);
 934         return ret == 0 ? +1 : ret;
 935     }
 936 }
 937
 938 int STRINGCLASS::compare(const wxStringBase& str) const
 939 {
 940     return ::wxDoCmp(data(), length(), str.data(), str.length());
 941 }
 942
 943 int STRINGCLASS::compare(size_t nStart, size_t nLen,
 944                          const wxStringBase& str) const
 945 {
 946     wxASSERT(nStart <= length());
 947     size_type strLen = length() - nStart;
 948     nLen = strLen < nLen ? strLen : nLen;
 949     return ::wxDoCmp(data() + nStart, nLen, str.data(), str.length());
 950 }
 951
 952 int STRINGCLASS::compare(size_t nStart, size_t nLen,
 953                          const wxStringBase& str,
 954                          size_t nStart2, size_t nLen2) const
 955 {
 956     wxASSERT(nStart <= length());
 957     wxASSERT(nStart2 <= str.length());
 958     size_type strLen  =     length() - nStart,
 959               strLen2 = str.length() - nStart2;
 960     nLen  = strLen  < nLen  ? strLen  : nLen;
 961     nLen2 = strLen2 < nLen2 ? strLen2 : nLen2;
 962     return ::wxDoCmp(data() + nStart, nLen, str.data() + nStart2, nLen2);
 963 }
 964
 965 int STRINGCLASS::compare(const wxChar* sz) const
 966 {
 967     size_t nLen = wxStrlen(sz);
 968     return ::wxDoCmp(data(), length(), sz, nLen);
 969 }
 970
 971 int STRINGCLASS::compare(size_t nStart, size_t nLen,
 972                          const wxChar* sz, size_t nCount) const
 973 {
 974     wxASSERT(nStart <= length());
 975     size_type strLen = length() - nStart;
 976     nLen = strLen < nLen ? strLen : nLen;
 977     if( nCount == npos )
 978         nCount = wxStrlen(sz);
 979
 980     return ::wxDoCmp(data() + nStart, nLen, sz, nCount);
 981 }
 982
 983 #undef STRINGCLASS
 984
 985 #endif // !wxUSE_STL || !defined(HAVE_STD_STRING_COMPARE)
 986
 987 // ===========================================================================
 988 // wxString class core
 989 // ===========================================================================
 990
 991 // ---------------------------------------------------------------------------
 992 // construction and conversion
 993 // ---------------------------------------------------------------------------
 994
 995 #if wxUSE_UNICODE
 996
 997 // from multibyte string
 998 wxString::wxString(const char *psz, wxMBConv& conv, size_t nLength)
 999 {
1000     // if nLength != npos, then we have to make a NULL-terminated copy
1001     // of first nLength bytes of psz first because the input buffer to MB2WC
1002     // must always be NULL-terminated:
1003     wxCharBuffer inBuf((const char *)NULL);
1004     if (nLength != npos)
1005     {
1006         wxASSERT( psz != NULL );
1007         wxCharBuffer tmp(nLength);
1008         memcpy(tmp.data(), psz, nLength);
1009         tmp.data()[nLength] = '\0';
1010         inBuf = tmp;
1011         psz = inBuf.data();
1012     }
1013
1014     // first get the size of the buffer we need
1015     size_t nLen;
1016     if ( psz )
1017     {
1018         // calculate the needed size ourselves or use the provided one
1019         if (nLength == npos)
1020             nLen = strlen(psz);
1021         else
1022             nLen = nLength;
1023     }
1024     else
1025     {
1026         // nothing to convert
1027         nLen = 0;
1028     }
1029
1030
1031     // anything to do?
1032     if ( (nLen != 0) && (nLen != (size_t)-1) )
1033     {
1034         //Convert string
1035         size_t nRealSize;
1036         wxWCharBuffer theBuffer = conv.cMB2WC(psz, nLen, &nRealSize);
1037
1038         //Copy
1039         if (nRealSize)
1040             assign( theBuffer.data() , nRealSize - 1 );
1041     }
1042 }
1043
1044 //Convert wxString in Unicode mode to a multi-byte string
1045 const wxCharBuffer wxString::mb_str(wxMBConv& conv) const
1046 {
1047     size_t dwOutSize;
1048     return conv.cWC2MB(c_str(), length(), &dwOutSize);
1049 }
1050
1051 #else // ANSI
1052
1053 #if wxUSE_WCHAR_T
1054 // from wide string
1055 wxString::wxString(const wchar_t *pwz, wxMBConv& conv, size_t nLength)
1056 {
1057     // if nLength != npos, then we have to make a NULL-terminated copy
1058     // of first nLength chars of psz first because the input buffer to WC2MB
1059     // must always be NULL-terminated:
1060     wxWCharBuffer inBuf((const wchar_t *)NULL);
1061     if (nLength != npos)
1062     {
1063         wxASSERT( pwz != NULL );
1064         wxWCharBuffer tmp(nLength);
1065         memcpy(tmp.data(), pwz, nLength * sizeof(wchar_t));
1066         tmp.data()[nLength] = '\0';
1067         inBuf = tmp;
1068         pwz = inBuf.data();
1069     }
1070
1071     // first get the size of the buffer we need
1072     size_t nLen;
1073     if ( pwz )
1074     {
1075         // calculate the needed size ourselves or use the provided one
1076         if (nLength == npos)
1077             nLen = wxWcslen(pwz);
1078         else
1079             nLen = nLength;
1080     }
1081     else
1082     {
1083         // nothing to convert
1084         nLen = 0;
1085     }
1086
1087     // anything to do?
1088     if ( (nLen != 0) && (nLen != (size_t)-1) )
1089     {
1090         //Convert string
1091         size_t nRealSize;
1092         wxCharBuffer theBuffer = conv.cWC2MB(pwz, nLen, &nRealSize);
1093
1094         //Copy
1095         if (nRealSize)
1096             assign( theBuffer.data() , nRealSize - 1 );
1097     }
1098 }
1099
1100 //Converts this string to a wide character string if unicode
1101 //mode is not enabled and wxUSE_WCHAR_T is enabled
1102 const wxWCharBuffer wxString::wc_str(wxMBConv& conv) const
1103 {
1104     size_t dwOutSize;
1105     return conv.cMB2WC(c_str(), length(), &dwOutSize);
1106 }
1107
1108 #endif // wxUSE_WCHAR_T
1109
1110 #endif // Unicode/ANSI
1111
1112 // shrink to minimal size (releasing extra memory)
1113 bool wxString::Shrink()
1114 {
1115   wxString tmp(begin(), end());
1116   swap(tmp);
1117   return tmp.length() == length();
1118 }
1119
1120 #if !wxUSE_STL
1121 // get the pointer to writable buffer of (at least) nLen bytes
1122 wxChar *wxString::GetWriteBuf(size_t nLen)
1123 {
1124   if ( !AllocBeforeWrite(nLen) ) {
1125     // allocation failure handled by caller
1126     return NULL;
1127   }
1128
1129   wxASSERT( GetStringData()->nRefs == 1 );
1130   GetStringData()->Validate(false);
1131
1132   return m_pchData;
1133 }
1134
1135 // put string back in a reasonable state after GetWriteBuf
1136 void wxString::UngetWriteBuf()
1137 {
1138   GetStringData()->nDataLength = wxStrlen(m_pchData);
1139   GetStringData()->Validate(true);
1140 }
1141
1142 void wxString::UngetWriteBuf(size_t nLen)
1143 {
1144   GetStringData()->nDataLength = nLen;
1145   GetStringData()->Validate(true);
1146 }
1147 #endif
1148
1149 // ---------------------------------------------------------------------------
1150 // data access
1151 // ---------------------------------------------------------------------------
1152
1153 // all functions are inline in string.h
1154
1155 // ---------------------------------------------------------------------------
1156 // assignment operators
1157 // ---------------------------------------------------------------------------
1158
1159 #if !wxUSE_UNICODE
1160
1161 // same as 'signed char' variant
1162 wxString& wxString::operator=(const unsigned char* psz)
1163 {
1164   *this = (const char *)psz;
1165   return *this;
1166 }
1167
1168 #if wxUSE_WCHAR_T
1169 wxString& wxString::operator=(const wchar_t *pwz)
1170 {
1171   wxString str(pwz);
1172   swap(str);
1173   return *this;
1174 }
1175 #endif
1176
1177 #endif
1178
1179 /*
1180  * concatenation functions come in 5 flavours:
1181  *  string + string
1182  *  char   + string      and      string + char
1183  *  C str  + string      and      string + C str
1184  */
1185
1186 wxString operator+(const wxString& str1, const wxString& str2)
1187 {
1188 #if !wxUSE_STL
1189   wxASSERT( str1.GetStringData()->IsValid() );
1190   wxASSERT( str2.GetStringData()->IsValid() );
1191 #endif
1192
1193   wxString s = str1;
1194   s += str2;
1195
1196   return s;
1197 }
1198
1199 wxString operator+(const wxString& str, wxChar ch)
1200 {
1201 #if !wxUSE_STL
1202   wxASSERT( str.GetStringData()->IsValid() );
1203 #endif
1204
1205   wxString s = str;
1206   s += ch;
1207
1208   return s;
1209 }
1210
1211 wxString operator+(wxChar ch, const wxString& str)
1212 {
1213 #if !wxUSE_STL
1214   wxASSERT( str.GetStringData()->IsValid() );
1215 #endif
1216
1217   wxString s = ch;
1218   s += str;
1219
1220   return s;
1221 }
1222
1223 wxString operator+(const wxString& str, const wxChar *psz)
1224 {
1225 #if !wxUSE_STL
1226   wxASSERT( str.GetStringData()->IsValid() );
1227 #endif
1228
1229   wxString s;
1230   if ( !s.Alloc(wxStrlen(psz) + str.Len()) ) {
1231     wxFAIL_MSG( _T("out of memory in wxString::operator+") );
1232   }
1233   s += str;
1234   s += psz;
1235
1236   return s;
1237 }
1238
1239 wxString operator+(const wxChar *psz, const wxString& str)
1240 {
1241 #if !wxUSE_STL
1242   wxASSERT( str.GetStringData()->IsValid() );
1243 #endif
1244
1245   wxString s;
1246   if ( !s.Alloc(wxStrlen(psz) + str.Len()) ) {
1247     wxFAIL_MSG( _T("out of memory in wxString::operator+") );
1248   }
1249   s = psz;
1250   s += str;
1251
1252   return s;
1253 }
1254
1255 // ===========================================================================
1256 // other common string functions
1257 // ===========================================================================
1258
1259 int wxString::Cmp(const wxString& s) const
1260 {
1261     return compare(s);
1262 }
1263
1264 int wxString::Cmp(const wxChar* psz) const
1265 {
1266     return compare(psz);
1267 }
1268
1269 static inline int wxDoCmpNoCase(const wxChar* s1, size_t l1,
1270                                 const wxChar* s2, size_t l2)
1271 {
1272     size_t i;
1273
1274     if( l1 == l2 )
1275     {
1276         for(i = 0; i < l1; ++i)
1277         {
1278             if(wxTolower(s1[i]) != wxTolower(s2[i]))
1279                 break;
1280         }
1281         return i == l1 ? 0 : wxTolower(s1[i]) < wxTolower(s2[i]) ? -1 : 1;
1282     }
1283     else if( l1 < l2 )
1284     {
1285         for(i = 0; i < l1; ++i)
1286         {
1287             if(wxTolower(s1[i]) != wxTolower(s2[i]))
1288                 break;
1289         }
1290         return i == l1 ? -1 : wxTolower(s1[i]) < wxTolower(s2[i]) ? -1 : 1;
1291     }
1292     else
1293     {
1294         for(i = 0; i < l2; ++i)
1295         {
1296             if(wxTolower(s1[i]) != wxTolower(s2[i]))
1297                 break;
1298         }
1299         return i == l2 ? 1 : wxTolower(s1[i]) < wxTolower(s2[i]) ? -1 : 1;
1300     }
1301 }
1302
1303 int wxString::CmpNoCase(const wxString& s) const
1304 {
1305     return wxDoCmpNoCase(data(), length(), s.data(), s.length());
1306 }
1307
1308 int wxString::CmpNoCase(const wxChar* psz) const
1309 {
1310     int nLen = wxStrlen(psz);
1311
1312     return wxDoCmpNoCase(data(), length(), psz, nLen);
1313 }
1314
1315
1316 #if wxUSE_UNICODE
1317
1318 #ifdef __MWERKS__
1319 #ifndef __SCHAR_MAX__
1320 #define __SCHAR_MAX__ 127
1321 #endif
1322 #endif
1323
1324 wxString wxString::FromAscii(const char *ascii)
1325 {
1326     if (!ascii)
1327        return wxEmptyString;
1328
1329     size_t len = strlen( ascii );
1330     wxString res;
1331
1332     if ( len )
1333     {
1334         wxStringBuffer buf(res, len);
1335
1336         wchar_t *dest = buf;
1337
1338         for ( ;; )
1339         {
1340            if ( (*dest++ = (wchar_t)(unsigned char)*ascii++) == L'\0' )
1341                break;
1342         }
1343     }
1344
1345     return res;
1346 }
1347
1348 wxString wxString::FromAscii(const char ascii)
1349 {
1350     // What do we do with '\0' ?
1351
1352     wxString res;
1353     res += (wchar_t)(unsigned char) ascii;
1354
1355     return res;
1356 }
1357
1358 const wxCharBuffer wxString::ToAscii() const
1359 {
1360     // this will allocate enough space for the terminating NUL too
1361     wxCharBuffer buffer(length());
1362
1363
1364     char *dest = buffer.data();
1365
1366     const wchar_t *pwc = c_str();
1367     for ( ;; )
1368     {
1369         *dest++ = (char)(*pwc > SCHAR_MAX ? wxT('_') : *pwc);
1370
1371         // the output string can't have embedded NULs anyhow, so we can safely
1372         // stop at first of them even if we do have any
1373         if ( !*pwc++ )
1374             break;
1375     }
1376
1377     return buffer;
1378 }
1379
1380 #endif // Unicode
1381
1382 // extract string of length nCount starting at nFirst
1383 wxString wxString::Mid(size_t nFirst, size_t nCount) const
1384 {
1385   size_t nLen = length();
1386
1387   // default value of nCount is npos and means "till the end"
1388   if ( nCount == npos )
1389   {
1390     nCount = nLen - nFirst;
1391   }
1392
1393   // out-of-bounds requests return sensible things
1394   if ( nFirst + nCount > nLen )
1395   {
1396     nCount = nLen - nFirst;
1397   }
1398
1399   if ( nFirst > nLen )
1400   {
1401     // AllocCopy() will return empty string
1402     nCount = 0;
1403   }
1404
1405   wxString dest(*this, nFirst, nCount);
1406   if ( dest.length() != nCount ) {
1407       wxFAIL_MSG( _T("out of memory in wxString::Mid") );
1408   }
1409
1410   return dest;
1411 }
1412
1413 // check that the string starts with prefix and return the rest of the string
1414 // in the provided pointer if it is not NULL, otherwise return false
1415 bool wxString::StartsWith(const wxChar *prefix, wxString *rest) const
1416 {
1417     wxASSERT_MSG( prefix, _T("invalid parameter in wxString::StartsWith") );
1418
1419     // first check if the beginning of the string matches the prefix: note
1420     // that we don't have to check that we don't run out of this string as
1421     // when we reach the terminating NUL, either prefix string ends too (and
1422     // then it's ok) or we break out of the loop because there is no match
1423     const wxChar *p = c_str();
1424     while ( *prefix )
1425     {
1426         if ( *prefix++ != *p++ )
1427         {
1428             // no match
1429             return false;
1430         }
1431     }
1432
1433     if ( rest )
1434     {
1435         // put the rest of the string into provided pointer
1436         *rest = p;
1437     }
1438
1439     return true;
1440 }
1441
1442 // extract nCount last (rightmost) characters
1443 wxString wxString::Right(size_t nCount) const
1444 {
1445   if ( nCount > length() )
1446     nCount = length();
1447
1448   wxString dest(*this, length() - nCount, nCount);
1449   if ( dest.length() != nCount ) {
1450     wxFAIL_MSG( _T("out of memory in wxString::Right") );
1451   }
1452   return dest;
1453 }
1454
1455 // get all characters after the last occurence of ch
1456 // (returns the whole string if ch not found)
1457 wxString wxString::AfterLast(wxChar ch) const
1458 {
1459   wxString str;
1460   int iPos = Find(ch, true);
1461   if ( iPos == wxNOT_FOUND )
1462     str = *this;
1463   else
1464     str = c_str() + iPos + 1;
1465
1466   return str;
1467 }
1468
1469 // extract nCount first (leftmost) characters
1470 wxString wxString::Left(size_t nCount) const
1471 {
1472   if ( nCount > length() )
1473     nCount = length();
1474
1475   wxString dest(*this, 0, nCount);
1476   if ( dest.length() != nCount ) {
1477     wxFAIL_MSG( _T("out of memory in wxString::Left") );
1478   }
1479   return dest;
1480 }
1481
1482 // get all characters before the first occurence of ch
1483 // (returns the whole string if ch not found)
1484 wxString wxString::BeforeFirst(wxChar ch) const
1485 {
1486   int iPos = Find(ch);
1487   if ( iPos == wxNOT_FOUND ) iPos = length();
1488   return wxString(*this, 0, iPos);
1489 }
1490
1491 /// get all characters before the last occurence of ch
1492 /// (returns empty string if ch not found)
1493 wxString wxString::BeforeLast(wxChar ch) const
1494 {
1495   wxString str;
1496   int iPos = Find(ch, true);
1497   if ( iPos != wxNOT_FOUND && iPos != 0 )
1498     str = wxString(c_str(), iPos);
1499
1500   return str;
1501 }
1502
1503 /// get all characters after the first occurence of ch
1504 /// (returns empty string if ch not found)
1505 wxString wxString::AfterFirst(wxChar ch) const
1506 {
1507   wxString str;
1508   int iPos = Find(ch);
1509   if ( iPos != wxNOT_FOUND )
1510     str = c_str() + iPos + 1;
1511
1512   return str;
1513 }
1514
1515 // replace first (or all) occurences of some substring with another one
1516 size_t
1517 wxString::Replace(const wxChar *szOld, const wxChar *szNew, bool bReplaceAll)
1518 {
1519     // if we tried to replace an empty string we'd enter an infinite loop below
1520     wxCHECK_MSG( szOld && *szOld && szNew, 0,
1521                  _T("wxString::Replace(): invalid parameter") );
1522
1523   size_t uiCount = 0;   // count of replacements made
1524
1525   size_t uiOldLen = wxStrlen(szOld);
1526
1527   wxString strTemp;
1528   const wxChar *pCurrent = c_str();
1529   const wxChar *pSubstr;
1530   while ( *pCurrent != wxT('\0') ) {
1531     pSubstr = wxStrstr(pCurrent, szOld);
1532     if ( pSubstr == NULL ) {
1533       // strTemp is unused if no replacements were made, so avoid the copy
1534       if ( uiCount == 0 )
1535         return 0;
1536
1537       strTemp += pCurrent;    // copy the rest
1538       break;                  // exit the loop
1539     }
1540     else {
1541       // take chars before match
1542       size_type len = strTemp.length();
1543       strTemp.append(pCurrent, pSubstr - pCurrent);
1544       if ( strTemp.length() != (size_t)(len + pSubstr - pCurrent) ) {
1545         wxFAIL_MSG( _T("out of memory in wxString::Replace") );
1546         return 0;
1547       }
1548       strTemp += szNew;
1549       pCurrent = pSubstr + uiOldLen;  // restart after match
1550
1551       uiCount++;
1552
1553       // stop now?
1554       if ( !bReplaceAll ) {
1555         strTemp += pCurrent;    // copy the rest
1556         break;                  // exit the loop
1557       }
1558     }
1559   }
1560
1561   // only done if there were replacements, otherwise would have returned above
1562   swap(strTemp);
1563
1564   return uiCount;
1565 }
1566
1567 bool wxString::IsAscii() const
1568 {
1569   const wxChar *s = (const wxChar*) *this;
1570   while(*s){
1571     if(!isascii(*s)) return(false);
1572     s++;
1573   }
1574   return(true);
1575 }
1576
1577 bool wxString::IsWord() const
1578 {
1579   const wxChar *s = (const wxChar*) *this;
1580   while(*s){
1581     if(!wxIsalpha(*s)) return(false);
1582     s++;
1583   }
1584   return(true);
1585 }
1586
1587 bool wxString::IsNumber() const
1588 {
1589   const wxChar *s = (const wxChar*) *this;
1590   if (wxStrlen(s))
1591      if ((s[0] == wxT('-')) || (s[0] == wxT('+'))) s++;
1592   while(*s){
1593     if(!wxIsdigit(*s)) return(false);
1594     s++;
1595   }
1596   return(true);
1597 }
1598
1599 wxString wxString::Strip(stripType w) const
1600 {
1601     wxString s = *this;
1602     if ( w & leading ) s.Trim(false);
1603     if ( w & trailing ) s.Trim(true);
1604     return s;
1605 }
1606
1607 // ---------------------------------------------------------------------------
1608 // case conversion
1609 // ---------------------------------------------------------------------------
1610
1611 wxString& wxString::MakeUpper()
1612 {
1613   for ( iterator it = begin(), en = end(); it != en; ++it )
1614     *it = (wxChar)wxToupper(*it);
1615
1616   return *this;
1617 }
1618
1619 wxString& wxString::MakeLower()
1620 {
1621   for ( iterator it = begin(), en = end(); it != en; ++it )
1622     *it = (wxChar)wxTolower(*it);
1623
1624   return *this;
1625 }
1626
1627 // ---------------------------------------------------------------------------
1628 // trimming and padding
1629 // ---------------------------------------------------------------------------
1630
1631 // some compilers (VC++ 6.0 not to name them) return true for a call to
1632 // isspace('ê') in the C locale which seems to be broken to me, but we have to
1633 // live with this by checking that the character is a 7 bit one - even if this
1634 // may fail to detect some spaces (I don't know if Unicode doesn't have
1635 // space-like symbols somewhere except in the first 128 chars), it is arguably
1636 // still better than trimming away accented letters
1637 inline int wxSafeIsspace(wxChar ch) { return (ch < 127) && wxIsspace(ch); }
1638
1639 // trims spaces (in the sense of isspace) from left or right side
1640 wxString& wxString::Trim(bool bFromRight)
1641 {
1642   // first check if we're going to modify the string at all
1643   if ( !empty() &&
1644        (
1645         (bFromRight && wxSafeIsspace(GetChar(Len() - 1))) ||
1646         (!bFromRight && wxSafeIsspace(GetChar(0u)))
1647        )
1648      )
1649   {
1650     if ( bFromRight )
1651     {
1652       // find last non-space character
1653       iterator psz = begin() + length() - 1;
1654       while ( wxSafeIsspace(*psz) && (psz >= begin()) )
1655         psz--;
1656
1657       // truncate at trailing space start
1658       *++psz = wxT('\0');
1659       erase(psz, end());
1660     }
1661     else
1662     {
1663       // find first non-space character
1664       iterator psz = begin();
1665       while ( wxSafeIsspace(*psz) )
1666         psz++;
1667
1668       // fix up data and length
1669       erase(begin(), psz);
1670     }
1671   }
1672
1673   return *this;
1674 }
1675
1676 // adds nCount characters chPad to the string from either side
1677 wxString& wxString::Pad(size_t nCount, wxChar chPad, bool bFromRight)
1678 {
1679   wxString s(chPad, nCount);
1680
1681   if ( bFromRight )
1682     *this += s;
1683   else
1684   {
1685     s += *this;
1686     swap(s);
1687   }
1688
1689   return *this;
1690 }
1691
1692 // truncate the string
1693 wxString& wxString::Truncate(size_t uiLen)
1694 {
1695   if ( uiLen < Len() ) {
1696     erase(begin() + uiLen, end());
1697   }
1698   //else: nothing to do, string is already short enough
1699
1700   return *this;
1701 }
1702
1703 // ---------------------------------------------------------------------------
1704 // finding (return wxNOT_FOUND if not found and index otherwise)
1705 // ---------------------------------------------------------------------------
1706
1707 // find a character
1708 int wxString::Find(wxChar ch, bool bFromEnd) const
1709 {
1710   size_type idx = bFromEnd ? find_last_of(ch) : find_first_of(ch);
1711
1712   return (idx == npos) ? wxNOT_FOUND : (int)idx;
1713 }
1714
1715 // find a sub-string (like strstr)
1716 int wxString::Find(const wxChar *pszSub) const
1717 {
1718   size_type idx = find(pszSub);
1719
1720   return (idx == npos) ? wxNOT_FOUND : (int)idx;
1721 }
1722
1723 // ----------------------------------------------------------------------------
1724 // conversion to numbers
1725 // ----------------------------------------------------------------------------
1726
1727 bool wxString::ToLong(long *val, int base) const
1728 {
1729     wxCHECK_MSG( val, false, _T("NULL pointer in wxString::ToLong") );
1730     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1731
1732     const wxChar *start = c_str();
1733     wxChar *end;
1734     *val = wxStrtol(start, &end, base);
1735
1736     // return true only if scan was stopped by the terminating NUL and if the
1737     // string was not empty to start with
1738     return !*end && (end != start);
1739 }
1740
1741 bool wxString::ToULong(unsigned long *val, int base) const
1742 {
1743     wxCHECK_MSG( val, false, _T("NULL pointer in wxString::ToULong") );
1744     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1745
1746     const wxChar *start = c_str();
1747     wxChar *end;
1748     *val = wxStrtoul(start, &end, base);
1749
1750     // return true only if scan was stopped by the terminating NUL and if the
1751     // string was not empty to start with
1752     return !*end && (end != start);
1753 }
1754
1755 bool wxString::ToDouble(double *val) const
1756 {
1757     wxCHECK_MSG( val, false, _T("NULL pointer in wxString::ToDouble") );
1758
1759     const wxChar *start = c_str();
1760     wxChar *end;
1761     *val = wxStrtod(start, &end);
1762
1763     // return true only if scan was stopped by the terminating NUL and if the
1764     // string was not empty to start with
1765     return !*end && (end != start);
1766 }
1767
1768 // ---------------------------------------------------------------------------
1769 // formatted output
1770 // ---------------------------------------------------------------------------
1771
1772 /* static */
1773 wxString wxString::Format(const wxChar *pszFormat, ...)
1774 {
1775     va_list argptr;
1776     va_start(argptr, pszFormat);
1777
1778     wxString s;
1779     s.PrintfV(pszFormat, argptr);
1780
1781     va_end(argptr);
1782
1783     return s;
1784 }
1785
1786 /* static */
1787 wxString wxString::FormatV(const wxChar *pszFormat, va_list argptr)
1788 {
1789     wxString s;
1790     s.PrintfV(pszFormat, argptr);
1791     return s;
1792 }
1793
1794 int wxString::Printf(const wxChar *pszFormat, ...)
1795 {
1796   va_list argptr;
1797   va_start(argptr, pszFormat);
1798
1799   int iLen = PrintfV(pszFormat, argptr);
1800
1801   va_end(argptr);
1802
1803   return iLen;
1804 }
1805
1806 int wxString::PrintfV(const wxChar* pszFormat, va_list argptr)
1807 {
1808     int size = 1024;
1809     int len;
1810
1811     for ( ;; )
1812     {
1813         {
1814             wxStringBuffer tmp(*this, size + 1);
1815             wxChar* buf = tmp;
1816
1817             if ( !buf )
1818             {
1819                 // out of memory
1820                 return -1;
1821             }
1822
1823             // wxVsnprintf() may modify the original arg pointer, so pass it
1824             // only a copy
1825             va_list argptrcopy;
1826             wxVaCopy(argptrcopy, argptr);
1827             len = wxVsnprintf(buf, size, pszFormat, argptrcopy);
1828             va_end(argptrcopy);
1829
1830             // some implementations of vsnprintf() don't NUL terminate
1831             // the string if there is not enough space for it so
1832             // always do it manually
1833             buf[size] = _T('\0');
1834         }
1835
1836         // vsnprintf() may return either -1 (traditional Unix behaviour) or the
1837         // total number of characters which would have been written if the
1838         // buffer were large enough
1839         // also, it may return an errno may be something like EILSEQ,
1840         // in which case we need to break out
1841         if ( (len >= 0 && len <= size) || errno != EOVERFLOW )
1842         {
1843             // ok, there was enough space
1844             break;
1845         }
1846
1847         // still not enough, double it again
1848         size *= 2;
1849     }
1850
1851     // we could have overshot
1852     Shrink();
1853
1854     return Len();
1855 }
1856
1857 // ----------------------------------------------------------------------------
1858 // misc other operations
1859 // ----------------------------------------------------------------------------
1860
1861 // returns true if the string matches the pattern which may contain '*' and
1862 // '?' metacharacters (as usual, '?' matches any character and '*' any number
1863 // of them)
1864 bool wxString::Matches(const wxChar *pszMask) const
1865 {
1866     // I disable this code as it doesn't seem to be faster (in fact, it seems
1867     // to be much slower) than the old, hand-written code below and using it
1868     // here requires always linking with libregex even if the user code doesn't
1869     // use it
1870 #if 0 // wxUSE_REGEX
1871     // first translate the shell-like mask into a regex
1872     wxString pattern;
1873     pattern.reserve(wxStrlen(pszMask));
1874
1875     pattern += _T('^');
1876     while ( *pszMask )
1877     {
1878         switch ( *pszMask )
1879         {
1880             case _T('?'):
1881                 pattern += _T('.');
1882                 break;
1883
1884             case _T('*'):
1885                 pattern += _T(".*");
1886                 break;
1887
1888             case _T('^'):
1889             case _T('.'):
1890             case _T('$'):
1891             case _T('('):
1892             case _T(')'):
1893             case _T('|'):
1894             case _T('+'):
1895             case _T('\\'):
1896                 // these characters are special in a RE, quote them
1897                 // (however note that we don't quote '[' and ']' to allow
1898                 // using them for Unix shell like matching)
1899                 pattern += _T('\\');
1900                 // fall through
1901
1902             default:
1903                 pattern += *pszMask;
1904         }
1905
1906         pszMask++;
1907     }
1908     pattern += _T('$');
1909
1910     // and now use it
1911     return wxRegEx(pattern, wxRE_NOSUB | wxRE_EXTENDED).Matches(c_str());
1912 #else // !wxUSE_REGEX
1913   // TODO: this is, of course, awfully inefficient...
1914
1915   // the char currently being checked
1916   const wxChar *pszTxt = c_str();
1917
1918   // the last location where '*' matched
1919   const wxChar *pszLastStarInText = NULL;
1920   const wxChar *pszLastStarInMask = NULL;
1921
1922 match:
1923   for ( ; *pszMask != wxT('\0'); pszMask++, pszTxt++ ) {
1924     switch ( *pszMask ) {
1925       case wxT('?'):
1926         if ( *pszTxt == wxT('\0') )
1927           return false;
1928
1929         // pszTxt and pszMask will be incremented in the loop statement
1930
1931         break;
1932
1933       case wxT('*'):
1934         {
1935           // remember where we started to be able to backtrack later
1936           pszLastStarInText = pszTxt;
1937           pszLastStarInMask = pszMask;
1938
1939           // ignore special chars immediately following this one
1940           // (should this be an error?)
1941           while ( *pszMask == wxT('*') || *pszMask == wxT('?') )
1942             pszMask++;
1943
1944           // if there is nothing more, match
1945           if ( *pszMask == wxT('\0') )
1946             return true;
1947
1948           // are there any other metacharacters in the mask?
1949           size_t uiLenMask;
1950           const wxChar *pEndMask = wxStrpbrk(pszMask, wxT("*?"));
1951
1952           if ( pEndMask != NULL ) {
1953             // we have to match the string between two metachars
1954             uiLenMask = pEndMask - pszMask;
1955           }
1956           else {
1957             // we have to match the remainder of the string
1958             uiLenMask = wxStrlen(pszMask);
1959           }
1960
1961           wxString strToMatch(pszMask, uiLenMask);
1962           const wxChar* pMatch = wxStrstr(pszTxt, strToMatch);
1963           if ( pMatch == NULL )
1964             return false;
1965
1966           // -1 to compensate "++" in the loop
1967           pszTxt = pMatch + uiLenMask - 1;
1968           pszMask += uiLenMask - 1;
1969         }
1970         break;
1971
1972       default:
1973         if ( *pszMask != *pszTxt )
1974           return false;
1975         break;
1976     }
1977   }
1978
1979   // match only if nothing left
1980   if ( *pszTxt == wxT('\0') )
1981     return true;
1982
1983   // if we failed to match, backtrack if we can
1984   if ( pszLastStarInText ) {
1985     pszTxt = pszLastStarInText + 1;
1986     pszMask = pszLastStarInMask;
1987
1988     pszLastStarInText = NULL;
1989
1990     // don't bother resetting pszLastStarInMask, it's unnecessary
1991
1992     goto match;
1993   }
1994
1995   return false;
1996 #endif // wxUSE_REGEX/!wxUSE_REGEX
1997 }
1998
1999 // Count the number of chars
2000 int wxString::Freq(wxChar ch) const
2001 {
2002     int count = 0;
2003     int len = Len();
2004     for (int i = 0; i < len; i++)
2005     {
2006         if (GetChar(i) == ch)
2007             count ++;
2008     }
2009     return count;
2010 }
2011
2012 // convert to upper case, return the copy of the string
2013 wxString wxString::Upper() const
2014 { wxString s(*this); return s.MakeUpper(); }
2015
2016 // convert to lower case, return the copy of the string
2017 wxString wxString::Lower() const { wxString s(*this); return s.MakeLower(); }
2018
2019 int wxString::sprintf(const wxChar *pszFormat, ...)
2020   {
2021     va_list argptr;
2022     va_start(argptr, pszFormat);
2023     int iLen = PrintfV(pszFormat, argptr);
2024     va_end(argptr);
2025     return iLen;
2026   }
2027
2028 // ============================================================================
2029 // ArrayString
2030 // ============================================================================
2031
2032 #include "wx/arrstr.h"
2033
2034 #if !wxUSE_STL
2035
2036 // size increment = min(50% of current size, ARRAY_MAXSIZE_INCREMENT)
2037 #define   ARRAY_MAXSIZE_INCREMENT       4096
2038
2039 #ifndef   ARRAY_DEFAULT_INITIAL_SIZE    // also defined in dynarray.h
2040 #define   ARRAY_DEFAULT_INITIAL_SIZE    (16)
2041 #endif
2042
2043 #define   STRING(p)   ((wxString *)(&(p)))
2044
2045 // ctor
2046 void wxArrayString::Init(bool autoSort)
2047 {
2048   m_nSize  =
2049   m_nCount = 0;
2050   m_pItems = (wxChar **) NULL;
2051   m_autoSort = autoSort;
2052 }
2053
2054 // copy ctor
2055 wxArrayString::wxArrayString(const wxArrayString& src)
2056 {
2057   Init(src.m_autoSort);
2058
2059   *this = src;
2060 }
2061
2062 // assignment operator
2063 wxArrayString& wxArrayString::operator=(const wxArrayString& src)
2064 {
2065   if ( m_nSize > 0 )
2066     Clear();
2067
2068   Copy(src);
2069
2070   m_autoSort = src.m_autoSort;
2071
2072   return *this;
2073 }
2074
2075 void wxArrayString::Copy(const wxArrayString& src)
2076 {
2077   if ( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE )
2078     Alloc(src.m_nCount);
2079
2080   for ( size_t n = 0; n < src.m_nCount; n++ )
2081     Add(src[n]);
2082 }
2083
2084 // grow the array
2085 void wxArrayString::Grow(size_t nIncrement)
2086 {
2087   // only do it if no more place
2088   if ( (m_nSize - m_nCount) < nIncrement ) {
2089     // if ARRAY_DEFAULT_INITIAL_SIZE were set to 0, the initially empty would
2090     // be never resized!
2091     #if ARRAY_DEFAULT_INITIAL_SIZE == 0
2092       #error "ARRAY_DEFAULT_INITIAL_SIZE must be > 0!"
2093     #endif
2094
2095     if ( m_nSize == 0 ) {
2096       // was empty, alloc some memory
2097       m_nSize = ARRAY_DEFAULT_INITIAL_SIZE;
2098       if (m_nSize < nIncrement)
2099           m_nSize = nIncrement;
2100       m_pItems = new wxChar *[m_nSize];
2101     }
2102     else {
2103       // otherwise when it's called for the first time, nIncrement would be 0
2104       // and the array would never be expanded
2105       // add 50% but not too much
2106       size_t ndefIncrement = m_nSize < ARRAY_DEFAULT_INITIAL_SIZE
2107                           ? ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
2108       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )
2109         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;
2110       if ( nIncrement < ndefIncrement )
2111         nIncrement = ndefIncrement;
2112       m_nSize += nIncrement;
2113       wxChar **pNew = new wxChar *[m_nSize];
2114
2115       // copy data to new location
2116       memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
2117
2118       // delete old memory (but do not release the strings!)
2119       wxDELETEA(m_pItems);
2120
2121       m_pItems = pNew;
2122     }
2123   }
2124 }
2125
2126 void wxArrayString::Free()
2127 {
2128   for ( size_t n = 0; n < m_nCount; n++ ) {
2129     STRING(m_pItems[n])->GetStringData()->Unlock();
2130   }
2131 }
2132
2133 // deletes all the strings from the list
2134 void wxArrayString::Empty()
2135 {
2136   Free();
2137
2138   m_nCount = 0;
2139 }
2140
2141 // as Empty, but also frees memory
2142 void wxArrayString::Clear()
2143 {
2144   Free();
2145
2146   m_nSize  =
2147   m_nCount = 0;
2148
2149   wxDELETEA(m_pItems);
2150 }
2151
2152 // dtor
2153 wxArrayString::~wxArrayString()
2154 {
2155   Free();
2156
2157   wxDELETEA(m_pItems);
2158 }
2159
2160 void wxArrayString::reserve(size_t nSize)
2161 {
2162     Alloc(nSize);
2163 }
2164
2165 // pre-allocates memory (frees the previous data!)
2166 void wxArrayString::Alloc(size_t nSize)
2167 {
2168   // only if old buffer was not big enough
2169   if ( nSize > m_nSize ) {
2170     Free();
2171     wxDELETEA(m_pItems);
2172     m_pItems = new wxChar *[nSize];
2173     m_nSize  = nSize;
2174   }
2175
2176   m_nCount = 0;
2177 }
2178
2179 // minimizes the memory usage by freeing unused memory
2180 void wxArrayString::Shrink()
2181 {
2182   // only do it if we have some memory to free
2183   if( m_nCount < m_nSize ) {
2184     // allocates exactly as much memory as we need
2185     wxChar **pNew = new wxChar *[m_nCount];
2186
2187     // copy data to new location
2188     memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
2189     delete [] m_pItems;
2190     m_pItems = pNew;
2191   }
2192 }
2193
2194 #if WXWIN_COMPATIBILITY_2_4
2195
2196 // return a wxString[] as required for some control ctors.
2197 wxString* wxArrayString::GetStringArray() const
2198 {
2199     wxString *array = 0;
2200
2201     if( m_nCount > 0 )
2202     {
2203         array = new wxString[m_nCount];
2204         for( size_t i = 0; i < m_nCount; i++ )
2205             array[i] = m_pItems[i];
2206     }
2207
2208     return array;
2209 }
2210
2211 void wxArrayString::Remove(size_t nIndex, size_t nRemove)
2212 {
2213     RemoveAt(nIndex, nRemove);
2214 }
2215
2216 #endif // WXWIN_COMPATIBILITY_2_4
2217
2218 // searches the array for an item (forward or backwards)
2219 int wxArrayString::Index(const wxChar *sz, bool bCase, bool bFromEnd) const
2220 {
2221   if ( m_autoSort ) {
2222     // use binary search in the sorted array
2223     wxASSERT_MSG( bCase && !bFromEnd,
2224                   wxT("search parameters ignored for auto sorted array") );
2225
2226     size_t i,
2227            lo = 0,
2228            hi = m_nCount;
2229     int res;
2230     while ( lo < hi ) {
2231       i = (lo + hi)/2;
2232
2233       res = wxStrcmp(sz, m_pItems[i]);
2234       if ( res < 0 )
2235         hi = i;
2236       else if ( res > 0 )
2237         lo = i + 1;
2238       else
2239         return i;
2240     }
2241
2242     return wxNOT_FOUND;
2243   }
2244   else {
2245     // use linear search in unsorted array
2246     if ( bFromEnd ) {
2247       if ( m_nCount > 0 ) {
2248         size_t ui = m_nCount;
2249         do {
2250           if ( STRING(m_pItems[--ui])->IsSameAs(sz, bCase) )
2251             return ui;
2252         }
2253         while ( ui != 0 );
2254       }
2255     }
2256     else {
2257       for( size_t ui = 0; ui < m_nCount; ui++ ) {
2258         if( STRING(m_pItems[ui])->IsSameAs(sz, bCase) )
2259           return ui;
2260       }
2261     }
2262   }
2263
2264   return wxNOT_FOUND;
2265 }
2266
2267 // add item at the end
2268 size_t wxArrayString::Add(const wxString& str, size_t nInsert)
2269 {
2270   if ( m_autoSort ) {
2271     // insert the string at the correct position to keep the array sorted
2272     size_t i,
2273            lo = 0,
2274            hi = m_nCount;
2275     int res;
2276     while ( lo < hi ) {
2277       i = (lo + hi)/2;
2278
2279       res = str.Cmp(m_pItems[i]);
2280       if ( res < 0 )
2281         hi = i;
2282       else if ( res > 0 )
2283         lo = i + 1;
2284       else {
2285         lo = hi = i;
2286         break;
2287       }
2288     }
2289
2290     wxASSERT_MSG( lo == hi, wxT("binary search broken") );
2291
2292     Insert(str, lo, nInsert);
2293
2294     return (size_t)lo;
2295   }
2296   else {
2297     wxASSERT( str.GetStringData()->IsValid() );
2298
2299     Grow(nInsert);
2300
2301     for (size_t i = 0; i < nInsert; i++)
2302     {
2303         // the string data must not be deleted!
2304         str.GetStringData()->Lock();
2305
2306         // just append
2307         m_pItems[m_nCount + i] = (wxChar *)str.c_str(); // const_cast
2308     }
2309     size_t ret = m_nCount;
2310     m_nCount += nInsert;
2311     return ret;
2312   }
2313 }
2314
2315 // add item at the given position
2316 void wxArrayString::Insert(const wxString& str, size_t nIndex, size_t nInsert)
2317 {
2318   wxASSERT( str.GetStringData()->IsValid() );
2319
2320   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
2321   wxCHECK_RET( m_nCount <= m_nCount + nInsert,
2322                wxT("array size overflow in wxArrayString::Insert") );
2323
2324   Grow(nInsert);
2325
2326   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],
2327           (m_nCount - nIndex)*sizeof(wxChar *));
2328
2329   for (size_t i = 0; i < nInsert; i++)
2330   {
2331       str.GetStringData()->Lock();
2332       m_pItems[nIndex + i] = (wxChar *)str.c_str();
2333   }
2334   m_nCount += nInsert;
2335 }
2336
2337 // range insert (STL 23.2.4.3)
2338 void
2339 wxArrayString::insert(iterator it, const_iterator first, const_iterator last)
2340 {
2341     const int idx = it - begin();
2342
2343     // grow it once
2344     Grow(last - first);
2345
2346     // reset "it" since it can change inside Grow()
2347     it = begin() + idx;
2348
2349     while ( first != last )
2350     {
2351         it = insert(it, *first);
2352
2353         // insert returns an iterator to the last element inserted but we need
2354         // insert the next after this one, that is before the next one
2355         ++it;
2356
2357         ++first;
2358     }
2359 }
2360
2361 // expand the array
2362 void wxArrayString::SetCount(size_t count)
2363 {
2364     Alloc(count);
2365
2366     wxString s;
2367     while ( m_nCount < count )
2368         m_pItems[m_nCount++] = (wxChar *)s.c_str();
2369 }
2370
2371 // removes item from array (by index)
2372 void wxArrayString::RemoveAt(size_t nIndex, size_t nRemove)
2373 {
2374   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArrayString::Remove") );
2375   wxCHECK_RET( nIndex + nRemove <= m_nCount,
2376                wxT("removing too many elements in wxArrayString::Remove") );
2377
2378   // release our lock
2379   for (size_t i = 0; i < nRemove; i++)
2380       Item(nIndex + i).GetStringData()->Unlock();
2381
2382   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],
2383           (m_nCount - nIndex - nRemove)*sizeof(wxChar *));
2384   m_nCount -= nRemove;
2385 }
2386
2387 // removes item from array (by value)
2388 void wxArrayString::Remove(const wxChar *sz)
2389 {
2390   int iIndex = Index(sz);
2391
2392   wxCHECK_RET( iIndex != wxNOT_FOUND,
2393                wxT("removing inexistent element in wxArrayString::Remove") );
2394
2395   RemoveAt(iIndex);
2396 }
2397
2398 void wxArrayString::assign(const_iterator first, const_iterator last)
2399 {
2400     reserve(last - first);
2401     for(; first != last; ++first)
2402         push_back(*first);
2403 }
2404
2405 // ----------------------------------------------------------------------------
2406 // sorting
2407 // ----------------------------------------------------------------------------
2408
2409 // we can only sort one array at a time with the quick-sort based
2410 // implementation
2411 #if wxUSE_THREADS
2412   // need a critical section to protect access to gs_compareFunction and
2413   // gs_sortAscending variables
2414   static wxCriticalSection *gs_critsectStringSort = NULL;
2415
2416   // call this before the value of the global sort vars is changed/after
2417   // you're finished with them
2418   #define START_SORT()     wxASSERT( !gs_critsectStringSort );                \
2419                            gs_critsectStringSort = new wxCriticalSection;     \
2420                            gs_critsectStringSort->Enter()
2421   #define END_SORT()       gs_critsectStringSort->Leave();                    \
2422                            delete gs_critsectStringSort;                      \
2423                            gs_critsectStringSort = NULL
2424 #else // !threads
2425   #define START_SORT()
2426   #define END_SORT()
2427 #endif // wxUSE_THREADS
2428
2429 // function to use for string comparaison
2430 static wxArrayString::CompareFunction gs_compareFunction = NULL;
2431
2432 // if we don't use the compare function, this flag tells us if we sort the
2433 // array in ascending or descending order
2434 static bool gs_sortAscending = true;
2435
2436 // function which is called by quick sort
2437 extern "C" int wxC_CALLING_CONV     // LINKAGEMODE
2438 wxStringCompareFunction(const void *first, const void *second)
2439 {
2440   wxString *strFirst = (wxString *)first;
2441   wxString *strSecond = (wxString *)second;
2442
2443   if ( gs_compareFunction ) {
2444     return gs_compareFunction(*strFirst, *strSecond);
2445   }
2446   else {
2447     // maybe we should use wxStrcoll
2448     int result = strFirst->Cmp(*strSecond);
2449
2450     return gs_sortAscending ? result : -result;
2451   }
2452 }
2453
2454 // sort array elements using passed comparaison function
2455 void wxArrayString::Sort(CompareFunction compareFunction)
2456 {
2457   START_SORT();
2458
2459   wxASSERT( !gs_compareFunction );  // must have been reset to NULL
2460   gs_compareFunction = compareFunction;
2461
2462   DoSort();
2463
2464   // reset it to NULL so that Sort(bool) will work the next time
2465   gs_compareFunction = NULL;
2466
2467   END_SORT();
2468 }
2469
2470 typedef  int (wxC_CALLING_CONV * wxStringCompareFn)(const void *first, const void *second);
2471
2472 void wxArrayString::Sort(CompareFunction2 compareFunction)
2473 {
2474   qsort(m_pItems, m_nCount, sizeof(wxChar *), (wxStringCompareFn)compareFunction);
2475 }
2476
2477 void wxArrayString::Sort(bool reverseOrder)
2478 {
2479   Sort(reverseOrder ? wxStringSortDescending : wxStringSortAscending);
2480 }
2481
2482 void wxArrayString::DoSort()
2483 {
2484   wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
2485
2486   // just sort the pointers using qsort() - of course it only works because
2487   // wxString() *is* a pointer to its data
2488   qsort(m_pItems, m_nCount, sizeof(wxChar *), wxStringCompareFunction);
2489 }
2490
2491 bool wxArrayString::operator==(const wxArrayString& a) const
2492 {
2493     if ( m_nCount != a.m_nCount )
2494         return false;
2495
2496     for ( size_t n = 0; n < m_nCount; n++ )
2497     {
2498         if ( Item(n) != a[n] )
2499             return false;
2500     }
2501
2502     return true;
2503 }
2504
2505 #endif // !wxUSE_STL
2506
2507 int wxCMPFUNC_CONV wxStringSortAscending(wxString* s1, wxString* s2)
2508 {
2509     return  s1->Cmp(*s2);
2510 }
2511
2512 int wxCMPFUNC_CONV wxStringSortDescending(wxString* s1, wxString* s2)
2513 {
2514     return -s1->Cmp(*s2);
2515 }