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 wxNOT_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 wxNOT_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 != wxNOT_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 }