]> git.saurik.com Git - wxWidgets.git/blame - src/common/dynarray.cpp
mimetype.cpp/.h split into unix,mac,msw
[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
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
52wxBaseArray::wxBaseArray()
53{
3093cef8
VZ
54 m_nSize =
55 m_nCount = 0;
c67daf87 56 m_pItems = (long *) NULL;
c801d85f
KB
57}
58
59// copy ctor
60wxBaseArray::wxBaseArray(const wxBaseArray& src)
61{
3093cef8
VZ
62 m_nSize = // not src.m_nSize to save memory
63 m_nCount = src.m_nCount;
c801d85f 64
3093cef8
VZ
65 if ( m_nSize != 0 ) {
66 m_pItems = new long[m_nSize];
67 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
3bfa4402 68 }
c801d85f 69 else
c67daf87 70 m_pItems = (long *) NULL;
c801d85f
KB
71}
72
3bfa4402 73// assignment operator
c801d85f
KB
74wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
75{
c67daf87 76#if 0
a3622daa 77 wxDELETEA(m_pItems);
c67daf87
UR
78#else
79 if ( (m_pItems)) {
80 delete (m_pItems);
81 (m_pItems) = 0;
82 }
83#endif
c801d85f 84
3093cef8
VZ
85 m_nSize = // not src.m_nSize to save memory
86 m_nCount = src.m_nCount;
c801d85f 87
3093cef8
VZ
88 if ( m_nSize != 0 ) {
89 m_pItems = new long[m_nSize];
90 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
3bfa4402 91 }
c801d85f 92 else
c67daf87 93 m_pItems = (long *) NULL;
c801d85f 94
c801d85f
KB
95 return *this;
96}
97
98// grow the array
99void wxBaseArray::Grow()
100{
101 // only do it if no more place
3093cef8
VZ
102 if( m_nCount == m_nSize ) {
103 if( m_nSize == 0 ) {
c801d85f 104 // was empty, alloc some memory
3093cef8
VZ
105 m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
106 m_pItems = new long[m_nSize];
c801d85f
KB
107 }
108 else
109 {
110 // add 50% but not too much
3093cef8
VZ
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];
c801d85f
KB
117
118 // copy data to new location
3093cef8 119 memcpy(pNew, m_pItems, m_nCount*sizeof(long));
c801d85f
KB
120 delete [] m_pItems;
121 m_pItems = pNew;
122 }
123 }
124}
125
126// dtor
127wxBaseArray::~wxBaseArray()
128{
a3622daa 129 wxDELETEA(m_pItems);
c801d85f
KB
130}
131
132// clears the list
133void wxBaseArray::Clear()
134{
3093cef8
VZ
135 m_nSize =
136 m_nCount = 0;
c801d85f 137
a3622daa 138 wxDELETEA(m_pItems);
c801d85f
KB
139}
140
141// pre-allocates memory (frees the previous data!)
3093cef8 142void wxBaseArray::Alloc(size_t nSize)
c801d85f 143{
3093cef8 144 wxASSERT( nSize > 0 );
c801d85f
KB
145
146 // only if old buffer was not big enough
3093cef8 147 if ( nSize > m_nSize ) {
a3622daa 148 wxDELETEA(m_pItems);
3093cef8
VZ
149 m_pItems = new long[nSize];
150 m_nSize = nSize;
c801d85f
KB
151 }
152
3093cef8
VZ
153 m_nCount = 0;
154}
155
156// minimizes the memory usage by freeing unused memory
157void 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 }
c801d85f
KB
169}
170
171// searches the array for an item (forward or backwards)
05fafecd 172int wxBaseArray::Index(long lItem, bool bFromEnd) const
c801d85f
KB
173{
174 if ( bFromEnd ) {
3093cef8
VZ
175 if ( m_nCount > 0 ) {
176 size_t n = m_nCount;
c801d85f 177 do {
3093cef8
VZ
178 if ( m_pItems[--n] == lItem )
179 return n;
c801d85f 180 }
3093cef8 181 while ( n != 0 );
c801d85f
KB
182 }
183 }
184 else {
3093cef8
VZ
185 for( size_t n = 0; n < m_nCount; n++ ) {
186 if( m_pItems[n] == lItem )
187 return n;
c801d85f
KB
188 }
189 }
190
3c67202d 191 return wxNOT_FOUND;
c801d85f
KB
192}
193
3bfa4402 194// search for an item in a sorted array (binary search)
e99c3048 195int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
3bfa4402 196{
c86f1403 197 size_t i,
3bfa4402 198 lo = 0,
3093cef8 199 hi = m_nCount;
3bfa4402
VZ
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
3c67202d 214 return wxNOT_FOUND;
3bfa4402 215}
c801d85f
KB
216// add item at the end
217void wxBaseArray::Add(long lItem)
218{
219 Grow();
3093cef8 220 m_pItems[m_nCount++] = lItem;
c801d85f
KB
221}
222
3bfa4402
VZ
223// add item assuming the array is sorted with fnCompare function
224void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
225{
c86f1403 226 size_t i,
3bfa4402 227 lo = 0,
3093cef8 228 hi = m_nCount;
3bfa4402
VZ
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
c801d85f 250// add item at the given position
3093cef8 251void wxBaseArray::Insert(long lItem, size_t nIndex)
c801d85f 252{
223d09f6 253 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );
c801d85f
KB
254
255 Grow();
256
3093cef8
VZ
257 memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex],
258 (m_nCount - nIndex)*sizeof(long));
259 m_pItems[nIndex] = lItem;
260 m_nCount++;
c801d85f
KB
261}
262
263// removes item from array (by index)
8a729bb8 264void wxBaseArray::RemoveAt(size_t nIndex)
c801d85f 265{
8a729bb8 266 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") );
c801d85f 267
3093cef8
VZ
268 memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1],
269 (m_nCount - nIndex - 1)*sizeof(long));
270 m_nCount--;
c801d85f
KB
271}
272
273// removes item from array (by value)
274void wxBaseArray::Remove(long lItem)
275{
276 int iIndex = Index(lItem);
277
3c67202d 278 wxCHECK_RET( iIndex != wxNOT_FOUND,
223d09f6 279 wxT("removing inexistent item in wxArray::Remove") );
c801d85f 280
f373f197 281 RemoveAt((size_t)iIndex);
c801d85f
KB
282}
283
284// sort array elements using passed comparaison function
285void wxBaseArray::Sort(CMPFUNC fCmp)
286{
3093cef8 287 qsort(m_pItems, m_nCount, sizeof(long), fCmp);
c801d85f 288}