src/common/arrstr.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        src/common/arrstr.cpp
   3 // Purpose:     wxArrayString class
   4 // Author:      Vadim Zeitlin
   5 // Modified by:
   6 // Created:     29/01/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 // ===========================================================================
  13 // headers, declarations, constants
  14 // ===========================================================================
  15
  16 // For compilers that support precompilation, includes "wx.h".
  17 #include "wx/wxprec.h"
  18
  19 #ifdef __BORLANDC__
  20     #pragma hdrstop
  21 #endif
  22
  23 #include "wx/arrstr.h"
  24
  25 #include "wx/beforestd.h"
  26 #include <algorithm>
  27 #include <functional>
  28 #include "wx/afterstd.h"
  29
  30 // ============================================================================
  31 // ArrayString
  32 // ============================================================================
  33
  34 wxArrayString::wxArrayString(size_t sz, const char** a)
  35 {
  36 #if !wxUSE_STL
  37     Init(false);
  38 #endif
  39     for (size_t i=0; i < sz; i++)
  40         Add(a[i]);
  41 }
  42
  43 wxArrayString::wxArrayString(size_t sz, const wchar_t** a)
  44 {
  45 #if !wxUSE_STL
  46     Init(false);
  47 #endif
  48     for (size_t i=0; i < sz; i++)
  49         Add(a[i]);
  50 }
  51
  52 wxArrayString::wxArrayString(size_t sz, const wxString* a)
  53 {
  54 #if !wxUSE_STL
  55     Init(false);
  56 #endif
  57     for (size_t i=0; i < sz; i++)
  58         Add(a[i]);
  59 }
  60
  61 #if !wxUSE_STL
  62
  63 // size increment = min(50% of current size, ARRAY_MAXSIZE_INCREMENT)
  64 #define   ARRAY_MAXSIZE_INCREMENT       4096
  65
  66 #ifndef   ARRAY_DEFAULT_INITIAL_SIZE    // also defined in dynarray.h
  67 #define   ARRAY_DEFAULT_INITIAL_SIZE    (16)
  68 #endif
  69
  70 // ctor
  71 void wxArrayString::Init(bool autoSort)
  72 {
  73   m_nSize  =
  74   m_nCount = 0;
  75   m_pItems = NULL;
  76   m_autoSort = autoSort;
  77 }
  78
  79 // copy ctor
  80 wxArrayString::wxArrayString(const wxArrayString& src)
  81 {
  82   Init(src.m_autoSort);
  83
  84   *this = src;
  85 }
  86
  87 // assignment operator
  88 wxArrayString& wxArrayString::operator=(const wxArrayString& src)
  89 {
  90   if ( m_nSize > 0 )
  91     Clear();
  92
  93   Copy(src);
  94
  95   m_autoSort = src.m_autoSort;
  96
  97   return *this;
  98 }
  99
 100 void wxArrayString::Copy(const wxArrayString& src)
 101 {
 102   if ( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE )
 103     Alloc(src.m_nCount);
 104
 105   for ( size_t n = 0; n < src.m_nCount; n++ )
 106     Add(src[n]);
 107 }
 108
 109 // grow the array
 110 void wxArrayString::Grow(size_t nIncrement)
 111 {
 112   // only do it if no more place
 113   if ( (m_nSize - m_nCount) < nIncrement ) {
 114     // if ARRAY_DEFAULT_INITIAL_SIZE were set to 0, the initially empty would
 115     // be never resized!
 116     #if ARRAY_DEFAULT_INITIAL_SIZE == 0
 117       #error "ARRAY_DEFAULT_INITIAL_SIZE must be > 0!"
 118     #endif
 119
 120     if ( m_nSize == 0 ) {
 121       // was empty, alloc some memory
 122       m_nSize = ARRAY_DEFAULT_INITIAL_SIZE;
 123       if (m_nSize < nIncrement)
 124           m_nSize = nIncrement;
 125       m_pItems = new wxString[m_nSize];
 126     }
 127     else {
 128       // otherwise when it's called for the first time, nIncrement would be 0
 129       // and the array would never be expanded
 130       // add 50% but not too much
 131       size_t ndefIncrement = m_nSize < ARRAY_DEFAULT_INITIAL_SIZE
 132                           ? ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
 133       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )
 134         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;
 135       if ( nIncrement < ndefIncrement )
 136         nIncrement = ndefIncrement;
 137       m_nSize += nIncrement;
 138       wxString *pNew = new wxString[m_nSize];
 139
 140       // copy data to new location
 141       for ( size_t j = 0; j < m_nCount; j++ )
 142           pNew[j] = m_pItems[j];
 143
 144       // delete old memory (but do not release the strings!)
 145       delete [] m_pItems;
 146
 147       m_pItems = pNew;
 148     }
 149   }
 150 }
 151
 152 // deletes all the strings from the list
 153 void wxArrayString::Empty()
 154 {
 155   m_nCount = 0;
 156 }
 157
 158 // as Empty, but also frees memory
 159 void wxArrayString::Clear()
 160 {
 161   m_nSize  =
 162   m_nCount = 0;
 163
 164   wxDELETEA(m_pItems);
 165 }
 166
 167 // dtor
 168 wxArrayString::~wxArrayString()
 169 {
 170   delete [] m_pItems;
 171 }
 172
 173 void wxArrayString::reserve(size_t nSize)
 174 {
 175     Alloc(nSize);
 176 }
 177
 178 // pre-allocates memory (frees the previous data!)
 179 void wxArrayString::Alloc(size_t nSize)
 180 {
 181   // only if old buffer was not big enough
 182   if ( nSize > m_nSize ) {
 183     wxString *pNew = new wxString[nSize];
 184     if ( !pNew )
 185         return;
 186
 187     for ( size_t j = 0; j < m_nCount; j++ )
 188         pNew[j] = m_pItems[j];
 189     delete [] m_pItems;
 190
 191     m_pItems = pNew;
 192     m_nSize  = nSize;
 193   }
 194 }
 195
 196 // minimizes the memory usage by freeing unused memory
 197 void wxArrayString::Shrink()
 198 {
 199   // only do it if we have some memory to free
 200   if( m_nCount < m_nSize ) {
 201     // allocates exactly as much memory as we need
 202     wxString *pNew = new wxString[m_nCount];
 203
 204     // copy data to new location
 205     for ( size_t j = 0; j < m_nCount; j++ )
 206         pNew[j] = m_pItems[j];
 207     delete [] m_pItems;
 208     m_pItems = pNew;
 209     m_nSize = m_nCount;
 210   }
 211 }
 212
 213 // searches the array for an item (forward or backwards)
 214 int wxArrayString::Index(const wxString& str, bool bCase, bool bFromEnd) const
 215 {
 216   if ( m_autoSort ) {
 217     // use binary search in the sorted array
 218     wxASSERT_MSG( bCase && !bFromEnd,
 219                   wxT("search parameters ignored for auto sorted array") );
 220
 221     size_t i,
 222            lo = 0,
 223            hi = m_nCount;
 224     int res;
 225     while ( lo < hi ) {
 226       i = (lo + hi)/2;
 227
 228       res = str.compare(m_pItems[i]);
 229       if ( res < 0 )
 230         hi = i;
 231       else if ( res > 0 )
 232         lo = i + 1;
 233       else
 234         return i;
 235     }
 236
 237     return wxNOT_FOUND;
 238   }
 239   else {
 240     // use linear search in unsorted array
 241     if ( bFromEnd ) {
 242       if ( m_nCount > 0 ) {
 243         size_t ui = m_nCount;
 244         do {
 245           if ( m_pItems[--ui].IsSameAs(str, bCase) )
 246             return ui;
 247         }
 248         while ( ui != 0 );
 249       }
 250     }
 251     else {
 252       for( size_t ui = 0; ui < m_nCount; ui++ ) {
 253         if( m_pItems[ui].IsSameAs(str, bCase) )
 254           return ui;
 255       }
 256     }
 257   }
 258
 259   return wxNOT_FOUND;
 260 }
 261
 262 // add item at the end
 263 size_t wxArrayString::Add(const wxString& str, size_t nInsert)
 264 {
 265   if ( m_autoSort ) {
 266     // insert the string at the correct position to keep the array sorted
 267     size_t i,
 268            lo = 0,
 269            hi = m_nCount;
 270     int res;
 271     while ( lo < hi ) {
 272       i = (lo + hi)/2;
 273
 274       res = str.Cmp(m_pItems[i]);
 275       if ( res < 0 )
 276         hi = i;
 277       else if ( res > 0 )
 278         lo = i + 1;
 279       else {
 280         lo = hi = i;
 281         break;
 282       }
 283     }
 284
 285     wxASSERT_MSG( lo == hi, wxT("binary search broken") );
 286
 287     Insert(str, lo, nInsert);
 288
 289     return (size_t)lo;
 290   }
 291   else {
 292     Grow(nInsert);
 293
 294     for (size_t i = 0; i < nInsert; i++)
 295     {
 296         // just append
 297         m_pItems[m_nCount + i] = str;
 298     }
 299     size_t ret = m_nCount;
 300     m_nCount += nInsert;
 301     return ret;
 302   }
 303 }
 304
 305 // add item at the given position
 306 void wxArrayString::Insert(const wxString& str, size_t nIndex, size_t nInsert)
 307 {
 308   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
 309   wxCHECK_RET( m_nCount <= m_nCount + nInsert,
 310                wxT("array size overflow in wxArrayString::Insert") );
 311
 312   Grow(nInsert);
 313
 314   for (int j = m_nCount - nIndex - 1; j >= 0; j--)
 315       m_pItems[nIndex + nInsert + j] = m_pItems[nIndex + j];
 316
 317   for (size_t i = 0; i < nInsert; i++)
 318   {
 319       m_pItems[nIndex + i] = str;
 320   }
 321   m_nCount += nInsert;
 322 }
 323
 324 // range insert (STL 23.2.4.3)
 325 void
 326 wxArrayString::insert(iterator it, const_iterator first, const_iterator last)
 327 {
 328     const int idx = it - begin();
 329
 330     // grow it once
 331     Grow(last - first);
 332
 333     // reset "it" since it can change inside Grow()
 334     it = begin() + idx;
 335
 336     while ( first != last )
 337     {
 338         it = insert(it, *first);
 339
 340         // insert returns an iterator to the last element inserted but we need
 341         // insert the next after this one, that is before the next one
 342         ++it;
 343
 344         ++first;
 345     }
 346 }
 347
 348 void wxArrayString::resize(size_type n, value_type v)
 349 {
 350   if ( n < m_nCount )
 351       m_nCount = n;
 352   else if ( n > m_nCount )
 353       Add(v, n - m_nCount);
 354 }
 355
 356 // expand the array
 357 void wxArrayString::SetCount(size_t count)
 358 {
 359     Alloc(count);
 360
 361     wxString s;
 362     while ( m_nCount < count )
 363         m_pItems[m_nCount++] = s;
 364 }
 365
 366 // removes item from array (by index)
 367 void wxArrayString::RemoveAt(size_t nIndex, size_t nRemove)
 368 {
 369   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArrayString::Remove") );
 370   wxCHECK_RET( nIndex + nRemove <= m_nCount,
 371                wxT("removing too many elements in wxArrayString::Remove") );
 372
 373   for ( size_t j =  0; j < m_nCount - nIndex -nRemove; j++)
 374       m_pItems[nIndex + j] = m_pItems[nIndex + nRemove + j];
 375
 376   m_nCount -= nRemove;
 377 }
 378
 379 // removes item from array (by value)
 380 void wxArrayString::Remove(const wxString& sz)
 381 {
 382   int iIndex = Index(sz);
 383
 384   wxCHECK_RET( iIndex != wxNOT_FOUND,
 385                wxT("removing inexistent element in wxArrayString::Remove") );
 386
 387   RemoveAt(iIndex);
 388 }
 389
 390 // ----------------------------------------------------------------------------
 391 // sorting
 392 // ----------------------------------------------------------------------------
 393
 394 // we need an adaptor as our predicates use qsort() convention and so return
 395 // negative, null or positive value depending on whether the first item is less
 396 // than, equal to or greater than the other one while we need a real boolean
 397 // predicate now that we use std::sort()
 398 struct wxSortPredicateAdaptor
 399 {
 400     wxSortPredicateAdaptor(wxArrayString::CompareFunction compareFunction)
 401         : m_compareFunction(compareFunction)
 402     {
 403     }
 404
 405     bool operator()(const wxString& first, const wxString& second) const
 406     {
 407         return (*m_compareFunction)(first, second) < 0;
 408     }
 409
 410     wxArrayString::CompareFunction m_compareFunction;
 411 };
 412
 413 void wxArrayString::Sort(CompareFunction compareFunction)
 414 {
 415     wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
 416
 417     std::sort(m_pItems, m_pItems + m_nCount,
 418                 wxSortPredicateAdaptor(compareFunction));
 419 }
 420
 421 struct wxSortPredicateAdaptor2
 422 {
 423     wxSortPredicateAdaptor2(wxArrayString::CompareFunction2 compareFunction)
 424         : m_compareFunction(compareFunction)
 425     {
 426     }
 427
 428     bool operator()(const wxString& first, const wxString& second) const
 429     {
 430         return (*m_compareFunction)(const_cast<wxString *>(&first),
 431                                     const_cast<wxString *>(&second)) < 0;
 432     }
 433
 434     wxArrayString::CompareFunction2 m_compareFunction;
 435 };
 436
 437 void wxArrayString::Sort(CompareFunction2 compareFunction)
 438 {
 439     std::sort(m_pItems, m_pItems + m_nCount,
 440                 wxSortPredicateAdaptor2(compareFunction));
 441 }
 442
 443 void wxArrayString::Sort(bool reverseOrder)
 444 {
 445     if ( reverseOrder )
 446         std::sort(m_pItems, m_pItems + m_nCount, std::greater<wxString>());
 447     else // normal sort
 448         std::sort(m_pItems, m_pItems + m_nCount);
 449 }
 450
 451 bool wxArrayString::operator==(const wxArrayString& a) const
 452 {
 453     if ( m_nCount != a.m_nCount )
 454         return false;
 455
 456     for ( size_t n = 0; n < m_nCount; n++ )
 457     {
 458         if ( Item(n) != a[n] )
 459             return false;
 460     }
 461
 462     return true;
 463 }
 464
 465 #endif // !wxUSE_STL
 466
 467 // ===========================================================================
 468 // wxJoin and wxSplit
 469 // ===========================================================================
 470
 471 #include "wx/tokenzr.h"
 472
 473 wxString wxJoin(const wxArrayString& arr, const wxChar sep, const wxChar escape)
 474 {
 475     size_t count = arr.size();
 476     if ( count == 0 )
 477         return wxEmptyString;
 478
 479     wxString str;
 480
 481     // pre-allocate memory using the estimation of the average length of the
 482     // strings in the given array: this is very imprecise, of course, but
 483     // better than nothing
 484     str.reserve(count*(arr[0].length() + arr[count-1].length()) / 2);
 485
 486     if ( escape == wxT('\0') )
 487     {
 488         // escaping is disabled:
 489         for ( size_t i = 0; i < count; i++ )
 490         {
 491             if ( i )
 492                 str += sep;
 493             str += arr[i];
 494         }
 495     }
 496     else // use escape character
 497     {
 498         for ( size_t n = 0; n < count; n++ )
 499         {
 500             if ( n )
 501                 str += sep;
 502
 503             for ( wxString::const_iterator i = arr[n].begin(),
 504                                          end = arr[n].end();
 505                   i != end;
 506                   ++i )
 507             {
 508                 const wxChar ch = *i;
 509                 if ( ch == sep )
 510                     str += escape;      // escape this separator
 511                 str += ch;
 512             }
 513         }
 514     }
 515
 516     str.Shrink(); // release extra memory if we allocated too much
 517     return str;
 518 }
 519
 520 wxArrayString wxSplit(const wxString& str, const wxChar sep, const wxChar escape)
 521 {
 522     if ( escape == wxT('\0') )
 523     {
 524         // simple case: we don't need to honour the escape character
 525         return wxStringTokenize(str, sep, wxTOKEN_RET_EMPTY_ALL);
 526     }
 527
 528     wxArrayString ret;
 529     wxString curr;
 530     wxChar prev = wxT('\0');
 531
 532     for ( wxString::const_iterator i = str.begin(),
 533                                  end = str.end();
 534           i != end;
 535           ++i )
 536     {
 537         const wxChar ch = *i;
 538
 539         if ( ch == sep )
 540         {
 541             if ( prev == escape )
 542             {
 543                 // remove the escape character and don't consider this
 544                 // occurrence of 'sep' as a real separator
 545                 *curr.rbegin() = sep;
 546             }
 547             else // real separator
 548             {
 549                 ret.push_back(curr);
 550                 curr.clear();
 551             }
 552         }
 553         else // normal character
 554         {
 555             curr += ch;
 556         }
 557
 558         prev = ch;
 559     }
 560
 561     // add the last token
 562     if ( !curr.empty() || prev == sep )
 563         ret.Add(curr);
 564
 565     return ret;
 566 }