]>
Commit | Line | Data |
---|---|---|
1 | /////////////////////////////////////////////////////////////////////////////// | |
2 | // Name: dynarray.h | |
3 | // Purpose: auto-resizable (i.e. dynamic) array support | |
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 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" | |
20 | #include "wx/debug.h" | |
21 | ||
22 | /** @name Dynamic arrays and object arrays (array which own their elements) | |
23 | @memo Arrays which grow on demand and do range checking (only in debug) | |
24 | */ | |
25 | //@{ | |
26 | ||
27 | // ---------------------------------------------------------------------------- | |
28 | // constants | |
29 | // ---------------------------------------------------------------------------- | |
30 | ||
31 | /** | |
32 | the initial size by which an array grows when an element is added | |
33 | default value avoids allocate one or two bytes when the array is created | |
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 | |
44 | must return negative value, 0 or positive value if pItem1 <, = or > pItem2 | |
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 | |
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 | |
62 | "SomeArray *" as "BaseArray *" and then delete it) | |
63 | ||
64 | @memo Base class for template array classes | |
65 | */ | |
66 | // ---------------------------------------------------------------------------- | |
67 | class WXDLLEXPORT wxBaseArray | |
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 | //@{ | |
88 | /// empties the array, but doesn't release memory | |
89 | void Empty() { m_nCount = 0; } | |
90 | /// empties the array and releases memory | |
91 | void Clear(); | |
92 | /// preallocates memory for given number of items | |
93 | void Alloc(size_t uiSize); | |
94 | /// minimizes the memory used by the array (frees unused memory) | |
95 | void Shrink(); | |
96 | //@} | |
97 | ||
98 | /** @name simple accessors */ | |
99 | //@{ | |
100 | /// number of elements in the array | |
101 | size_t Count() const { return m_nCount; } | |
102 | size_t GetCount() const { return m_nCount; } | |
103 | /// is it empty? | |
104 | bool IsEmpty() const { return m_nCount == 0; } | |
105 | //@} | |
106 | ||
107 | protected: | |
108 | // these methods are protected because if they were public one could | |
109 | // mistakenly call one of them instead of DEFINE_ARRAY's or OBJARRAY's | |
110 | // type safe methods | |
111 | ||
112 | /** @name items access */ | |
113 | //@{ | |
114 | /// get item at position uiIndex (range checking is done in debug version) | |
115 | long& Item(size_t uiIndex) const | |
116 | { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; } | |
117 | /// same as Item() | |
118 | long& operator[](size_t uiIndex) const { return Item(uiIndex); } | |
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 wxNOT_FOUND | |
127 | @see wxNOT_FOUND | |
128 | */ | |
129 | int Index(long lItem, bool bFromEnd = FALSE) const; | |
130 | /// search for an item using binary search in a sorted array | |
131 | int Index(long lItem, CMPFUNC fnCompare) const; | |
132 | /// add new element at the end | |
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]) | |
137 | void Insert(long lItem, size_t uiIndex); | |
138 | /// remove first item matching this value | |
139 | void Remove(long lItem); | |
140 | /// remove item by index | |
141 | void Remove(size_t uiIndex); | |
142 | //@} | |
143 | ||
144 | /// sort array elements using given compare function | |
145 | void Sort(CMPFUNC fnCompare); | |
146 | ||
147 | private: | |
148 | void Grow(); // makes array bigger if needed | |
149 | ||
150 | size_t m_nSize, // current size of the array | |
151 | m_nCount; // current number of elements | |
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) | |
163 | // | |
164 | // NB: it has only inline functions => takes no space at all | |
165 | // Mod by JACS: Salford C++ doesn't like 'var->operator=' syntax, as in: | |
166 | // { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src); | |
167 | // so using a temporary variable instead. | |
168 | // ---------------------------------------------------------------------------- | |
169 | #define _WX_DEFINE_ARRAY(T, name) \ | |
170 | typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \ | |
171 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ | |
172 | { \ | |
173 | public: \ | |
174 | name() \ | |
175 | { wxASSERT( sizeof(T) <= sizeof(long) ); } \ | |
176 | \ | |
177 | name& operator=(const name& src) \ | |
178 | { wxBaseArray* temp = (wxBaseArray*) this; \ | |
179 | (*temp) = ((const wxBaseArray&)src); \ | |
180 | return *this; } \ | |
181 | \ | |
182 | T& operator[](size_t uiIndex) const \ | |
183 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ | |
184 | T& Item(size_t uiIndex) const \ | |
185 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ | |
186 | T& Last() const \ | |
187 | { return (T&)(wxBaseArray::Item(Count() - 1)); } \ | |
188 | \ | |
189 | int Index(T Item, bool bFromEnd = FALSE) const \ | |
190 | { return wxBaseArray::Index((long)Item, bFromEnd); } \ | |
191 | \ | |
192 | void Add(T Item) \ | |
193 | { wxBaseArray::Add((long)Item); } \ | |
194 | void Insert(T Item, size_t uiIndex) \ | |
195 | { wxBaseArray::Insert((long)Item, uiIndex) ; } \ | |
196 | \ | |
197 | void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ | |
198 | void Remove(T Item) \ | |
199 | { int iIndex = Index(Item); \ | |
200 | wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \ | |
201 | "removing inexisting element in wxArray::Remove" ); \ | |
202 | wxBaseArray::Remove((size_t)iIndex); } \ | |
203 | \ | |
204 | void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \ | |
205 | } | |
206 | ||
207 | // ---------------------------------------------------------------------------- | |
208 | // This is the same as the previous macro, but it defines a sorted array. | |
209 | // Differences: | |
210 | // 1) it must be given a COMPARE function in ctor which takes 2 items of type | |
211 | // T* and should return -1, 0 or +1 if the first one is less/greater | |
212 | // than/equal to the second one. | |
213 | // 2) the Add() method inserts the item in such was that the array is always | |
214 | // sorted (it uses the COMPARE function) | |
215 | // 3) it has no Sort() method because it's always sorted | |
216 | // 4) Index() method is much faster (the sorted arrays use binary search | |
217 | // instead of linear one), but Add() is slower. | |
218 | // | |
219 | // Summary: use this class when the speed of Index() function is important, use | |
220 | // the normal arrays otherwise. | |
221 | // | |
222 | // NB: it has only inline functions => takes no space at all | |
223 | // Mod by JACS: Salford C++ doesn't like 'var->operator=' syntax, as in: | |
224 | // { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src); | |
225 | // so using a temporary variable instead. | |
226 | // ---------------------------------------------------------------------------- | |
227 | #define _WX_DEFINE_SORTED_ARRAY(T, name) \ | |
228 | typedef int (CMPFUNC_CONV *SCMPFUNC##T)(T pItem1, T pItem2); \ | |
229 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ | |
230 | { \ | |
231 | public: \ | |
232 | name(SCMPFUNC##T fn) \ | |
233 | { wxASSERT( sizeof(T) <= sizeof(long) ); m_fnCompare = fn; } \ | |
234 | \ | |
235 | name& operator=(const name& src) \ | |
236 | { wxBaseArray* temp = (wxBaseArray*) this; \ | |
237 | (*temp) = ((const wxBaseArray&)src); \ | |
238 | m_fnCompare = src.m_fnCompare; \ | |
239 | return *this; } \ | |
240 | \ | |
241 | T& operator[](size_t uiIndex) const \ | |
242 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ | |
243 | T& Item(size_t uiIndex) const \ | |
244 | { return (T&)(wxBaseArray::Item(uiIndex)); } \ | |
245 | T& Last() const \ | |
246 | { return (T&)(wxBaseArray::Item(Count() - 1)); } \ | |
247 | \ | |
248 | int Index(T Item) const \ | |
249 | { return wxBaseArray::Index((long)Item, (CMPFUNC)m_fnCompare); }\ | |
250 | \ | |
251 | void Add(T Item) \ | |
252 | { wxBaseArray::Add((long)Item, (CMPFUNC)m_fnCompare); } \ | |
253 | \ | |
254 | void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ | |
255 | void Remove(T Item) \ | |
256 | { int iIndex = Index(Item); \ | |
257 | wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \ | |
258 | "removing inexisting element in wxArray::Remove" ); \ | |
259 | wxBaseArray::Remove((size_t)iIndex); } \ | |
260 | \ | |
261 | private: \ | |
262 | SCMPFUNC##T m_fnCompare; \ | |
263 | } | |
264 | ||
265 | // ---------------------------------------------------------------------------- | |
266 | // see WX_DECLARE_OBJARRAY and WX_DEFINE_OBJARRAY | |
267 | // ---------------------------------------------------------------------------- | |
268 | #define _WX_DECLARE_OBJARRAY(T, name) \ | |
269 | typedef int (CMPFUNC_CONV *CMPFUNC##T)(T** pItem1, T** pItem2); \ | |
270 | class WXDLLEXPORTLOCAL name : public wxBaseArray \ | |
271 | { \ | |
272 | public: \ | |
273 | name() { } \ | |
274 | name(const name& src); \ | |
275 | name& operator=(const name& src); \ | |
276 | \ | |
277 | ~name(); \ | |
278 | \ | |
279 | T& operator[](size_t uiIndex) const \ | |
280 | { return *(T*)wxBaseArray::Item(uiIndex); } \ | |
281 | T& Item(size_t uiIndex) const \ | |
282 | { return *(T*)wxBaseArray::Item(uiIndex); } \ | |
283 | T& Last() const \ | |
284 | { return *(T*)(wxBaseArray::Item(Count() - 1)); } \ | |
285 | \ | |
286 | int Index(const T& Item, bool bFromEnd = FALSE) const; \ | |
287 | \ | |
288 | void Add(const T& Item); \ | |
289 | void Add(const T* pItem) \ | |
290 | { wxBaseArray::Add((long)pItem); } \ | |
291 | \ | |
292 | void Insert(const T& Item, size_t uiIndex); \ | |
293 | void Insert(const T* pItem, size_t uiIndex) \ | |
294 | { wxBaseArray::Insert((long)pItem, uiIndex); } \ | |
295 | \ | |
296 | void Empty(); \ | |
297 | \ | |
298 | T* Detach(size_t uiIndex) \ | |
299 | { T* p = (T*)wxBaseArray::Item(uiIndex); \ | |
300 | wxBaseArray::Remove(uiIndex); return p; } \ | |
301 | void Remove(size_t uiIndex); \ | |
302 | \ | |
303 | void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \ | |
304 | \ | |
305 | private: \ | |
306 | void DoCopy(const name& src); \ | |
307 | } | |
308 | ||
309 | // ---------------------------------------------------------------------------- | |
310 | /** @name Macros for definition of dynamic arrays and objarrays | |
311 | ||
312 | These macros are ugly (especially if you look in the sources ;-), but they | |
313 | allow us to define 'template' classes without actually using templates. | |
314 | <BR> | |
315 | <BR> | |
316 | Range checking is performed in debug build for both arrays and objarrays. | |
317 | Type checking is done at compile-time. Warning: arrays <I>never</I> shrink, | |
318 | they only grow, so loading 10 millions in an array only to delete them 2 | |
319 | lines below is <I>not</I> recommended. However, it does free memory when | |
320 | it's destroyed, so if you destroy array also, it's ok. | |
321 | */ | |
322 | // ---------------------------------------------------------------------------- | |
323 | ||
324 | //@{ | |
325 | /** | |
326 | This macro generates a new array class. It is intended for storage of simple | |
327 | types of sizeof()<=sizeof(long) or pointers if sizeof(pointer)<=sizeof(long) | |
328 | <BR> | |
329 | NB: it has only inline functions => takes no space at all | |
330 | <BR> | |
331 | ||
332 | @memo declare and define array class 'name' containing elements of type 'T' | |
333 | */ | |
334 | #define WX_DEFINE_ARRAY(T, name) typedef T _A##name; \ | |
335 | _WX_DEFINE_ARRAY(_A##name, name) | |
336 | ||
337 | /** | |
338 | This macro does the same as WX_DEFINE_ARRAY except that the array will be | |
339 | sorted with the specified compare function. | |
340 | */ | |
341 | #define WX_DEFINE_SORTED_ARRAY(T, name) typedef T _A##name; \ | |
342 | _WX_DEFINE_SORTED_ARRAY(_A##name, name) | |
343 | ||
344 | /** | |
345 | This macro generates a new objarrays class which owns the objects it | |
346 | contains, i.e. it will delete them when it is destroyed. An element is of | |
347 | type T*, but arguments of type T& are taken (see below!) and T& is | |
348 | returned. <BR> | |
349 | Don't use this for simple types such as "int" or "long"! | |
350 | You _may_ use it for "double" but it's awfully inefficient. | |
351 | <BR> | |
352 | <BR> | |
353 | Note on Add/Insert functions: | |
354 | <BR> | |
355 | 1) function(T*) gives the object to the array, i.e. it will delete the | |
356 | object when it's removed or in the array's dtor | |
357 | <BR> | |
358 | 2) function(T&) will create a copy of the object and work with it | |
359 | <BR> | |
360 | <BR> | |
361 | Also: | |
362 | <BR> | |
363 | 1) Remove() will delete the object after removing it from the array | |
364 | <BR> | |
365 | 2) Detach() just removes the object from the array (returning pointer to it) | |
366 | <BR> | |
367 | <BR> | |
368 | NB1: Base type T should have an accessible copy ctor if Add(T&) is used, | |
369 | <BR> | |
370 | NB2: Never ever cast a array to it's base type: as dtor is <B>not</B> virtual | |
371 | it will provoke memory leaks | |
372 | <BR> | |
373 | <BR> | |
374 | some functions of this class are not inline, so it takes some space to | |
375 | define new class from this template. | |
376 | ||
377 | @memo declare objarray class 'name' containing elements of type 'T' | |
378 | */ | |
379 | #define WX_DECLARE_OBJARRAY(T, name) typedef T _L##name; \ | |
380 | _WX_DECLARE_OBJARRAY(_L##name, name) | |
381 | /** | |
382 | To use an objarray class you must | |
383 | <ll> | |
384 | <li>#include "dynarray.h" | |
385 | <li>WX_DECLARE_OBJARRAY(element_type, list_class_name) | |
386 | <li>#include "arrimpl.cpp" | |
387 | <li>WX_DEFINE_OBJARRAY(list_class_name) // same as above! | |
388 | </ll> | |
389 | <BR><BR> | |
390 | This is necessary because at the moment of DEFINE_OBJARRAY class | |
391 | element_type must be fully defined (i.e. forward declaration is not | |
392 | enough), while WX_DECLARE_OBJARRAY may be done anywhere. The separation of | |
393 | two allows to break cicrcular dependencies with classes which have member | |
394 | variables of objarray type. | |
395 | ||
396 | @memo define (must include arrimpl.cpp!) objarray class 'name' | |
397 | */ | |
398 | #define WX_DEFINE_OBJARRAY(name) "don't forget to include arrimpl.cpp!" | |
399 | //@} | |
400 | ||
401 | // ---------------------------------------------------------------------------- | |
402 | /** @name Some commonly used predefined arrays */ | |
403 | // # overhead if not used? | |
404 | // ---------------------------------------------------------------------------- | |
405 | ||
406 | #define WXDLLEXPORTLOCAL WXDLLEXPORT | |
407 | ||
408 | //@{ | |
409 | /** @name ArrayInt */ | |
410 | WX_DEFINE_ARRAY(int, wxArrayInt); | |
411 | /** @name ArrayLong */ | |
412 | WX_DEFINE_ARRAY(long, wxArrayLong); | |
413 | /** @name ArrayPtrVoid */ | |
414 | WX_DEFINE_ARRAY(void *, wxArrayPtrVoid); | |
415 | //@} | |
416 | ||
417 | //@} | |
418 | ||
419 | #undef WXDLLEXPORTLOCAL | |
420 | #define WXDLLEXPORTLOCAL | |
421 | ||
422 | // ----------------------------------------------------------------------------- | |
423 | // convinience macros | |
424 | // ----------------------------------------------------------------------------- | |
425 | ||
426 | // delete all array elements | |
427 | // | |
428 | // NB: the class declaration of the array elements must be visible from the | |
429 | // place where you use this macro, otherwise the proper destructor may not | |
430 | // be called (a decent compiler should give a warning about it, but don't | |
431 | // count on it)! | |
432 | #define WX_CLEAR_ARRAY(array) \ | |
433 | { \ | |
434 | size_t count = array.Count(); \ | |
435 | for ( size_t n = 0; n < count; n++ ) \ | |
436 | { \ | |
437 | delete array[n]; \ | |
438 | } \ | |
439 | \ | |
440 | array.Empty(); \ | |
441 | } | |
442 | #endif // _DYNARRAY_H | |
443 |