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