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_uiSize  =
  55   m_uiCount = 0;
  56   m_pItems  = NULL;
  57 }
  58
  59 // copy ctor
  60 wxBaseArray::wxBaseArray(const wxBaseArray& src)
  61 {
  62   m_uiSize  = // not src.m_uiSize to save memory
  63   m_uiCount = src.m_uiCount;
  64
  65   if ( m_uiSize != 0 ) {
  66     m_pItems = new long[m_uiSize];
  67     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
  68   }
  69   else
  70     m_pItems = NULL;
  71 }
  72
  73 // assignment operator
  74 wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
  75 {
  76   wxDELETEA(m_pItems);
  77
  78   m_uiSize  = // not src.m_uiSize to save memory
  79   m_uiCount = src.m_uiCount;
  80
  81   if ( m_uiSize != 0 ) {
  82     m_pItems = new long[m_uiSize];
  83     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
  84   }
  85   else
  86     m_pItems = 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_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       size_t uiIncrement = m_uiSize < WX_ARRAY_DEFAULT_INITIAL_SIZE
 105                          ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_uiSize >> 1;
 106       if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT )
 107         uiIncrement = ARRAY_MAXSIZE_INCREMENT;
 108       m_uiSize += uiIncrement;
 109       long *pNew = new long[m_uiSize];
 110
 111       // copy data to new location
 112       memcpy(pNew, m_pItems, m_uiCount*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_uiSize  =
 129   m_uiCount = 0;
 130
 131   wxDELETEA(m_pItems);
 132 }
 133
 134 // pre-allocates memory (frees the previous data!)
 135 void wxBaseArray::Alloc(size_t uiSize)
 136 {
 137   wxASSERT( uiSize > 0 );
 138
 139   // only if old buffer was not big enough
 140   if ( uiSize > m_uiSize ) {
 141     wxDELETEA(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       size_t 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( size_t 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 // search for an item in a sorted array (binary search)
 173 int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
 174 {
 175   size_t i,
 176        lo = 0,
 177        hi = m_uiCount;
 178   int res;
 179
 180   while ( lo < hi ) {
 181     i = (lo + hi)/2;
 182
 183     res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
 184     if ( res < 0 )
 185       hi = i;
 186     else if ( res > 0 )
 187       lo = i + 1;
 188     else
 189       return i;
 190   }
 191
 192   return NOT_FOUND;
 193 }
 194 // add item at the end
 195 void wxBaseArray::Add(long lItem)
 196 {
 197   Grow();
 198   m_pItems[m_uiCount++] = lItem;
 199 }
 200
 201 // add item assuming the array is sorted with fnCompare function
 202 void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
 203 {
 204   size_t i,
 205        lo = 0,
 206        hi = m_uiCount;
 207   int res;
 208
 209   while ( lo < hi ) {
 210     i = (lo + hi)/2;
 211
 212     res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
 213     if ( res < 0 )
 214       hi = i;
 215     else if ( res > 0 )
 216       lo = i + 1;
 217     else {
 218       lo = hi = i;
 219       break;
 220     }
 221   }
 222
 223   wxASSERT( lo == hi ); // I hope I got binary search right :-)
 224
 225   Insert(lItem, lo);
 226 }
 227
 228 // add item at the given position
 229 void wxBaseArray::Insert(long lItem, size_t uiIndex)
 230 {
 231   wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Insert") );
 232
 233   Grow();
 234
 235   memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex],
 236           (m_uiCount - uiIndex)*sizeof(long));
 237   m_pItems[uiIndex] = lItem;
 238   m_uiCount++;
 239 }
 240
 241 // removes item from array (by index)
 242 void wxBaseArray::Remove(size_t uiIndex)
 243 {
 244   wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Remove") );
 245
 246   memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1],
 247           (m_uiCount - uiIndex - 1)*sizeof(long));
 248   m_uiCount--;
 249 }
 250
 251 // removes item from array (by value)
 252 void wxBaseArray::Remove(long lItem)
 253 {
 254   int iIndex = Index(lItem);
 255
 256   wxCHECK_RET( iIndex != NOT_FOUND,
 257                _("removing inexistent item in wxArray::Remove") );
 258
 259   Remove((size_t)iIndex);
 260 }
 261
 262 // sort array elements using passed comparaison function
 263 void wxBaseArray::Sort(CMPFUNC fCmp)
 264 {
 265   qsort(m_pItems, m_uiCount, sizeof(long), fCmp);
 266 }