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
  28 #include <stdlib.h>
  29 #include <string.h> // for memmove
  30
  31 #ifndef max
  32   #define max(a, b)   (((a) > (b)) ? (a) : (b))
  33 #endif
  34
  35 // ============================================================================
  36 // constants
  37 // ============================================================================
  38
  39 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
  40 #define   ARRAY_MAXSIZE_INCREMENT    4096
  41
  42 // ============================================================================
  43 // implementation
  44 // ============================================================================
  45
  46 // ----------------------------------------------------------------------------
  47 // wxBaseArray - dynamice array of 'long's
  48 // ----------------------------------------------------------------------------
  49
  50 // ctor
  51 wxBaseArray::wxBaseArray()
  52 {
  53   m_uiSize  =
  54   m_uiCount = 0;
  55   m_pItems  = NULL;
  56 }
  57
  58 // copy ctor
  59 wxBaseArray::wxBaseArray(const wxBaseArray& src)
  60 {
  61   m_uiSize  = // not src.m_uiSize to save memory
  62   m_uiCount = src.m_uiCount;
  63
  64   if ( m_uiSize != 0 ) {
  65     m_pItems = new long[m_uiSize];
  66     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
  67   }
  68   else
  69     m_pItems = NULL;
  70 }
  71
  72 // assignment operator
  73 wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
  74 {
  75   wxDELETEA(m_pItems);
  76
  77   m_uiSize  = // not src.m_uiSize to save memory
  78   m_uiCount = src.m_uiCount;
  79
  80   if ( m_uiSize != 0 ) {
  81     m_pItems = new long[m_uiSize];
  82     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
  83   }
  84   else
  85     m_pItems = NULL;
  86
  87   return *this;
  88 }
  89
  90 // grow the array
  91 void wxBaseArray::Grow()
  92 {
  93   // only do it if no more place
  94   if( m_uiCount == m_uiSize ) {
  95     if( m_uiSize == 0 ) {
  96       // was empty, alloc some memory
  97       m_uiSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
  98       m_pItems = new long[m_uiSize];
  99     }
 100     else
 101     {
 102       // add 50% but not too much
 103       uint uiIncrement = m_uiSize < WX_ARRAY_DEFAULT_INITIAL_SIZE
 104                          ? WX_ARRAY_DEFAULT_INITIAL_SIZE : 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   wxDELETEA(m_pItems);
 122 }
 123
 124 // clears the list
 125 void wxBaseArray::Clear()
 126 {
 127   m_uiSize  =
 128   m_uiCount = 0;
 129
 130   wxDELETEA(m_pItems);
 131 }
 132
 133 // pre-allocates memory (frees the previous data!)
 134 void wxBaseArray::Alloc(uint uiSize)
 135 {
 136   wxASSERT( uiSize > 0 );
 137
 138   // only if old buffer was not big enough
 139   if ( uiSize > m_uiSize ) {
 140     wxDELETEA(m_pItems);
 141     m_pItems = new long[uiSize];
 142     m_uiSize  = uiSize;
 143   }
 144
 145   m_uiCount = 0;
 146 }
 147
 148 // searches the array for an item (forward or backwards)
 149 int wxBaseArray::Index(long lItem, bool bFromEnd) const
 150 {
 151   if ( bFromEnd ) {
 152     if ( m_uiCount > 0 ) {
 153       uint ui = m_uiCount;
 154       do {
 155         if ( m_pItems[--ui] == lItem )
 156           return ui;
 157       }
 158       while ( ui != 0 );
 159     }
 160   }
 161   else {
 162     for( uint ui = 0; ui < m_uiCount; ui++ ) {
 163       if( m_pItems[ui] == lItem )
 164         return ui;
 165     }
 166   }
 167
 168   return NOT_FOUND;
 169 }
 170
 171 // search for an item in a sorted array (binary search)
 172 int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
 173 {
 174   uint i,
 175        lo = 0,
 176        hi = m_uiCount;
 177   int res;
 178
 179   while ( lo < hi ) {
 180     i = (lo + hi)/2;
 181
 182     res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
 183     if ( res < 0 )
 184       hi = i;
 185     else if ( res > 0 )
 186       lo = i + 1;
 187     else
 188       return i;
 189   }
 190
 191   return NOT_FOUND;
 192 }
 193 // add item at the end
 194 void wxBaseArray::Add(long lItem)
 195 {
 196   Grow();
 197   m_pItems[m_uiCount++] = lItem;
 198 }
 199
 200 // add item assuming the array is sorted with fnCompare function
 201 void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
 202 {
 203   uint i,
 204        lo = 0,
 205        hi = m_uiCount;
 206   int res;
 207
 208   while ( lo < hi ) {
 209     i = (lo + hi)/2;
 210
 211     res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
 212     if ( res < 0 )
 213       hi = i;
 214     else if ( res > 0 )
 215       lo = i + 1;
 216     else {
 217       lo = hi = i;
 218       break;
 219     }
 220   }
 221
 222   wxASSERT( lo == hi ); // I hope I got binary search right :-)
 223
 224   Insert(lItem, lo);
 225 }
 226
 227 // add item at the given position
 228 void wxBaseArray::Insert(long lItem, uint uiIndex)
 229 {
 230   wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Insert" );
 231
 232   Grow();
 233
 234   memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex],
 235           (m_uiCount - uiIndex)*sizeof(long));
 236   m_pItems[uiIndex] = lItem;
 237   m_uiCount++;
 238 }
 239
 240 // removes item from array (by index)
 241 void wxBaseArray::Remove(uint uiIndex)
 242 {
 243   wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Remove" );
 244
 245   memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1],
 246           (m_uiCount - uiIndex - 1)*sizeof(long));
 247   m_uiCount--;
 248 }
 249
 250 // removes item from array (by value)
 251 void wxBaseArray::Remove(long lItem)
 252 {
 253   int iIndex = Index(lItem);
 254
 255   wxCHECK_RET( iIndex != NOT_FOUND,
 256                "removing inexistent item in wxArray::Remove" );
 257
 258   Remove((uint)iIndex);
 259 }
 260
 261 // sort array elements using passed comparaison function
 262 void wxBaseArray::Sort(CMPFUNC fCmp)
 263 {
 264   qsort(m_pItems, m_uiCount, sizeof(long), fCmp);
 265 }