]> git.saurik.com Git - wxWidgets.git/blame - include/wx/dynarray.h
1. suppressed some messages from HasEntry()/HasKeys()
[wxWidgets.git] / include / wx / dynarray.h
CommitLineData
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
52typedef 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 67class WXDLLEXPORT wxBaseArray
c801d85f
KB
68{
69public:
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
107protected:
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
147private:
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) \
167typedef int (CMPFUNC_CONV *CMPFUNC##T)(T *pItem1, T *pItem2); \
fbcb4166 168class WXDLLEXPORTLOCAL name : public wxBaseArray \
c801d85f
KB
169{ \
170public: \
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) \
221typedef int (CMPFUNC_CONV *SCMPFUNC##T)(T pItem1, T pItem2); \
fbcb4166 222class WXDLLEXPORTLOCAL name : public wxBaseArray \
3bfa4402
VZ
223{ \
224public: \
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 \
253private: \
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 261typedef int (CMPFUNC_CONV *CMPFUNC##T)(T** pItem1, T** pItem2); \
2600d8ee 262class WXDLLEXPORTLOCAL name : public wxBaseArray \
c801d85f
KB
263{ \
264public: \
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 \
297private: \
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 */
402WX_DEFINE_ARRAY(int, wxArrayInt);
403 /** @name ArrayLong */
404WX_DEFINE_ARRAY(long, wxArrayLong);
405 /** @name ArrayPtrVoid */
406WX_DEFINE_ARRAY(void *, wxArrayPtrVoid);
407//@}
408
409//@}
410
fbcb4166
JS
411#undef WXDLLEXPORTLOCAL
412#define WXDLLEXPORTLOCAL
413
c801d85f
KB
414#endif // _DYNARRAY_H
415