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