]> git.saurik.com Git - wxWidgets.git/blob - src/common/arrstr.cpp
Eliminate a warning
[wxWidgets.git] / 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 }