home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2233.zip / wxOS2-2_3_3.zip / wxWindows-2.3.3 / src / common / dynarray.cpp < prev    next >
C/C++ Source or Header  |  2002-06-04  |  22KB  |  315 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.26 2002/05/22 18:04:36 VZ 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 ) {                                               \
  114.     if( m_nSize == 0 ) {                                                    \
  115.         /* was empty, alloc some memory */                                  \
  116.       m_pItems = new T[WX_ARRAY_DEFAULT_INITIAL_SIZE];                      \
  117.       /* only grow if allocation succeeded */                               \
  118.       if ( m_pItems ) {                                                     \
  119.           m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;                          \
  120.       }                                                                     \
  121.     }                                                                       \
  122.     else                                                                    \
  123.     {                                                                       \
  124.       /* add at least 50% but not too much */                               \
  125.       size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE        \
  126.                             ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
  127.       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )                        \
  128.         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;                            \
  129.       if ( nIncrement < ndefIncrement )                                     \
  130.         nIncrement = ndefIncrement;                                         \
  131.       T *pNew = new T[m_nSize + nIncrement];                                \
  132.       /* only grow if allocation succeeded */                               \
  133.       if ( pNew ) {                                                         \
  134.           m_nSize += nIncrement;                                            \
  135.           /* copy data to new location */                                   \
  136.           memcpy(pNew, m_pItems, m_nCount*sizeof(T));                       \
  137.           delete [] m_pItems;                                               \
  138.           m_pItems = pNew;                                                  \
  139.       }                                                                     \
  140.     }                                                                       \
  141.   }                                                                         \
  142. }                                                                           \
  143.                                                                             \
  144. /* dtor */                                                                  \
  145. name::~name()                                                               \
  146. {                                                                           \
  147.   wxDELETEA(m_pItems);                                                      \
  148. }                                                                           \
  149.                                                                             \
  150. /* clears the list */                                                       \
  151. void name::Clear()                                                          \
  152. {                                                                           \
  153.   m_nSize  =                                                                \
  154.   m_nCount = 0;                                                             \
  155.                                                                             \
  156.   wxDELETEA(m_pItems);                                                      \
  157. }                                                                           \
  158.                                                                             \
  159. /* pre-allocates memory (frees the previous data!) */                       \
  160. void name::Alloc(size_t nSize)                                              \
  161. {                                                                           \
  162.   /* only if old buffer was not big enough */                               \
  163.   if ( nSize > m_nSize ) {                                                  \
  164.     wxDELETEA(m_pItems);                                                    \
  165.     m_nSize  = 0;                                                           \
  166.     m_pItems = new T[nSize];                                                \
  167.     /* only alloc if allocation succeeded */                                \
  168.     if ( m_pItems ) {                                                       \
  169.         m_nSize  = nSize;                                                   \
  170.     }                                                                       \
  171.   }                                                                         \
  172.                                                                             \
  173.   m_nCount = 0;                                                             \
  174. }                                                                           \
  175.                                                                             \
  176. /* minimizes the memory usage by freeing unused memory */                   \
  177. void name::Shrink()                                                         \
  178. {                                                                           \
  179.   /* only do it if we have some memory to free */                           \
  180.   if( m_nCount < m_nSize ) {                                                \
  181.     /* allocates exactly as much memory as we need */                       \
  182.     T *pNew = new T[m_nCount];                                              \
  183.     /* only shrink if allocation succeeded */                               \
  184.     if ( pNew ) {                                                           \
  185.         /* copy data to new location */                                     \
  186.         memcpy(pNew, m_pItems, m_nCount*sizeof(T));                         \
  187.         delete [] m_pItems;                                                 \
  188.         m_pItems = pNew;                                                    \
  189.     }                                                                       \
  190.   }                                                                         \
  191. }                                                                           \
  192.                                                                             \
  193. /* searches the array for an item (forward or backwards) */                 \
  194. int name::Index(T lItem, bool bFromEnd) const                               \
  195. {                                                                           \
  196.   if ( bFromEnd ) {                                                         \
  197.     if ( m_nCount > 0 ) {                                                   \
  198.       size_t n = m_nCount;                                                  \
  199.       do {                                                                  \
  200.         if ( m_pItems[--n] == lItem )                                       \
  201.           return n;                                                         \
  202.       }                                                                     \
  203.       while ( n != 0 );                                                     \
  204.     }                                                                       \
  205.   }                                                                         \
  206.   else {                                                                    \
  207.     for( size_t n = 0; n < m_nCount; n++ ) {                                \
  208.       if( m_pItems[n] == lItem )                                            \
  209.         return n;                                                           \
  210.     }                                                                       \
  211.   }                                                                         \
  212.                                                                             \
  213.   return wxNOT_FOUND;                                                       \
  214. }                                                                           \
  215.                                                                             \
  216. /* search for a place to insert item into sorted array (binary search) */   \
  217. size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const               \
  218. {                                                                           \
  219.   size_t i,                                                                 \
  220.        lo = 0,                                                              \
  221.        hi = m_nCount;                                                       \
  222.   int res;                                                                  \
  223.                                                                             \
  224.   while ( lo < hi ) {                                                       \
  225.     i = (lo + hi)/2;                                                        \
  226.                                                                             \
  227.     res = (*fnCompare)((const void *)(long)lItem,                           \
  228.                        (const void *)(long)(m_pItems[i]));                  \
  229.     if ( res < 0 )                                                          \
  230.       hi = i;                                                               \
  231.     else if ( res > 0 )                                                     \
  232.       lo = i + 1;                                                           \
  233.     else {                                                                  \
  234.       lo = i;                                                               \
  235.       break;                                                                \
  236.     }                                                                       \
  237.   }                                                                         \
  238.                                                                             \
  239.   return lo;                                                                \
  240. }                                                                           \
  241.                                                                             \
  242. /* search for an item in a sorted array (binary search) */                  \
  243. int name::Index(T lItem, CMPFUNC fnCompare) const                           \
  244. {                                                                           \
  245.     size_t n = IndexForInsert(lItem, fnCompare);                            \
  246.                                                                             \
  247.     return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;     \
  248. }                                                                           \
  249.                                                                             \
  250. /* add item at the end */                                                   \
  251. void name::Add(T lItem, size_t nInsert)                                     \
  252. {                                                                           \
  253.   Grow(nInsert);                                                            \
  254.   for (size_t i = 0; i < nInsert; i++)                                      \
  255.       m_pItems[m_nCount++] = lItem;                                         \
  256. }                                                                           \
  257.                                                                             \
  258. /* add item assuming the array is sorted with fnCompare function */         \
  259. void name::Add(T lItem, CMPFUNC fnCompare)                                  \
  260. {                                                                           \
  261.   Insert(lItem, IndexForInsert(lItem, fnCompare));                          \
  262. }                                                                           \
  263.                                                                             \
  264. /* add item at the given position */                                        \
  265. void name::Insert(T lItem, size_t nIndex, size_t nInsert)                   \
  266. {                                                                           \
  267.   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );   \
  268.   wxCHECK_RET( m_nCount <= m_nCount + nInsert,                              \
  269.                wxT("array size overflow in wxArray::Insert") );             \
  270.                                                                             \
  271.   Grow(nInsert);                                                            \
  272.                                                                             \
  273.   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],                   \
  274.           (m_nCount - nIndex)*sizeof(T));                                   \
  275.   for (size_t i = 0; i < nInsert; i++)                                      \
  276.       m_pItems[nIndex + i] = lItem;                                         \
  277.   m_nCount += nInsert;                                                      \
  278. }                                                                           \
  279.                                                                             \
  280. /* removes item from array (by index) */                                    \
  281. void name::RemoveAt(size_t nIndex, size_t nRemove)                          \
  282. {                                                                           \
  283.   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") );  \
  284.   wxCHECK_RET( nIndex + nRemove <= m_nCount,                                \
  285.                wxT("removing too many elements in wxArray::RemoveAt") );    \
  286.                                                                             \
  287.   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],                   \
  288.           (m_nCount - nIndex - nRemove)*sizeof(T));                         \
  289.   m_nCount -= nRemove;                                                      \
  290. }                                                                           \
  291.                                                                             \
  292. /* removes item from array (by value) */                                    \
  293. void name::Remove(T lItem)                                                  \
  294. {                                                                           \
  295.   int iIndex = Index(lItem);                                                \
  296.                                                                             \
  297.   wxCHECK_RET( iIndex != wxNOT_FOUND,                                       \
  298.                wxT("removing inexistent item in wxArray::Remove") );        \
  299.                                                                             \
  300.   RemoveAt((size_t)iIndex);                                                 \
  301. }                                                                           \
  302.                                                                             \
  303. /* sort array elements using passed comparaison function */                 \
  304. void name::Sort(CMPFUNC fCmp)                                               \
  305. {                                                                           \
  306.   qsort(m_pItems, m_nCount, sizeof(T), fCmp);                               \
  307. }
  308.  
  309. _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
  310. _WX_DEFINE_BASEARRAY(short,        wxBaseArrayShort)
  311. _WX_DEFINE_BASEARRAY(int,          wxBaseArrayInt)
  312. _WX_DEFINE_BASEARRAY(long,         wxBaseArrayLong)
  313. //_WX_DEFINE_BASEARRAY(double,       wxBaseArrayDouble)
  314.  
  315.