projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
fixed bug with searching in sorted arrays
[wxWidgets.git] / src / common / dynarray.cpp
1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: dynarray.cpp
3 // Purpose: implementation of wxBaseArray class
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 licence
10 ///////////////////////////////////////////////////////////////////////////////
11
12 // ============================================================================
13 // headers
14 // ============================================================================
15
16 #ifdef __GNUG__
17 #pragma implementation "dynarray.h"
18 #endif
19
20 #include "wx/wxprec.h"
21
22 #ifdef __BORLANDC__
23 #pragma hdrstop
24 #endif
25
26 #include "wx/dynarray.h"
27 #include "wx/intl.h"
28
29 #include <stdlib.h>
30 #include <string.h> // for memmove
31
32 #ifndef max
33 #define max(a, b) (((a) > (b)) ? (a) : (b))
34 #endif
35
36 // we cast the value to long from which we cast it to void * in IndexForInsert:
37 // this can't work if the pointers are not big enough
38 wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *),
39 wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
40
41 // ============================================================================
42 // constants
43 // ============================================================================
44
45 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
46 #define ARRAY_MAXSIZE_INCREMENT 4096
47
48 // ============================================================================
49 // implementation
50 // ============================================================================
51
52 // ----------------------------------------------------------------------------
53 // wxBaseArray - dynamic array of 'T's
54 // ----------------------------------------------------------------------------
55
56 #define _WX_DEFINE_BASEARRAY(T, name) \
57 /* ctor */ \
58 name::name() \
59 { \
60 m_nSize = \
61 m_nCount = 0; \
62 m_pItems = (T *)NULL; \
63 } \
64 \
65 /* copy ctor */ \
66 name::name(const name& src) \
67 { \
68 m_nSize = /* not src.m_nSize to save memory */ \
69 m_nCount = src.m_nCount; \
70 \
71 if ( m_nSize != 0 ) { \
72 m_pItems = new T[m_nSize]; \
73 /* only copy if allocation succeeded */ \
74 if ( m_pItems ) { \
75 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
76 } \
77 else { \
78 m_nSize = 0; \
79 } \
80 } \
81 else \
82 m_pItems = (T *) NULL; \
83 } \
84 \
85 /* assignment operator */ \
86 name& name::operator=(const name& src) \
87 { \
88 wxDELETEA(m_pItems); \
89 \
90 m_nSize = /* not src.m_nSize to save memory */ \
91 m_nCount = src.m_nCount; \
92 \
93 if ( m_nSize != 0 ){ \
94 m_pItems = new T[m_nSize]; \
95 /* only copy if allocation succeeded */ \
96 if ( m_pItems ) { \
97 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
98 } \
99 else { \
100 m_nSize = 0; \
101 } \
102 } \
103 else \
104 m_pItems = (T *) NULL; \
105 \
106 return *this; \
107 } \
108 \
109 /* allocate new buffer of the given size and move our data to it */ \
110 bool name::Realloc(size_t nSize) \
111 { \
112 T *pNew = new T[nSize]; \
113 /* only grow if allocation succeeded */ \
114 if ( !pNew ) \
115 return false; \
116 \
117 m_nSize = nSize; \
118 /* copy data to new location */ \
119 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
120 delete [] m_pItems; \
121 m_pItems = pNew; \
122 \
123 return true; \
124 } \
125 \
126 /* grow the array */ \
127 void name::Grow(size_t nIncrement) \
128 { \
129 /* only do it if no more place */ \
130 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
131 if( m_nSize == 0 ) { \
132 /* was empty, determine initial size */ \
133 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
134 if (size < nIncrement) size = nIncrement; \
135 /* allocate some memory */ \
136 m_pItems = new T[size]; \
137 /* only grow if allocation succeeded */ \
138 if ( m_pItems ) { \
139 m_nSize = size; \
140 } \
141 } \
142 else \
143 { \
144 /* add at least 50% but not too much */ \
145 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
146 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
147 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
148 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
149 if ( nIncrement < ndefIncrement ) \
150 nIncrement = ndefIncrement; \
151 Realloc(m_nSize + nIncrement); \
152 } \
153 } \
154 } \
155 \
156 /* make sure that the array has at least count elements */ \
157 void name::SetCount(size_t count, T defval) \
158 { \
159 if ( m_nSize < count ) \
160 { \
161 /* need to realloc memory: don't overallocate it here as if */ \
162 /* SetCount() is called, it probably means that the caller */ \
163 /* knows in advance how many elements there will be in the */ \
164 /* array and so it won't be necessary to realloc it later */ \
165 if ( !Realloc(count) ) \
166 { \
167 /* out of memory -- what can we do? */ \
168 return; \
169 } \
170 } \
171 \
172 /* add new elements if we extend the array */ \
173 while ( m_nCount < count ) \
174 { \
175 m_pItems[m_nCount++] = defval; \
176 } \
177 } \
178 \
179 /* dtor */ \
180 name::~name() \
181 { \
182 wxDELETEA(m_pItems); \
183 } \
184 \
185 /* clears the list */ \
186 void name::Clear() \
187 { \
188 m_nSize = \
189 m_nCount = 0; \
190 \
191 wxDELETEA(m_pItems); \
192 } \
193 \
194 /* pre-allocates memory (frees the previous data!) */ \
195 void name::Alloc(size_t nSize) \
196 { \
197 /* only if old buffer was not big enough */ \
198 if ( nSize > m_nSize ) { \
199 wxDELETEA(m_pItems); \
200 m_nSize = 0; \
201 m_pItems = new T[nSize]; \
202 /* only alloc if allocation succeeded */ \
203 if ( m_pItems ) { \
204 m_nSize = nSize; \
205 } \
206 } \
207 \
208 m_nCount = 0; \
209 } \
210 \
211 /* minimizes the memory usage by freeing unused memory */ \
212 void name::Shrink() \
213 { \
214 /* only do it if we have some memory to free */ \
215 if( m_nCount < m_nSize ) { \
216 /* allocates exactly as much memory as we need */ \
217 T *pNew = new T[m_nCount]; \
218 /* only shrink if allocation succeeded */ \
219 if ( pNew ) { \
220 /* copy data to new location */ \
221 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
222 delete [] m_pItems; \
223 m_pItems = pNew; \
224 \
225 /* update the size of the new block */ \
226 m_nSize = m_nCount; \
227 } \
228 /* else: don't do anything, better keep old memory block! */ \
229 } \
230 } \
231 \
232 /* searches the array for an item (forward or backwards) */ \
233 int name::Index(T lItem, bool bFromEnd) const \
234 { \
235 if ( bFromEnd ) { \
236 if ( m_nCount > 0 ) { \
237 size_t n = m_nCount; \
238 do { \
239 if ( m_pItems[--n] == lItem ) \
240 return n; \
241 } \
242 while ( n != 0 ); \
243 } \
244 } \
245 else { \
246 for( size_t n = 0; n < m_nCount; n++ ) { \
247 if( m_pItems[n] == lItem ) \
248 return n; \
249 } \
250 } \
251 \
252 return wxNOT_FOUND; \
253 } \
254 \
255 /* search for a place to insert item into sorted array (binary search) */ \
256 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
257 { \
258 size_t i, \
259 lo = 0, \
260 hi = m_nCount; \
261 int res; \
262 \
263 while ( lo < hi ) { \
264 i = (lo + hi)/2; \
265 \
266 res = (*fnCompare)((const void *)(long)lItem, \
267 (const void *)(long)(m_pItems[i])); \
268 if ( res < 0 ) \
269 hi = i; \
270 else if ( res > 0 ) \
271 lo = i + 1; \
272 else { \
273 lo = i; \
274 break; \
275 } \
276 } \
277 \
278 return lo; \
279 } \
280 \
281 /* search for an item in a sorted array (binary search) */ \
282 int name::Index(T lItem, CMPFUNC fnCompare) const \
283 { \
284 size_t n = IndexForInsert(lItem, fnCompare); \
285 \
286 return n < m_nCount && \
287 (*fnCompare)((const void *)(long)lItem, \
288 ((const void *)(long)m_pItems[n])) ? (int)n \
289 : wxNOT_FOUND; \
290 } \
291 \
292 /* add item at the end */ \
293 void name::Add(T lItem, size_t nInsert) \
294 { \
295 if (nInsert == 0) \
296 return; \
297 Grow(nInsert); \
298 for (size_t i = 0; i < nInsert; i++) \
299 m_pItems[m_nCount++] = lItem; \
300 } \
301 \
302 /* add item assuming the array is sorted with fnCompare function */ \
303 void name::Add(T lItem, CMPFUNC fnCompare) \
304 { \
305 Insert(lItem, IndexForInsert(lItem, fnCompare)); \
306 } \
307 \
308 /* add item at the given position */ \
309 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
310 { \
311 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
312 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
313 wxT("array size overflow in wxArray::Insert") ); \
314 \
315 if (nInsert == 0) \
316 return; \
317 Grow(nInsert); \
318 \
319 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
320 (m_nCount - nIndex)*sizeof(T)); \
321 for (size_t i = 0; i < nInsert; i++) \
322 m_pItems[nIndex + i] = lItem; \
323 m_nCount += nInsert; \
324 } \
325 \
326 /* removes item from array (by index) */ \
327 void name::RemoveAt(size_t nIndex, size_t nRemove) \
328 { \
329 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
330 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
331 wxT("removing too many elements in wxArray::RemoveAt") ); \
332 \
333 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
334 (m_nCount - nIndex - nRemove)*sizeof(T)); \
335 m_nCount -= nRemove; \
336 } \
337 \
338 /* removes item from array (by value) */ \
339 void name::Remove(T lItem) \
340 { \
341 int iIndex = Index(lItem); \
342 \
343 wxCHECK_RET( iIndex != wxNOT_FOUND, \
344 wxT("removing inexistent item in wxArray::Remove") ); \
345 \
346 RemoveAt((size_t)iIndex); \
347 } \
348 \
349 /* sort array elements using passed comparaison function */ \
350 void name::Sort(CMPFUNC fCmp) \
351 { \
352 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
353 }
354
355 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
356 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
357 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
358 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
359 //_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
360
wxWidgets (Impactor)