X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/4365da58c8f11f5c0bee18cc03ff81664c639299..bba35861478a26f5d8c756a9a7fa2bbd19a69cb1:/src/common/dynarray.cpp diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index 012c6077a3..5d99bf67fd 100644 --- a/src/common/dynarray.cpp +++ b/src/common/dynarray.cpp @@ -1,5 +1,5 @@ /////////////////////////////////////////////////////////////////////////////// -// Name: dynarray.cpp +// Name: src/common/dynarray.cpp // Purpose: implementation of wxBaseArray class // Author: Vadim Zeitlin // Modified by: @@ -13,29 +13,24 @@ // headers // ============================================================================ -#ifdef __GNUG__ -#pragma implementation "dynarray.h" -#endif - +// For compilers that support precompilation, includes "wx.h". #include "wx/wxprec.h" #ifdef __BORLANDC__ - #pragma hdrstop + #pragma hdrstop #endif -#include "wx/dynarray.h" -#include "wx/intl.h" +#ifndef WX_PRECOMP + #include "wx/dynarray.h" + #include "wx/intl.h" +#endif //WX_PRECOMP #include #include // for memmove -#ifndef max - #define max(a, b) (((a) > (b)) ? (a) : (b)) -#endif - // 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(long) <= sizeof(void *), +wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr) <= sizeof(void *), wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols // ============================================================================ @@ -53,7 +48,65 @@ wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *), // wxBaseArray - dynamic array of 'T's // ---------------------------------------------------------------------------- -#define _WX_DEFINE_BASEARRAY(T, name) \ +#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() \ { \ @@ -191,23 +244,6 @@ void name::Clear() \ wxDELETEA(m_pItems); \ } \ \ -/* pre-allocates memory (frees the previous data!) */ \ -void name::Alloc(size_t nSize) \ -{ \ - /* only if old buffer was not big enough */ \ - if ( nSize > m_nSize ) { \ - wxDELETEA(m_pItems); \ - m_nSize = 0; \ - m_pItems = new T[nSize]; \ - /* only alloc if allocation succeeded */ \ - if ( m_pItems ) { \ - m_nSize = nSize; \ - } \ - } \ - \ - m_nCount = 0; \ -} \ - \ /* minimizes the memory usage by freeing unused memory */ \ void name::Shrink() \ { \ @@ -229,27 +265,32 @@ void name::Shrink() \ } \ } \ \ -/* searches the array for an item (forward or backwards) */ \ -int name::Index(T lItem, bool bFromEnd) const \ +/* add item at the end */ \ +void name::Add(T lItem, size_t nInsert) \ { \ - if ( bFromEnd ) { \ - if ( m_nCount > 0 ) { \ - size_t n = m_nCount; \ - do { \ - if ( m_pItems[--n] == lItem ) \ - return n; \ - } \ - while ( n != 0 ); \ - } \ - } \ - else { \ - for( size_t n = 0; n < m_nCount; n++ ) { \ - if( m_pItems[n] == lItem ) \ - return n; \ - } \ - } \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + for (size_t i = 0; i < nInsert; i++) \ + m_pItems[m_nCount++] = lItem; \ +} \ \ - return wxNOT_FOUND; \ +/* add item at the given position */ \ +void name::Insert(T lItem, size_t nIndex, size_t nInsert) \ +{ \ + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \ + wxCHECK_RET( m_nCount <= m_nCount + nInsert, \ + wxT("array size overflow in wxArray::Insert") ); \ + \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + \ + memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ + (m_nCount - nIndex)*sizeof(T)); \ + for (size_t i = 0; i < nInsert; i++) \ + m_pItems[nIndex + i] = lItem; \ + m_nCount += nInsert; \ } \ \ /* search for a place to insert item into sorted array (binary search) */ \ @@ -263,8 +304,8 @@ size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \ while ( lo < hi ) { \ i = (lo + hi)/2; \ \ - res = (*fnCompare)((const void *)(long)lItem, \ - (const void *)(long)(m_pItems[i])); \ + res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \ + (const void *)(wxUIntPtr)(m_pItems[i])); \ if ( res < 0 ) \ hi = i; \ else if ( res > 0 ) \ @@ -283,44 +324,11 @@ int name::Index(T lItem, CMPFUNC fnCompare) const \ { \ size_t n = IndexForInsert(lItem, fnCompare); \ \ - return n < m_nCount && \ - (*fnCompare)((const void *)(long)lItem, \ - ((const void *)(long)m_pItems[n])) ? (int)n \ - : wxNOT_FOUND; \ -} \ - \ -/* add item at the end */ \ -void name::Add(T lItem, size_t nInsert) \ -{ \ - if (nInsert == 0) \ - return; \ - Grow(nInsert); \ - for (size_t i = 0; i < nInsert; i++) \ - m_pItems[m_nCount++] = lItem; \ -} \ - \ -/* add item assuming the array is sorted with fnCompare function */ \ -void name::Add(T lItem, CMPFUNC fnCompare) \ -{ \ - Insert(lItem, IndexForInsert(lItem, fnCompare)); \ -} \ - \ -/* add item at the given position */ \ -void name::Insert(T lItem, size_t nIndex, size_t nInsert) \ -{ \ - wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \ - wxCHECK_RET( m_nCount <= m_nCount + nInsert, \ - wxT("array size overflow in wxArray::Insert") ); \ - \ - if (nInsert == 0) \ - return; \ - Grow(nInsert); \ - \ - memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ - (m_nCount - nIndex)*sizeof(T)); \ - for (size_t i = 0; i < nInsert; i++) \ - m_pItems[nIndex + i] = lItem; \ - m_nCount += nInsert; \ + return (n >= m_nCount || \ + (*fnCompare)((const void *)(wxUIntPtr)lItem, \ + ((const void *)(wxUIntPtr)m_pItems[n]))) \ + ? wxNOT_FOUND \ + : (int)n; \ } \ \ /* removes item from array (by index) */ \ @@ -350,11 +358,181 @@ void name::Remove(T lItem) \ void name::Sort(CMPFUNC fCmp) \ { \ qsort(m_pItems, m_nCount, sizeof(T), fCmp); \ +} \ + \ +void name::assign(const_iterator first, const_iterator last) \ +{ \ + clear(); \ + reserve(last - first); \ + for(; first != last; ++first) \ + push_back(*first); \ +} \ + \ +void name::assign(size_type n, const_reference v) \ +{ \ + clear(); \ + reserve(n); \ + for( size_type i = 0; i < n; ++i ) \ + push_back(v); \ +} \ + \ +void name::insert(iterator it, const_iterator first, const_iterator last) \ +{ \ + size_t nInsert = last - first, nIndex = it - begin(); \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + \ + memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ + (m_nCount - nIndex)*sizeof(T)); \ + for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \ + *it = *first; \ + m_nCount += nInsert; \ } +#endif + +#define _WX_DEFINE_BASEARRAY(T, name) \ + _WX_DEFINE_BASEARRAY_COMMON(T, name) \ + _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) + +#ifdef __INTELC__ + #pragma warning(push) + #pragma warning(disable: 1684) + #pragma warning(disable: 1572) +#endif + _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid) +_WX_DEFINE_BASEARRAY(char, wxBaseArrayChar) _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort) _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt) _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong) -//_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble) +_WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT) +_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble) + +#ifdef __INTELC__ + #pragma warning(pop) +#endif + +#if wxUSE_STL +#include "wx/arrstr.h" + +#include "wx/beforestd.h" +#include +#include "wx/afterstd.h" + +_WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase) + +// some compilers (Sun CC being the only known example) distinguish between +// extern "C" functions and the functions with C++ linkage and ptr_fun and +// wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in +// this case, we need the wrappers below to make this work +struct wxStringCmp +{ + typedef wxString first_argument_type; + typedef wxString second_argument_type; + typedef int result_type; + + int operator()(const wxString& s1, const wxString& s2) const + { + return s1.compare(s2); + } +}; + +struct wxStringCmpNoCase +{ + typedef wxString first_argument_type; + typedef wxString second_argument_type; + typedef int result_type; + + int operator()(const wxString& s1, const wxString& s2) const + { + return s1.CmpNoCase(s2); + } +}; + +int wxArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const +{ + wxArrayString::const_iterator it; + + if (bCase) + { + it = std::find_if(begin(), end(), + std::not1( + std::bind2nd( + wxStringCmp(), str))); + } + else // !bCase + { + it = std::find_if(begin(), end(), + std::not1( + std::bind2nd( + wxStringCmpNoCase(), str))); + } + + return it == end() ? wxNOT_FOUND : it - begin(); +} + +template +class wxStringCompareLess +{ +public: + wxStringCompareLess(F f) : m_f(f) { } + bool operator()(const wxString& s1, const wxString& s2) + { return m_f(s1, s2) < 0; } +private: + F m_f; +}; + +template +wxStringCompareLess wxStringCompare(F f) +{ + return wxStringCompareLess(f); +} + +void wxArrayString::Sort(CompareFunction function) +{ + std::sort(begin(), end(), wxStringCompare(function)); +} + +void wxArrayString::Sort(bool reverseOrder) +{ + if (reverseOrder) + { + std::sort(begin(), end(), std::greater()); + } + else + { + std::sort(begin(), end()); + } +} + +int wxSortedArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const +{ + wxSortedArrayString::const_iterator it; + + if (bCase) + it = std::lower_bound(begin(), end(), str, + wxStringCompare(wxStringCmp())); + else + it = std::lower_bound(begin(), end(), str, + wxStringCompare(wxStringCmpNoCase())); + + if (it == end()) + return wxNOT_FOUND; + + if (bCase) + { + if (str.Cmp(*it) != 0) + return wxNOT_FOUND; + } + else + { + if (str.CmpNoCase(*it) != 0) + return wxNOT_FOUND; + } + + return it - begin(); +} +#endif // wxUSE_STL