]> git.saurik.com Git - wxWidgets.git/blob - src/common/dynarray.cpp
projects / wxWidgets.git / blob
? search:


3f8fa81887ae6f040754407f8b8e2659d6333606
[wxWidgets.git] / src / common / dynarray.cpp
1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: dynarray.cpp
3 // Purpose: implementation of wxBaseArray class
4 // Author: Vadim Zeitlin
5 // Modified by:
6 // Created: 12.09.97
7 // RCS-ID: $Id$
8 // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
11
12 // ============================================================================
13 // headers
14 // ============================================================================
15
16 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
17 #pragma implementation "dynarray.h"
18 #endif
19
20 #include "wx/wxprec.h"
21
22 #ifdef __BORLANDC__
23 #pragma hdrstop
24 #endif
25
26 #include "wx/dynarray.h"
27 #include "wx/intl.h"
28
29 #include <stdlib.h>
30 #include <string.h> // for memmove
31
32 // we cast the value to long from which we cast it to void * in IndexForInsert:
33 // this can't work if the pointers are not big enough
34 wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr) <= sizeof(void *),
35 wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
36
37 // ============================================================================
38 // constants
39 // ============================================================================
40
41 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
42 #define ARRAY_MAXSIZE_INCREMENT 4096
43
44 // ============================================================================
45 // implementation
46 // ============================================================================
47
48 // ----------------------------------------------------------------------------
49 // wxBaseArray - dynamic array of 'T's
50 // ----------------------------------------------------------------------------
51
52 #define _WX_DEFINE_BASEARRAY_COMMON(T, name) \
53 /* searches the array for an item (forward or backwards) */ \
54 int name::Index(T lItem, bool bFromEnd) const \
55 { \
56 if ( bFromEnd ) { \
57 if ( size() > 0 ) { \
58 size_t n = size(); \
59 do { \
60 if ( (*this)[--n] == lItem ) \
61 return n; \
62 } \
63 while ( n != 0 ); \
64 } \
65 } \
66 else { \
67 for( size_t n = 0; n < size(); n++ ) { \
68 if( (*this)[n] == lItem ) \
69 return n; \
70 } \
71 } \
72 \
73 return wxNOT_FOUND; \
74 } \
75 \
76 /* add item assuming the array is sorted with fnCompare function */ \
77 size_t name::Add(T lItem, CMPFUNC fnCompare) \
78 { \
79 size_t idx = IndexForInsert(lItem, fnCompare); \
80 Insert(lItem, idx); \
81 return idx; \
82 }
83
84 #if wxUSE_STL
85
86 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
87 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
88 { \
89 Predicate p((SCMPFUNC)fnCompare); \
90 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
91 return it - begin(); \
92 } \
93 \
94 int name::Index(T lItem, CMPFUNC fnCompare) const \
95 { \
96 Predicate p((SCMPFUNC)fnCompare); \
97 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
98 return (it != end() && !p(lItem, *it)) ? \
99 (int)(it - begin()) : wxNOT_FOUND; \
100 } \
101 \
102 void name::Shrink() \
103 { \
104 name tmp(*this); \
105 swap(tmp); \
106 }
107
108 #else // if !wxUSE_STL
109
110 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
111 /* ctor */ \
112 name::name() \
113 { \
114 m_nSize = \
115 m_nCount = 0; \
116 m_pItems = (T *)NULL; \
117 } \
118 \
119 /* copy ctor */ \
120 name::name(const name& src) \
121 { \
122 m_nSize = /* not src.m_nSize to save memory */ \
123 m_nCount = src.m_nCount; \
124 \
125 if ( m_nSize != 0 ) { \
126 m_pItems = new T[m_nSize]; \
127 /* only copy if allocation succeeded */ \
128 if ( m_pItems ) { \
129 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
130 } \
131 else { \
132 m_nSize = 0; \
133 } \
134 } \
135 else \
136 m_pItems = (T *) NULL; \
137 } \
138 \
139 /* assignment operator */ \
140 name& name::operator=(const name& src) \
141 { \
142 wxDELETEA(m_pItems); \
143 \
144 m_nSize = /* not src.m_nSize to save memory */ \
145 m_nCount = src.m_nCount; \
146 \
147 if ( m_nSize != 0 ){ \
148 m_pItems = new T[m_nSize]; \
149 /* only copy if allocation succeeded */ \
150 if ( m_pItems ) { \
151 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
152 } \
153 else { \
154 m_nSize = 0; \
155 } \
156 } \
157 else \
158 m_pItems = (T *) NULL; \
159 \
160 return *this; \
161 } \
162 \
163 /* allocate new buffer of the given size and move our data to it */ \
164 bool name::Realloc(size_t nSize) \
165 { \
166 T *pNew = new T[nSize]; \
167 /* only grow if allocation succeeded */ \
168 if ( !pNew ) \
169 return false; \
170 \
171 m_nSize = nSize; \
172 /* copy data to new location */ \
173 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
174 delete [] m_pItems; \
175 m_pItems = pNew; \
176 \
177 return true; \
178 } \
179 \
180 /* grow the array */ \
181 void name::Grow(size_t nIncrement) \
182 { \
183 /* only do it if no more place */ \
184 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
185 if( m_nSize == 0 ) { \
186 /* was empty, determine initial size */ \
187 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
188 if (size < nIncrement) size = nIncrement; \
189 /* allocate some memory */ \
190 m_pItems = new T[size]; \
191 /* only grow if allocation succeeded */ \
192 if ( m_pItems ) { \
193 m_nSize = size; \
194 } \
195 } \
196 else \
197 { \
198 /* add at least 50% but not too much */ \
199 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
200 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
201 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
202 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
203 if ( nIncrement < ndefIncrement ) \
204 nIncrement = ndefIncrement; \
205 Realloc(m_nSize + nIncrement); \
206 } \
207 } \
208 } \
209 \
210 /* make sure that the array has at least count elements */ \
211 void name::SetCount(size_t count, T defval) \
212 { \
213 if ( m_nSize < count ) \
214 { \
215 /* need to realloc memory: don't overallocate it here as if */ \
216 /* SetCount() is called, it probably means that the caller */ \
217 /* knows in advance how many elements there will be in the */ \
218 /* array and so it won't be necessary to realloc it later */ \
219 if ( !Realloc(count) ) \
220 { \
221 /* out of memory -- what can we do? */ \
222 return; \
223 } \
224 } \
225 \
226 /* add new elements if we extend the array */ \
227 while ( m_nCount < count ) \
228 { \
229 m_pItems[m_nCount++] = defval; \
230 } \
231 } \
232 \
233 /* dtor */ \
234 name::~name() \
235 { \
236 wxDELETEA(m_pItems); \
237 } \
238 \
239 /* clears the list */ \
240 void name::Clear() \
241 { \
242 m_nSize = \
243 m_nCount = 0; \
244 \
245 wxDELETEA(m_pItems); \
246 } \
247 \
248 /* pre-allocates memory (frees the previous data!) */ \
249 void name::Alloc(size_t nSize) \
250 { \
251 /* only if old buffer was not big enough */ \
252 if ( nSize > m_nSize ) { \
253 wxDELETEA(m_pItems); \
254 m_nSize = 0; \
255 m_pItems = new T[nSize]; \
256 /* only alloc if allocation succeeded */ \
257 if ( m_pItems ) { \
258 m_nSize = nSize; \
259 } \
260 } \
261 \
262 m_nCount = 0; \
263 } \
264 \
265 /* minimizes the memory usage by freeing unused memory */ \
266 void name::Shrink() \
267 { \
268 /* only do it if we have some memory to free */ \
269 if( m_nCount < m_nSize ) { \
270 /* allocates exactly as much memory as we need */ \
271 T *pNew = new T[m_nCount]; \
272 /* only shrink if allocation succeeded */ \
273 if ( pNew ) { \
274 /* copy data to new location */ \
275 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
276 delete [] m_pItems; \
277 m_pItems = pNew; \
278 \
279 /* update the size of the new block */ \
280 m_nSize = m_nCount; \
281 } \
282 /* else: don't do anything, better keep old memory block! */ \
283 } \
284 } \
285 \
286 /* add item at the end */ \
287 void name::Add(T lItem, size_t nInsert) \
288 { \
289 if (nInsert == 0) \
290 return; \
291 Grow(nInsert); \
292 for (size_t i = 0; i < nInsert; i++) \
293 m_pItems[m_nCount++] = lItem; \
294 } \
295 \
296 /* add item at the given position */ \
297 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
298 { \
299 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
300 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
301 wxT("array size overflow in wxArray::Insert") ); \
302 \
303 if (nInsert == 0) \
304 return; \
305 Grow(nInsert); \
306 \
307 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
308 (m_nCount - nIndex)*sizeof(T)); \
309 for (size_t i = 0; i < nInsert; i++) \
310 m_pItems[nIndex + i] = lItem; \
311 m_nCount += nInsert; \
312 } \
313 \
314 /* search for a place to insert item into sorted array (binary search) */ \
315 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
316 { \
317 size_t i, \
318 lo = 0, \
319 hi = m_nCount; \
320 int res; \
321 \
322 while ( lo < hi ) { \
323 i = (lo + hi)/2; \
324 \
325 res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \
326 (const void *)(wxUIntPtr)(m_pItems[i])); \
327 if ( res < 0 ) \
328 hi = i; \
329 else if ( res > 0 ) \
330 lo = i + 1; \
331 else { \
332 lo = i; \
333 break; \
334 } \
335 } \
336 \
337 return lo; \
338 } \
339 \
340 /* search for an item in a sorted array (binary search) */ \
341 int name::Index(T lItem, CMPFUNC fnCompare) const \
342 { \
343 size_t n = IndexForInsert(lItem, fnCompare); \
344 \
345 return (n >= m_nCount || \
346 (*fnCompare)((const void *)(wxUIntPtr)lItem, \
347 ((const void *)(wxUIntPtr)m_pItems[n]))) \
348 ? wxNOT_FOUND \
349 : (int)n; \
350 } \
351 \
352 /* removes item from array (by index) */ \
353 void name::RemoveAt(size_t nIndex, size_t nRemove) \
354 { \
355 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
356 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
357 wxT("removing too many elements in wxArray::RemoveAt") ); \
358 \
359 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
360 (m_nCount - nIndex - nRemove)*sizeof(T)); \
361 m_nCount -= nRemove; \
362 } \
363 \
364 /* removes item from array (by value) */ \
365 void name::Remove(T lItem) \
366 { \
367 int iIndex = Index(lItem); \
368 \
369 wxCHECK_RET( iIndex != wxNOT_FOUND, \
370 wxT("removing inexistent item in wxArray::Remove") ); \
371 \
372 RemoveAt((size_t)iIndex); \
373 } \
374 \
375 /* sort array elements using passed comparaison function */ \
376 void name::Sort(CMPFUNC fCmp) \
377 { \
378 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
379 } \
380 \
381 void name::assign(const_iterator first, const_iterator last) \
382 { \
383 clear(); \
384 reserve(last - first); \
385 for(; first != last; ++first) \
386 push_back(*first); \
387 } \
388 \
389 void name::assign(size_type n, const_reference v) \
390 { \
391 clear(); \
392 reserve(n); \
393 for( size_type i = 0; i < n; ++i ) \
394 push_back(v); \
395 } \
396 \
397 void name::insert(iterator it, const_iterator first, const_iterator last) \
398 { \
399 size_t nInsert = last - first, nIndex = it - begin(); \
400 if (nInsert == 0) \
401 return; \
402 Grow(nInsert); \
403 \
404 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
405 (m_nCount - nIndex)*sizeof(T)); \
406 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
407 *it = *first; \
408 m_nCount += nInsert; \
409 }
410
411 #endif
412
413 #define _WX_DEFINE_BASEARRAY(T, name) \
414 _WX_DEFINE_BASEARRAY_COMMON(T, name) \
415 _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)
416
417 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
418 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
419 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
420 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
421 _WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT)
422 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
423
424 #if wxUSE_STL
425 #include "wx/arrstr.h"
426
427 #include "wx/beforestd.h"
428 #include <functional>
429 #include "wx/afterstd.h"
430
431 _WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase);
432
433 // some compilers (Sun CC being the only known example) distinguish between
434 // extern "C" functions and the functions with C++ linkage and ptr_fun and
435 // wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in
436 // this case, we need the wrappers below to make this work
437 inline int wxStrcmpCppWrapper(const wxChar *p, const wxChar *q)
438 {
439 return wxStrcmp(p, q);
440 }
441
442 inline int wxStricmpCppWrapper(const wxChar *p, const wxChar *q)
443 {
444 return wxStricmp(p, q);
445 }
446
447 int wxArrayString::Index(const wxChar* sz, bool bCase, bool WXUNUSED(bFromEnd)) const
448 {
449 wxArrayString::const_iterator it;
450
451 if (bCase)
452 {
453 it = std::find_if(begin(), end(),
454 std::not1(
455 std::bind2nd(
456 std::ptr_fun(wxStrcmpCppWrapper), sz)));
457 }
458 else // !bCase
459 {
460 it = std::find_if(begin(), end(),
461 std::not1(
462 std::bind2nd(
463 std::ptr_fun(wxStricmpCppWrapper), sz)));
464 }
465
466 return it == end() ? wxNOT_FOUND : it - begin();
467 }
468
469 template<class F>
470 class wxStringCompareLess
471 {
472 public:
473 wxStringCompareLess(F f) : m_f(f) { }
474 bool operator()(const wxChar* s1, const wxChar* s2)
475 { return m_f(s1, s2) < 0; }
476 bool operator()(const wxString& s1, const wxString& s2)
477 { return m_f(s1, s2) < 0; }
478 private:
479 F m_f;
480 };
481
482 template<class F>
483 wxStringCompareLess<F> wxStringCompare(F f)
484 {
485 return wxStringCompareLess<F>(f);
486 }
487
488 void wxArrayString::Sort(CompareFunction function)
489 {
490 std::sort(begin(), end(), wxStringCompare(function));
491 }
492
493 void wxArrayString::Sort(bool reverseOrder)
494 {
495 if (reverseOrder)
496 {
497 std::sort(begin(), end(), std::greater<wxString>());
498 }
499 else
500 {
501 std::sort(begin(), end());
502 }
503 }
504
505 int wxSortedArrayString::Index(const wxChar* sz, bool bCase, bool WXUNUSED(bFromEnd)) const
506 {
507 wxSortedArrayString::const_iterator it;
508 wxString s(sz);
509
510 if (bCase)
511 it = std::lower_bound(begin(), end(), s,
512 wxStringCompare(wxStrcmpCppWrapper));
513 else
514 it = std::lower_bound(begin(), end(), s,
515 wxStringCompare(wxStricmpCppWrapper));
516
517 if (it == end())
518 return wxNOT_FOUND;
519
520 if (bCase)
521 {
522 if (wxStrcmp(it->c_str(), sz) != 0)
523 return wxNOT_FOUND;
524 }
525 else
526 {
527 if (wxStricmp(it->c_str(), sz) != 0)
528 return wxNOT_FOUND;
529 }
530
531 return it - begin();
532 }
533
534 #endif
wxWidgets (Impactor)