]> git.saurik.com Git - wxWidgets.git/blob - include/wx/dynarray.h
SCROLLWIN instead of SCROLL again
[wxWidgets.git] / include / wx / dynarray.h
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 typedef int (wxCMPFUNC_CONV *CMPFUNC)(const void* pItem1, const void* pItem2);
47
48 // ----------------------------------------------------------------------------
49 /**
50 base class managing data having size of type 'long' (not used directly)
51
52 NB: for efficiency this often used class has no virtual functions (hence no
53 VTBL), even dtor is <B>not</B> virtual. If used as expected it won't
54 create any problems because ARRAYs from DEFINE_ARRAY have no dtor at all,
55 so it's not too important if it's not called (this happens when you cast
56 "SomeArray *" as "BaseArray *" and then delete it)
57
58 @memo Base class for template array classes
59 */
60 // ----------------------------------------------------------------------------
61 class WXDLLEXPORT wxBaseArray
62 {
63 public:
64 /** @name ctors and dtor */
65 //@{
66 /// default ctor
67 wxBaseArray();
68 /// copy ctor
69 wxBaseArray(const wxBaseArray& array);
70 /// assignment operator
71 wxBaseArray& operator=(const wxBaseArray& src);
72 /// not virtual, see above
73 /// EXCEPT for Gnu compiler to reduce warnings...
74 #ifdef __GNUG__
75 virtual
76 #endif
77 ~wxBaseArray();
78 //@}
79
80 /** @name memory management */
81 //@{
82 /// empties the array, but doesn't release memory
83 void Empty() { m_nCount = 0; }
84 /// empties the array and releases memory
85 void Clear();
86 /// preallocates memory for given number of items
87 void Alloc(size_t uiSize);
88 /// minimizes the memory used by the array (frees unused memory)
89 void Shrink();
90 //@}
91
92 /** @name simple accessors */
93 //@{
94 /// number of elements in the array
95 size_t Count() const { return m_nCount; }
96 size_t GetCount() const { return m_nCount; }
97 /// is it empty?
98 bool IsEmpty() const { return m_nCount == 0; }
99 //@}
100
101 protected:
102 // these methods are protected because if they were public one could
103 // mistakenly call one of them instead of DEFINE_ARRAY's or OBJARRAY's
104 // type safe methods
105
106 /** @name items access */
107 //@{
108 /// get item at position uiIndex (range checking is done in debug version)
109 long& Item(size_t uiIndex) const
110 { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; }
111 /// same as Item()
112 long& operator[](size_t uiIndex) const { return Item(uiIndex); }
113 //@}
114
115 /** @name item management */
116 //@{
117 /**
118 Search the element in the array, starting from the either side
119 @param bFromEnd if TRUE, start from the end
120 @return index of the first item matched or wxNOT_FOUND
121 @see wxNOT_FOUND
122 */
123 int Index(long lItem, bool bFromEnd = FALSE) const;
124 /// search for an item using binary search in a sorted array
125 int Index(long lItem, CMPFUNC fnCompare) const;
126 /// add new element at the end
127 void Add(long lItem);
128 /// add item assuming the array is sorted with fnCompare function
129 void Add(long lItem, CMPFUNC fnCompare);
130 /// add new element at given position (it becomes Item[uiIndex])
131 void Insert(long lItem, size_t uiIndex);
132 /// remove first item matching this value
133 void Remove(long lItem);
134 /// remove item by index
135 void RemoveAt(size_t uiIndex);
136 //@}
137
138 /// sort array elements using given compare function
139 void Sort(CMPFUNC fnCompare);
140
141 private:
142 void Grow(); // makes array bigger if needed
143
144 size_t m_nSize, // current size of the array
145 m_nCount; // current number of elements
146
147 long *m_pItems; // pointer to data
148 };
149
150 // ============================================================================
151 // template classes
152 // ============================================================================
153
154 // resolves the name conflict between the wxT() macor and T typedef: we can't
155 // use wxT() inside WX_DEFINE_ARRAY!
156 #define _WX_ERROR_SIZEOF wxT("illegal use of DEFINE_ARRAY")
157 #define _WX_ERROR_REMOVE wxT("removing inexisting element in wxArray::Remove")
158
159 // ----------------------------------------------------------------------------
160 // This macro generates a new array class. It is intended for storage of simple
161 // types of sizeof()<=sizeof(long) or pointers if sizeof(pointer)<=sizeof(long)
162 //
163 // NB: it has only inline functions => takes no space at all
164 // Mod by JACS: Salford C++ doesn't like 'var->operator=' syntax, as in:
165 // { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src);
166 // so using a temporary variable instead.
167 // ----------------------------------------------------------------------------
168 #define _WX_DEFINE_ARRAY(T, name, classexp) \
169 typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \
170 classexp name : public wxBaseArray \
171 { \
172 public: \
173 name() \
174 { \
175 size_t type = sizeof(T); \
176 size_t sizelong = sizeof(long); \
177 if ( type > sizelong ) \
178 { wxFAIL_MSG( _WX_ERROR_SIZEOF ); } \
179 } \
180 \
181 name& operator=(const name& src) \
182 { wxBaseArray* temp = (wxBaseArray*) this; \
183 (*temp) = ((const wxBaseArray&)src); \
184 return *this; } \
185 \
186 T& operator[](size_t uiIndex) const \
187 { return (T&)(wxBaseArray::Item(uiIndex)); } \
188 T& Item(size_t uiIndex) const \
189 { return (T&)(wxBaseArray::Item(uiIndex)); } \
190 T& Last() const \
191 { return (T&)(wxBaseArray::Item(Count() - 1)); } \
192 \
193 int Index(T Item, bool bFromEnd = FALSE) const \
194 { return wxBaseArray::Index((long)Item, bFromEnd); } \
195 \
196 void Add(T Item) \
197 { wxBaseArray::Add((long)Item); } \
198 void Insert(T Item, size_t uiIndex) \
199 { wxBaseArray::Insert((long)Item, uiIndex) ; } \
200 \
201 void Remove(size_t uiIndex) { RemoveAt(uiIndex); } \
202 void RemoveAt(size_t uiIndex) { wxBaseArray::RemoveAt(uiIndex); } \
203 void Remove(T Item) \
204 { int iIndex = Index(Item); \
205 wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \
206 _WX_ERROR_REMOVE); \
207 wxBaseArray::RemoveAt((size_t)iIndex); } \
208 \
209 void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \
210 }
211
212 // ----------------------------------------------------------------------------
213 // This is the same as the previous macro, but it defines a sorted array.
214 // Differences:
215 // 1) it must be given a COMPARE function in ctor which takes 2 items of type
216 // T* and should return -1, 0 or +1 if the first one is less/greater
217 // than/equal to the second one.
218 // 2) the Add() method inserts the item in such was that the array is always
219 // sorted (it uses the COMPARE function)
220 // 3) it has no Sort() method because it's always sorted
221 // 4) Index() method is much faster (the sorted arrays use binary search
222 // instead of linear one), but Add() is slower.
223 //
224 // Summary: use this class when the speed of Index() function is important, use
225 // the normal arrays otherwise.
226 //
227 // NB: it has only inline functions => takes no space at all
228 // Mod by JACS: Salford C++ doesn't like 'var->operator=' syntax, as in:
229 // { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src);
230 // so using a temporary variable instead.
231 // ----------------------------------------------------------------------------
232 #define _WX_DEFINE_SORTED_ARRAY(T, name, classexp) \
233 typedef int (CMPFUNC_CONV *SCMPFUNC##T)(T pItem1, T pItem2); \
234 classexp name : public wxBaseArray \
235 { \
236 public: \
237 name(SCMPFUNC##T fn) \
238 { size_t type = sizeof(T); \
239 size_t sizelong = sizeof(long); \
240 if ( type > sizelong ) \
241 { wxFAIL_MSG( _WX_ERROR_SIZEOF ); } \
242 m_fnCompare = fn; \
243 } \
244 \
245 name& operator=(const name& src) \
246 { wxBaseArray* temp = (wxBaseArray*) this; \
247 (*temp) = ((const wxBaseArray&)src); \
248 m_fnCompare = src.m_fnCompare; \
249 return *this; } \
250 \
251 T& operator[](size_t uiIndex) const \
252 { return (T&)(wxBaseArray::Item(uiIndex)); } \
253 T& Item(size_t uiIndex) const \
254 { return (T&)(wxBaseArray::Item(uiIndex)); } \
255 T& Last() const \
256 { return (T&)(wxBaseArray::Item(Count() - 1)); } \
257 \
258 int Index(T Item) const \
259 { return wxBaseArray::Index((long)Item, (CMPFUNC)m_fnCompare); }\
260 \
261 void Add(T Item) \
262 { wxBaseArray::Add((long)Item, (CMPFUNC)m_fnCompare); } \
263 \
264 void Remove(size_t uiIndex) { RemoveAt(uiIndex); } \
265 void RemoveAt(size_t uiIndex) { wxBaseArray::RemoveAt(uiIndex); } \
266 void Remove(T Item) \
267 { int iIndex = Index(Item); \
268 wxCHECK2_MSG( iIndex != wxNOT_FOUND, return, \
269 _WX_ERROR_REMOVE ); \
270 wxBaseArray::RemoveAt((size_t)iIndex); } \
271 \
272 private: \
273 SCMPFUNC##T m_fnCompare; \
274 }
275
276 // ----------------------------------------------------------------------------
277 // see WX_DECLARE_OBJARRAY and WX_DEFINE_OBJARRAY
278 // ----------------------------------------------------------------------------
279 #define _WX_DECLARE_OBJARRAY(T, name, classexp) \
280 typedef int (CMPFUNC_CONV *CMPFUNC##T)(T** pItem1, T** pItem2); \
281 classexp name : public wxBaseArray \
282 { \
283 public: \
284 name() { } \
285 name(const name& src); \
286 name& operator=(const name& src); \
287 \
288 ~name(); \
289 \
290 T& operator[](size_t uiIndex) const \
291 { return *(T*)wxBaseArray::Item(uiIndex); } \
292 T& Item(size_t uiIndex) const \
293 { return *(T*)wxBaseArray::Item(uiIndex); } \
294 T& Last() const \
295 { return *(T*)(wxBaseArray::Item(Count() - 1)); } \
296 \
297 int Index(const T& Item, bool bFromEnd = FALSE) const; \
298 \
299 void Add(const T& Item); \
300 void Add(const T* pItem) \
301 { wxBaseArray::Add((long)pItem); } \
302 \
303 void Insert(const T& Item, size_t uiIndex); \
304 void Insert(const T* pItem, size_t uiIndex) \
305 { wxBaseArray::Insert((long)pItem, uiIndex); } \
306 \
307 void Empty(); \
308 \
309 T* Detach(size_t uiIndex) \
310 { T* p = (T*)wxBaseArray::Item(uiIndex); \
311 wxBaseArray::RemoveAt(uiIndex); return p; } \
312 void Remove(size_t uiIndex) { RemoveAt(uiIndex); } \
313 void RemoveAt(size_t uiIndex); \
314 \
315 void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \
316 \
317 private: \
318 void DoCopy(const name& src); \
319 }
320
321 // ----------------------------------------------------------------------------
322 /** @name Macros for definition of dynamic arrays and objarrays
323
324 These macros are ugly (especially if you look in the sources ;-), but they
325 allow us to define 'template' classes without actually using templates.
326 <BR>
327 <BR>
328 Range checking is performed in debug build for both arrays and objarrays.
329 Type checking is done at compile-time. Warning: arrays <I>never</I> shrink,
330 they only grow, so loading 10 millions in an array only to delete them 2
331 lines below is <I>not</I> recommended. However, it does free memory when
332 it's destroyed, so if you destroy array also, it's ok.
333 */
334 // ----------------------------------------------------------------------------
335
336 //@{
337 /**
338 This macro generates a new array class. It is intended for storage of simple
339 types of sizeof()<=sizeof(long) or pointers if sizeof(pointer)<=sizeof(long)
340 <BR>
341 NB: it has only inline functions => takes no space at all
342 <BR>
343
344 @memo declare and define array class 'name' containing elements of type 'T'
345 */
346 #define WX_DEFINE_ARRAY(T, name) \
347 typedef T _A##name; \
348 _WX_DEFINE_ARRAY(_A##name, name, class)
349
350 /**
351 This macro does the same as WX_DEFINE_ARRAY except that the array will be
352 sorted with the specified compare function.
353 */
354 #define WX_DEFINE_SORTED_ARRAY(T, name) \
355 typedef T _A##name; \
356 _WX_DEFINE_SORTED_ARRAY(_A##name, name, class)
357
358 /**
359 This macro generates a new objarrays class which owns the objects it
360 contains, i.e. it will delete them when it is destroyed. An element is of
361 type T*, but arguments of type T& are taken (see below!) and T& is
362 returned. <BR>
363 Don't use this for simple types such as "int" or "long"!
364 You _may_ use it for "double" but it's awfully inefficient.
365 <BR>
366 <BR>
367 Note on Add/Insert functions:
368 <BR>
369 1) function(T*) gives the object to the array, i.e. it will delete the
370 object when it's removed or in the array's dtor
371 <BR>
372 2) function(T&) will create a copy of the object and work with it
373 <BR>
374 <BR>
375 Also:
376 <BR>
377 1) Remove() will delete the object after removing it from the array
378 <BR>
379 2) Detach() just removes the object from the array (returning pointer to it)
380 <BR>
381 <BR>
382 NB1: Base type T should have an accessible copy ctor if Add(T&) is used,
383 <BR>
384 NB2: Never ever cast a array to it's base type: as dtor is <B>not</B> virtual
385 it will provoke memory leaks
386 <BR>
387 <BR>
388 some functions of this class are not inline, so it takes some space to
389 define new class from this template.
390
391 @memo declare objarray class 'name' containing elements of type 'T'
392 */
393 #define WX_DECLARE_OBJARRAY(T, name) \
394 typedef T _L##name; \
395 _WX_DECLARE_OBJARRAY(_L##name, name, class)
396
397 /**
398 To use an objarray class you must
399 <ll>
400 <li>#include "dynarray.h"
401 <li>WX_DECLARE_OBJARRAY(element_type, list_class_name)
402 <li>#include "arrimpl.cpp"
403 <li>WX_DEFINE_OBJARRAY(list_class_name) // same as above!
404 </ll>
405 <BR><BR>
406 This is necessary because at the moment of DEFINE_OBJARRAY class
407 element_type must be fully defined (i.e. forward declaration is not
408 enough), while WX_DECLARE_OBJARRAY may be done anywhere. The separation of
409 two allows to break cicrcular dependencies with classes which have member
410 variables of objarray type.
411
412 @memo define (must include arrimpl.cpp!) objarray class 'name'
413 */
414 #define WX_DEFINE_OBJARRAY(name) "don't forget to include arrimpl.cpp!"
415 //@}
416
417 // these macros do the same thing as the WX_XXX ones above, but should be used
418 // inside the library for user visible classes because otherwise they wouldn't
419 // be visible from outside (when using wxWindows as DLL under Windows)
420 #define WX_DEFINE_EXPORTED_ARRAY(T, name) \
421 typedef T _A##name; \
422 _WX_DEFINE_ARRAY(_A##name, name, class WXDLLEXPORT)
423
424 #define WX_DEFINE_SORTED_EXPORTED_ARRAY(T, name) \
425 typedef T _A##name; \
426 _WX_DEFINE_SORTED_ARRAY(_A##name, name, class WXDLLEXPORT)
427
428 #define WX_DECLARE_EXPORTED_OBJARRAY(T, name) \
429 typedef T _L##name; \
430 _WX_DECLARE_OBJARRAY(_L##name, name, class WXDLLEXPORT)
431
432 // ----------------------------------------------------------------------------
433 /** @name Some commonly used predefined arrays */
434 // ----------------------------------------------------------------------------
435
436 //@{
437 /** @name ArrayInt */
438 WX_DEFINE_EXPORTED_ARRAY(int, wxArrayInt);
439 /** @name ArrayLong */
440 WX_DEFINE_EXPORTED_ARRAY(long, wxArrayLong);
441 /** @name ArrayPtrVoid */
442 WX_DEFINE_EXPORTED_ARRAY(void *, wxArrayPtrVoid);
443 //@}
444
445 //@}
446
447 // -----------------------------------------------------------------------------
448 // convinience macros
449 // -----------------------------------------------------------------------------
450
451 // append all element of one array to another one
452 #define WX_APPEND_ARRAY(array, other) \
453 { \
454 size_t count = other.Count(); \
455 for ( size_t n = 0; n < count; n++ ) \
456 { \
457 array.Add(other[n]); \
458 } \
459 }
460
461 // delete all array elements
462 //
463 // NB: the class declaration of the array elements must be visible from the
464 // place where you use this macro, otherwise the proper destructor may not
465 // be called (a decent compiler should give a warning about it, but don't
466 // count on it)!
467 #define WX_CLEAR_ARRAY(array) \
468 { \
469 size_t count = array.Count(); \
470 for ( size_t n = 0; n < count; n++ ) \
471 { \
472 delete array[n]; \
473 } \
474 \
475 array.Empty(); \
476 }
477
478 #endif // _DYNARRAY_H
479