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