X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/1311c7a9bbaefda6b68eee5c32c3309f163a8861..6f34921d9369a31de14e4b07e4824e2d701710f0:/src/common/dynarray.cpp?ds=inline

diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp
index ee700fbb0c..305a1f07d4 100644
--- 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
-// Modified by: 
+// Modified by:
 // Created:     12.09.97
 // RCS-ID:      $Id$
 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
@@ -24,8 +24,10 @@
 #endif
 
 #include "wx/dynarray.h"
+#include <wx/intl.h>
 
 #include <stdlib.h>
+#include <string.h> // for memmove
 
 #ifndef max
   #define max(a, b)   (((a) > (b)) ? (a) : (b))
@@ -51,39 +53,44 @@ wxBaseArray::wxBaseArray()
 {
   m_uiSize  =
   m_uiCount = 0;
-  m_pItems  = NULL;
+  m_pItems  = (long *) NULL;
 }
 
 // copy ctor
 wxBaseArray::wxBaseArray(const wxBaseArray& src)
 {
-  m_uiSize  = src.m_uiSize;
+  m_uiSize  = // not src.m_uiSize to save memory
   m_uiCount = src.m_uiCount;
 
-  if ( m_uiSize != 0 )
+  if ( m_uiSize != 0 ) {
     m_pItems = new long[m_uiSize];
-  else
-    m_pItems = NULL;
-
-  if ( m_uiCount != 0 )
     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
+  }
+  else
+    m_pItems = (long *) NULL;
 }
 
-// copy operator
+// assignment operator
 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_uiSize  = // not src.m_uiSize to save memory
   m_uiCount = src.m_uiCount;
 
-  if ( m_uiSize != 0 )
+  if ( m_uiSize != 0 ) {
     m_pItems = new long[m_uiSize];
-  else
-    m_pItems = NULL;
-
-  if ( m_uiCount != 0 )
     memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
+  }
+  else
+    m_pItems = (long *) NULL;
 
   return *this;
 }
@@ -101,7 +108,8 @@ void wxBaseArray::Grow()
     else
     {
       // add 50% but not too much
-      uint uiIncrement = m_uiSize >> 1;
+      size_t uiIncrement = m_uiSize < WX_ARRAY_DEFAULT_INITIAL_SIZE 
+                         ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_uiSize >> 1;
       if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT )
         uiIncrement = ARRAY_MAXSIZE_INCREMENT;
       m_uiSize += uiIncrement;
@@ -118,27 +126,26 @@ void wxBaseArray::Grow()
 // dtor
 wxBaseArray::~wxBaseArray()
 {
-  DELETEA(m_pItems);
+  wxDELETEA(m_pItems);
 }
 
 // clears the list
 void wxBaseArray::Clear()
 {
-  m_uiSize  = 
+  m_uiSize  =
   m_uiCount = 0;
 
-  DELETEA(m_pItems);
-  m_pItems = NULL;
+  wxDELETEA(m_pItems);
 }
 
 // pre-allocates memory (frees the previous data!)
-void wxBaseArray::Alloc(uint uiSize)
+void wxBaseArray::Alloc(size_t uiSize)
 {
   wxASSERT( uiSize > 0 );
 
   // only if old buffer was not big enough
   if ( uiSize > m_uiSize ) {
-    DELETEA(m_pItems);
+    wxDELETEA(m_pItems);
     m_pItems = new long[uiSize];
     m_uiSize  = uiSize;
   }
@@ -151,7 +158,7 @@ int wxBaseArray::Index(long lItem, bool bFromEnd) const
 {
   if ( bFromEnd ) {
     if ( m_uiCount > 0 ) {
-      uint ui = m_uiCount;
+      size_t ui = m_uiCount;
       do {
         if ( m_pItems[--ui] == lItem )
           return ui;
@@ -160,7 +167,7 @@ int wxBaseArray::Index(long lItem, bool bFromEnd) const
     }
   }
   else {
-    for( uint ui = 0; ui < m_uiCount; ui++ ) {
+    for( size_t ui = 0; ui < m_uiCount; ui++ ) {
       if( m_pItems[ui] == lItem )
         return ui;
     }
@@ -169,6 +176,28 @@ int wxBaseArray::Index(long lItem, bool bFromEnd) const
   return NOT_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_uiCount;
+  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 NOT_FOUND;
+}
 // add item at the end
 void wxBaseArray::Add(long lItem)
 {
@@ -176,25 +205,52 @@ void wxBaseArray::Add(long lItem)
   m_pItems[m_uiCount++] = 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_uiCount;
+  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
-void wxBaseArray::Insert(long lItem, uint uiIndex)
+void wxBaseArray::Insert(long lItem, size_t uiIndex)
 {
-  wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Insert" );
+  wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Insert") );
 
   Grow();
 
-  memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex], 
+  memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex],
           (m_uiCount - uiIndex)*sizeof(long));
   m_pItems[uiIndex] = lItem;
   m_uiCount++;
 }
 
 // removes item from array (by index)
-void wxBaseArray::Remove(uint uiIndex)
+void wxBaseArray::Remove(size_t uiIndex)
 {
-  wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Remove" );
+  wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Remove") );
 
-  memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1], 
+  memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1],
           (m_uiCount - uiIndex - 1)*sizeof(long));
   m_uiCount--;
 }
@@ -204,10 +260,10 @@ void wxBaseArray::Remove(long lItem)
 {
   int iIndex = Index(lItem);
 
-  wxCHECK_RET( iIndex != NOT_FOUND, 
-               "removing inexistent item in wxArray::Remove" );
+  wxCHECK_RET( iIndex != NOT_FOUND,
+               _("removing inexistent item in wxArray::Remove") );
 
-  Remove((uint)iIndex);
+  Remove((size_t)iIndex);
 }
 
 // sort array elements using passed comparaison function