projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Remove all lines containing cvs/svn "$Id$" keyword.
[wxWidgets.git] / src / common / dynarray.cpp
1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/dynarray.cpp
3 // Purpose: implementation of wxBaseArray class
4 // Author: Vadim Zeitlin
5 // Modified by:
6 // Created: 12.09.97
7 // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
8 // Licence: wxWindows licence
9 ///////////////////////////////////////////////////////////////////////////////
10
11 // ============================================================================
12 // headers
13 // ============================================================================
14
15 // For compilers that support precompilation, includes "wx.h".
16 #include "wx/wxprec.h"
17
18 #ifdef __BORLANDC__
19 #pragma hdrstop
20 #endif
21
22 #ifndef WX_PRECOMP
23 #include "wx/dynarray.h"
24 #include "wx/intl.h"
25 #endif //WX_PRECOMP
26
27 #include <stdlib.h>
28 #include <string.h> // for memmove
29
30 #if !wxUSE_STD_CONTAINERS
31
32 // we cast the value to long from which we cast it to void * in IndexForInsert:
33 // this can't work if the pointers are not big enough
34 wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr) <= sizeof(void *),
35 wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
36
37 // ============================================================================
38 // constants
39 // ============================================================================
40
41 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
42 #define ARRAY_MAXSIZE_INCREMENT 4096
43
44 // ============================================================================
45 // implementation
46 // ============================================================================
47
48 // ----------------------------------------------------------------------------
49 // wxBaseArray - dynamic array of 'T's
50 // ----------------------------------------------------------------------------
51
52 #define _WX_DEFINE_BASEARRAY(T, name) \
53 /* searches the array for an item (forward or backwards) */ \
54 int name::Index(T lItem, bool bFromEnd) const \
55 { \
56 if ( bFromEnd ) { \
57 if ( size() > 0 ) { \
58 size_t n = size(); \
59 do { \
60 if ( (*this)[--n] == lItem ) \
61 return n; \
62 } \
63 while ( n != 0 ); \
64 } \
65 } \
66 else { \
67 for( size_t n = 0; n < size(); n++ ) { \
68 if( (*this)[n] == lItem ) \
69 return n; \
70 } \
71 } \
72 \
73 return wxNOT_FOUND; \
74 } \
75 \
76 /* add item assuming the array is sorted with fnCompare function */ \
77 size_t name::Add(T lItem, CMPFUNC fnCompare) \
78 { \
79 size_t idx = IndexForInsert(lItem, fnCompare); \
80 Insert(lItem, idx); \
81 return idx; \
82 } \
83 \
84 /* ctor */ \
85 name::name() \
86 { \
87 m_nSize = \
88 m_nCount = 0; \
89 m_pItems = NULL; \
90 } \
91 \
92 /* copy ctor */ \
93 name::name(const name& src) \
94 { \
95 m_nSize = /* not src.m_nSize to save memory */ \
96 m_nCount = src.m_nCount; \
97 \
98 if ( m_nSize != 0 ) { \
99 m_pItems = new T[m_nSize]; \
100 /* only copy if allocation succeeded */ \
101 if ( m_pItems ) { \
102 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
103 } \
104 else { \
105 m_nSize = 0; \
106 } \
107 } \
108 else \
109 m_pItems = NULL; \
110 } \
111 \
112 /* assignment operator */ \
113 name& name::operator=(const name& src) \
114 { \
115 wxDELETEA(m_pItems); \
116 \
117 m_nSize = /* not src.m_nSize to save memory */ \
118 m_nCount = src.m_nCount; \
119 \
120 if ( m_nSize != 0 ){ \
121 m_pItems = new T[m_nSize]; \
122 /* only copy if allocation succeeded */ \
123 if ( m_pItems ) { \
124 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
125 } \
126 else { \
127 m_nSize = 0; \
128 } \
129 } \
130 else \
131 m_pItems = NULL; \
132 \
133 return *this; \
134 } \
135 \
136 /* allocate new buffer of the given size and move our data to it */ \
137 bool name::Realloc(size_t nSize) \
138 { \
139 T *pNew = new T[nSize]; \
140 /* only grow if allocation succeeded */ \
141 if ( !pNew ) \
142 return false; \
143 \
144 m_nSize = nSize; \
145 /* copy data to new location */ \
146 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
147 delete [] m_pItems; \
148 m_pItems = pNew; \
149 \
150 return true; \
151 } \
152 \
153 /* grow the array */ \
154 void name::Grow(size_t nIncrement) \
155 { \
156 /* only do it if no more place */ \
157 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
158 if( m_nSize == 0 ) { \
159 /* was empty, determine initial size */ \
160 size_t sz = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
161 if (sz < nIncrement) sz = nIncrement; \
162 /* allocate some memory */ \
163 m_pItems = new T[sz]; \
164 /* only grow if allocation succeeded */ \
165 if ( m_pItems ) { \
166 m_nSize = sz; \
167 } \
168 } \
169 else \
170 { \
171 /* add at least 50% but not too much */ \
172 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
173 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
174 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
175 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
176 if ( nIncrement < ndefIncrement ) \
177 nIncrement = ndefIncrement; \
178 Realloc(m_nSize + nIncrement); \
179 } \
180 } \
181 } \
182 \
183 /* make sure that the array has at least count elements */ \
184 void name::SetCount(size_t count, T defval) \
185 { \
186 if ( m_nSize < count ) \
187 { \
188 /* need to realloc memory: don't overallocate it here as if */ \
189 /* SetCount() is called, it probably means that the caller */ \
190 /* knows in advance how many elements there will be in the */ \
191 /* array and so it won't be necessary to realloc it later */ \
192 if ( !Realloc(count) ) \
193 { \
194 /* out of memory -- what can we do? */ \
195 return; \
196 } \
197 } \
198 \
199 /* add new elements if we extend the array */ \
200 while ( m_nCount < count ) \
201 { \
202 m_pItems[m_nCount++] = defval; \
203 } \
204 } \
205 \
206 /* dtor */ \
207 name::~name() \
208 { \
209 wxDELETEA(m_pItems); \
210 } \
211 \
212 /* clears the list */ \
213 void name::Clear() \
214 { \
215 m_nSize = \
216 m_nCount = 0; \
217 \
218 wxDELETEA(m_pItems); \
219 } \
220 \
221 /* minimizes the memory usage by freeing unused memory */ \
222 void name::Shrink() \
223 { \
224 /* only do it if we have some memory to free */ \
225 if( m_nCount < m_nSize ) { \
226 /* allocates exactly as much memory as we need */ \
227 T *pNew = new T[m_nCount]; \
228 /* only shrink if allocation succeeded */ \
229 if ( pNew ) { \
230 /* copy data to new location */ \
231 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
232 delete [] m_pItems; \
233 m_pItems = pNew; \
234 \
235 /* update the size of the new block */ \
236 m_nSize = m_nCount; \
237 } \
238 /* else: don't do anything, better keep old memory block! */ \
239 } \
240 } \
241 \
242 /* add item at the end */ \
243 void name::Add(T lItem, size_t nInsert) \
244 { \
245 if (nInsert == 0) \
246 return; \
247 Grow(nInsert); \
248 for (size_t i = 0; i < nInsert; i++) \
249 m_pItems[m_nCount++] = lItem; \
250 } \
251 \
252 /* add item at the given position */ \
253 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
254 { \
255 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
256 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
257 wxT("array size overflow in wxArray::Insert") ); \
258 \
259 if (nInsert == 0) \
260 return; \
261 Grow(nInsert); \
262 \
263 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
264 (m_nCount - nIndex)*sizeof(T)); \
265 for (size_t i = 0; i < nInsert; i++) \
266 m_pItems[nIndex + i] = lItem; \
267 m_nCount += nInsert; \
268 } \
269 \
270 /* search for a place to insert item into sorted array (binary search) */ \
271 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
272 { \
273 size_t i, \
274 lo = 0, \
275 hi = m_nCount; \
276 int res; \
277 \
278 while ( lo < hi ) { \
279 i = (lo + hi)/2; \
280 \
281 res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \
282 (const void *)(wxUIntPtr)(m_pItems[i])); \
283 if ( res < 0 ) \
284 hi = i; \
285 else if ( res > 0 ) \
286 lo = i + 1; \
287 else { \
288 lo = i; \
289 break; \
290 } \
291 } \
292 \
293 return lo; \
294 } \
295 \
296 /* search for an item in a sorted array (binary search) */ \
297 int name::Index(T lItem, CMPFUNC fnCompare) const \
298 { \
299 size_t n = IndexForInsert(lItem, fnCompare); \
300 \
301 return (n >= m_nCount || \
302 (*fnCompare)((const void *)(wxUIntPtr)lItem, \
303 ((const void *)(wxUIntPtr)m_pItems[n]))) \
304 ? wxNOT_FOUND \
305 : (int)n; \
306 } \
307 \
308 /* removes item from array (by index) */ \
309 void name::RemoveAt(size_t nIndex, size_t nRemove) \
310 { \
311 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
312 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
313 wxT("removing too many elements in wxArray::RemoveAt") ); \
314 \
315 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
316 (m_nCount - nIndex - nRemove)*sizeof(T)); \
317 m_nCount -= nRemove; \
318 } \
319 \
320 /* removes item from array (by value) */ \
321 void name::Remove(T lItem) \
322 { \
323 int iIndex = Index(lItem); \
324 \
325 wxCHECK_RET( iIndex != wxNOT_FOUND, \
326 wxT("removing inexistent item in wxArray::Remove") ); \
327 \
328 RemoveAt((size_t)iIndex); \
329 } \
330 \
331 /* sort array elements using passed comparaison function */ \
332 void name::Sort(CMPFUNC fCmp) \
333 { \
334 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
335 } \
336 \
337 void name::assign(const_iterator first, const_iterator last) \
338 { \
339 clear(); \
340 reserve(last - first); \
341 for(; first != last; ++first) \
342 push_back(*first); \
343 } \
344 \
345 void name::assign(size_type n, const_reference v) \
346 { \
347 clear(); \
348 reserve(n); \
349 for( size_type i = 0; i < n; ++i ) \
350 push_back(v); \
351 } \
352 \
353 void name::insert(iterator it, const_iterator first, const_iterator last) \
354 { \
355 size_t nInsert = last - first, nIndex = it - begin(); \
356 if (nInsert == 0) \
357 return; \
358 Grow(nInsert); \
359 \
360 /* old iterator could have been invalidated by Grow(). */ \
361 it = begin() + nIndex; \
362 \
363 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
364 (m_nCount - nIndex)*sizeof(T)); \
365 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
366 *it = *first; \
367 m_nCount += nInsert; \
368 }
369
370 #ifdef __INTELC__
371 #pragma warning(push)
372 #pragma warning(disable: 1684)
373 #pragma warning(disable: 1572)
374 #endif
375
376 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
377 _WX_DEFINE_BASEARRAY(char, wxBaseArrayChar)
378 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
379 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
380 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
381 _WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT)
382 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
383
384 #ifdef __INTELC__
385 #pragma warning(pop)
386 #endif
387
388 #else // wxUSE_STD_CONTAINERS
389
390 #include "wx/arrstr.h"
391
392 #include "wx/beforestd.h"
393 #include <functional>
394 #include "wx/afterstd.h"
395
396 // some compilers (Sun CC being the only known example) distinguish between
397 // extern "C" functions and the functions with C++ linkage and ptr_fun and
398 // wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in
399 // this case, we need the wrappers below to make this work
400 struct wxStringCmp
401 {
402 typedef wxString first_argument_type;
403 typedef wxString second_argument_type;
404 typedef int result_type;
405
406 int operator()(const wxString& s1, const wxString& s2) const
407 {
408 return s1.compare(s2);
409 }
410 };
411
412 struct wxStringCmpNoCase
413 {
414 typedef wxString first_argument_type;
415 typedef wxString second_argument_type;
416 typedef int result_type;
417
418 int operator()(const wxString& s1, const wxString& s2) const
419 {
420 return s1.CmpNoCase(s2);
421 }
422 };
423
424 int wxArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const
425 {
426 wxArrayString::const_iterator it;
427
428 if (bCase)
429 {
430 it = std::find_if(begin(), end(),
431 std::not1(
432 std::bind2nd(
433 wxStringCmp(), str)));
434 }
435 else // !bCase
436 {
437 it = std::find_if(begin(), end(),
438 std::not1(
439 std::bind2nd(
440 wxStringCmpNoCase(), str)));
441 }
442
443 return it == end() ? wxNOT_FOUND : it - begin();
444 }
445
446 template<class F>
447 class wxStringCompareLess
448 {
449 public:
450 wxStringCompareLess(F f) : m_f(f) { }
451 bool operator()(const wxString& s1, const wxString& s2)
452 { return m_f(s1, s2) < 0; }
453 private:
454 F m_f;
455 };
456
457 template<class F>
458 wxStringCompareLess<F> wxStringCompare(F f)
459 {
460 return wxStringCompareLess<F>(f);
461 }
462
463 void wxArrayString::Sort(CompareFunction function)
464 {
465 std::sort(begin(), end(), wxStringCompare(function));
466 }
467
468 void wxArrayString::Sort(bool reverseOrder)
469 {
470 if (reverseOrder)
471 {
472 std::sort(begin(), end(), std::greater<wxString>());
473 }
474 else
475 {
476 std::sort(begin(), end());
477 }
478 }
479
480 int wxSortedArrayString::Index(const wxString& str,
481 bool WXUNUSED_UNLESS_DEBUG(bCase),
482 bool WXUNUSED_UNLESS_DEBUG(bFromEnd)) const
483 {
484 wxASSERT_MSG( bCase && !bFromEnd,
485 "search parameters ignored for sorted array" );
486
487 wxSortedArrayString::const_iterator
488 it = std::lower_bound(begin(), end(), str, wxStringCompare(wxStringCmp()));
489
490 if ( it == end() || str.Cmp(*it) != 0 )
491 return wxNOT_FOUND;
492
493 return it - begin();
494 }
495
496 #endif // !wxUSE_STD_CONTAINERS/wxUSE_STD_CONTAINERS
wxWidgets (Impactor)