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