]> git.saurik.com Git - wxWidgets.git/blame - src/common/dynarray.cpp
projects / wxWidgets.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Minor corrections.
[wxWidgets.git] / src / common / dynarray.cpp
CommitLineData
c801d85f
KB		 1///////////////////////////////////////////////////////////////////////////////
2// Name: dynarray.cpp
3// Purpose: implementation of wxBaseArray class
4// Author: Vadim Zeitlin
3bfa4402 5// Modified by:
c801d85f
KB		 6// Created: 12.09.97
7// RCS-ID: $Id$
8// Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
9// Licence: wxWindows license
10///////////////////////////////////////////////////////////////////////////////
11
12// ============================================================================
13// headers
14// ============================================================================
15
16#ifdef __GNUG__
17#pragma implementation "dynarray.h"
18#endif
19
3096bd2f 20#include "wx/wxprec.h"
c801d85f
KB		 21
22#ifdef __BORLANDC__
23 #pragma hdrstop
24#endif
25
26#include "wx/dynarray.h"
3096bd2f 27#include "wx/intl.h"
c801d85f
KB		 28
29#include <stdlib.h>
3bfa4402 30#include <string.h> // for memmove
c801d85f
KB		 31
32#ifndef max
33 #define max(a, b) (((a) > (b)) ? (a) : (b))
34#endif
35
acf88ae6
VZ		 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
38wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *),
39 wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
40
c801d85f
KB		 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// ----------------------------------------------------------------------------
5a1cad6e 53// wxBaseArray - dynamic array of 'T's
c801d85f
KB		 54// ----------------------------------------------------------------------------
55
f1322419 56#define _WX_DEFINE_BASEARRAY(T, name) \
5a1cad6e
GD		 57/* ctor */ \
58name::name() \
59{ \
60 m_nSize = \
61 m_nCount = 0; \
62 m_pItems = (T *)NULL; \
63} \
64 \
65/* copy ctor */ \
66name::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 */ \
86name& 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 \
2abb9d2f
VZ		 109/* allocate new buffer of the given size and move our data to it */ \
110bool 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 \
5a1cad6e 126/* grow the array */ \
3b0b5f13 127void name::Grow(size_t nIncrement) \
5a1cad6e
GD		 128{ \
129 /* only do it if no more place */ \
2b5f62a0 130 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
5a1cad6e 131 if( m_nSize == 0 ) { \
a1db4ad4
SN		 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]; \
5a1cad6e
GD		 137 /* only grow if allocation succeeded */ \
138 if ( m_pItems ) { \
a1db4ad4 139 m_nSize = size; \
5a1cad6e
GD		 140 } \
141 } \
142 else \
143 { \
3b0b5f13
VZ		 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; \
2abb9d2f 151 Realloc(m_nSize + nIncrement); \
5a1cad6e
GD		 152 } \
153 } \
154} \
155 \
2abb9d2f
VZ		 156/* make sure that the array has at least count elements */ \
157void 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 \
5a1cad6e
GD		 179/* dtor */ \
180name::~name() \
181{ \
182 wxDELETEA(m_pItems); \
183} \
184 \
185/* clears the list */ \
186void 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!) */ \
195void 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 */ \
212void 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 } \
226} \
227 \
228/* searches the array for an item (forward or backwards) */ \
229int name::Index(T lItem, bool bFromEnd) const \
230{ \
231 if ( bFromEnd ) { \
232 if ( m_nCount > 0 ) { \
233 size_t n = m_nCount; \
234 do { \
235 if ( m_pItems[--n] == lItem ) \
236 return n; \
237 } \
238 while ( n != 0 ); \
239 } \
240 } \
241 else { \
242 for( size_t n = 0; n < m_nCount; n++ ) { \
243 if( m_pItems[n] == lItem ) \
244 return n; \
245 } \
246 } \
247 \
248 return wxNOT_FOUND; \
249} \
250 \
251/* search for a place to insert item into sorted array (binary search) */ \
252size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
253{ \
254 size_t i, \
255 lo = 0, \
256 hi = m_nCount; \
257 int res; \
258 \
259 while ( lo < hi ) { \
260 i = (lo + hi)/2; \
261 \
acf88ae6
VZ		 262 res = (*fnCompare)((const void *)(long)lItem, \
263 (const void *)(long)(m_pItems[i])); \
5a1cad6e
GD		 264 if ( res < 0 ) \
265 hi = i; \
266 else if ( res > 0 ) \
267 lo = i + 1; \
268 else { \
269 lo = i; \
270 break; \
271 } \
272 } \
273 \
274 return lo; \
275} \
276 \
277/* search for an item in a sorted array (binary search) */ \
278int name::Index(T lItem, CMPFUNC fnCompare) const \
279{ \
280 size_t n = IndexForInsert(lItem, fnCompare); \
281 \
282 return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND; \
283} \
284 \
285/* add item at the end */ \
3b0b5f13 286void name::Add(T lItem, size_t nInsert) \
5a1cad6e 287{ \
2b5f62a0
VZ		 288 if (nInsert == 0) \
289 return; \
3b0b5f13
VZ		 290 Grow(nInsert); \
291 for (size_t i = 0; i < nInsert; i++) \
292 m_pItems[m_nCount++] = lItem; \
5a1cad6e
GD		 293} \
294 \
295/* add item assuming the array is sorted with fnCompare function */ \
296void name::Add(T lItem, CMPFUNC fnCompare) \
297{ \
298 Insert(lItem, IndexForInsert(lItem, fnCompare)); \
299} \
300 \
301/* add item at the given position */ \
3b0b5f13 302void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
5a1cad6e
GD		 303{ \
304 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
3b0b5f13
VZ		 305 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
306 wxT("array size overflow in wxArray::Insert") ); \
5a1cad6e 307 \
2b5f62a0
VZ		 308 if (nInsert == 0) \
309 return; \
3b0b5f13 310 Grow(nInsert); \
5a1cad6e 311 \
3b0b5f13 312 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
5a1cad6e 313 (m_nCount - nIndex)*sizeof(T)); \
3b0b5f13
VZ		 314 for (size_t i = 0; i < nInsert; i++) \
315 m_pItems[nIndex + i] = lItem; \
316 m_nCount += nInsert; \
5a1cad6e
GD		 317} \
318 \
319/* removes item from array (by index) */ \
3b0b5f13 320void name::RemoveAt(size_t nIndex, size_t nRemove) \
5a1cad6e 321{ \
3b0b5f13
VZ		 322 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
323 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
324 wxT("removing too many elements in wxArray::RemoveAt") ); \
5a1cad6e 325 \
3b0b5f13
VZ		 326 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
327 (m_nCount - nIndex - nRemove)*sizeof(T)); \
328 m_nCount -= nRemove; \
5a1cad6e
GD		 329} \
330 \
331/* removes item from array (by value) */ \
332void name::Remove(T lItem) \
333{ \
334 int iIndex = Index(lItem); \
335 \
336 wxCHECK_RET( iIndex != wxNOT_FOUND, \
337 wxT("removing inexistent item in wxArray::Remove") ); \
338 \
339 RemoveAt((size_t)iIndex); \
340} \
341 \
342/* sort array elements using passed comparaison function */ \
343void name::Sort(CMPFUNC fCmp) \
344{ \
345 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
c801d85f
KB		 346}
347
f1322419
VZ		 348_WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
349_WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
350_WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
351_WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
352//_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
c801d85f 353
wxWidgets (Impactor)