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