From e87271f35887a50e011c7c97fc63c35f5d623e50 Mon Sep 17 00:00:00 2001
From: Vadim Zeitlin <vadim@wxwidgets.org>
Date: Fri, 22 Oct 1999 09:24:15 +0000
Subject: [PATCH] 1. made wxBase compile/link/run again under Unix 2. added
 wxSortedArrayString class and documented it

git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@4128 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775
---
 docs/latex/wx/arrstrng.tex  |  44 +++++++++++--
 include/wx/string.h         |  27 ++++++--
 samples/console/console.cpp |  86 ++++++++++++++++++++++++
 src/common/appcmn.cpp       |   1 +
 src/common/event.cpp        |   2 +-
 src/common/init.cpp         |  18 ++----
 src/common/string.cpp       | 126 ++++++++++++++++++++++++++++--------
 7 files changed, 252 insertions(+), 52 deletions(-)

diff --git a/docs/latex/wx/arrstrng.tex b/docs/latex/wx/arrstrng.tex
index ab2cd02788..62f1f245e6 100644
--- a/docs/latex/wx/arrstrng.tex
+++ b/docs/latex/wx/arrstrng.tex
@@ -6,8 +6,8 @@ wxArrayString is an efficient container for storing
 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
@@ -26,8 +26,18 @@ array elements may be modified in place like this
     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}
 
@@ -54,6 +64,9 @@ functions.
 
 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}}{}
@@ -69,7 +82,7 @@ Assignment operator.
 
 \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
@@ -83,6 +96,11 @@ This is the operator version of \helpref{Item}{wxarraystringitem} method.
 
 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}
@@ -136,6 +154,10 @@ Search the element in the array, starting from the beginning if
 {\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}
@@ -152,6 +174,10 @@ Insert("foo", 0);
 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}{}
@@ -211,6 +237,10 @@ See also: \helpref{Alloc}{wxarraystringalloc}, \helpref{Dynamic array memory man
 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}
@@ -245,5 +275,9 @@ array.Add("four");
 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}
 
diff --git a/include/wx/string.h b/include/wx/string.h
index d21eb47a47..3c642cc6be 100644
--- a/include/wx/string.h
+++ b/include/wx/string.h
@@ -869,8 +869,9 @@ public:
                                  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
@@ -927,16 +928,30 @@ public:
     // 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); }
 };
 
 // ---------------------------------------------------------------------------
diff --git a/samples/console/console.cpp b/samples/console/console.cpp
index 804577456c..8b8fbcf9e1 100644
--- a/samples/console/console.cpp
+++ b/samples/console/console.cpp
@@ -9,11 +9,38 @@
 // 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;
@@ -71,6 +98,31 @@ void MyThread::OnExit()
     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() )
@@ -78,6 +130,39 @@ int main(int argc, char **argv)
         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;
@@ -101,6 +186,7 @@ int main(int argc, char **argv)
     {
         threads[n]->Delete();
     }
+#endif // TEST_THREADS
 
     wxUninitialize();
 
diff --git a/src/common/appcmn.cpp b/src/common/appcmn.cpp
index 357f388c08..d72316a6dd 100644
--- a/src/common/appcmn.cpp
+++ b/src/common/appcmn.cpp
@@ -30,6 +30,7 @@
 
 #ifndef WX_PRECOMP
     #include "wx/app.h"
+    #include "wx/list.h"
 #endif
 
 #include "wx/thread.h"
diff --git a/src/common/event.cpp b/src/common/event.cpp
index 32b436d3a9..1b71ae0912 100644
--- a/src/common/event.cpp
+++ b/src/common/event.cpp
@@ -615,7 +615,7 @@ void wxEvtHandler::AddPendingEvent(wxEvent& event)
     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;
diff --git a/src/common/init.cpp b/src/common/init.cpp
index 8af743b0d2..50b8642fbe 100644
--- a/src/common/init.cpp
+++ b/src/common/init.cpp
@@ -17,19 +17,17 @@
 // 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
@@ -40,12 +38,6 @@ wxApp * WXDLLEXPORT wxTheApp = NULL;
 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
 // ----------------------------------------------------------------------------
diff --git a/src/common/string.cpp b/src/common/string.cpp
index c0f3c6e218..4a667a59cc 100644
--- a/src/common/string.cpp
+++ b/src/common/string.cpp
@@ -1639,11 +1639,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 +1653,7 @@ wxArrayString::wxArrayString(const wxArrayString& src)
   m_nSize  =
   m_nCount = 0;
   m_pItems = (wxChar **) NULL;
+  m_autoSort = src.m_autoSort;
 
   *this = src;
 }
@@ -1662,18 +1664,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 +1703,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 +1797,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;
+      }
     }
   }
 
@@ -1806,13 +1846,41 @@ 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() );
+  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
@@ -1820,7 +1888,9 @@ 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( !m_autoSort, wxT("can't use this method with sorted arrays") );
+
+  wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
 
   Grow();
 
@@ -1836,7 +1906,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 +1922,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 +2002,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);
-- 
2.50.0

