]>
Commit | Line | Data |
---|---|---|
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 | |
35 | wxCOMPILE_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) */ \ | |
55 | int 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 */ \ | |
78 | size_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 */ \ | |
86 | name::name() \ | |
87 | { \ | |
88 | m_nSize = \ | |
89 | m_nCount = 0; \ | |
90 | m_pItems = NULL; \ | |
91 | } \ | |
92 | \ | |
93 | /* copy ctor */ \ | |
94 | name::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 */ \ | |
114 | name& 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 */ \ | |
138 | bool 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 */ \ | |
155 | void 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 */ \ | |
185 | void 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 */ \ | |
208 | name::~name() \ | |
209 | { \ | |
210 | wxDELETEA(m_pItems); \ | |
211 | } \ | |
212 | \ | |
213 | /* clears the list */ \ | |
214 | void 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 */ \ | |
223 | void 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 */ \ | |
244 | void 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 */ \ | |
254 | void 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) */ \ | |
272 | size_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) */ \ | |
298 | int 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) */ \ | |
310 | void 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) */ \ | |
322 | void 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 */ \ | |
333 | void name::Sort(CMPFUNC fCmp) \ | |
334 | { \ | |
335 | qsort(m_pItems, m_nCount, sizeof(T), fCmp); \ | |
336 | } \ | |
337 | \ | |
338 | void 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 | \ | |
346 | void 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 | \ | |
354 | void 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 | |
398 | struct 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 | ||
410 | struct 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 | ||
422 | int 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 | ||
444 | template<class F> | |
445 | class wxStringCompareLess | |
446 | { | |
447 | public: | |
448 | wxStringCompareLess(F f) : m_f(f) { } | |
449 | bool operator()(const wxString& s1, const wxString& s2) | |
450 | { return m_f(s1, s2) < 0; } | |
451 | private: | |
452 | F m_f; | |
453 | }; | |
454 | ||
455 | template<class F> | |
456 | wxStringCompareLess<F> wxStringCompare(F f) | |
457 | { | |
458 | return wxStringCompareLess<F>(f); | |
459 | } | |
460 | ||
461 | void wxArrayString::Sort(CompareFunction function) | |
462 | { | |
463 | std::sort(begin(), end(), wxStringCompare(function)); | |
464 | } | |
465 | ||
466 | void 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 | ||
478 | int 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 |