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 // expand the array
 349 void wxArrayString::SetCount(size_t count)
 350 {
 351     Alloc(count);
 352
 353     wxString s;
 354     while ( m_nCount < count )
 355         m_pItems[m_nCount++] = s;
 356 }
 357
 358 // removes item from array (by index)
 359 void wxArrayString::RemoveAt(size_t nIndex, size_t nRemove)
 360 {
 361   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArrayString::Remove") );
 362   wxCHECK_RET( nIndex + nRemove <= m_nCount,
 363                wxT("removing too many elements in wxArrayString::Remove") );
 364
 365   for ( size_t j =  0; j < m_nCount - nIndex -nRemove; j++)
 366       m_pItems[nIndex + j] = m_pItems[nIndex + nRemove + j];
 367
 368   m_nCount -= nRemove;
 369 }
 370
 371 // removes item from array (by value)
 372 void wxArrayString::Remove(const wxString& sz)
 373 {
 374   int iIndex = Index(sz);
 375
 376   wxCHECK_RET( iIndex != wxNOT_FOUND,
 377                wxT("removing inexistent element in wxArrayString::Remove") );
 378
 379   RemoveAt(iIndex);
 380 }
 381
 382 // ----------------------------------------------------------------------------
 383 // sorting
 384 // ----------------------------------------------------------------------------
 385
 386 // we need an adaptor as our predicates use qsort() convention and so return
 387 // negative, null or positive value depending on whether the first item is less
 388 // than, equal to or greater than the other one while we need a real boolean
 389 // predicate now that we use std::sort()
 390 struct wxSortPredicateAdaptor
 391 {
 392     wxSortPredicateAdaptor(wxArrayString::CompareFunction compareFunction)
 393         : m_compareFunction(compareFunction)
 394     {
 395     }
 396
 397     bool operator()(const wxString& first, const wxString& second) const
 398     {
 399         return (*m_compareFunction)(first, second) < 0;
 400     }
 401
 402     wxArrayString::CompareFunction m_compareFunction;
 403 };
 404
 405 void wxArrayString::Sort(CompareFunction compareFunction)
 406 {
 407     wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
 408
 409     std::sort(m_pItems, m_pItems + m_nCount,
 410                 wxSortPredicateAdaptor(compareFunction));
 411 }
 412
 413 struct wxSortPredicateAdaptor2
 414 {
 415     wxSortPredicateAdaptor2(wxArrayString::CompareFunction2 compareFunction)
 416         : m_compareFunction(compareFunction)
 417     {
 418     }
 419
 420     bool operator()(const wxString& first, const wxString& second) const
 421     {
 422         return (*m_compareFunction)(const_cast<wxString *>(&first),
 423                                     const_cast<wxString *>(&second)) < 0;
 424     }
 425
 426     wxArrayString::CompareFunction2 m_compareFunction;
 427 };
 428
 429 void wxArrayString::Sort(CompareFunction2 compareFunction)
 430 {
 431     std::sort(m_pItems, m_pItems + m_nCount,
 432                 wxSortPredicateAdaptor2(compareFunction));
 433 }
 434
 435 void wxArrayString::Sort(bool reverseOrder)
 436 {
 437     if ( reverseOrder )
 438         std::sort(m_pItems, m_pItems + m_nCount, std::greater<wxString>());
 439     else // normal sort
 440         std::sort(m_pItems, m_pItems + m_nCount);
 441 }
 442
 443 bool wxArrayString::operator==(const wxArrayString& a) const
 444 {
 445     if ( m_nCount != a.m_nCount )
 446         return false;
 447
 448     for ( size_t n = 0; n < m_nCount; n++ )
 449     {
 450         if ( Item(n) != a[n] )
 451             return false;
 452     }
 453
 454     return true;
 455 }
 456
 457 #endif // !wxUSE_STL
 458
 459 // ===========================================================================
 460 // wxJoin and wxSplit
 461 // ===========================================================================
 462
 463 #include "wx/tokenzr.h"
 464
 465 wxString wxJoin(const wxArrayString& arr, const wxChar sep, const wxChar escape)
 466 {
 467     size_t count = arr.size();
 468     if ( count == 0 )
 469         return wxEmptyString;
 470
 471     wxString str;
 472
 473     // pre-allocate memory using the estimation of the average length of the
 474     // strings in the given array: this is very imprecise, of course, but
 475     // better than nothing
 476     str.reserve(count*(arr[0].length() + arr[count-1].length()) / 2);
 477
 478     if ( escape == wxT('\0') )
 479     {
 480         // escaping is disabled:
 481         for ( size_t i = 0; i < count; i++ )
 482         {
 483             if ( i )
 484                 str += sep;
 485             str += arr[i];
 486         }
 487     }
 488     else // use escape character
 489     {
 490         for ( size_t n = 0; n < count; n++ )
 491         {
 492             if ( n )
 493                 str += sep;
 494
 495             for ( wxString::const_iterator i = arr[n].begin(),
 496                                          end = arr[n].end();
 497                   i != end;
 498                   ++i )
 499             {
 500                 const wxChar ch = *i;
 501                 if ( ch == sep )
 502                     str += escape;      // escape this separator
 503                 str += ch;
 504             }
 505         }
 506     }
 507
 508     str.Shrink(); // release extra memory if we allocated too much
 509     return str;
 510 }
 511
 512 wxArrayString wxSplit(const wxString& str, const wxChar sep, const wxChar escape)
 513 {
 514     if ( escape == wxT('\0') )
 515     {
 516         // simple case: we don't need to honour the escape character
 517         return wxStringTokenize(str, sep, wxTOKEN_RET_EMPTY_ALL);
 518     }
 519
 520     wxArrayString ret;
 521     wxString curr;
 522     wxChar prev = wxT('\0');
 523
 524     for ( wxString::const_iterator i = str.begin(),
 525                                  end = str.end();
 526           i != end;
 527           ++i )
 528     {
 529         const wxChar ch = *i;
 530
 531         if ( ch == sep )
 532         {
 533             if ( prev == escape )
 534             {
 535                 // remove the escape character and don't consider this
 536                 // occurrence of 'sep' as a real separator
 537                 *curr.rbegin() = sep;
 538             }
 539             else // real separator
 540             {
 541                 ret.push_back(curr);
 542                 curr.clear();
 543             }
 544         }
 545         else // normal character
 546         {
 547             curr += ch;
 548         }
 549
 550         prev = ch;
 551     }
 552
 553     // add the last token
 554     if ( !curr.empty() || prev == sep )
 555         ret.Add(curr);
 556
 557     return ret;
 558 }