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