X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/223d09f6b523aac674ef9b72a883dfa8d37c5d4e..7aa733b31e265f79c7a4424ee0e5b8a10422dd76:/src/common/string.cpp diff --git a/src/common/string.cpp b/src/common/string.cpp index c0f3c6e218..c18e35f606 100644 --- a/src/common/string.cpp +++ b/src/common/string.cpp @@ -36,7 +36,7 @@ #include "wx/string.h" #include "wx/intl.h" #if wxUSE_THREADS - #include + #include "wx/thread.h" #endif #endif @@ -176,6 +176,12 @@ istream& operator>>(istream& is, wxString& WXUNUSED(str)) return is; } +ostream& operator<<(ostream& os, const wxString& str) +{ + os << str.c_str(); + return os; +} + #endif //std::string compatibility // ---------------------------------------------------------------------------- @@ -1639,11 +1645,12 @@ wxString& wxString::replace(size_t nStart, size_t nLen, #define STRING(p) ((wxString *)(&(p))) // ctor -wxArrayString::wxArrayString() +wxArrayString::wxArrayString(bool autoSort) { m_nSize = m_nCount = 0; m_pItems = (wxChar **) NULL; + m_autoSort = autoSort; } // copy ctor @@ -1652,6 +1659,7 @@ wxArrayString::wxArrayString(const wxArrayString& src) m_nSize = m_nCount = 0; m_pItems = (wxChar **) NULL; + m_autoSort = src.m_autoSort; *this = src; } @@ -1662,18 +1670,30 @@ wxArrayString& wxArrayString::operator=(const wxArrayString& src) if ( m_nSize > 0 ) Clear(); + Copy(src); + + return *this; +} + +void wxArrayString::Copy(const wxArrayString& src) +{ if ( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE ) Alloc(src.m_nCount); // we can't just copy the pointers here because otherwise we would share - // the strings with another array - for ( size_t n = 0; n < src.m_nCount; n++ ) - Add(src[n]); - + // the strings with another array because strings are ref counted +#if 0 if ( m_nCount != 0 ) memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(wxChar *)); +#endif // 0 - return *this; + for ( size_t n = 0; n < src.m_nCount; n++ ) + Add(src[n]); + + // if the other array is auto sorted too, we're already sorted, but + // otherwise we should rearrange the items + if ( m_autoSort && !src.m_autoSort ) + Sort(); } // grow the array @@ -1689,8 +1709,8 @@ void wxArrayString::Grow() else { // otherwise when it's called for the first time, nIncrement would be 0 // and the array would never be expanded -#if defined(__VISAGECPP__) - int array_size = ARRAY_DEFAULT_INITIAL_SIZE; +#if defined(__VISAGECPP__) && defined(__WXDEBUG__) + int array_size = ARRAY_DEFAULT_INITIAL_SIZE; wxASSERT( array_size != 0 ); #else wxASSERT( ARRAY_DEFAULT_INITIAL_SIZE != 0 ); @@ -1783,20 +1803,46 @@ void wxArrayString::Shrink() // searches the array for an item (forward or backwards) int wxArrayString::Index(const wxChar *sz, bool bCase, bool bFromEnd) const { - if ( bFromEnd ) { - if ( m_nCount > 0 ) { - size_t ui = m_nCount; - do { - if ( STRING(m_pItems[--ui])->IsSameAs(sz, bCase) ) - return ui; - } - while ( ui != 0 ); + if ( m_autoSort ) { + // use binary search in the sorted array + wxASSERT_MSG( bCase && !bFromEnd, + wxT("search parameters ignored for auto sorted array") ); + + size_t i, + lo = 0, + hi = m_nCount; + int res; + while ( lo < hi ) { + i = (lo + hi)/2; + + res = wxStrcmp(sz, m_pItems[i]); + if ( res < 0 ) + hi = i; + else if ( res > 0 ) + lo = i + 1; + else + return i; } + + return wxNOT_FOUND; } else { - for( size_t ui = 0; ui < m_nCount; ui++ ) { - if( STRING(m_pItems[ui])->IsSameAs(sz, bCase) ) - return ui; + // use linear search in unsorted array + if ( bFromEnd ) { + if ( m_nCount > 0 ) { + size_t ui = m_nCount; + do { + if ( STRING(m_pItems[--ui])->IsSameAs(sz, bCase) ) + return ui; + } + while ( ui != 0 ); + } + } + else { + for( size_t ui = 0; ui < m_nCount; ui++ ) { + if( STRING(m_pItems[ui])->IsSameAs(sz, bCase) ) + return ui; + } } } @@ -1804,15 +1850,47 @@ int wxArrayString::Index(const wxChar *sz, bool bCase, bool bFromEnd) const } // add item at the end -void wxArrayString::Add(const wxString& str) -{ - wxASSERT( str.GetStringData()->IsValid() ); +size_t wxArrayString::Add(const wxString& str) +{ + if ( m_autoSort ) { + // insert the string at the correct position to keep the array sorted + size_t i, + lo = 0, + hi = m_nCount; + int res; + while ( lo < hi ) { + i = (lo + hi)/2; + + res = wxStrcmp(str, m_pItems[i]); + if ( res < 0 ) + hi = i; + else if ( res > 0 ) + lo = i + 1; + else { + lo = hi = i; + break; + } + } - Grow(); + wxASSERT_MSG( lo == hi, wxT("binary search broken") ); - // the string data must not be deleted! - str.GetStringData()->Lock(); - m_pItems[m_nCount++] = (wxChar *)str.c_str(); + Insert(str, lo); + + return (size_t)lo; + } + else { + wxASSERT( str.GetStringData()->IsValid() ); + + Grow(); + + // the string data must not be deleted! + str.GetStringData()->Lock(); + + // just append + m_pItems[m_nCount] = (wxChar *)str.c_str(); // const_cast + + return m_nCount++; + } } // add item at the given position @@ -1820,7 +1898,7 @@ void wxArrayString::Insert(const wxString& str, size_t nIndex) { wxASSERT( str.GetStringData()->IsValid() ); - wxCHECK_RET( nIndex <= m_nCount, _("bad index in wxArrayString::Insert") ); + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") ); Grow(); @@ -1836,7 +1914,7 @@ void wxArrayString::Insert(const wxString& str, size_t nIndex) // removes item from array (by index) void wxArrayString::Remove(size_t nIndex) { - wxCHECK_RET( nIndex <= m_nCount, _("bad index in wxArrayString::Remove") ); + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Remove") ); // release our lock Item(nIndex).GetStringData()->Unlock(); @@ -1852,7 +1930,7 @@ void wxArrayString::Remove(const wxChar *sz) int iIndex = Index(sz); wxCHECK_RET( iIndex != wxNOT_FOUND, - _("removing inexistent element in wxArrayString::Remove") ); + wxT("removing inexistent element in wxArrayString::Remove") ); Remove(iIndex); } @@ -1932,6 +2010,8 @@ void wxArrayString::Sort(bool reverseOrder) void wxArrayString::DoSort() { + wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") ); + // just sort the pointers using qsort() - of course it only works because // wxString() *is* a pointer to its data qsort(m_pItems, m_nCount, sizeof(wxChar *), wxStringCompareFunction);