| 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 | |
| 28 | #include <stdlib.h> |
| 29 | |
| 30 | #ifndef max |
| 31 | #define max(a, b) (((a) > (b)) ? (a) : (b)) |
| 32 | #endif |
| 33 | |
| 34 | // ============================================================================ |
| 35 | // constants |
| 36 | // ============================================================================ |
| 37 | |
| 38 | // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT) |
| 39 | #define ARRAY_MAXSIZE_INCREMENT 4096 |
| 40 | |
| 41 | // ============================================================================ |
| 42 | // implementation |
| 43 | // ============================================================================ |
| 44 | |
| 45 | // ---------------------------------------------------------------------------- |
| 46 | // wxBaseArray - dynamice array of 'long's |
| 47 | // ---------------------------------------------------------------------------- |
| 48 | |
| 49 | // ctor |
| 50 | wxBaseArray::wxBaseArray() |
| 51 | { |
| 52 | m_uiSize = |
| 53 | m_uiCount = 0; |
| 54 | m_pItems = NULL; |
| 55 | } |
| 56 | |
| 57 | // copy ctor |
| 58 | wxBaseArray::wxBaseArray(const wxBaseArray& src) |
| 59 | { |
| 60 | m_uiSize = src.m_uiSize; |
| 61 | m_uiCount = src.m_uiCount; |
| 62 | |
| 63 | if ( m_uiSize != 0 ) |
| 64 | m_pItems = new long[m_uiSize]; |
| 65 | else |
| 66 | m_pItems = NULL; |
| 67 | |
| 68 | if ( m_uiCount != 0 ) |
| 69 | memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); |
| 70 | } |
| 71 | |
| 72 | // copy operator |
| 73 | wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src) |
| 74 | { |
| 75 | DELETEA(m_pItems); |
| 76 | |
| 77 | m_uiSize = src.m_uiSize; |
| 78 | m_uiCount = src.m_uiCount; |
| 79 | |
| 80 | if ( m_uiSize != 0 ) |
| 81 | m_pItems = new long[m_uiSize]; |
| 82 | else |
| 83 | m_pItems = NULL; |
| 84 | |
| 85 | if ( m_uiCount != 0 ) |
| 86 | memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); |
| 87 | |
| 88 | return *this; |
| 89 | } |
| 90 | |
| 91 | // grow the array |
| 92 | void wxBaseArray::Grow() |
| 93 | { |
| 94 | // only do it if no more place |
| 95 | if( m_uiCount == m_uiSize ) { |
| 96 | if( m_uiSize == 0 ) { |
| 97 | // was empty, alloc some memory |
| 98 | m_uiSize = WX_ARRAY_DEFAULT_INITIAL_SIZE; |
| 99 | m_pItems = new long[m_uiSize]; |
| 100 | } |
| 101 | else |
| 102 | { |
| 103 | // add 50% but not too much |
| 104 | uint uiIncrement = m_uiSize >> 1; |
| 105 | if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT ) |
| 106 | uiIncrement = ARRAY_MAXSIZE_INCREMENT; |
| 107 | m_uiSize += uiIncrement; |
| 108 | long *pNew = new long[m_uiSize]; |
| 109 | |
| 110 | // copy data to new location |
| 111 | memcpy(pNew, m_pItems, m_uiCount*sizeof(long)); |
| 112 | delete [] m_pItems; |
| 113 | m_pItems = pNew; |
| 114 | } |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | // dtor |
| 119 | wxBaseArray::~wxBaseArray() |
| 120 | { |
| 121 | DELETEA(m_pItems); |
| 122 | } |
| 123 | |
| 124 | // clears the list |
| 125 | void wxBaseArray::Clear() |
| 126 | { |
| 127 | m_uiSize = |
| 128 | m_uiCount = 0; |
| 129 | |
| 130 | DELETEA(m_pItems); |
| 131 | m_pItems = NULL; |
| 132 | } |
| 133 | |
| 134 | // pre-allocates memory (frees the previous data!) |
| 135 | void wxBaseArray::Alloc(uint uiSize) |
| 136 | { |
| 137 | wxASSERT( uiSize > 0 ); |
| 138 | |
| 139 | // only if old buffer was not big enough |
| 140 | if ( uiSize > m_uiSize ) { |
| 141 | DELETEA(m_pItems); |
| 142 | m_pItems = new long[uiSize]; |
| 143 | m_uiSize = uiSize; |
| 144 | } |
| 145 | |
| 146 | m_uiCount = 0; |
| 147 | } |
| 148 | |
| 149 | // searches the array for an item (forward or backwards) |
| 150 | int wxBaseArray::Index(long lItem, bool bFromEnd) const |
| 151 | { |
| 152 | if ( bFromEnd ) { |
| 153 | if ( m_uiCount > 0 ) { |
| 154 | uint ui = m_uiCount; |
| 155 | do { |
| 156 | if ( m_pItems[--ui] == lItem ) |
| 157 | return ui; |
| 158 | } |
| 159 | while ( ui != 0 ); |
| 160 | } |
| 161 | } |
| 162 | else { |
| 163 | for( uint ui = 0; ui < m_uiCount; ui++ ) { |
| 164 | if( m_pItems[ui] == lItem ) |
| 165 | return ui; |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | return NOT_FOUND; |
| 170 | } |
| 171 | |
| 172 | // add item at the end |
| 173 | void wxBaseArray::Add(long lItem) |
| 174 | { |
| 175 | Grow(); |
| 176 | m_pItems[m_uiCount++] = lItem; |
| 177 | } |
| 178 | |
| 179 | // add item at the given position |
| 180 | void wxBaseArray::Insert(long lItem, uint uiIndex) |
| 181 | { |
| 182 | wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Insert" ); |
| 183 | |
| 184 | Grow(); |
| 185 | |
| 186 | memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex], |
| 187 | (m_uiCount - uiIndex)*sizeof(long)); |
| 188 | m_pItems[uiIndex] = lItem; |
| 189 | m_uiCount++; |
| 190 | } |
| 191 | |
| 192 | // removes item from array (by index) |
| 193 | void wxBaseArray::Remove(uint uiIndex) |
| 194 | { |
| 195 | wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Remove" ); |
| 196 | |
| 197 | memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1], |
| 198 | (m_uiCount - uiIndex - 1)*sizeof(long)); |
| 199 | m_uiCount--; |
| 200 | } |
| 201 | |
| 202 | // removes item from array (by value) |
| 203 | void wxBaseArray::Remove(long lItem) |
| 204 | { |
| 205 | int iIndex = Index(lItem); |
| 206 | |
| 207 | wxCHECK_RET( iIndex != NOT_FOUND, |
| 208 | "removing inexistent item in wxArray::Remove" ); |
| 209 | |
| 210 | Remove((uint)iIndex); |
| 211 | } |
| 212 | |
| 213 | // sort array elements using passed comparaison function |
| 214 | void wxBaseArray::Sort(CMPFUNC fCmp) |
| 215 | { |
| 216 | qsort(m_pItems, m_uiCount, sizeof(long), fCmp); |
| 217 | } |