are added to it (so it is as easy to use as a linked list), but the access
time to the elements is constant, instead of being linear in number of
elements as in the case of linked lists. It is also very size efficient and
-doesn't take more space than a C array {\it wxString[]} type. wxArrayString
-uses its knowledge of internals of wxString class to achieve this.
+doesn't take more space than a C array {\it wxString[]} type (wxArrayString
+uses its knowledge of internals of wxString class to achieve this).
This class is used in the same way as other dynamic \helpref{arrays}{wxarray},
except that no {\it WX\_DEFINE\_ARRAY} declaration is needed for it. When a
array.Last().MakeUpper();
\end{verbatim}
-Finally, none of the methods of this class is virtual including its
-destructor, so this class should not be derived from.
+There is also a varian of wxArrayString called wxSortedArrayString which has
+exactly the same methods as wxArrayString, but which always keeps the string
+in it in (alphabetical) order. wxSortedArrayString uses binary search in its
+\helpref{Index}{wxarraystringindex} function (insteadf of linear search for
+wxArrayString::Index) which makes it much more efficient if you add strings to
+the array rarely (because, of course, you have to pay for Index() efficiency
+by having Add() be slower) but search for them often. Several methods should
+not be used with sorted array (basicly, all which break the order of items)
+which is mentioned in their description.
+
+Final word: none of the methods of wxArrayString is virtual including its
+destructor, so this class should not be used as a base class.
\wxheading{Derived from}
Default and copy constructors.
+Note that when an array is assigned to a sorted array, its contents is
+automatically sorted during construction.
+
\membersection{wxArrayString::\destruct{wxArrayString}}\label{wxarraystringdtor}
\func{}{\destruct{wxArrayString}}{}
\membersection{wxArrayString::operator[]}\label{wxarraystringoperatorindex}
-\func{wxString\&}{operatorp[]}{\param{size\_t }{nIndex}}
+\func{wxString\&}{operator[]}{\param{size\_t }{nIndex}}
Return the array element at position {\it nIndex}. An assert failure will
result from an attempt to access an element beyond the end of array in debug
Appends a new item to the array.
+{\bf Warning:} For sorted arrays, the index of the inserted item will not be,
+in general, equal to \helpref{GetCount()}{wxarraystringgetcount} - 1 because
+the item is inserted at the correct position to keep the array sorted and not
+appended.
+
See also: \helpref{Insert}{wxarraystringinsert}
\membersection{wxArrayString::Alloc}\label{wxarraystringalloc}
{\it bFromEnd} is FALSE or from end otherwise. If {\it bCase}, comparison is
case sensitive (default), otherwise the case is ignored.
+This function uses linear search for wxArrayString and binary search for
+wxSortedArrayString, but it ignores the {\it bCase} and {\it bFromEnd}
+parameters in the latter case.
+
Returns index of the first item matched or wxNOT\_FOUND if there is no match.
\membersection{wxArrayString::Insert}\label{wxarraystringinsert}
If {\it nIndex} is equal to {\it GetCount() + 1} this function behaves as
\helpref{Add}{wxarraystringadd}.
+{\bf Warning:} this function should not be used with sorted array because it
+could break the order of items and, for example, subsequent calls to
+\helpref{Index()}{wxarraystringindex} would not work then!
+
\membersection{wxArrayString::IsEmpty}\label{wxarraystringisempty}
\func{}{IsEmpty}{}
Sorts the array in alphabetical order or in reverse alphabetical order if
{\it reverseOrder} is TRUE.
+{\bf Warning:} this function should not be used with sorted array because it
+could break the order of items and, for example, subsequent calls to
+\helpref{Index()}{wxarraystringindex} would not work then!
+
See also: \helpref{Sort}{wxarraystringsortcallback}
\membersection{wxArrayString::Sort (user defined)}\label{wxarraystringsortcallback}
array.Sort(CompareStringLen);
\end{verbatim}
+{\bf Warning:} this function should not be used with sorted array because it
+could break the order of items and, for example, subsequent calls to
+\helpref{Index()}{wxarraystringindex} would not work then!
+
See also: \helpref{Sort}{wxarraystringsort}
const wxString& second);
// constructors and destructor
- // default ctor
- wxArrayString();
+ // default ctor: if autoSort is TRUE, the array is always sorted (in
+ // alphabetical order)
+ wxArrayString(bool autoSort = FALSE);
// copy ctor
wxArrayString(const wxArrayString& array);
// assignment operator
// sort array elements using specified comparaison function
void Sort(CompareFunction compareFunction);
+protected:
+ void Copy(const wxArrayString& src); // copies the contents of another array
+
private:
- void Grow(); // makes array bigger if needed
- void Free(); // free the string stored
+ void Grow(); // makes array bigger if needed
+ void Free(); // free all the strings stored
- void DoSort(); // common part of all Sort() variants
+ void DoSort(); // common part of all Sort() variants
size_t m_nSize, // current size of the array
m_nCount; // current number of elements
- wxChar **m_pItems; // pointer to data
+ wxChar **m_pItems; // pointer to data
+
+ bool m_autoSort; // if TRUE, keep the array always sorted
+};
+
+class WXDLLEXPORT wxSortedArrayString : public wxArrayString
+{
+public:
+ wxSortedArrayString() : wxArrayString(TRUE)
+ { }
+ wxSortedArrayString(const wxArrayString& array) : wxArrayString(TRUE)
+ { Copy(array); }
};
// ---------------------------------------------------------------------------
// Licence: wxWindows license
/////////////////////////////////////////////////////////////////////////////
+// ============================================================================
+// declarations
+// ============================================================================
+
+// ----------------------------------------------------------------------------
+// headers
+// ----------------------------------------------------------------------------
+
#include <stdio.h>
#include <wx/string.h>
#include <wx/file.h>
#include <wx/app.h>
+
+// ----------------------------------------------------------------------------
+// conditional compilation
+// ----------------------------------------------------------------------------
+
+// what to test?
+#define TEST_ARRAYS
+#undef TEST_THREADS
+
+// ============================================================================
+// implementation
+// ============================================================================
+
+// ----------------------------------------------------------------------------
+// threads
+// ----------------------------------------------------------------------------
+
+#ifdef TEST_THREADS
+
#include <wx/thread.h>
static size_t gs_counter = (size_t)-1;
gs_counter--;
}
+#endif // TEST_THREADS
+
+// ----------------------------------------------------------------------------
+// arrays
+// ----------------------------------------------------------------------------
+
+#ifdef TEST_ARRAYS
+
+void PrintArray(const char* name, const wxArrayString& array)
+{
+ printf("Dump of the array '%s'\n", name);
+
+ size_t nCount = array.GetCount();
+ for ( size_t n = 0; n < nCount; n++ )
+ {
+ printf("\t%s[%u] = '%s'\n", name, n, array[n].c_str());
+ }
+}
+
+#endif // TEST_ARRAYS
+
+// ----------------------------------------------------------------------------
+// entry point
+// ----------------------------------------------------------------------------
+
int main(int argc, char **argv)
{
if ( !wxInitialize() )
fprintf(stderr, "Failed to initialize the wxWindows library, aborting.");
}
+#ifdef TEST_ARRAYS
+ wxArrayString a1;
+ a1.Add("tiger");
+ a1.Add("cat");
+ a1.Add("lion");
+ a1.Add("dog");
+ a1.Add("human");
+ a1.Add("ape");
+
+ puts("*** Initially:");
+
+ PrintArray("a1", a1);
+
+ wxArrayString a2(a1);
+ PrintArray("a2", a2);
+
+ wxSortedArrayString a3(a1);
+ PrintArray("a3", a3);
+
+ puts("*** After deleting a string from a1");
+ a1.Remove(2);
+
+ PrintArray("a1", a1);
+ PrintArray("a2", a2);
+ PrintArray("a3", a3);
+
+ puts("*** After reassigning a1 to a2 and a3");
+ a3 = a2 = a1;
+ PrintArray("a2", a2);
+ PrintArray("a3", a3);
+#endif // TEST_ARRAYS
+
+#ifdef TEST_THREADS
static const size_t nThreads = 3;
MyThread *threads[nThreads];
size_t n;
{
threads[n]->Delete();
}
+#endif // TEST_THREADS
wxUninitialize();
#ifndef WX_PRECOMP
#include "wx/app.h"
+ #include "wx/list.h"
#endif
#include "wx/thread.h"
extern void wxapp_install_idle_handler();
if ( g_isIdle )
wxapp_install_idle_handler();
-#else // this works for wxMSW, but may be for others too?
+#elif wxUSE_GUI // this works for wxMSW, but may be for others too?
// might also send a dummy message to the top level window, this would
// probably be cleaner?
wxIdleEvent eventIdle;
// headers
// ----------------------------------------------------------------------------
-#ifdef __GNUG__
- #pragma implementation "appbase.h"
-#endif
-
#include "wx/wxprec.h"
#ifdef __BORLANDC__
#pragma hdrstop
#endif //__BORLANDC__
-
-#include "wx/app.h"
-#include "wx/debug.h"
+#ifndef WX_PRECOMP
+ #include "wx/app.h"
+ #include "wx/debug.h"
+ #include "wx/module.h"
+#endif
// ----------------------------------------------------------------------------
// global vars
wxAppInitializerFunction
wxAppBase::m_appInitFn = (wxAppInitializerFunction)NULL;
-#if wxUSE_THREADS
- // List of events pending processing
- wxList *wxPendingEvents = NULL;
- wxCriticalSection *wxPendingEventsLocker = NULL;
-#endif // wxUSE_THREADS
-
// ----------------------------------------------------------------------------
// private classes
// ----------------------------------------------------------------------------
#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
m_nSize =
m_nCount = 0;
m_pItems = (wxChar **) NULL;
+ m_autoSort = src.m_autoSort;
*this = 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
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 );
// 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;
+ }
}
}
// add item at the end
void wxArrayString::Add(const wxString& str)
{
- wxASSERT( str.GetStringData()->IsValid() );
+ 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);
+ }
+ 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();
+ }
}
// add item at the given position
{
wxASSERT( str.GetStringData()->IsValid() );
- wxCHECK_RET( nIndex <= m_nCount, _("bad index in wxArrayString::Insert") );
+ wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
+
+ wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
Grow();
// 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();
int iIndex = Index(sz);
wxCHECK_RET( iIndex != wxNOT_FOUND,
- _("removing inexistent element in wxArrayString::Remove") );
+ wxT("removing inexistent element in wxArrayString::Remove") );
Remove(iIndex);
}
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);
projects / wxWidgets.git / commitdiff
