]> git.saurik.com Git - wxWidgets.git/blob - src/common/dynarray.cpp
projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xti extensions
[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_COMMON(T, name) \
57 /* searches the array for an item (forward or backwards) */ \
58 int name::Index(T lItem, bool bFromEnd) const \
59 { \
60 if ( bFromEnd ) { \
61 if ( size() > 0 ) { \
62 size_t n = size(); \
63 do { \
64 if ( (*this)[--n] == lItem ) \
65 return n; \
66 } \
67 while ( n != 0 ); \
68 } \
69 } \
70 else { \
71 for( size_t n = 0; n < size(); n++ ) { \
72 if( (*this)[n] == lItem ) \
73 return n; \
74 } \
75 } \
76 \
77 return wxNOT_FOUND; \
78 } \
79 \
80 /* add item assuming the array is sorted with fnCompare function */ \
81 size_t name::Add(T lItem, CMPFUNC fnCompare) \
82 { \
83 size_t idx = IndexForInsert(lItem, fnCompare); \
84 Insert(lItem, idx); \
85 return idx; \
86 }
87
88 #if wxUSE_STL
89
90 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
91 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
92 { \
93 Predicate p((SCMPFUNC)fnCompare); \
94 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
95 return it - begin(); \
96 } \
97 \
98 int name::Index(T lItem, CMPFUNC fnCompare) const \
99 { \
100 Predicate p((SCMPFUNC)fnCompare); \
101 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
102 return (it != end() && \
103 p(lItem, *it)) ? (int)(it - begin()) : wxNOT_FOUND; \
104 } \
105 \
106 void name::Shrink() \
107 { \
108 name tmp(*this); \
109 swap(tmp); \
110 }
111
112 #else // if !wxUSE_STL
113
114 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
115 /* ctor */ \
116 name::name() \
117 { \
118 m_nSize = \
119 m_nCount = 0; \
120 m_pItems = (T *)NULL; \
121 } \
122 \
123 /* copy ctor */ \
124 name::name(const name& src) \
125 { \
126 m_nSize = /* not src.m_nSize to save memory */ \
127 m_nCount = src.m_nCount; \
128 \
129 if ( m_nSize != 0 ) { \
130 m_pItems = new T[m_nSize]; \
131 /* only copy if allocation succeeded */ \
132 if ( m_pItems ) { \
133 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
134 } \
135 else { \
136 m_nSize = 0; \
137 } \
138 } \
139 else \
140 m_pItems = (T *) NULL; \
141 } \
142 \
143 /* assignment operator */ \
144 name& name::operator=(const name& src) \
145 { \
146 wxDELETEA(m_pItems); \
147 \
148 m_nSize = /* not src.m_nSize to save memory */ \
149 m_nCount = src.m_nCount; \
150 \
151 if ( m_nSize != 0 ){ \
152 m_pItems = new T[m_nSize]; \
153 /* only copy if allocation succeeded */ \
154 if ( m_pItems ) { \
155 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
156 } \
157 else { \
158 m_nSize = 0; \
159 } \
160 } \
161 else \
162 m_pItems = (T *) NULL; \
163 \
164 return *this; \
165 } \
166 \
167 /* allocate new buffer of the given size and move our data to it */ \
168 bool name::Realloc(size_t nSize) \
169 { \
170 T *pNew = new T[nSize]; \
171 /* only grow if allocation succeeded */ \
172 if ( !pNew ) \
173 return false; \
174 \
175 m_nSize = nSize; \
176 /* copy data to new location */ \
177 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
178 delete [] m_pItems; \
179 m_pItems = pNew; \
180 \
181 return true; \
182 } \
183 \
184 /* grow the array */ \
185 void name::Grow(size_t nIncrement) \
186 { \
187 /* only do it if no more place */ \
188 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
189 if( m_nSize == 0 ) { \
190 /* was empty, determine initial size */ \
191 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
192 if (size < nIncrement) size = nIncrement; \
193 /* allocate some memory */ \
194 m_pItems = new T[size]; \
195 /* only grow if allocation succeeded */ \
196 if ( m_pItems ) { \
197 m_nSize = size; \
198 } \
199 } \
200 else \
201 { \
202 /* add at least 50% but not too much */ \
203 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
204 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
205 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
206 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
207 if ( nIncrement < ndefIncrement ) \
208 nIncrement = ndefIncrement; \
209 Realloc(m_nSize + nIncrement); \
210 } \
211 } \
212 } \
213 \
214 /* make sure that the array has at least count elements */ \
215 void name::SetCount(size_t count, T defval) \
216 { \
217 if ( m_nSize < count ) \
218 { \
219 /* need to realloc memory: don't overallocate it here as if */ \
220 /* SetCount() is called, it probably means that the caller */ \
221 /* knows in advance how many elements there will be in the */ \
222 /* array and so it won't be necessary to realloc it later */ \
223 if ( !Realloc(count) ) \
224 { \
225 /* out of memory -- what can we do? */ \
226 return; \
227 } \
228 } \
229 \
230 /* add new elements if we extend the array */ \
231 while ( m_nCount < count ) \
232 { \
233 m_pItems[m_nCount++] = defval; \
234 } \
235 } \
236 \
237 /* dtor */ \
238 name::~name() \
239 { \
240 wxDELETEA(m_pItems); \
241 } \
242 \
243 /* clears the list */ \
244 void name::Clear() \
245 { \
246 m_nSize = \
247 m_nCount = 0; \
248 \
249 wxDELETEA(m_pItems); \
250 } \
251 \
252 /* pre-allocates memory (frees the previous data!) */ \
253 void name::Alloc(size_t nSize) \
254 { \
255 /* only if old buffer was not big enough */ \
256 if ( nSize > m_nSize ) { \
257 wxDELETEA(m_pItems); \
258 m_nSize = 0; \
259 m_pItems = new T[nSize]; \
260 /* only alloc if allocation succeeded */ \
261 if ( m_pItems ) { \
262 m_nSize = nSize; \
263 } \
264 } \
265 \
266 m_nCount = 0; \
267 } \
268 \
269 /* minimizes the memory usage by freeing unused memory */ \
270 void name::Shrink() \
271 { \
272 /* only do it if we have some memory to free */ \
273 if( m_nCount < m_nSize ) { \
274 /* allocates exactly as much memory as we need */ \
275 T *pNew = new T[m_nCount]; \
276 /* only shrink if allocation succeeded */ \
277 if ( pNew ) { \
278 /* copy data to new location */ \
279 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
280 delete [] m_pItems; \
281 m_pItems = pNew; \
282 \
283 /* update the size of the new block */ \
284 m_nSize = m_nCount; \
285 } \
286 /* else: don't do anything, better keep old memory block! */ \
287 } \
288 } \
289 \
290 /* add item at the end */ \
291 void name::Add(T lItem, size_t nInsert) \
292 { \
293 if (nInsert == 0) \
294 return; \
295 Grow(nInsert); \
296 for (size_t i = 0; i < nInsert; i++) \
297 m_pItems[m_nCount++] = lItem; \
298 } \
299 \
300 /* add item at the given position */ \
301 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
302 { \
303 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
304 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
305 wxT("array size overflow in wxArray::Insert") ); \
306 \
307 if (nInsert == 0) \
308 return; \
309 Grow(nInsert); \
310 \
311 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
312 (m_nCount - nIndex)*sizeof(T)); \
313 for (size_t i = 0; i < nInsert; i++) \
314 m_pItems[nIndex + i] = lItem; \
315 m_nCount += nInsert; \
316 } \
317 \
318 /* search for a place to insert item into sorted array (binary search) */ \
319 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
320 { \
321 size_t i, \
322 lo = 0, \
323 hi = m_nCount; \
324 int res; \
325 \
326 while ( lo < hi ) { \
327 i = (lo + hi)/2; \
328 \
329 res = (*fnCompare)((const void *)(long)lItem, \
330 (const void *)(long)(m_pItems[i])); \
331 if ( res < 0 ) \
332 hi = i; \
333 else if ( res > 0 ) \
334 lo = i + 1; \
335 else { \
336 lo = i; \
337 break; \
338 } \
339 } \
340 \
341 return lo; \
342 } \
343 \
344 /* search for an item in a sorted array (binary search) */ \
345 int name::Index(T lItem, CMPFUNC fnCompare) const \
346 { \
347 size_t n = IndexForInsert(lItem, fnCompare); \
348 \
349 return (n >= m_nCount || \
350 (*fnCompare)((const void *)(long)lItem, \
351 ((const void *)(long)m_pItems[n]))) ? wxNOT_FOUND \
352 : (int)n; \
353 } \
354 \
355 /* removes item from array (by index) */ \
356 void name::RemoveAt(size_t nIndex, size_t nRemove) \
357 { \
358 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
359 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
360 wxT("removing too many elements in wxArray::RemoveAt") ); \
361 \
362 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
363 (m_nCount - nIndex - nRemove)*sizeof(T)); \
364 m_nCount -= nRemove; \
365 } \
366 \
367 /* removes item from array (by value) */ \
368 void name::Remove(T lItem) \
369 { \
370 int iIndex = Index(lItem); \
371 \
372 wxCHECK_RET( iIndex != wxNOT_FOUND, \
373 wxT("removing inexistent item in wxArray::Remove") ); \
374 \
375 RemoveAt((size_t)iIndex); \
376 } \
377 \
378 /* sort array elements using passed comparaison function */ \
379 void name::Sort(CMPFUNC fCmp) \
380 { \
381 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
382 } \
383 \
384 void name::assign(const_iterator first, const_iterator last) \
385 { \
386 clear(); \
387 reserve(last - first); \
388 for(; first != last; ++first) \
389 push_back(*first); \
390 } \
391 \
392 void name::assign(size_type n, const_reference v) \
393 { \
394 clear(); \
395 reserve(n); \
396 for( size_type i = 0; i < n; ++i ) \
397 push_back(v); \
398 } \
399 \
400 void name::insert(iterator it, const_iterator first, const_iterator last) \
401 { \
402 size_t nInsert = last - first, nIndex = it - begin(); \
403 if (nInsert == 0) \
404 return; \
405 Grow(nInsert); \
406 \
407 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
408 (m_nCount - nIndex)*sizeof(T)); \
409 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
410 *it = *first; \
411 m_nCount += nInsert; \
412 }
413
414 #endif
415
416 #define _WX_DEFINE_BASEARRAY(T, name) \
417 _WX_DEFINE_BASEARRAY_COMMON(T, name) \
418 _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)
419
420 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
421 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
422 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
423 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
424 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
425
426 #if wxUSE_STL
427 #include "wx/arrstr.h"
428
429 #include "wx/beforestd.h"
430 #include <functional>
431 #include "wx/afterstd.h"
432
433 _WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase);
434
435 int wxArrayString::Index(const wxChar* sz, bool bCase, bool bFromEnd) const
436 {
437 wxArrayString::const_iterator it;
438
439 if (bCase)
440 it = std::find_if(begin(), end(),
441 std::not1(std::bind2nd(std::ptr_fun(wxStrcmp), sz)));
442 else
443 it = std::find_if(begin(), end(),
444 std::not1(std::bind2nd(std::ptr_fun(wxStricmp), sz)));
445
446 return it == end() ? wxNOT_FOUND : it - begin();
447 }
448
449 class wxStringCompareLess
450 {
451 public:
452 typedef int (wxCMPFUNC_CONV * fnc)(const wxChar*, const wxChar*);
453 public:
454 wxStringCompareLess(fnc f) : m_f(f) { }
455 bool operator()(const wxChar* s1, const wxChar* s2)
456 { return m_f(s1, s2) < 0; }
457 private:
458 fnc m_f;
459 };
460
461 int wxSortedArrayString::Index(const wxChar* sz, bool bCase, bool bFromEnd) const
462 {
463 wxSortedArrayString::const_iterator it;
464
465 if (bCase)
466 it = std::lower_bound(begin(), end(), sz,
467 wxStringCompareLess(wxStrcmp));
468 else
469 it = std::lower_bound(begin(), end(), sz,
470 wxStringCompareLess(wxStricmp));
471
472 if (it == end() || (bCase ? wxStrcmp : wxStricmp)(it->c_str(), sz) != 0)
473 return wxNOT_FOUND;
474 return it - begin();
475 }
476
477 #endif
wxWidgets (Impactor)