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