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