// 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>
#pragma implementation "dynarray.h"
#endif
-#include <wx/wxprec.h>
+#include "wx/wxprec.h"
#ifdef __BORLANDC__
#pragma hdrstop
#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))
// 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)
{
- 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
- 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)
{
- DELETEA(m_pItems);
+ wxDELETEA(m_pItems);
- 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
- m_pItems = NULL;
-
- if ( m_uiCount != 0 )
- memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long));
+ m_pItems = (long *) NULL;
return *this;
}
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
- 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
- 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
- memcpy(pNew, m_pItems, m_uiCount*sizeof(long));
+ memcpy(pNew, m_pItems, m_nCount*sizeof(long));
delete [] m_pItems;
m_pItems = pNew;
}
// dtor
wxBaseArray::~wxBaseArray()
{
- DELETEA(m_pItems);
+ wxDELETEA(m_pItems);
}
// 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!)
-void wxBaseArray::Alloc(uint uiSize)
+void wxBaseArray::Alloc(size_t nSize)
{
- wxASSERT( uiSize > 0 );
-
// 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
+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 {
- if ( m_pItems[--ui] == lItem )
- return ui;
+ if ( m_pItems[--n] == lItem )
+ return n;
}
- while ( ui != 0 );
+ while ( n != 0 );
}
}
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 wxNOT_FOUND;
+}
+
+// search for a place to insert an item into a sorted array (binary search)
+size_t wxBaseArray::IndexForInsert(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 {
+ lo = i;
+ break;
}
}
- return NOT_FOUND;
+ return lo;
+}
+
+// search for an item in a sorted array (binary search)
+int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const
+{
+ size_t n = IndexForInsert(lItem, fnCompare);
+
+ return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND;
}
// 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)
+{
+ Insert(lItem, IndexForInsert(lItem, fnCompare));
}
// 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();
- 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)
-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)
{
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)
{
- qsort(m_pItems, m_uiCount, sizeof(long), fCmp);
+ qsort(m_pItems, m_nCount, sizeof(long), fCmp);
}
projects / wxWidgets.git / blobdiff