]> git.saurik.com Git - wxWidgets.git/blob - src/common/dynarray.cpp
Changed m_children to GetChildren() -- not all ports are the same!
[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 license
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 // ============================================================================
37 // constants
38 // ============================================================================
39
40 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
41 #define ARRAY_MAXSIZE_INCREMENT 4096
42
43 // ============================================================================
44 // implementation
45 // ============================================================================
46
47 // ----------------------------------------------------------------------------
48 // wxBaseArray - dynamice array of 'long's
49 // ----------------------------------------------------------------------------
50
51 // ctor
52 wxBaseArray::wxBaseArray()
53 {
54 m_nSize =
55 m_nCount = 0;
56 m_pItems = (long *) NULL;
57 }
58
59 // copy ctor
60 wxBaseArray::wxBaseArray(const wxBaseArray& src)
61 {
62 m_nSize = // not src.m_nSize to save memory
63 m_nCount = src.m_nCount;
64
65 if ( m_nSize != 0 ) {
66 m_pItems = new long[m_nSize];
67 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
68 }
69 else
70 m_pItems = (long *) NULL;
71 }
72
73 // assignment operator
74 wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
75 {
76 #if 0
77 wxDELETEA(m_pItems);
78 #else
79 if ( (m_pItems)) {
80 delete (m_pItems);
81 (m_pItems) = 0;
82 }
83 #endif
84
85 m_nSize = // not src.m_nSize to save memory
86 m_nCount = src.m_nCount;
87
88 if ( m_nSize != 0 ) {
89 m_pItems = new long[m_nSize];
90 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
91 }
92 else
93 m_pItems = (long *) NULL;
94
95 return *this;
96 }
97
98 // grow the array
99 void wxBaseArray::Grow()
100 {
101 // only do it if no more place
102 if( m_nCount == m_nSize ) {
103 if( m_nSize == 0 ) {
104 // was empty, alloc some memory
105 m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
106 m_pItems = new long[m_nSize];
107 }
108 else
109 {
110 // add 50% but not too much
111 size_t nIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE
112 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
113 if ( nIncrement > ARRAY_MAXSIZE_INCREMENT )
114 nIncrement = ARRAY_MAXSIZE_INCREMENT;
115 m_nSize += nIncrement;
116 long *pNew = new long[m_nSize];
117
118 // copy data to new location
119 memcpy(pNew, m_pItems, m_nCount*sizeof(long));
120 delete [] m_pItems;
121 m_pItems = pNew;
122 }
123 }
124 }
125
126 // dtor
127 wxBaseArray::~wxBaseArray()
128 {
129 wxDELETEA(m_pItems);
130 }
131
132 // clears the list
133 void wxBaseArray::Clear()
134 {
135 m_nSize =
136 m_nCount = 0;
137
138 wxDELETEA(m_pItems);
139 }
140
141 // pre-allocates memory (frees the previous data!)
142 void wxBaseArray::Alloc(size_t nSize)
143 {
144 wxASSERT( nSize > 0 );
145
146 // only if old buffer was not big enough
147 if ( nSize > m_nSize ) {
148 wxDELETEA(m_pItems);
149 m_pItems = new long[nSize];
150 m_nSize = nSize;
151 }
152
153 m_nCount = 0;
154 }
155
156 // minimizes the memory usage by freeing unused memory
157 void wxBaseArray::Shrink()
158 {
159 // only do it if we have some memory to free
160 if( m_nCount < m_nSize ) {
161 // allocates exactly as much memory as we need
162 long *pNew = new long[m_nCount];
163
164 // copy data to new location
165 memcpy(pNew, m_pItems, m_nCount*sizeof(long));
166 delete [] m_pItems;
167 m_pItems = pNew;
168 }
169 }
170
171 // searches the array for an item (forward or backwards)
172 int wxBaseArray::Index(long lItem, bool bFromEnd) const
173 {
174 if ( bFromEnd ) {
175 if ( m_nCount > 0 ) {
176 size_t n = m_nCount;
177 do {
178 if ( m_pItems[--n] == lItem )
179 return n;
180 }
181 while ( n != 0 );
182 }
183 }
184 else {
185 for( size_t n = 0; n < m_nCount; n++ ) {
186 if( m_pItems[n] == lItem )
187 return n;
188 }
189 }
190
191 return NOT_FOUND;
192 }
193
194 // search for an item in a sorted array (binary search)
195 int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
196 {
197 size_t i,
198 lo = 0,
199 hi = m_nCount;
200 int res;
201
202 while ( lo < hi ) {
203 i = (lo + hi)/2;
204
205 res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
206 if ( res < 0 )
207 hi = i;
208 else if ( res > 0 )
209 lo = i + 1;
210 else
211 return i;
212 }
213
214 return NOT_FOUND;
215 }
216 // add item at the end
217 void wxBaseArray::Add(long lItem)
218 {
219 Grow();
220 m_pItems[m_nCount++] = lItem;
221 }
222
223 // add item assuming the array is sorted with fnCompare function
224 void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
225 {
226 size_t i,
227 lo = 0,
228 hi = m_nCount;
229 int res;
230
231 while ( lo < hi ) {
232 i = (lo + hi)/2;
233
234 res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
235 if ( res < 0 )
236 hi = i;
237 else if ( res > 0 )
238 lo = i + 1;
239 else {
240 lo = hi = i;
241 break;
242 }
243 }
244
245 wxASSERT( lo == hi ); // I hope I got binary search right :-)
246
247 Insert(lItem, lo);
248 }
249
250 // add item at the given position
251 void wxBaseArray::Insert(long lItem, size_t nIndex)
252 {
253 wxCHECK_RET( nIndex <= m_nCount, "bad index in wxArray::Insert" );
254
255 Grow();
256
257 memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex],
258 (m_nCount - nIndex)*sizeof(long));
259 m_pItems[nIndex] = lItem;
260 m_nCount++;
261 }
262
263 // removes item from array (by index)
264 void wxBaseArray::Remove(size_t nIndex)
265 {
266 wxCHECK_RET( nIndex <= m_nCount, "bad index in wxArray::Remove" );
267
268 memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1],
269 (m_nCount - nIndex - 1)*sizeof(long));
270 m_nCount--;
271 }
272
273 // removes item from array (by value)
274 void wxBaseArray::Remove(long lItem)
275 {
276 int iIndex = Index(lItem);
277
278 wxCHECK_RET( iIndex != NOT_FOUND,
279 "removing inexistent item in wxArray::Remove" );
280
281 Remove((size_t)iIndex);
282 }
283
284 // sort array elements using passed comparaison function
285 void wxBaseArray::Sort(CMPFUNC fCmp)
286 {
287 qsort(m_pItems, m_nCount, sizeof(long), fCmp);
288 }