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