home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2240.zip / wxWindows-2.4.0 / src / common / dynarray.cpp < prev    next >
C/C++ Source or Header  |  2002-09-24  |  23KB  |  322 lines
  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: dynarray.cpp,v 1.27.2.2 2002/09/24 00:35:08 RD Exp $
  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. // we cast the value to long from which we cast it to void * in IndexForInsert:
  37. // this can't work if the pointers are not big enough
  38. wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *),
  39.                        wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
  40.  
  41. // ============================================================================
  42. // constants
  43. // ============================================================================
  44.  
  45. // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
  46. #define   ARRAY_MAXSIZE_INCREMENT    4096
  47.  
  48. // ============================================================================
  49. // implementation
  50. // ============================================================================
  51.  
  52. // ----------------------------------------------------------------------------
  53. // wxBaseArray - dynamic array of 'T's
  54. // ----------------------------------------------------------------------------
  55.  
  56. #define _WX_DEFINE_BASEARRAY(T, name)                                       \
  57. /* ctor */                                                                  \
  58. name::name()                                                                \
  59. {                                                                           \
  60.   m_nSize  =                                                                \
  61.   m_nCount = 0;                                                             \
  62.   m_pItems = (T *)NULL;                                                     \
  63. }                                                                           \
  64.                                                                             \
  65. /* copy ctor */                                                             \
  66. name::name(const name& src)                                                 \
  67. {                                                                           \
  68.   m_nSize  = /* not src.m_nSize to save memory */                           \
  69.   m_nCount = src.m_nCount;                                                  \
  70.                                                                             \
  71.   if ( m_nSize != 0 ) {                                                     \
  72.       m_pItems = new T[m_nSize];                                            \
  73.       /* only copy if allocation succeeded */                               \
  74.       if ( m_pItems ) {                                                     \
  75.           memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
  76.       }                                                                     \
  77.       else {                                                                \
  78.           m_nSize = 0;                                                      \
  79.       }                                                                     \
  80.   }                                                                         \
  81.   else                                                                      \
  82.     m_pItems = (T *) NULL;                                                  \
  83. }                                                                           \
  84.                                                                             \
  85. /* assignment operator */                                                   \
  86. name& name::operator=(const name& src)                                      \
  87. {                                                                           \
  88.   wxDELETEA(m_pItems);                                                      \
  89.                                                                             \
  90.   m_nSize  = /* not src.m_nSize to save memory */                           \
  91.   m_nCount = src.m_nCount;                                                  \
  92.                                                                             \
  93.   if ( m_nSize != 0 ){                                                      \
  94.       m_pItems = new T[m_nSize];                                            \
  95.       /* only copy if allocation succeeded */                               \
  96.       if ( m_pItems ) {                                                     \
  97.           memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
  98.       }                                                                     \
  99.       else {                                                                \
  100.           m_nSize = 0;                                                      \
  101.       }                                                                     \
  102.   }                                                                         \
  103.   else                                                                      \
  104.     m_pItems = (T *) NULL;                                                  \
  105.                                                                             \
  106.   return *this;                                                             \
  107. }                                                                           \
  108.                                                                             \
  109. /* grow the array */                                                        \
  110. void name::Grow(size_t nIncrement)                                          \
  111. {                                                                           \
  112.   /* only do it if no more place */                                         \
  113.   if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) {      \
  114.     if( m_nSize == 0 ) {                                                    \
  115.       /* was empty, determine initial size */                               \
  116.       size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE;                          \
  117.       if (size < nIncrement) size = nIncrement;                             \
  118.       /* allocate some memory */                                            \
  119.       m_pItems = new T[size];                                               \
  120.       /* only grow if allocation succeeded */                               \
  121.       if ( m_pItems ) {                                                     \
  122.           m_nSize = size;                                                   \
  123.       }                                                                     \
  124.     }                                                                       \
  125.     else                                                                    \
  126.     {                                                                       \
  127.       /* add at least 50% but not too much */                               \
  128.       size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE        \
  129.                             ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
  130.       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )                        \
  131.         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;                            \
  132.       if ( nIncrement < ndefIncrement )                                     \
  133.         nIncrement = ndefIncrement;                                         \
  134.       T *pNew = new T[m_nSize + nIncrement];                                \
  135.       /* only grow if allocation succeeded */                               \
  136.       if ( pNew ) {                                                         \
  137.           m_nSize += nIncrement;                                            \
  138.           /* copy data to new location */                                   \
  139.           memcpy(pNew, m_pItems, m_nCount*sizeof(T));                       \
  140.           delete [] m_pItems;                                               \
  141.           m_pItems = pNew;                                                  \
  142.       }                                                                     \
  143.     }                                                                       \
  144.   }                                                                         \
  145. }                                                                           \
  146.                                                                             \
  147. /* dtor */                                                                  \
  148. name::~name()                                                               \
  149. {                                                                           \
  150.   wxDELETEA(m_pItems);                                                      \
  151. }                                                                           \
  152.                                                                             \
  153. /* clears the list */                                                       \
  154. void name::Clear()                                                          \
  155. {                                                                           \
  156.   m_nSize  =                                                                \
  157.   m_nCount = 0;                                                             \
  158.                                                                             \
  159.   wxDELETEA(m_pItems);                                                      \
  160. }                                                                           \
  161.                                                                             \
  162. /* pre-allocates memory (frees the previous data!) */                       \
  163. void name::Alloc(size_t nSize)                                              \
  164. {                                                                           \
  165.   /* only if old buffer was not big enough */                               \
  166.   if ( nSize > m_nSize ) {                                                  \
  167.     wxDELETEA(m_pItems);                                                    \
  168.     m_nSize  = 0;                                                           \
  169.     m_pItems = new T[nSize];                                                \
  170.     /* only alloc if allocation succeeded */                                \
  171.     if ( m_pItems ) {                                                       \
  172.         m_nSize  = nSize;                                                   \
  173.     }                                                                       \
  174.   }                                                                         \
  175.                                                                             \
  176.   m_nCount = 0;                                                             \
  177. }                                                                           \
  178.                                                                             \
  179. /* minimizes the memory usage by freeing unused memory */                   \
  180. void name::Shrink()                                                         \
  181. {                                                                           \
  182.   /* only do it if we have some memory to free */                           \
  183.   if( m_nCount < m_nSize ) {                                                \
  184.     /* allocates exactly as much memory as we need */                       \
  185.     T *pNew = new T[m_nCount];                                              \
  186.     /* only shrink if allocation succeeded */                               \
  187.     if ( pNew ) {                                                           \
  188.         /* copy data to new location */                                     \
  189.         memcpy(pNew, m_pItems, m_nCount*sizeof(T));                         \
  190.         delete [] m_pItems;                                                 \
  191.         m_pItems = pNew;                                                    \
  192.     }                                                                       \
  193.   }                                                                         \
  194. }                                                                           \
  195.                                                                             \
  196. /* searches the array for an item (forward or backwards) */                 \
  197. int name::Index(T lItem, bool bFromEnd) const                               \
  198. {                                                                           \
  199.   if ( bFromEnd ) {                                                         \
  200.     if ( m_nCount > 0 ) {                                                   \
  201.       size_t n = m_nCount;                                                  \
  202.       do {                                                                  \
  203.         if ( m_pItems[--n] == lItem )                                       \
  204.           return n;                                                         \
  205.       }                                                                     \
  206.       while ( n != 0 );                                                     \
  207.     }                                                                       \
  208.   }                                                                         \
  209.   else {                                                                    \
  210.     for( size_t n = 0; n < m_nCount; n++ ) {                                \
  211.       if( m_pItems[n] == lItem )                                            \
  212.         return n;                                                           \
  213.     }                                                                       \
  214.   }                                                                         \
  215.                                                                             \
  216.   return wxNOT_FOUND;                                                       \
  217. }                                                                           \
  218.                                                                             \
  219. /* search for a place to insert item into sorted array (binary search) */   \
  220. size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const               \
  221. {                                                                           \
  222.   size_t i,                                                                 \
  223.        lo = 0,                                                              \
  224.        hi = m_nCount;                                                       \
  225.   int res;                                                                  \
  226.                                                                             \
  227.   while ( lo < hi ) {                                                       \
  228.     i = (lo + hi)/2;                                                        \
  229.                                                                             \
  230.     res = (*fnCompare)((const void *)(long)lItem,                           \
  231.                        (const void *)(long)(m_pItems[i]));                  \
  232.     if ( res < 0 )                                                          \
  233.       hi = i;                                                               \
  234.     else if ( res > 0 )                                                     \
  235.       lo = i + 1;                                                           \
  236.     else {                                                                  \
  237.       lo = i;                                                               \
  238.       break;                                                                \
  239.     }                                                                       \
  240.   }                                                                         \
  241.                                                                             \
  242.   return lo;                                                                \
  243. }                                                                           \
  244.                                                                             \
  245. /* search for an item in a sorted array (binary search) */                  \
  246. int name::Index(T lItem, CMPFUNC fnCompare) const                           \
  247. {                                                                           \
  248.     size_t n = IndexForInsert(lItem, fnCompare);                            \
  249.                                                                             \
  250.     return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;     \
  251. }                                                                           \
  252.                                                                             \
  253. /* add item at the end */                                                   \
  254. void name::Add(T lItem, size_t nInsert)                                     \
  255. {                                                                           \
  256.   if (nInsert == 0)                                                         \
  257.       return;                                                               \
  258.   Grow(nInsert);                                                            \
  259.   for (size_t i = 0; i < nInsert; i++)                                      \
  260.       m_pItems[m_nCount++] = lItem;                                         \
  261. }                                                                           \
  262.                                                                             \
  263. /* add item assuming the array is sorted with fnCompare function */         \
  264. void name::Add(T lItem, CMPFUNC fnCompare)                                  \
  265. {                                                                           \
  266.   Insert(lItem, IndexForInsert(lItem, fnCompare));                          \
  267. }                                                                           \
  268.                                                                             \
  269. /* add item at the given position */                                        \
  270. void name::Insert(T lItem, size_t nIndex, size_t nInsert)                   \
  271. {                                                                           \
  272.   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );   \
  273.   wxCHECK_RET( m_nCount <= m_nCount + nInsert,                              \
  274.                wxT("array size overflow in wxArray::Insert") );             \
  275.                                                                             \
  276.   if (nInsert == 0)                                                         \
  277.       return;                                                               \
  278.   Grow(nInsert);                                                            \
  279.                                                                             \
  280.   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],                   \
  281.           (m_nCount - nIndex)*sizeof(T));                                   \
  282.   for (size_t i = 0; i < nInsert; i++)                                      \
  283.       m_pItems[nIndex + i] = lItem;                                         \
  284.   m_nCount += nInsert;                                                      \
  285. }                                                                           \
  286.                                                                             \
  287. /* removes item from array (by index) */                                    \
  288. void name::RemoveAt(size_t nIndex, size_t nRemove)                          \
  289. {                                                                           \
  290.   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") );  \
  291.   wxCHECK_RET( nIndex + nRemove <= m_nCount,                                \
  292.                wxT("removing too many elements in wxArray::RemoveAt") );    \
  293.                                                                             \
  294.   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],                   \
  295.           (m_nCount - nIndex - nRemove)*sizeof(T));                         \
  296.   m_nCount -= nRemove;                                                      \
  297. }                                                                           \
  298.                                                                             \
  299. /* removes item from array (by value) */                                    \
  300. void name::Remove(T lItem)                                                  \
  301. {                                                                           \
  302.   int iIndex = Index(lItem);                                                \
  303.                                                                             \
  304.   wxCHECK_RET( iIndex != wxNOT_FOUND,                                       \
  305.                wxT("removing inexistent item in wxArray::Remove") );        \
  306.                                                                             \
  307.   RemoveAt((size_t)iIndex);                                                 \
  308. }                                                                           \
  309.                                                                             \
  310. /* sort array elements using passed comparaison function */                 \
  311. void name::Sort(CMPFUNC fCmp)                                               \
  312. {                                                                           \
  313.   qsort(m_pItems, m_nCount, sizeof(T), fCmp);                               \
  314. }
  315.  
  316. _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
  317. _WX_DEFINE_BASEARRAY(short,        wxBaseArrayShort)
  318. _WX_DEFINE_BASEARRAY(int,          wxBaseArrayInt)
  319. _WX_DEFINE_BASEARRAY(long,         wxBaseArrayLong)
  320. //_WX_DEFINE_BASEARRAY(double,       wxBaseArrayDouble)
  321.  
  322.