merged in the commit from the 2.2 branch

[wxWidgets.git] / src / common / dynarray.cpp

diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp
index eb67d34504bf1846d33f7075d20a9e9691325fe0..bbf54265c431b7eb1d996e0b5a9e224e001a773d 100644 (file)
--- a/src/common/dynarray.cpp
+++ b/src/common/dynarray.cpp
@@ -2,7 +2,7 @@
 // Name:        dynarray.cpp
 // Purpose:     implementation of wxBaseArray class
 // Author:      Vadim Zeitlin
 // Name:        dynarray.cpp
 // Purpose:     implementation of wxBaseArray class
 // Author:      Vadim Zeitlin

-// Modified by: 
+// Modified by:

 // Created:     12.09.97
 // RCS-ID:      $Id$
 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
 // Created:     12.09.97
 // RCS-ID:      $Id$
 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>


@@ -17,15 +17,17 @@
 #pragma implementation "dynarray.h"
 #endif
 
 #pragma implementation "dynarray.h"
 #endif
 

-#include  <wx/wxprec.h>
+#include  "wx/wxprec.h"

 
 #ifdef __BORLANDC__
   #pragma hdrstop
 #endif
 
 #include "wx/dynarray.h"
 
 #ifdef __BORLANDC__
   #pragma hdrstop
 #endif
 
 #include "wx/dynarray.h"

+#include "wx/intl.h"

 
 #include <stdlib.h>
 
 #include <stdlib.h>

+#include <string.h> // for memmove

 
 #ifndef max
   #define max(a, b)   (((a) > (b)) ? (a) : (b))
 
 #ifndef max
   #define max(a, b)   (((a) > (b)) ? (a) : (b))


@@ -49,41 +51,46 @@
 // ctor
 wxBaseArray::wxBaseArray()
 {
 // ctor
 wxBaseArray::wxBaseArray()
 {

-  m_uiSize  =
-  m_uiCount = 0;
-  m_pItems  = NULL;
+  m_nSize  =
+  m_nCount = 0;
+  m_pItems  = (long *) NULL;

 }
 
 // copy ctor
 wxBaseArray::wxBaseArray(const wxBaseArray& src)
 {
 }
 
 // copy ctor
 wxBaseArray::wxBaseArray(const wxBaseArray& src)
 {

-  m_uiSize  = src.m_uiSize;
-  m_uiCount = src.m_uiCount;
+  m_nSize  = // not src.m_nSize to save memory
+  m_nCount = src.m_nCount;

 
 

-  if ( m_uiSize != 0 )
-    m_pItems = new long[m_uiSize];
+  if ( m_nSize != 0 ) {
+    m_pItems = new long[m_nSize];
+    memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
+  }

   else
   else

-    m_pItems = NULL;
-
-  if ( m_uiCount != 0 )
-    memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
+    m_pItems = (long *) NULL;

 }
 
 }
 

-// copy operator
+// assignment operator

 wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
 {
 wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
 {

-  DELETEA(m_pItems);
+#if 0
+  wxDELETEA(m_pItems);
+#else
+       if ( (m_pItems)) { 
+               delete (m_pItems); 
+               (m_pItems) = 0; 
+       }
+#endif

 
 

-  m_uiSize  = src.m_uiSize;
-  m_uiCount = src.m_uiCount;
+  m_nSize  = // not src.m_nSize to save memory
+  m_nCount = src.m_nCount;

 
 

-  if ( m_uiSize != 0 )
-    m_pItems = new long[m_uiSize];
+  if ( m_nSize != 0 ) {
+    m_pItems = new long[m_nSize];
+    memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long));
+  }

   else
   else

-    m_pItems = NULL;
-
-  if ( m_uiCount != 0 )
-    memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
+    m_pItems = (long *) NULL;

 
   return *this;
 }
 
   return *this;
 }


@@ -92,23 +99,24 @@ wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src)
 void wxBaseArray::Grow()
 {
   // only do it if no more place
 void wxBaseArray::Grow()
 {
   // only do it if no more place

-  if( m_uiCount == m_uiSize ) {
-    if( m_uiSize == 0 ) {
+  if( m_nCount == m_nSize ) {
+    if( m_nSize == 0 ) {

       // was empty, alloc some memory
       // was empty, alloc some memory

-      m_uiSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
-      m_pItems = new long[m_uiSize];
+      m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE;
+      m_pItems = new long[m_nSize];

     }
     else
     {
       // add 50% but not too much
     }
     else
     {
       // add 50% but not too much

-      uint uiIncrement = m_uiSize >> 1;
-      if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT )
-        uiIncrement = ARRAY_MAXSIZE_INCREMENT;
-      m_uiSize += uiIncrement;
-      long *pNew = new long[m_uiSize];
+      size_t nIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE 
+                         ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
+      if ( nIncrement > ARRAY_MAXSIZE_INCREMENT )
+        nIncrement = ARRAY_MAXSIZE_INCREMENT;
+      m_nSize += nIncrement;
+      long *pNew = new long[m_nSize];

 
       // copy data to new location
 
       // copy data to new location

-      memcpy(pNew, m_pItems, m_uiCount*sizeof(long));
+      memcpy(pNew, m_pItems, m_nCount*sizeof(long));

       delete [] m_pItems;
       m_pItems = pNew;
     }
       delete [] m_pItems;
       m_pItems = pNew;
     }


@@ -118,85 +126,148 @@ void wxBaseArray::Grow()
 // dtor
 wxBaseArray::~wxBaseArray()
 {
 // dtor
 wxBaseArray::~wxBaseArray()
 {

-  DELETEA(m_pItems);
+  wxDELETEA(m_pItems);

 }
 
 // clears the list
 void wxBaseArray::Clear()
 {
 }
 
 // clears the list
 void wxBaseArray::Clear()
 {

-  m_uiSize  = 
-  m_uiCount = 0;
+  m_nSize  =
+  m_nCount = 0;

 
 

-  DELETEA(m_pItems);
-  m_pItems = NULL;
+  wxDELETEA(m_pItems);

 }
 
 // pre-allocates memory (frees the previous data!)
 }
 
 // pre-allocates memory (frees the previous data!)

-void wxBaseArray::Alloc(uint uiSize)
+void wxBaseArray::Alloc(size_t nSize)

 {
 {

-  wxASSERT( uiSize > 0 );
+  wxASSERT( nSize > 0 );

 
   // only if old buffer was not big enough
 
   // only if old buffer was not big enough

-  if ( uiSize > m_uiSize ) {
-    DELETEA(m_pItems);
-    m_pItems = new long[uiSize];
-    m_uiSize  = uiSize;
+  if ( nSize > m_nSize ) {
+    wxDELETEA(m_pItems);
+    m_pItems = new long[nSize];
+    m_nSize  = nSize;

   }
 
   }
 

-  m_uiCount = 0;
+  m_nCount = 0;
+}
+
+// minimizes the memory usage by freeing unused memory
+void wxBaseArray::Shrink()
+{
+  // only do it if we have some memory to free
+  if( m_nCount < m_nSize ) {
+    // allocates exactly as much memory as we need
+    long *pNew = new long[m_nCount];
+
+    // copy data to new location
+    memcpy(pNew, m_pItems, m_nCount*sizeof(long));
+    delete [] m_pItems;
+    m_pItems = pNew;
+  }

 }
 
 // searches the array for an item (forward or backwards)
 int wxBaseArray::Index(long lItem, bool bFromEnd) const
 {
   if ( bFromEnd ) {
 }
 
 // searches the array for an item (forward or backwards)
 int wxBaseArray::Index(long lItem, bool bFromEnd) const
 {
   if ( bFromEnd ) {

-    if ( m_uiCount > 0 ) {
-      uint ui = m_uiCount;
+    if ( m_nCount > 0 ) {
+      size_t n = m_nCount;

       do {
       do {

-        if ( m_pItems[--ui] == lItem )
-          return ui;
+        if ( m_pItems[--n] == lItem )
+          return n;

       }
       }

-      while ( ui != 0 );
+      while ( n != 0 );

     }
   }
   else {
     }
   }
   else {

-    for( uint ui = 0; ui < m_uiCount; ui++ ) {
-      if( m_pItems[ui] == lItem )
-        return ui;
+    for( size_t n = 0; n < m_nCount; n++ ) {
+      if( m_pItems[n] == lItem )
+        return n;

     }
   }
 
     }
   }
 

-  return NOT_FOUND;
+  return wxNOT_FOUND;

 }
 
 }
 

+// search for an item in a sorted array (binary search)
+int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
+{
+  size_t i,
+       lo = 0,
+       hi = m_nCount;
+  int res;
+
+  while ( lo < hi ) {
+    i = (lo + hi)/2;
+
+    res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
+    if ( res < 0 )
+      hi = i;
+    else if ( res > 0 )
+      lo = i + 1;
+    else
+      return i;
+  }
+
+  return wxNOT_FOUND;
+}

 // add item at the end
 void wxBaseArray::Add(long lItem)
 {
   Grow();
 // add item at the end
 void wxBaseArray::Add(long lItem)
 {
   Grow();

-  m_pItems[m_uiCount++] = lItem;
+  m_pItems[m_nCount++] = lItem;
+}
+
+// add item assuming the array is sorted with fnCompare function
+void wxBaseArray::Add(long lItem, CMPFUNC fnCompare)
+{
+  size_t i,
+       lo = 0,
+       hi = m_nCount;
+  int res;
+
+  while ( lo < hi ) {
+    i = (lo + hi)/2;
+
+    res = (*fnCompare)((const void *)lItem, (const void *)m_pItems[i]);
+    if ( res < 0 )
+      hi = i;
+    else if ( res > 0 )
+      lo = i + 1;
+    else {
+      lo = hi = i;
+      break;
+    }
+  }
+
+  wxASSERT( lo == hi ); // I hope I got binary search right :-)
+
+  Insert(lItem, lo);

 }
 
 // add item at the given position
 }
 
 // add item at the given position

-void wxBaseArray::Insert(long lItem, uint uiIndex)
+void wxBaseArray::Insert(long lItem, size_t nIndex)

 {
 {

-  wxCHECK( uiIndex <= m_uiCount );
+  wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") );

 
   Grow();
 
 
   Grow();
 

-  memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex], 
-          (m_uiCount - uiIndex)*sizeof(long));
-  m_pItems[uiIndex] = lItem;
-  m_uiCount++;
+  memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex],
+          (m_nCount - nIndex)*sizeof(long));
+  m_pItems[nIndex] = lItem;
+  m_nCount++;

 }
 
 // removes item from array (by index)
 }
 
 // removes item from array (by index)

-void wxBaseArray::Remove(uint uiIndex)
+void wxBaseArray::RemoveAt(size_t nIndex)

 {
 {

-  wxCHECK( uiIndex <= m_uiCount );
+  wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") );

 
 

-  memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1], 
-          (m_uiCount - uiIndex - 1)*sizeof(long));
-  m_uiCount--;
+  memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1],
+          (m_nCount - nIndex - 1)*sizeof(long));
+  m_nCount--;

 }
 
 // removes item from array (by value)
 }
 
 // removes item from array (by value)


@@ -204,13 +275,14 @@ void wxBaseArray::Remove(long lItem)
 {
   int iIndex = Index(lItem);
 
 {
   int iIndex = Index(lItem);
 

-  wxCHECK( iIndex != NOT_FOUND );
+  wxCHECK_RET( iIndex != wxNOT_FOUND,
+               wxT("removing inexistent item in wxArray::Remove") );

 
 

-  Remove((uint)iIndex);
+  RemoveAt((size_t)iIndex);

 }
 
 // sort array elements using passed comparaison function
 void wxBaseArray::Sort(CMPFUNC fCmp)
 {
 }
 
 // sort array elements using passed comparaison function
 void wxBaseArray::Sort(CMPFUNC fCmp)
 {

-  qsort(m_pItems, m_uiCount, sizeof(long), fCmp);
+  qsort(m_pItems, m_nCount, sizeof(long), fCmp);

 }
 }