]>
Commit | Line | Data |
---|---|---|
c801d85f KB |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // Name: dynarray.h | |
3 | // Purpose: auto-resizable (i.e. dynamic) array support | |
4 | // Author: Vadim Zeitlin | |
3bfa4402 | 5 | // Modified by: |
c801d85f KB |
6 | // Created: 12.09.97 |
7 | // RCS-ID: $Id$ | |
8 | // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr> | |
9 | // Licence: wxWindows license | |
10 | /////////////////////////////////////////////////////////////////////////////// | |
11 | ||
12 | #ifndef _DYNARRAY_H | |
13 | #define _DYNARRAY_H | |
14 | ||
15 | #ifdef __GNUG__ | |
16 | #pragma interface "dynarray.h" | |
17 | #endif | |
18 | ||
19 | #include "wx/defs.h" | |
3bfa4402 | 20 | #include "wx/debug.h" |
c801d85f | 21 | |
2600d8ee | 22 | /** @name Dynamic arrays and object arrays (array which own their elements) |
c801d85f KB |
23 | @memo Arrays which grow on demand and do range checking (only in debug) |
24 | */ | |
25 | //@{ | |
26 | ||
27 | // ---------------------------------------------------------------------------- | |
28 | // constants | |
29 | // ---------------------------------------------------------------------------- | |
30 | ||
31 | /** | |
2600d8ee | 32 | the initial size by which an array grows when an element is added |
3bfa4402 | 33 | default value avoids allocate one or two bytes when the array is created |
c801d85f KB |
34 | which is rather inefficient |
35 | */ | |
36 | #define WX_ARRAY_DEFAULT_INITIAL_SIZE (16) | |
37 | ||
38 | // ---------------------------------------------------------------------------- | |
39 | // types | |
40 | // ---------------------------------------------------------------------------- | |
41 | ||
42 | /** | |
43 | callback compare function for quick sort | |
3bfa4402 | 44 | must return negative value, 0 or positive value if pItem1 <, = or > pItem2 |
c801d85f KB |
45 | */ |
46 | ||
47 | #ifdef __VISUALC__ | |
48 | #define CMPFUNC_CONV _cdecl | |
49 | #else // !Visual C++ | |
50 | #define CMPFUNC_CONV | |
51 | #endif // compiler | |
52 | typedef int (CMPFUNC_CONV *CMPFUNC)(const void* pItem1, const void* pItem2); | |
53 | ||
54 | // ---------------------------------------------------------------------------- | |
55 | /** | |
56 | base class managing data having size of type 'long' (not used directly) | |
57 | ||
58 | NB: for efficiency this often used class has no virtual functions (hence no | |
3bfa4402 VZ |
59 | VTBL), even dtor is <B>not</B> virtual. If used as expected it won't |
60 | create any problems because ARRAYs from DEFINE_ARRAY have no dtor at all, | |
61 | so it's not too important if it's not called (this happens when you cast | |
c801d85f KB |
62 | "SomeArray *" as "BaseArray *" and then delete it) |
63 | ||
2600d8ee | 64 | @memo Base class for template array classes |
c801d85f KB |
65 | */ |
66 | // ---------------------------------------------------------------------------- | |
fbcb4166 | 67 | class WXDLLEXPORT wxBaseArray |
c801d85f KB |
68 | { |
69 | public: | |
70 | /** @name ctors and dtor */ | |
71 | //@{ | |
72 | /// default ctor | |
73 | wxBaseArray(); | |
74 | /// copy ctor | |
75 | wxBaseArray(const wxBaseArray& array); | |
76 | /// assignment operator | |
77 | wxBaseArray& operator=(const wxBaseArray& src); | |
78 | /// not virtual, see above | |
79 | /// EXCEPT for Gnu compiler to reduce warnings... | |
80 | #ifdef __GNUG__ | |
81 | virtual | |
82 | #endif | |
83 | ~wxBaseArray(); | |
84 | //@} | |
85 | ||
86 | /** @name memory management */ | |
87 | //@{ | |
2600d8ee | 88 | /// empties the array, but doesn't release memory |
3093cef8 | 89 | void Empty() { m_nCount = 0; } |
2600d8ee | 90 | /// empties the array and releases memory |
c801d85f KB |
91 | void Clear(); |
92 | /// preallocates memory for given number of items | |
c86f1403 | 93 | void Alloc(size_t uiSize); |
3093cef8 VZ |
94 | /// minimizes the memory used by the array (frees unused memory) |
95 | void Shrink(); | |
c801d85f KB |
96 | //@} |
97 | ||
98 | /** @name simple accessors */ | |
99 | //@{ | |
100 | /// number of elements in the array | |
3093cef8 VZ |
101 | size_t Count() const { return m_nCount; } |
102 | size_t GetCount() const { return m_nCount; } | |
c801d85f | 103 | /// is it empty? |
3093cef8 | 104 | bool IsEmpty() const { return m_nCount == 0; } |
c801d85f KB |
105 | //@} |
106 | ||
107 | protected: | |
3bfa4402 | 108 | // these methods are protected because if they were public one could |
2600d8ee | 109 | // mistakenly call one of them instead of DEFINE_ARRAY's or OBJARRAY's |
c801d85f KB |
110 | // type safe methods |
111 | ||
112 | /** @name items access */ | |
113 | //@{ | |
114 | /// get item at position uiIndex (range checking is done in debug version) | |
c86f1403 | 115 | long& Item(size_t uiIndex) const |
3093cef8 | 116 | { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; } |
c801d85f | 117 | /// same as Item() |
c86f1403 | 118 | long& operator[](size_t uiIndex) const { return Item(uiIndex); } |
c801d85f KB |
119 | //@} |
120 | ||
121 | /** @name item management */ | |
122 | //@{ | |
123 | /** | |
124 | Search the element in the array, starting from the either side | |
125 | @param bFromEnd if TRUE, start from the end | |
126 | @return index of the first item matched or NOT_FOUND | |
127 | @see NOT_FOUND | |
128 | */ | |
3bfa4402 VZ |
129 | int Index(long lItem, bool bFromEnd = FALSE) const; |
130 | /// search for an item using binary search in a sorted array | |
e99c3048 | 131 | int Index(long lItem, CMPFUNC fnCompare) const; |
c801d85f | 132 | /// add new element at the end |
3bfa4402 VZ |
133 | void Add(long lItem); |
134 | /// add item assuming the array is sorted with fnCompare function | |
135 | void Add(long lItem, CMPFUNC fnCompare); | |
136 | /// add new element at given position (it becomes Item[uiIndex]) | |
c86f1403 | 137 | void Insert(long lItem, size_t uiIndex); |
c801d85f KB |
138 | /// remove first item matching this value |
139 | void Remove(long lItem); | |
140 | /// remove item by index | |
c86f1403 | 141 | void Remove(size_t uiIndex); |
c801d85f KB |
142 | //@} |
143 | ||
144 | /// sort array elements using given compare function | |
3bfa4402 | 145 | void Sort(CMPFUNC fnCompare); |
c801d85f KB |
146 | |
147 | private: | |
148 | void Grow(); // makes array bigger if needed | |
149 | ||
3093cef8 VZ |
150 | size_t m_nSize, // current size of the array |
151 | m_nCount; // current number of elements | |
c801d85f KB |
152 | |
153 | long *m_pItems; // pointer to data | |
154 | }; | |
155 | ||
156 | // ============================================================================ | |
157 | // template classes | |
158 | // ============================================================================ | |
159 | ||
160 | // ---------------------------------------------------------------------------- | |
161 | // This macro generates a new array class. It is intended for storage of simple | |
162 | // types of sizeof()<=sizeof(long) or pointers if sizeof(pointer)<=sizeof(long) | |
3bfa4402 | 163 | // |
c801d85f KB |
164 | // NB: it has only inline functions => takes no space at all |
165 | // ---------------------------------------------------------------------------- | |
166 | #define _WX_DEFINE_ARRAY(T, name) \ | |
167 | typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \ | |
fbcb4166 | 168 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ |
c801d85f KB |
169 | { \ |
170 | public: \ | |
171 | name() \ | |
172 | { wxASSERT( sizeof(T) <= sizeof(long) ); } \ | |
173 | \ | |
174 | name& operator=(const name& src) \ | |
175 | { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src); \ | |
176 | return *this; } \ | |
177 | \ | |
3093cef8 | 178 | T& operator[](size_t uiIndex) const \ |
c801d85f | 179 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ |
3093cef8 | 180 | T& Item(size_t uiIndex) const \ |
c801d85f | 181 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ |
3bfaaefe VZ |
182 | T& Last() const \ |
183 | { return (T&)(wxBaseArray::Item(Count() - 1)); } \ | |
c801d85f | 184 | \ |
bc7665d4 | 185 | int Index(T Item, bool bFromEnd = FALSE) const \ |
c801d85f KB |
186 | { return wxBaseArray::Index((long)Item, bFromEnd); } \ |
187 | \ | |
188 | void Add(T Item) \ | |
189 | { wxBaseArray::Add((long)Item); } \ | |
3093cef8 | 190 | void Insert(T Item, size_t uiIndex) \ |
c801d85f KB |
191 | { wxBaseArray::Insert((long)Item, uiIndex) ; } \ |
192 | \ | |
3093cef8 | 193 | void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ |
c801d85f KB |
194 | void Remove(T Item) \ |
195 | { int iIndex = Index(Item); \ | |
1311c7a9 VZ |
196 | wxCHECK2_MSG( iIndex != NOT_FOUND, return, \ |
197 | "removing inexisting element in wxArray::Remove" ); \ | |
c86f1403 | 198 | wxBaseArray::Remove((size_t)iIndex); } \ |
c801d85f KB |
199 | \ |
200 | void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \ | |
201 | } | |
202 | ||
3bfa4402 VZ |
203 | // ---------------------------------------------------------------------------- |
204 | // This is the same as the previous macro, but it defines a sorted array. | |
205 | // Differences: | |
206 | // 1) it must be given a COMPARE function in ctor which takes 2 items of type | |
207 | // T* and should return -1, 0 or +1 if the first one is less/greater | |
208 | // than/equal to the second one. | |
209 | // 2) the Add() method inserts the item in such was that the array is always | |
210 | // sorted (it uses the COMPARE function) | |
211 | // 3) it has no Sort() method because it's always sorted | |
212 | // 4) Index() method is much faster (the sorted arrays use binary search | |
213 | // instead of linear one), but Add() is slower. | |
214 | // | |
215 | // Summary: use this class when the speed of Index() function is important, use | |
216 | // the normal arrays otherwise. | |
217 | // | |
218 | // NB: it has only inline functions => takes no space at all | |
219 | // ---------------------------------------------------------------------------- | |
220 | #define _WX_DEFINE_SORTED_ARRAY(T, name) \ | |
221 | typedef int (CMPFUNC_CONV *SCMPFUNC##T)(T pItem1, T pItem2); \ | |
fbcb4166 | 222 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ |
3bfa4402 VZ |
223 | { \ |
224 | public: \ | |
225 | name(SCMPFUNC##T fn) \ | |
226 | { wxASSERT( sizeof(T) <= sizeof(long) ); m_fnCompare = fn; } \ | |
227 | \ | |
228 | name& operator=(const name& src) \ | |
229 | { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src); \ | |
230 | m_fnCompare = src.m_fnCompare; \ | |
231 | return *this; } \ | |
232 | \ | |
3093cef8 | 233 | T& operator[](size_t uiIndex) const \ |
3bfa4402 | 234 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ |
3093cef8 | 235 | T& Item(size_t uiIndex) const \ |
3bfa4402 VZ |
236 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ |
237 | T& Last() const \ | |
238 | { return (T&)(wxBaseArray::Item(Count() - 1)); } \ | |
239 | \ | |
240 | int Index(T Item) const \ | |
241 | { return wxBaseArray::Index((long)Item, (CMPFUNC)m_fnCompare); }\ | |
242 | \ | |
243 | void Add(T Item) \ | |
244 | { wxBaseArray::Add((long)Item, (CMPFUNC)m_fnCompare); } \ | |
245 | \ | |
3093cef8 | 246 | void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ |
3bfa4402 VZ |
247 | void Remove(T Item) \ |
248 | { int iIndex = Index(Item); \ | |
249 | wxCHECK2_MSG( iIndex != NOT_FOUND, return, \ | |
250 | "removing inexisting element in wxArray::Remove" ); \ | |
3093cef8 | 251 | wxBaseArray::Remove((size_t)iIndex); } \ |
3bfa4402 VZ |
252 | \ |
253 | private: \ | |
254 | SCMPFUNC##T m_fnCompare; \ | |
255 | } | |
256 | ||
c801d85f | 257 | // ---------------------------------------------------------------------------- |
2600d8ee | 258 | // see WX_DECLARE_OBJARRAY and WX_DEFINE_OBJARRAY |
c801d85f | 259 | // ---------------------------------------------------------------------------- |
2600d8ee | 260 | #define _WX_DECLARE_OBJARRAY(T, name) \ |
c801d85f | 261 | typedef int (CMPFUNC_CONV *CMPFUNC##T)(T** pItem1, T** pItem2); \ |
2600d8ee | 262 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ |
c801d85f KB |
263 | { \ |
264 | public: \ | |
265 | name() { } \ | |
266 | name(const name& src); \ | |
267 | name& operator=(const name& src); \ | |
268 | \ | |
269 | ~name(); \ | |
270 | \ | |
3093cef8 | 271 | T& operator[](size_t uiIndex) const \ |
c801d85f | 272 | { return *(T*)wxBaseArray::Item(uiIndex); } \ |
3093cef8 | 273 | T& Item(size_t uiIndex) const \ |
c801d85f | 274 | { return *(T*)wxBaseArray::Item(uiIndex); } \ |
3bfaaefe VZ |
275 | T& Last() const \ |
276 | { return *(T*)(wxBaseArray::Item(Count() - 1)); } \ | |
c801d85f | 277 | \ |
bc7665d4 | 278 | int Index(const T& Item, bool bFromEnd = FALSE) const; \ |
c801d85f KB |
279 | \ |
280 | void Add(const T& Item); \ | |
281 | void Add(const T* pItem) \ | |
282 | { wxBaseArray::Add((long)pItem); } \ | |
283 | \ | |
3093cef8 VZ |
284 | void Insert(const T& Item, size_t uiIndex); \ |
285 | void Insert(const T* pItem, size_t uiIndex) \ | |
c801d85f KB |
286 | { wxBaseArray::Insert((long)pItem, uiIndex); } \ |
287 | \ | |
288 | void Empty(); \ | |
289 | \ | |
3093cef8 | 290 | T* Detach(size_t uiIndex) \ |
c801d85f KB |
291 | { T* p = (T*)wxBaseArray::Item(uiIndex); \ |
292 | wxBaseArray::Remove(uiIndex); return p; } \ | |
3093cef8 | 293 | void Remove(size_t uiIndex); \ |
c801d85f KB |
294 | \ |
295 | void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \ | |
296 | \ | |
297 | private: \ | |
298 | void DoCopy(const name& src); \ | |
299 | } | |
300 | ||
301 | // ---------------------------------------------------------------------------- | |
2600d8ee | 302 | /** @name Macros for definition of dynamic arrays and objarrays |
c801d85f KB |
303 | |
304 | These macros are ugly (especially if you look in the sources ;-), but they | |
305 | allow us to define 'template' classes without actually using templates. | |
306 | <BR> | |
307 | <BR> | |
2600d8ee VZ |
308 | Range checking is performed in debug build for both arrays and objarrays. |
309 | Type checking is done at compile-time. Warning: arrays <I>never</I> shrink, | |
310 | they only grow, so loading 10 millions in an array only to delete them 2 | |
311 | lines below is <I>not</I> recommended. However, it does free memory when | |
312 | it's destroyed, so if you destroy array also, it's ok. | |
c801d85f KB |
313 | */ |
314 | // ---------------------------------------------------------------------------- | |
315 | ||
316 | //@{ | |
317 | /** | |
318 | This macro generates a new array class. It is intended for storage of simple | |
319 | types of sizeof()<=sizeof(long) or pointers if sizeof(pointer)<=sizeof(long) | |
320 | <BR> | |
321 | NB: it has only inline functions => takes no space at all | |
322 | <BR> | |
323 | ||
324 | @memo declare and define array class 'name' containing elements of type 'T' | |
325 | */ | |
326 | #define WX_DEFINE_ARRAY(T, name) typedef T _A##name; \ | |
327 | _WX_DEFINE_ARRAY(_A##name, name) | |
3bfa4402 VZ |
328 | |
329 | /** | |
330 | This macro does the same as WX_DEFINE_ARRAY except that the array will be | |
331 | sorted with the specified compare function. | |
332 | */ | |
333 | #define WX_DEFINE_SORTED_ARRAY(T, name) typedef T _A##name; \ | |
334 | _WX_DEFINE_SORTED_ARRAY(_A##name, name) | |
335 | ||
c801d85f | 336 | /** |
2600d8ee VZ |
337 | This macro generates a new objarrays class which owns the objects it |
338 | contains, i.e. it will delete them when it is destroyed. An element is of | |
339 | type T*, but arguments of type T& are taken (see below!) and T& is | |
340 | returned. <BR> | |
c801d85f KB |
341 | Don't use this for simple types such as "int" or "long"! |
342 | You _may_ use it for "double" but it's awfully inefficient. | |
343 | <BR> | |
344 | <BR> | |
345 | Note on Add/Insert functions: | |
346 | <BR> | |
2600d8ee VZ |
347 | 1) function(T*) gives the object to the array, i.e. it will delete the |
348 | object when it's removed or in the array's dtor | |
c801d85f KB |
349 | <BR> |
350 | 2) function(T&) will create a copy of the object and work with it | |
351 | <BR> | |
352 | <BR> | |
353 | Also: | |
354 | <BR> | |
2600d8ee | 355 | 1) Remove() will delete the object after removing it from the array |
c801d85f | 356 | <BR> |
2600d8ee | 357 | 2) Detach() just removes the object from the array (returning pointer to it) |
c801d85f KB |
358 | <BR> |
359 | <BR> | |
360 | NB1: Base type T should have an accessible copy ctor if Add(T&) is used, | |
361 | <BR> | |
2600d8ee | 362 | NB2: Never ever cast a array to it's base type: as dtor is <B>not</B> virtual |
c801d85f KB |
363 | it will provoke memory leaks |
364 | <BR> | |
365 | <BR> | |
3bfa4402 | 366 | some functions of this class are not inline, so it takes some space to |
c801d85f KB |
367 | define new class from this template. |
368 | ||
2600d8ee | 369 | @memo declare objarray class 'name' containing elements of type 'T' |
c801d85f | 370 | */ |
fd3f686c VZ |
371 | #define WX_DECLARE_OBJARRAY(T, name) typedef T _L##name; \ |
372 | _WX_DECLARE_LIST(_L##name, name) | |
c801d85f | 373 | /** |
2600d8ee | 374 | To use an objarray class you must |
c801d85f KB |
375 | <ll> |
376 | <li>#include "dynarray.h" | |
2600d8ee VZ |
377 | <li>WX_DECLARE_OBJARRAY(element_type, list_class_name) |
378 | <li>#include "arrimpl.cpp" | |
379 | <li>WX_DEFINE_OBJARRAY(list_class_name) // same as above! | |
c801d85f KB |
380 | </ll> |
381 | <BR><BR> | |
2600d8ee VZ |
382 | This is necessary because at the moment of DEFINE_OBJARRAY class |
383 | element_type must be fully defined (i.e. forward declaration is not | |
384 | enough), while WX_DECLARE_OBJARRAY may be done anywhere. The separation of | |
385 | two allows to break cicrcular dependencies with classes which have member | |
386 | variables of objarray type. | |
c801d85f | 387 | |
2600d8ee | 388 | @memo define (must include arrimpl.cpp!) objarray class 'name' |
c801d85f | 389 | */ |
2600d8ee | 390 | #define WX_DEFINE_OBJARRAY(name) "don't forget to include arrimpl.cpp!" |
c801d85f KB |
391 | //@} |
392 | ||
393 | // ---------------------------------------------------------------------------- | |
394 | /** @name Some commonly used predefined arrays */ | |
395 | // # overhead if not used? | |
396 | // ---------------------------------------------------------------------------- | |
397 | ||
fbcb4166 JS |
398 | #define WXDLLEXPORTLOCAL WXDLLEXPORT |
399 | ||
c801d85f KB |
400 | //@{ |
401 | /** @name ArrayInt */ | |
402 | WX_DEFINE_ARRAY(int, wxArrayInt); | |
403 | /** @name ArrayLong */ | |
404 | WX_DEFINE_ARRAY(long, wxArrayLong); | |
405 | /** @name ArrayPtrVoid */ | |
406 | WX_DEFINE_ARRAY(void *, wxArrayPtrVoid); | |
407 | //@} | |
408 | ||
409 | //@} | |
410 | ||
fbcb4166 JS |
411 | #undef WXDLLEXPORTLOCAL |
412 | #define WXDLLEXPORTLOCAL | |
413 | ||
c801d85f KB |
414 | #endif // _DYNARRAY_H |
415 |