1 ///////////////////////////////////////////////////////////////////////////////
3 // Purpose: auto-resizable (i.e. dynamic) array support
4 // Author: Vadim Zeitlin
8 // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
15 #if defined(__GNUG__) && !defined(__APPLE__) && \
16 !(defined(__MINGW32__) && __GNUC__ == 3 && __GNUC_MINOR__ == 2)
17 #pragma interface "dynarray.h"
23 #include "wx/beforestd.h"
26 #include "wx/afterstd.h"
30 This header defines the dynamic arrays and object arrays (i.e. arrays which
31 own their elements). Dynamic means that the arrays grow automatically as
34 These macros are ugly (especially if you look in the sources ;-), but they
35 allow us to define "template" classes without actually using templates and so
36 this works with all compilers (and may be also much faster to compile even
37 with a compiler which does support templates). The arrays defined with these
40 Range checking is performed in debug build for both arrays and objarrays but
41 not in release build - so using an invalid index will just lead to a crash
44 Note about memory usage: arrays never shrink automatically (although you may
45 use Shrink() function explicitly), they only grow, so loading 10 millions in
46 an array only to delete them 2 lines below might be a bad idea if the array
47 object is not going to be destroyed soon. However, as it does free memory
48 when destroyed, it is ok if the array is a local variable.
51 // ----------------------------------------------------------------------------
53 // ----------------------------------------------------------------------------
56 The initial size by which an array grows when an element is added default
57 value avoids allocate one or two bytes when the array is created which is
60 #define WX_ARRAY_DEFAULT_INITIAL_SIZE (16)
62 // ----------------------------------------------------------------------------
64 // ----------------------------------------------------------------------------
67 Callback compare function for quick sort.
69 It must return negative value, 0 or positive value if the first item is
70 less than, equal to or greater than the second one.
74 typedef int (wxCMPFUNC_CONV
*CMPFUNC
)(const void* pItem1
, const void* pItem2
);
77 // ----------------------------------------------------------------------------
78 // Base class managing data having size of type 'long' (not used directly)
80 // NB: for efficiency this often used class has no virtual functions (hence no
81 // virtual table), even dtor is *not* virtual. If used as expected it
82 // won't create any problems because ARRAYs from DEFINE_ARRAY have no dtor
83 // at all, so it's not too important if it's not called (this happens when
84 // you cast "SomeArray *" as "BaseArray *" and then delete it)
85 // ----------------------------------------------------------------------------
90 class WXDLLIMPEXP_BASE wxArray_SortFunction
93 typedef int (wxCMPFUNC_CONV
*CMPFUNC
)(T
* pItem1
, T
* pItem2
);
95 wxArray_SortFunction(CMPFUNC f
) : m_f(f
) { }
96 bool operator()(const T
& i1
, const T
& i2
)
97 { return m_f((T
*)&i1
, (T
*)&i2
) < 0; }
102 template<class T
, typename F
>
103 class WXDLLIMPEXP_BASE wxSortedArray_SortFunction
108 wxSortedArray_SortFunction(CMPFUNC f
) : m_f(f
) { }
109 bool operator()(const T
& i1
, const T
& i2
)
110 { return m_f(i1
, i2
) < 0; }
115 #define _WX_DECLARE_BASEARRAY(T, name, classexp) \
116 typedef int (wxCMPFUNC_CONV *CMPFUN##name)(T pItem1, T pItem2); \
117 typedef wxSortedArray_SortFunction<T, CMPFUN##name> name##_Predicate; \
118 _WX_DECLARE_BASEARRAY_2(T, name, name##_Predicate, classexp)
120 #define _WX_DECLARE_BASEARRAY_2(T, name, predicate, classexp) \
121 classexp name : public std::vector<T> \
123 typedef predicate Predicate; \
124 typedef predicate::CMPFUNC SCMPFUNC; \
125 typedef wxArray_SortFunction<T>::CMPFUNC CMPFUNC; \
127 void Empty() { clear(); } \
128 void Clear() { clear(); } \
129 void Alloc(size_t uiSize) { reserve(uiSize); } \
132 size_t GetCount() const { return size(); } \
133 void SetCount(size_t n, T v = T()) { resize(n, v); } \
134 bool IsEmpty() const { return empty(); } \
135 size_t Count() const { return size(); } \
137 typedef T base_type; \
140 T& Item(size_t uiIndex) const \
141 { wxASSERT( uiIndex < size() ); return (T&)operator[](uiIndex); } \
143 int Index(T e, bool bFromEnd = FALSE) const; \
144 int Index(T lItem, CMPFUNC fnCompare) const; \
145 size_t IndexForInsert(T lItem, CMPFUNC fnCompare) const; \
146 void Add(T lItem, size_t nInsert = 1) \
147 { insert(end(), nInsert, lItem); } \
148 size_t Add(T lItem, CMPFUNC fnCompare); \
149 void Insert(T lItem, size_t uiIndex, size_t nInsert = 1) \
150 { insert(begin() + uiIndex, nInsert, lItem); } \
151 void Remove(T lItem); \
152 void RemoveAt(size_t uiIndex, size_t nRemove = 1) \
153 { erase(begin() + uiIndex, begin() + uiIndex + nRemove); } \
155 void Sort(CMPFUNC fCmp) \
157 wxArray_SortFunction<T> p(fCmp); \
158 std::sort(begin(), end(), p); \
162 #else // if !wxUSE_STL
164 #define _WX_DECLARE_BASEARRAY(T, name, classexp) \
167 typedef CMPFUNC SCMPFUNC; /* for compatibility wuth wxUSE_STL */ \
170 name(const name& array); \
171 name& operator=(const name& src); \
174 void Empty() { m_nCount = 0; } \
176 void Alloc(size_t uiSize); \
179 size_t GetCount() const { return m_nCount; } \
180 void SetCount(size_t n, T defval = T(0)); \
181 bool IsEmpty() const { return m_nCount == 0; } \
182 size_t Count() const { return m_nCount; } \
184 typedef T base_type; \
187 T& Item(size_t uiIndex) const \
188 { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; } \
189 T& operator[](size_t uiIndex) const { return Item(uiIndex); } \
191 int Index(T lItem, bool bFromEnd = FALSE) const; \
192 int Index(T lItem, CMPFUNC fnCompare) const; \
193 size_t IndexForInsert(T lItem, CMPFUNC fnCompare) const; \
194 void Add(T lItem, size_t nInsert = 1); \
195 size_t Add(T lItem, CMPFUNC fnCompare); \
196 void Insert(T lItem, size_t uiIndex, size_t nInsert = 1); \
197 void Remove(T lItem); \
198 void RemoveAt(size_t uiIndex, size_t nRemove = 1); \
200 void Sort(CMPFUNC fnCompare); \
202 /* *minimal* STL-ish interface, for derived classes */ \
203 typedef T value_type; \
204 typedef value_type* iterator; \
205 typedef const value_type* const_iterator; \
206 typedef value_type& reference; \
207 typedef const value_type& const_reference; \
208 typedef int difference_type; \
209 typedef size_t size_type; \
211 void assign(const_iterator first, const_iterator last); \
212 void assign(size_type n, const_reference v); \
213 size_type capacity() const { return m_nSize; } \
214 void clear() { Clear(); } \
215 bool empty() const { return IsEmpty(); } \
216 iterator erase(iterator first, iterator last) \
218 size_type idx = first - begin(); \
219 RemoveAt(idx, last - first); \
220 return begin() + idx; \
222 iterator erase(iterator it) { return erase(it, it + 1); } \
223 void insert(iterator it, size_type n, const value_type& v) \
224 { Insert(v, it - begin(), n); } \
225 iterator insert(iterator it, const value_type& v = value_type()) \
227 size_type idx = it - begin(); \
229 return begin() + idx; \
231 void insert(iterator it, const_iterator first, const_iterator last);\
232 size_type max_size() const { return INT_MAX; } \
233 void pop_back() { RemoveAt(size() - 1); } \
234 void push_back(const value_type& v) { Add(v); } \
235 void reserve(size_type n) { if(n > m_nSize) Realloc(n); } \
236 void resize(size_type n, value_type v = value_type()); \
237 size_type size() const { return GetCount(); } \
239 iterator begin() { return m_pItems; } \
240 iterator end() { return m_pItems + m_nCount; } \
241 const_iterator begin() const { return m_pItems; } \
242 const_iterator end() const { return m_pItems + m_nCount; } \
244 void Grow(size_t nIncrement = 0); \
245 bool Realloc(size_t nSize); \
255 // ============================================================================
256 // The private helper macros containing the core of the array classes
257 // ============================================================================
259 // Implementation notes:
261 // JACS: Salford C++ doesn't like 'var->operator=' syntax, as in:
262 // { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src);
263 // so using a temporary variable instead.
265 // The classes need a (even trivial) ~name() to link under Mac X
267 // _WX_ERROR_REMOVE is needed to resolve the name conflict between the wxT()
268 // macro and T typedef: we can't use wxT() inside WX_DEFINE_ARRAY!
270 #define _WX_ERROR_REMOVE wxT("removing inexisting element in wxArray::Remove")
272 // ----------------------------------------------------------------------------
273 // _WX_DEFINE_TYPEARRAY: array for simple types
274 // ----------------------------------------------------------------------------
278 #define _WX_DEFINE_TYPEARRAY(T, name, base, classexp) \
279 typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \
280 classexp name : public base \
283 T& operator[](size_t uiIndex) const \
284 { return (T&)(base::operator[](uiIndex)); } \
285 T& Item(size_t uiIndex) const \
286 { return (T&)/*const cast*/base::operator[](uiIndex); } \
288 { return Item(Count() - 1); } \
290 int Index(T e, bool bFromEnd = FALSE) const \
291 { return base::Index(e, bFromEnd); } \
293 void Add(T Item, size_t nInsert = 1) \
294 { insert(end(), nInsert, Item); } \
295 void Insert(T Item, size_t uiIndex, size_t nInsert = 1) \
296 { insert(begin() + uiIndex, nInsert, Item); } \
298 void RemoveAt(size_t uiIndex, size_t nRemove = 1) \
299 { base::RemoveAt(uiIndex, nRemove); } \
300 void Remove(T Item) \
301 { int iIndex = Index(Item); \
302 wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \
304 RemoveAt((size_t)iIndex); } \
306 void Sort(CMPFUNC##T fCmp) { base::Sort((CMPFUNC)fCmp); } \
309 #else // if !wxUSE_STL
311 #define _WX_DEFINE_TYPEARRAY(T, name, base, classexp) \
312 wxCOMPILE_TIME_ASSERT2(sizeof(T) <= sizeof(base::base_type), \
313 TypeTooBigToBeStoredIn##base, \
315 typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \
316 classexp name : public base \
322 name& operator=(const name& src) \
323 { base* temp = (base*) this; \
324 (*temp) = ((const base&)src); \
327 T& operator[](size_t uiIndex) const \
328 { return (T&)(base::operator[](uiIndex)); } \
329 T& Item(size_t uiIndex) const \
330 { return (T&)(base::operator[](uiIndex)); } \
332 { return (T&)(base::operator[](Count() - 1)); } \
334 int Index(T Item, bool bFromEnd = FALSE) const \
335 { return base::Index((base_type)Item, bFromEnd); } \
337 void Add(T Item, size_t nInsert = 1) \
338 { base::Add((base_type)Item, nInsert); } \
339 void Insert(T Item, size_t uiIndex, size_t nInsert = 1) \
340 { base::Insert((base_type)Item, uiIndex, nInsert) ; } \
342 void RemoveAt(size_t uiIndex, size_t nRemove = 1) \
343 { base::RemoveAt(uiIndex, nRemove); } \
344 void Remove(T Item) \
345 { int iIndex = Index(Item); \
346 wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \
348 base::RemoveAt((size_t)iIndex); } \
350 void Sort(CMPFUNC##T fCmp) { base::Sort((CMPFUNC)fCmp); } \
352 /* STL-like interface */ \
354 typedef base::iterator biterator; \
355 typedef base::const_iterator bconst_iterator; \
356 typedef base::value_type bvalue_type; \
357 typedef base::const_reference bconst_reference; \
359 typedef T value_type; \
360 typedef value_type* pointer; \
361 typedef const value_type* const_pointer; \
362 typedef value_type* iterator; \
363 typedef const value_type* const_iterator; \
364 typedef value_type& reference; \
365 typedef const value_type& const_reference; \
366 typedef base::difference_type difference_type; \
367 typedef base::size_type size_type; \
369 class reverse_iterator \
371 typedef T value_type; \
372 typedef value_type& reference; \
373 typedef value_type* pointer; \
374 typedef reverse_iterator itor; \
375 friend inline itor operator+(int o, const itor& it) \
376 { return it.m_ptr - o; } \
377 friend inline itor operator+(const itor& it, int o) \
378 { return it.m_ptr - o; } \
379 friend inline itor operator-(const itor& it, int o) \
380 { return it.m_ptr + o; } \
381 friend inline difference_type operator-(const itor& i1, \
383 { return i1.m_ptr - i2.m_ptr; } \
387 reverse_iterator() : m_ptr(NULL) { } \
388 reverse_iterator(pointer ptr) : m_ptr(ptr) { } \
389 reverse_iterator(const itor& it) : m_ptr(it.m_ptr) { } \
390 reference operator*() const { return *m_ptr; } \
391 pointer operator->() const { return m_ptr; } \
392 itor operator++() { --m_ptr; return *this; } \
393 itor operator++(int) \
394 { reverse_iterator tmp = *this; --m_ptr; return tmp; } \
395 itor operator--() { ++m_ptr; return *this; } \
396 itor operator--(int) { itor tmp = *this; ++m_ptr; return tmp; } \
397 bool operator ==(const itor& it) { return m_ptr == it.m_ptr; } \
398 bool operator !=(const itor& it) { return m_ptr != it.m_ptr; } \
401 class const_reverse_iterator \
403 typedef T value_type; \
404 typedef const value_type& reference; \
405 typedef const value_type* pointer; \
406 typedef const_reverse_iterator itor; \
407 friend inline itor operator+(int o, const itor& it) \
408 { return it.m_ptr - o; } \
409 friend inline itor operator+(const itor& it, int o) \
410 { return it.m_ptr - o; } \
411 friend inline itor operator-(const itor& it, int o) \
412 { return it.m_ptr + o; } \
413 friend inline difference_type operator-(const itor& i1, \
415 { return i1.m_ptr - i2.m_ptr; } \
419 const_reverse_iterator() : m_ptr(NULL) { } \
420 const_reverse_iterator(pointer ptr) : m_ptr(ptr) { } \
421 const_reverse_iterator(const itor& it) : m_ptr(it.m_ptr) { } \
422 const_reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { }\
423 reference operator*() const { return *m_ptr; } \
424 pointer operator->() const { return m_ptr; } \
425 itor operator++() { --m_ptr; return *this; } \
426 itor operator++(int) \
427 { itor tmp = *this; --m_ptr; return tmp; } \
428 itor operator--() { ++m_ptr; return *this; } \
429 itor operator--(int) { itor tmp = *this; ++m_ptr; return tmp; } \
430 bool operator ==(const itor& it) { return m_ptr == it.m_ptr; } \
431 bool operator !=(const itor& it) { return m_ptr != it.m_ptr; } \
434 void assign(const_iterator first, const_iterator last) \
435 { base::assign((bconst_iterator)first, (bconst_iterator)last); } \
436 void assign(size_type n, const_reference v) \
437 { base::assign(n, (bconst_reference)v); } \
438 reference back() { return *(end() - 1); } \
439 const_reference back() const { return *(end() - 1); } \
440 iterator begin() { return (iterator)base::begin(); } \
441 const_iterator begin() const { return (const_iterator)base::begin(); }\
442 size_type capacity() const { return base::capacity(); } \
443 void clear() { base::clear(); } \
444 bool empty() const { return base::empty(); } \
445 iterator end() { return (iterator)base::end(); } \
446 const_iterator end() const { return (const_iterator)base::end(); } \
447 iterator erase(iterator first, iterator last) \
448 { return (iterator)base::erase((biterator)first, (biterator)last); }\
449 iterator erase(iterator it) \
450 { return (iterator)base::erase((biterator)it); } \
451 reference front() { return *begin(); } \
452 const_reference front() const { return *begin(); } \
453 void insert(iterator it, size_type n, const_reference v) \
454 { base::insert((biterator)it, n, (bconst_reference)v); } \
455 iterator insert(iterator it, const_reference v = value_type()) \
456 { return (iterator)base::insert((biterator)it, (bconst_reference)v); }\
457 void insert(iterator it, const_iterator first, const_iterator last) \
458 { base::insert((biterator)it, (bconst_iterator)first, \
459 (bconst_iterator)last); } \
460 size_type max_size() const { return base::max_size(); } \
461 void pop_back() { base::pop_back(); } \
462 void push_back(const_reference v) \
463 { base::push_back((bconst_reference)v); } \
464 reverse_iterator rbegin() { return reverse_iterator(end() - 1); } \
465 const_reverse_iterator rbegin() const; \
466 reverse_iterator rend() { return reverse_iterator(begin() - 1); } \
467 const_reverse_iterator rend() const; \
468 void reserve(size_type n) { base::reserve(n); }; \
469 void resize(size_type n, value_type v = value_type()); \
470 size_type size() const { return base::size(); } \
476 // ----------------------------------------------------------------------------
477 // _WX_DEFINE_SORTED_TYPEARRAY: sorted array for simple data types
478 // cannot handle types with size greater than pointer because of sorting
479 // ----------------------------------------------------------------------------
481 #define _WX_DEFINE_SORTED_TYPEARRAY_2(T, name, base, defcomp, classexp, comptype)\
482 wxCOMPILE_TIME_ASSERT2(sizeof(T) <= sizeof(base::base_type), \
483 TypeTooBigToBeStoredInSorted##base, \
485 classexp name : public base \
487 typedef comptype SCMPFUNC; \
489 name(comptype fn defcomp) { m_fnCompare = fn; } \
491 name& operator=(const name& src) \
492 { base* temp = (base*) this; \
493 (*temp) = ((const base&)src); \
494 m_fnCompare = src.m_fnCompare; \
497 T& operator[](size_t uiIndex) const \
498 { return (T&)(base::operator[](uiIndex)); } \
499 T& Item(size_t uiIndex) const \
500 { return (T&)(base::operator[](uiIndex)); } \
502 { return (T&)(base::operator[](size() - 1)); } \
504 int Index(T Item) const \
505 { return base::Index(Item, (CMPFUNC)m_fnCompare); } \
507 size_t IndexForInsert(T Item) const \
508 { return base::IndexForInsert(Item, (CMPFUNC)m_fnCompare); } \
510 void AddAt(T item, size_t index) \
511 { base::insert(begin() + index, item); } \
514 { return base::Add(Item, (CMPFUNC)m_fnCompare); } \
516 void RemoveAt(size_t uiIndex, size_t nRemove = 1) \
517 { base::erase(begin() + uiIndex, begin() + uiIndex + nRemove); } \
518 void Remove(T Item) \
519 { int iIndex = Index(Item); \
520 wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \
521 _WX_ERROR_REMOVE ); \
522 base::erase(begin() + iIndex); } \
525 comptype m_fnCompare; \
529 // ----------------------------------------------------------------------------
530 // _WX_DECLARE_OBJARRAY: an array for pointers to type T with owning semantics
531 // ----------------------------------------------------------------------------
533 #define _WX_DECLARE_OBJARRAY(T, name, base, classexp) \
534 typedef int (CMPFUNC_CONV *CMPFUNC##T)(T **pItem1, T **pItem2); \
535 classexp name : protected base \
537 typedef int (CMPFUNC_CONV *CMPFUNC##base)(void **pItem1, void **pItem2); \
538 typedef base base_array; \
541 name(const name& src); \
542 name& operator=(const name& src); \
546 void Alloc(size_t count) { reserve(count); } \
547 size_t GetCount() const { return base_array::size(); } \
548 size_t size() const { return base_array::size(); } \
549 bool IsEmpty() const { return base_array::empty(); } \
550 size_t Count() const { return base_array::size(); } \
551 void Shrink() { base::Shrink(); } \
553 T& operator[](size_t uiIndex) const \
554 { return *(T*)base::operator[](uiIndex); } \
555 T& Item(size_t uiIndex) const \
556 { return *(T*)base::operator[](uiIndex); } \
558 { return *(T*)(base::operator[](size() - 1)); } \
560 int Index(const T& Item, bool bFromEnd = FALSE) const; \
562 void Add(const T& Item, size_t nInsert = 1); \
563 void Add(const T* pItem) \
564 { base::push_back((T*)pItem); } \
565 void push_back(const T* pItem) \
566 { base::push_back((T*)pItem); } \
567 void push_back(const T& Item) \
570 void Insert(const T& Item, size_t uiIndex, size_t nInsert = 1); \
571 void Insert(const T* pItem, size_t uiIndex) \
572 { base::insert(begin() + uiIndex, (T*)pItem); } \
574 void Empty() { DoEmpty(); base::clear(); } \
575 void Clear() { DoEmpty(); base::clear(); } \
577 T* Detach(size_t uiIndex) \
578 { T* p = (T*)base::operator[](uiIndex); \
579 base::erase(begin() + uiIndex); return p; } \
580 void RemoveAt(size_t uiIndex, size_t nRemove = 1); \
582 void Sort(CMPFUNC##T fCmp) { base::Sort((CMPFUNC##base)fCmp); } \
586 void DoCopy(const name& src); \
589 // ============================================================================
590 // The public macros for declaration and definition of the dynamic arrays
591 // ============================================================================
593 // Please note that for each macro WX_FOO_ARRAY we also have
594 // WX_FOO_EXPORTED_ARRAY and WX_FOO_USER_EXPORTED_ARRAY which are exactly the
595 // same except that they use an additional __declspec(dllexport) or equivalent
596 // under Windows if needed.
598 // The first (just EXPORTED) macros do it if wxWindows was compiled as a DLL
599 // and so must be used used inside the library. The second kind (USER_EXPORTED)
600 // allow the user code to do it when it wants. This is needed if you have a dll
601 // that wants to export a wxArray daubed with your own import/export goo.
603 // Finally, you can define the macro below as something special to modify the
604 // arrays defined by a simple WX_FOO_ARRAY as well. By default is is empty.
605 #define wxARRAY_DEFAULT_EXPORT
607 // ----------------------------------------------------------------------------
608 // WX_DECLARE_BASEARRAY(T, name) declare an array class named "name" containing
609 // the elements of type T
610 // ----------------------------------------------------------------------------
612 #define WX_DECLARE_BASEARRAY(T, name) \
613 WX_DECLARE_USER_EXPORTED_BASEARRAY(T, name, wxARRAY_DEFAULT_EXPORT)
615 #define WX_DECLARE_EXPORTED_BASEARRAY(T, name) \
616 WX_DECLARE_USER_EXPORTED_BASEARRAY(T, name, WXDLLEXPORT)
618 #define WX_DECLARE_USER_EXPORTED_BASEARRAY(T, name, expmode) \
619 typedef T _wxArray##name; \
620 _WX_DECLARE_BASEARRAY(_wxArray##name, name, class expmode)
622 // ----------------------------------------------------------------------------
623 // WX_DEFINE_TYPEARRAY(T, name, base) define an array class named "name" deriving
624 // from class "base" containing the elements of type T
626 // Note that the class defined has only inline function and doesn't take any
627 // space at all so there is no size penalty for defining multiple array classes
628 // ----------------------------------------------------------------------------
630 #define WX_DEFINE_TYPEARRAY(T, name, base) \
631 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, base, class wxARRAY_DEFAULT_EXPORT)
633 #define WX_DEFINE_EXPORTED_TYPEARRAY(T, name, base) \
634 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, base, class WXDLLEXPORT)
636 #define WX_DEFINE_USER_EXPORTED_TYPEARRAY(T, name, base, expdecl) \
637 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, base, class expdecl)
639 #define WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, base, classdecl) \
640 typedef T _wxArray##name; \
641 _WX_DEFINE_TYPEARRAY(_wxArray##name, name, base, classdecl)
643 // ----------------------------------------------------------------------------
644 // WX_DEFINE_SORTED_TYPEARRAY: this is the same as the previous macro, but it
645 // defines a sorted array.
648 // 1) it must be given a COMPARE function in ctor which takes 2 items of type
649 // T* and should return -1, 0 or +1 if the first one is less/greater
650 // than/equal to the second one.
651 // 2) the Add() method inserts the item in such was that the array is always
652 // sorted (it uses the COMPARE function)
653 // 3) it has no Sort() method because it's always sorted
654 // 4) Index() method is much faster (the sorted arrays use binary search
655 // instead of linear one), but Add() is slower.
656 // 5) there is no Insert() method because you can't insert an item into the
657 // given position in a sorted array but there is IndexForInsert()/AddAt()
658 // pair which may be used to optimize a common operation of "insert only if
661 // Note that you have to specify the comparison function when creating the
662 // objects of this array type. If, as in 99% of cases, the comparison function
663 // is the same for all objects of a class, WX_DEFINE_SORTED_TYPEARRAY_CMP below
664 // is more convenient.
666 // Summary: use this class when the speed of Index() function is important, use
667 // the normal arrays otherwise.
668 // ----------------------------------------------------------------------------
670 #define wxARRAY_EMPTY_CMP
672 #define WX_DEFINE_SORTED_TYPEARRAY(T, name, base) \
673 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, base, \
674 wxARRAY_DEFAULT_EXPORT)
676 #define WX_DEFINE_SORTED_EXPORTED_TYPEARRAY(T, name, base) \
677 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, base, WXDLLEXPORT)
679 #define WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, base, expmode) \
680 typedef T _wxArray##name; \
681 typedef int (CMPFUNC_CONV *SCMPFUNC##name)(T pItem1, T pItem2); \
682 _WX_DEFINE_SORTED_TYPEARRAY_2(_wxArray##name, name, base, \
683 wxARRAY_EMPTY_CMP, class expmode, SCMPFUNC##name)
685 // ----------------------------------------------------------------------------
686 // WX_DEFINE_SORTED_TYPEARRAY_CMP: exactly the same as above but the comparison
687 // function is provided by this macro and the objects of this class have a
688 // default constructor which just uses it.
690 // The arguments are: the element type, the comparison function and the array
693 // NB: this is, of course, how WX_DEFINE_SORTED_TYPEARRAY() should have worked
694 // from the very beginning - unfortunately I didn't think about this earlier
695 // ----------------------------------------------------------------------------
697 #define WX_DEFINE_SORTED_TYPEARRAY_CMP(T, cmpfunc, name, base) \
698 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, base, \
699 wxARRAY_DEFAULT_EXPORT)
701 #define WX_DEFINE_SORTED_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, base) \
702 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, base, \
705 #define WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, base, \
707 typedef T _wxArray##name; \
708 typedef int (CMPFUNC_CONV *SCMPFUNC##name)(T pItem1, T pItem2); \
709 _WX_DEFINE_SORTED_TYPEARRAY_2(_wxArray##name, name, base, = cmpfunc, \
710 class expmode, SCMPFUNC##name)
712 // ----------------------------------------------------------------------------
713 // WX_DECLARE_OBJARRAY(T, name): this macro generates a new array class
714 // named "name" which owns the objects of type T it contains, i.e. it will
715 // delete them when it is destroyed.
717 // An element is of type T*, but arguments of type T& are taken (see below!)
718 // and T& is returned.
720 // Don't use this for simple types such as "int" or "long"!
722 // Note on Add/Insert functions:
723 // 1) function(T*) gives the object to the array, i.e. it will delete the
724 // object when it's removed or in the array's dtor
725 // 2) function(T&) will create a copy of the object and work with it
728 // 1) Remove() will delete the object after removing it from the array
729 // 2) Detach() just removes the object from the array (returning pointer to it)
731 // NB1: Base type T should have an accessible copy ctor if Add(T&) is used
732 // NB2: Never ever cast a array to it's base type: as dtor is not virtual
733 // and so you risk having at least the memory leaks and probably worse
735 // Some functions of this class are not inline, so it takes some space to
736 // define new class from this template even if you don't use it - which is not
737 // the case for the simple (non-object) array classes
739 // To use an objarray class you must
740 // #include "dynarray.h"
741 // WX_DECLARE_OBJARRAY(element_type, list_class_name)
742 // #include "arrimpl.cpp"
743 // WX_DEFINE_OBJARRAY(list_class_name) // name must be the same as above!
745 // This is necessary because at the moment of DEFINE_OBJARRAY class parsing the
746 // element_type must be fully defined (i.e. forward declaration is not
747 // enough), while WX_DECLARE_OBJARRAY may be done anywhere. The separation of
748 // two allows to break cicrcular dependencies with classes which have member
749 // variables of objarray type.
750 // ----------------------------------------------------------------------------
752 #define WX_DECLARE_OBJARRAY(T, name) \
753 WX_DECLARE_USER_EXPORTED_OBJARRAY(T, name, wxARRAY_DEFAULT_EXPORT)
755 #define WX_DECLARE_EXPORTED_OBJARRAY(T, name) \
756 WX_DECLARE_USER_EXPORTED_OBJARRAY(T, name, WXDLLEXPORT)
758 #define WX_DECLARE_USER_EXPORTED_OBJARRAY(T, name, expmode) \
759 typedef T _wxObjArray##name; \
760 _WX_DECLARE_OBJARRAY(_wxObjArray##name, name, wxArrayPtrVoid, class expmode)
762 // WX_DEFINE_OBJARRAY is going to be redefined when arrimpl.cpp is included,
763 // try to provoke a human-understandable error if it used incorrectly.
765 // there is no real need for 3 different macros in the DEFINE case but do it
766 // anyhow for consistency
767 #define WX_DEFINE_OBJARRAY(name) DidYouIncludeArrimplCpp
768 #define WX_DEFINE_EXPORTED_OBJARRAY(name) WX_DEFINE_OBJARRAY(name)
769 #define WX_DEFINE_USER_EXPORTED_OBJARRAY(name) WX_DEFINE_OBJARRAY(name)
771 // ----------------------------------------------------------------------------
772 // Some commonly used predefined base arrays
773 // ----------------------------------------------------------------------------
775 WX_DECLARE_USER_EXPORTED_BASEARRAY(const void *, wxBaseArrayPtrVoid
,
777 WX_DECLARE_USER_EXPORTED_BASEARRAY(short, wxBaseArrayShort
,
779 WX_DECLARE_USER_EXPORTED_BASEARRAY(int, wxBaseArrayInt
,
781 WX_DECLARE_USER_EXPORTED_BASEARRAY(long, wxBaseArrayLong
,
783 WX_DECLARE_USER_EXPORTED_BASEARRAY(double, wxBaseArrayDouble
,
786 // ----------------------------------------------------------------------------
787 // Convenience macros to define arrays from base arrays
788 // ----------------------------------------------------------------------------
790 #define WX_DEFINE_ARRAY(T, name) \
791 WX_DEFINE_TYPEARRAY(T, name, wxBaseArrayPtrVoid)
792 #define WX_DEFINE_EXPORTED_ARRAY(T, name) \
793 WX_DEFINE_EXPORTED_TYPEARRAY(T, name, wxBaseArrayPtrVoid)
794 #define WX_DEFINE_USER_EXPORTED_ARRAY(T, name, expmode) \
795 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, wxBaseArrayPtrVoid, expmode)
797 #define WX_DEFINE_ARRAY_SHORT(T, name) \
798 WX_DEFINE_TYPEARRAY(T, name, wxBaseArrayShort)
799 #define WX_DEFINE_EXPORTED_ARRAY_SHORT(T, name) \
800 WX_DEFINE_EXPORTED_TYPEARRAY(T, name, wxBaseArrayShort)
801 #define WX_DEFINE_USER_EXPORTED_ARRAY_SHORT(T, name, expmode) \
802 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, wxBaseArrayShort, expmode)
804 #define WX_DEFINE_ARRAY_INT(T, name) \
805 WX_DEFINE_TYPEARRAY(T, name, wxBaseArrayInt)
806 #define WX_DEFINE_EXPORTED_ARRAY_INT(T, name) \
807 WX_DEFINE_EXPORTED_TYPEARRAY(T, name, wxBaseArrayInt)
808 #define WX_DEFINE_USER_EXPORTED_ARRAY_INT(T, name, expmode) \
809 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, wxBaseArrayInt, expmode)
811 #define WX_DEFINE_ARRAY_LONG(T, name) \
812 WX_DEFINE_TYPEARRAY(T, name, wxBaseArrayLong)
813 #define WX_DEFINE_EXPORTED_ARRAY_LONG(T, name) \
814 WX_DEFINE_EXPORTED_TYPEARRAY(T, name, wxBaseArrayLong)
815 #define WX_DEFINE_USER_EXPORTED_ARRAY_LONG(T, name, expmode) \
816 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, wxBaseArrayLong, expmode)
818 #define WX_DEFINE_ARRAY_DOUBLE(T, name) \
819 WX_DEFINE_TYPEARRAY(T, name, wxBaseArrayDouble)
820 #define WX_DEFINE_EXPORTED_ARRAY_DOUBLE(T, name) \
821 WX_DEFINE_EXPORTED_TYPEARRAY(T, name, wxBaseArrayDouble)
822 #define WX_DEFINE_USER_EXPORTED_ARRAY_DOUBLE(T, name, expmode) \
823 WX_DEFINE_TYPEARRAY_WITH_DECL(T, name, wxBaseArrayDouble, expmode)
825 // ----------------------------------------------------------------------------
826 // Convenience macros to define sorted arrays from base arrays
827 // ----------------------------------------------------------------------------
829 #define WX_DEFINE_SORTED_ARRAY(T, name) \
830 WX_DEFINE_SORTED_TYPEARRAY(T, name, wxBaseArrayPtrVoid)
831 #define WX_DEFINE_SORTED_EXPORTED_ARRAY(T, name) \
832 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY(T, name, wxBaseArrayPtrVoid)
833 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY(T, name, expmode) \
834 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, wxBaseArrayPtrVoid, expmode)
836 #define WX_DEFINE_SORTED_ARRAY_SHORT(T, name) \
837 WX_DEFINE_SORTED_TYPEARRAY(T, name, wxBaseArrayShort)
838 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_SHORT(T, name) \
839 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY(T, name, wxBaseArrayShort)
840 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_SHORT(T, name, expmode) \
841 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, wxBaseArrayShort, expmode)
843 #define WX_DEFINE_SORTED_ARRAY_INT(T, name) \
844 WX_DEFINE_SORTED_TYPEARRAY(T, name, wxBaseArrayInt)
845 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_INT(T, name) \
846 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY(T, name, wxBaseArrayInt)
847 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_INT(T, name, expmode) \
848 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, wxBaseArrayInt, expmode)
850 #define WX_DEFINE_SORTED_ARRAY_LONG(T, name) \
851 WX_DEFINE_SORTED_TYPEARRAY(T, name, wxBaseArrayLong)
852 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_LONG(T, name) \
853 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY(T, name, wxBaseArrayLong)
854 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_LONG(T, name, expmode) \
855 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY(T, name, wxBaseArrayLong, expmode)
857 // ----------------------------------------------------------------------------
858 // Convenience macros to define sorted arrays from base arrays
859 // ----------------------------------------------------------------------------
861 #define WX_DEFINE_SORTED_ARRAY_CMP(T, cmpfunc, name) \
862 WX_DEFINE_SORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayPtrVoid)
863 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_CMP(T, cmpfunc, name) \
864 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayPtrVoid)
865 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_CMP(T, cmpfunc, \
867 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, \
868 wxBaseArrayPtrVoid, expmode)
870 #define WX_DEFINE_SORTED_ARRAY_CMP_SHORT(T, cmpfunc, name) \
871 WX_DEFINE_SORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayShort)
872 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_CMP_SHORT(T, cmpfunc, name) \
873 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayShort)
874 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_CMP_SHORT(T, cmpfunc, \
876 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, \
877 wxBaseArrayShort, expmode)
879 #define WX_DEFINE_SORTED_ARRAY_CMP_INT(T, cmpfunc, name) \
880 WX_DEFINE_SORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayInt)
881 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_CMP_INT(T, cmpfunc, name) \
882 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayInt)
883 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_CMP_INT(T, cmpfunc, \
885 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, \
886 wxBaseArrayInt, expmode)
888 #define WX_DEFINE_SORTED_ARRAY_CMP_LONG(T, cmpfunc, name) \
889 WX_DEFINE_SORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayLong)
890 #define WX_DEFINE_SORTED_EXPORTED_ARRAY_CMP_LONG(T, cmpfunc, name) \
891 WX_DEFINE_SORTED_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, wxBaseArrayLong)
892 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_CMP_LONG(T, cmpfunc, \
894 WX_DEFINE_SORTED_USER_EXPORTED_TYPEARRAY_CMP(T, cmpfunc, name, \
895 wxBaseArrayLong, expmode)
897 // ----------------------------------------------------------------------------
898 // Some commonly used predefined arrays
899 // ----------------------------------------------------------------------------
901 WX_DEFINE_USER_EXPORTED_ARRAY_SHORT (short, wxArrayShort
, class WXDLLIMPEXP_BASE
);
902 WX_DEFINE_USER_EXPORTED_ARRAY_INT (int, wxArrayInt
, class WXDLLIMPEXP_BASE
);
903 WX_DEFINE_USER_EXPORTED_ARRAY_LONG (long, wxArrayLong
, class WXDLLIMPEXP_BASE
);
904 WX_DEFINE_USER_EXPORTED_ARRAY (void *, wxArrayPtrVoid
, class WXDLLIMPEXP_BASE
);
906 // -----------------------------------------------------------------------------
907 // convenience macros
908 // -----------------------------------------------------------------------------
910 // append all element of one array to another one
911 #define WX_APPEND_ARRAY(array, other) \
913 size_t count = (other).size(); \
914 for ( size_t n = 0; n < count; n++ ) \
916 (array).push_back((other)[n]); \
920 // delete all array elements
922 // NB: the class declaration of the array elements must be visible from the
923 // place where you use this macro, otherwise the proper destructor may not
924 // be called (a decent compiler should give a warning about it, but don't
926 #define WX_CLEAR_ARRAY(array) \
928 size_t count = (array).size(); \
929 for ( size_t n = 0; n < count; n++ ) \
937 #endif // _DYNARRAY_H