dynarray.h

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C头文件 代码 · 共 1,001 行 · 第 1/4 页

///////////////////////////////////////////////////////////////////////////////
// Name:        dynarray.h
// Purpose:     auto-resizable (i.e. dynamic) array support
// Author:      Vadim Zeitlin
// Modified by:
// Created:     12.09.97
// RCS-ID:      $Id: dynarray.h,v 1.81 2005/06/08 15:17:42 ABX Exp $
// Copyright:   (c) 1998 Vadim Zeitlin <[e-mail]>
// Licence:     wxWindows licence
///////////////////////////////////////////////////////////////////////////////

#ifndef   _DYNARRAY_H
#define   _DYNARRAY_H

#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) && \
    !(defined(__MINGW32__) && __GNUC__ == 3 && __GNUC_MINOR__ == 2)
#pragma interface "dynarray.h"
#endif

#include "wx/defs.h"

#if wxUSE_STL
    #include "wx/beforestd.h"
    #include <vector>
    #include <algorithm>
    #include "wx/afterstd.h"
#endif

/*
  This header defines the dynamic arrays and object arrays (i.e. arrays which
  own their elements). Dynamic means that the arrays grow automatically as
  needed.

  These macros are ugly (especially if you look in the sources ;-), but they
  allow us to define "template" classes without actually using templates and so
  this works with all compilers (and may be also much faster to compile even
  with a compiler which does support templates). The arrays defined with these
  macros are type-safe.

  Range checking is performed in debug build for both arrays and objarrays but
  not in release build - so using an invalid index will just lead to a crash
  then.

  Note about memory usage: arrays never shrink automatically (although you may
  use Shrink() function explicitly), they only grow, so loading 10 millions in
  an array only to delete them 2 lines below might be a bad idea if the array
  object is not going to be destroyed soon. However, as it does free memory
  when destroyed, it is ok if the array is a local variable.
 */

// ----------------------------------------------------------------------------
// constants
// ----------------------------------------------------------------------------

/*
   The initial size by which an array grows when an element is added default
   value avoids allocate one or two bytes when the array is created which is
   rather inefficient
*/
#define WX_ARRAY_DEFAULT_INITIAL_SIZE    (16)

// ----------------------------------------------------------------------------
// types
// ----------------------------------------------------------------------------

/*
    Callback compare function for quick sort.

    It must return negative value, 0 or positive value if the first item is
    less than, equal to or greater than the second one.
 */
extern "C"
{
typedef int (wxCMPFUNC_CONV *CMPFUNC)(const void* pItem1, const void* pItem2);
}

// ----------------------------------------------------------------------------
// Base class managing data having size of type 'long' (not used directly)
//
// NB: for efficiency this often used class has no virtual functions (hence no
//     virtual table), even dtor is *not* virtual. If used as expected it
//     won't create any problems because ARRAYs from DEFINE_ARRAY have no dtor
//     at all, so it's not too important if it's not called (this happens when
//     you cast "SomeArray *" as "BaseArray *" and then delete it)
// ----------------------------------------------------------------------------

#if wxUSE_STL

template<class T>
class WXDLLIMPEXP_BASE wxArray_SortFunction
{
public:
    typedef int (wxCMPFUNC_CONV *CMPFUNC)(T* pItem1, T* pItem2);

    wxArray_SortFunction(CMPFUNC f) : m_f(f) { }
    bool operator()(const T& i1, const T& i2)
      { return m_f((T*)&i1, (T*)&i2) < 0; }
private:
    CMPFUNC m_f;
};

template<class T, typename F>
class WXDLLIMPEXP_BASE wxSortedArray_SortFunction
{
public:
    typedef F CMPFUNC;

    wxSortedArray_SortFunction(CMPFUNC f) : m_f(f) { }
    bool operator()(const T& i1, const T& i2)
      { return m_f(i1, i2) < 0; }
private:
    CMPFUNC m_f;
};

#define  _WX_DECLARE_BASEARRAY(T, name, classexp)                   \
   typedef int (wxCMPFUNC_CONV *CMPFUN##name)(T pItem1, T pItem2);  \
   typedef wxSortedArray_SortFunction<T, CMPFUN##name> name##_Predicate; \
   _WX_DECLARE_BASEARRAY_2(T, name, name##_Predicate, classexp)

#define  _WX_DECLARE_BASEARRAY_2(T, name, predicate, classexp)      \
classexp name : public std::vector<T>                               \
{                                                                   \
  typedef predicate Predicate;                                      \
  typedef predicate::CMPFUNC SCMPFUNC;                              \
public:                                                             \
  typedef wxArray_SortFunction<T>::CMPFUNC CMPFUNC;                 \
public:                                                             \
  void Empty() { clear(); }                                         \
  void Clear() { clear(); }                                         \
  void Alloc(size_t uiSize) { reserve(uiSize); }                    \
  void Shrink();                                                    \
                                                                    \
  size_t GetCount() const { return size(); }                        \
  void SetCount(size_t n, T v = T()) { resize(n, v); }              \
  bool IsEmpty() const { return empty(); }                          \
  size_t Count() const { return size(); }                           \
                                                                    \
  typedef T base_type;                                              \
                                                                    \
protected:                                                          \
  T& Item(size_t uiIndex) const                                     \
    { wxASSERT( uiIndex < size() ); return (T&)operator[](uiIndex); }   \
                                                                    \
  int Index(T e, bool bFromEnd = false) const;                      \
  int Index(T lItem, CMPFUNC fnCompare) const;                      \
  size_t IndexForInsert(T lItem, CMPFUNC fnCompare) const;          \
  void Add(T lItem, size_t nInsert = 1)                             \
    { insert(end(), nInsert, lItem); }                              \
  size_t Add(T lItem, CMPFUNC fnCompare);                           \
  void Insert(T lItem, size_t uiIndex, size_t nInsert = 1)          \
    { insert(begin() + uiIndex, nInsert, lItem); }                  \
  void Remove(T lItem);                                             \
  void RemoveAt(size_t uiIndex, size_t nRemove = 1)                 \
    { erase(begin() + uiIndex, begin() + uiIndex + nRemove); }      \
                                                                    \
  void Sort(CMPFUNC fCmp)                                           \
  {                                                                 \
    wxArray_SortFunction<T> p(fCmp);                                \
    std::sort(begin(), end(), p);                                   \
  }                                                                 \
}

#else // if !wxUSE_STL

#define  _WX_DECLARE_BASEARRAY(T, name, classexp)                   \
classexp name                                                       \
{                                                                   \
  typedef CMPFUNC SCMPFUNC; /* for compatibility wuth wxUSE_STL */  \
public:                                                             \
  name();                                                           \
  name(const name& array);                                          \
  name& operator=(const name& src);                                 \
  ~name();                                                          \
                                                                    \
  void Empty() { m_nCount = 0; }                                    \
  void Clear();                                                     \
  void Alloc(size_t uiSize);                                        \
  void Shrink();                                                    \
                                                                    \
  size_t GetCount() const { return m_nCount; }                      \
  void SetCount(size_t n, T defval = T());                          \
  bool IsEmpty() const { return m_nCount == 0; }                    \
  size_t Count() const { return m_nCount; }                         \
                                                                    \
  typedef T base_type;                                              \
                                                                    \
protected:                                                          \
  T& Item(size_t uiIndex) const                                     \
    { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; }   \
  T& operator[](size_t uiIndex) const { return Item(uiIndex); }     \
                                                                    \
  int Index(T lItem, bool bFromEnd = false) const;                  \
  int Index(T lItem, CMPFUNC fnCompare) const;                      \
  size_t IndexForInsert(T lItem, CMPFUNC fnCompare) const;          \
  void Add(T lItem, size_t nInsert = 1);                            \
  size_t Add(T lItem, CMPFUNC fnCompare);                           \
  void Insert(T lItem, size_t uiIndex, size_t nInsert = 1);         \
  void Remove(T lItem);                                             \
  void RemoveAt(size_t uiIndex, size_t nRemove = 1);                \
                                                                    \
  void Sort(CMPFUNC fnCompare);                                     \
                                                                    \
  /* *minimal* STL-ish interface, for derived classes */            \
  typedef T value_type;                                             \
  typedef value_type* iterator;                                     \
  typedef const value_type* const_iterator;                         \
  typedef value_type& reference;                                    \
  typedef const value_type& const_reference;                        \
  typedef int difference_type;                                      \
  typedef size_t size_type;                                         \
                                                                    \
  void assign(const_iterator first, const_iterator last);           \
  void assign(size_type n, const_reference v);                      \
  size_type capacity() const { return m_nSize; }                    \
  iterator erase(iterator first, iterator last)                     \
  {                                                                 \
    size_type idx = first - begin();                                \
    RemoveAt(idx, last - first);                                    \
    return begin() + idx;                                           \
  }                                                                 \
  iterator erase(iterator it) { return erase(it, it + 1); }         \
  void insert(iterator it, size_type n, const value_type& v)        \
    { Insert(v, it - begin(), n); }                                 \
  iterator insert(iterator it, const value_type& v = value_type())  \
  {                                                                 \
    size_type idx = it - begin();                                   \
    Insert(v, idx);                                                 \
    return begin() + idx;                                           \
  }                                                                 \
  void insert(iterator it, const_iterator first, const_iterator last);\
  void pop_back() { RemoveAt(size() - 1); }                         \
  void push_back(const value_type& v) { Add(v); }                   \
  void reserve(size_type n) { if(n > m_nSize) Realloc(n); }         \
  void resize(size_type n, value_type v = value_type());            \
                                                                    \
  iterator begin() { return m_pItems; }                             \
  iterator end() { return m_pItems + m_nCount; }                    \
  const_iterator begin() const { return m_pItems; }                 \
  const_iterator end() const { return m_pItems + m_nCount; }        \
                                                                    \
  /* the following functions may be made directly public because */ \
  /* they don't use the type of the elements at all */              \
public:                                                             \
  void clear() { Clear(); }                                         \
  bool empty() const { return IsEmpty(); }                          \
  size_type max_size() const { return INT_MAX; }                    \
  size_type size() const { return GetCount(); }                     \
                                                                    \
private:                                                            \
  void Grow(size_t nIncrement = 0);                                 \
  bool Realloc(size_t nSize);                                       \