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
  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( uiIndex <= m_uiCount );
 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( uiIndex <= m_uiCount );
 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( iIndex != NOT_FOUND );
 208
 209   Remove((uint)iIndex);
 210 }
 211
 212 // sort array elements using passed comparaison function
 213 void wxBaseArray::Sort(CMPFUNC fCmp)
 214 {
 215   qsort(m_pItems, m_uiCount, sizeof(long), fCmp);
 216 }