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