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