dynarray.cpp

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C++ 代码 · 共 535 行 · 第 1/3 页

///////////////////////////////////////////////////////////////////////////////
// Name:        dynarray.cpp
// Purpose:     implementation of wxBaseArray class
// Author:      Vadim Zeitlin
// Modified by:
// Created:     12.09.97
// RCS-ID:      $Id: dynarray.cpp,v 1.52.2.2 2006/01/18 16:32:45 JS Exp $
// Copyright:   (c) 1998 Vadim Zeitlin <[e-mail]>
// Licence:     wxWindows licence
///////////////////////////////////////////////////////////////////////////////

// ============================================================================
// headers
// ============================================================================

#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
#pragma implementation "dynarray.h"
#endif

#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

// we cast the value to long from which we cast it to void * in IndexForInsert:
// this can't work if the pointers are not big enough
wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr) <= sizeof(void *),
                       wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols

// ============================================================================
// constants
// ============================================================================

// size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
#define   ARRAY_MAXSIZE_INCREMENT    4096

// ============================================================================
// implementation
// ============================================================================

// ----------------------------------------------------------------------------
// wxBaseArray - dynamic array of 'T's
// ----------------------------------------------------------------------------

#define _WX_DEFINE_BASEARRAY_COMMON(T, name)                                \
/* searches the array for an item (forward or backwards) */                 \
int name::Index(T lItem, bool bFromEnd) const                               \
{                                                                           \
  if ( bFromEnd ) {                                                         \
    if ( size() > 0 ) {                                                     \
      size_t n = size();                                                    \
      do {                                                                  \
        if ( (*this)[--n] == lItem )                                        \
          return n;                                                         \
      }                                                                     \
      while ( n != 0 );                                                     \
    }                                                                       \
  }                                                                         \
  else {                                                                    \
    for( size_t n = 0; n < size(); n++ ) {                                  \
      if( (*this)[n] == lItem )                                             \
        return n;                                                           \
    }                                                                       \
  }                                                                         \
                                                                            \
  return wxNOT_FOUND;                                                       \
}                                                                           \
                                                                            \
/* add item assuming the array is sorted with fnCompare function */         \
size_t name::Add(T lItem, CMPFUNC fnCompare)                                \
{                                                                           \
  size_t idx = IndexForInsert(lItem, fnCompare);                            \
  Insert(lItem, idx);                                                       \
  return idx;                                                               \
}

#if wxUSE_STL

#define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)                              \
size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const               \
{                                                                           \
    Predicate p((SCMPFUNC)fnCompare);                                       \
    const_iterator it = std::lower_bound(begin(), end(), lItem, p);         \
    return it - begin();                                                    \
}                                                                           \
                                                                            \
int name::Index(T lItem, CMPFUNC fnCompare) const                           \
{                                                                           \
    Predicate p((SCMPFUNC)fnCompare);                                       \
    const_iterator it = std::lower_bound(begin(), end(), lItem, p);         \
    return (it != end() && !p(lItem, *it)) ?                                \
                             (int)(it - begin()) : wxNOT_FOUND;             \
}                                                                           \
                                                                            \
void name::Shrink()                                                         \
{                                                                           \
    name tmp(*this);                                                        \
    swap(tmp);                                                              \
}

#else // if !wxUSE_STL

#define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)                              \
/* ctor */                                                                  \
name::name()                                                                \
{                                                                           \
  m_nSize  =                                                                \
  m_nCount = 0;                                                             \
  m_pItems = (T *)NULL;                                                     \
}                                                                           \
                                                                            \
/* copy ctor */                                                             \
name::name(const name& src)                                                 \
{                                                                           \
  m_nSize  = /* not src.m_nSize to save memory */                           \
  m_nCount = src.m_nCount;                                                  \
                                                                            \
  if ( m_nSize != 0 ) {                                                     \
      m_pItems = new T[m_nSize];                                            \
      /* only copy if allocation succeeded */                               \
      if ( m_pItems ) {                                                     \
          memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
      }                                                                     \
      else {                                                                \
          m_nSize = 0;                                                      \
      }                                                                     \
  }                                                                         \
  else                                                                      \
    m_pItems = (T *) NULL;                                                  \
}                                                                           \
                                                                            \
/* assignment operator */                                                   \
name& name::operator=(const name& src)                                      \
{                                                                           \
  wxDELETEA(m_pItems);                                                      \
                                                                            \
  m_nSize  = /* not src.m_nSize to save memory */                           \
  m_nCount = src.m_nCount;                                                  \
                                                                            \
  if ( m_nSize != 0 ){                                                      \
      m_pItems = new T[m_nSize];                                            \
      /* only copy if allocation succeeded */                               \
      if ( m_pItems ) {                                                     \
          memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T));               \
      }                                                                     \
      else {                                                                \
          m_nSize = 0;                                                      \
      }                                                                     \
  }                                                                         \
  else                                                                      \
    m_pItems = (T *) NULL;                                                  \
                                                                            \
  return *this;                                                             \
}                                                                           \
                                                                            \
/* allocate new buffer of the given size and move our data to it */         \
bool name::Realloc(size_t nSize)                                            \
{                                                                           \
  T *pNew = new T[nSize];                                                   \
  /* only grow if allocation succeeded */                                   \
  if ( !pNew )                                                              \
      return false;                                                         \
                                                                            \
  m_nSize = nSize;                                                          \
  /* copy data to new location */                                           \
  memcpy(pNew, m_pItems, m_nCount*sizeof(T));                               \
  delete [] m_pItems;                                                       \
  m_pItems = pNew;                                                          \
                                                                            \
  return true;                                                              \
}                                                                           \
                                                                            \