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   wxDELETEA(m_pItems);
  77
  78   m_nSize  = // not src.m_nSize to save memory
  79   m_nCount = src.m_nCount;
  80
  81   if ( m_nSize != 0 ) {
  82     m_pItems = new long[m_nSize];
  83     memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
  84   }
  85   else
  86     m_pItems = (long *) NULL;
  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_nCount == m_nSize ) {
  96     if( m_nSize == 0 ) {
  97       // was empty, alloc some memory
  98       m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
  99       m_pItems = new long[m_nSize];
 100     }
 101     else
 102     {
 103       // add 50% but not too much
 104       size_t nIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE
 105                          ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
 106       if ( nIncrement > ARRAY_MAXSIZE_INCREMENT )
 107         nIncrement = ARRAY_MAXSIZE_INCREMENT;
 108       m_nSize += nIncrement;
 109       long *pNew = new long[m_nSize];
 110
 111       // copy data to new location
 112       memcpy(pNew, m_pItems, m_nCount*sizeof(long));
 113       delete [] m_pItems;
 114       m_pItems = pNew;
 115     }
 116   }
 117 }
 118
 119 // dtor
 120 wxBaseArray::~wxBaseArray()
 121 {
 122   wxDELETEA(m_pItems);
 123 }
 124
 125 // clears the list
 126 void wxBaseArray::Clear()
 127 {
 128   m_nSize  =
 129   m_nCount = 0;
 130
 131   wxDELETEA(m_pItems);
 132 }
 133
 134 // pre-allocates memory (frees the previous data!)
 135 void wxBaseArray::Alloc(size_t nSize)
 136 {
 137   // only if old buffer was not big enough
 138   if ( nSize > m_nSize ) {
 139     wxDELETEA(m_pItems);
 140     m_pItems = new long[nSize];
 141     m_nSize  = nSize;
 142   }
 143
 144   m_nCount = 0;
 145 }
 146
 147 // minimizes the memory usage by freeing unused memory
 148 void wxBaseArray::Shrink()
 149 {
 150   // only do it if we have some memory to free
 151   if( m_nCount < m_nSize ) {
 152     // allocates exactly as much memory as we need
 153     long *pNew = new long[m_nCount];
 154
 155     // copy data to new location
 156     memcpy(pNew, m_pItems, m_nCount*sizeof(long));
 157     delete [] m_pItems;
 158     m_pItems = pNew;
 159   }
 160 }
 161
 162 // searches the array for an item (forward or backwards)
 163 int wxBaseArray::Index(long lItem, bool bFromEnd) const
 164 {
 165   if ( bFromEnd ) {
 166     if ( m_nCount > 0 ) {
 167       size_t n = m_nCount;
 168       do {
 169         if ( m_pItems[--n] == lItem )
 170           return n;
 171       }
 172       while ( n != 0 );
 173     }
 174   }
 175   else {
 176     for( size_t n = 0; n < m_nCount; n++ ) {
 177       if( m_pItems[n] == lItem )
 178         return n;
 179     }
 180   }
 181
 182   return wxNOT_FOUND;
 183 }
 184
 185 // search for a place to insert an item into a sorted array (binary search)
 186 size_t wxBaseArray::IndexForInsert(long lItem, CMPFUNC fnCompare) const
 187 {
 188   size_t i,
 189        lo = 0,
 190        hi = m_nCount;
 191   int res;
 192
 193   while ( lo < hi ) {
 194     i = (lo + hi)/2;
 195
 196     res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
 197     if ( res < 0 )
 198       hi = i;
 199     else if ( res > 0 )
 200       lo = i + 1;
 201     else {
 202       lo = i;
 203       break;
 204     }
 205   }
 206
 207   return lo;
 208 }
 209
 210 // search for an item in a sorted array (binary search)
 211 int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
 212 {
 213     size_t n = IndexForInsert(lItem, fnCompare);
 214
 215     return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;
 216 }
 217
 218 // add item at the end
 219 void wxBaseArray::Add(long lItem)
 220 {
 221   Grow();
 222   m_pItems[m_nCount++] = lItem;
 223 }
 224
 225 // add item assuming the array is sorted with fnCompare function
 226 void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
 227 {
 228   Insert(lItem, IndexForInsert(lItem, fnCompare));
 229 }
 230
 231 // add item at the given position
 232 void wxBaseArray::Insert(long lItem, size_t nIndex)
 233 {
 234   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );
 235
 236   Grow();
 237
 238   memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex],
 239           (m_nCount - nIndex)*sizeof(long));
 240   m_pItems[nIndex] = lItem;
 241   m_nCount++;
 242 }
 243
 244 // removes item from array (by index)
 245 void wxBaseArray::RemoveAt(size_t nIndex)
 246 {
 247   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") );
 248
 249   memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1],
 250           (m_nCount - nIndex - 1)*sizeof(long));
 251   m_nCount--;
 252 }
 253
 254 // removes item from array (by value)
 255 void wxBaseArray::Remove(long lItem)
 256 {
 257   int iIndex = Index(lItem);
 258
 259   wxCHECK_RET( iIndex != wxNOT_FOUND,
 260                wxT("removing inexistent item in wxArray::Remove") );
 261
 262   RemoveAt((size_t)iIndex);
 263 }
 264
 265 // sort array elements using passed comparaison function
 266 void wxBaseArray::Sort(CMPFUNC fCmp)
 267 {
 268   qsort(m_pItems, m_nCount, sizeof(long), fCmp);
 269 }