Feature [#981]. Added autocompletion order property to allow list to be ordered

according to container preference but still allowing selection by typing.
From Alpha.

6 files changed, 160 insertions, 11 deletions

diff --git a/doc/ScintillaDoc.html b/doc/ScintillaDoc.html
index cfa13bfdc..9760c7c27 100644
--- a/doc/ScintillaDoc.html
+++ b/doc/ScintillaDoc.html
@@ -4108,6 +4108,8 @@ struct Sci_TextToFind {
      <a class="message" href="#SCI_AUTOCGETIGNORECASE">SCI_AUTOCGETIGNORECASE</a><br />
      <a class="message" href="#SCI_AUTOCSETCASEINSENSITIVEBEHAVIOUR">SCI_AUTOCSETCASEINSENSITIVEBEHAVIOUR(int behaviour)</a><br>
      <a class="message" href="#SCI_AUTOCGETCASEINSENSITIVEBEHAVIOUR">SCI_AUTOCGETCASEINSENSITIVEBEHAVIOUR</a><br>
+     <a class="message" href="#SCI_AUTOCSETORDER">SCI_AUTOCSETORDER(int order)</a><br>
+     <a class="message" href="#SCI_AUTOCGETORDER">SCI_AUTOCGETORDER</a><br>
      <a class="message" href="#SCI_AUTOCSETAUTOHIDE">SCI_AUTOCSETAUTOHIDE(bool autoHide)</a><br />
      <a class="message" href="#SCI_AUTOCGETAUTOHIDE">SCI_AUTOCGETAUTOHIDE</a><br />
      <a class="message" href="#SCI_AUTOCSETDROPRESTOFWORD">SCI_AUTOCSETDROPRESTOFWORD(bool
@@ -4132,10 +4134,13 @@ struct Sci_TextToFind {
     and <a class="message"
     href="#SCI_AUTOCGETSEPARATOR"><code>SCI_AUTOCGETSEPARATOR</code></a>.</p>
 
-    <p>The list of words should be in sorted order. If set to ignore case mode with <a class="message" href="#SCI_AUTOCSETIGNORECASE"><code>SCI_AUTOCSETIGNORECASE</code></a>, then
+    <p>With default settings, the list of words should be in sorted order.
+    If set to ignore case mode with <a class="message" href="#SCI_AUTOCSETIGNORECASE"><code>SCI_AUTOCSETIGNORECASE</code></a>, then
     strings are matched after being converted to upper case. One result of this is that the list
     should be sorted with the punctuation characters '[', '\', ']', '^', '_', and '`' sorted after
-    letters.</p>
+    letters.
+    Alternative handling of list order may be specified with  <a class="message" href="#SCI_AUTOCSETORDER">SCI_AUTOCSETORDER</a>
+    </p>
 
     <p><b id="SCI_AUTOCCANCEL">SCI_AUTOCCANCEL</b><br />
      This message cancels any displayed autocompletion list. When in autocompletion mode, the list
@@ -4220,6 +4225,20 @@ struct Sci_TextToFind {
     This corresponds to a behaviour property of <code>SC_CASEINSENSITIVEBEHAVIOUR_RESPECTCASE</code> (0).
     If you want autocompletion to ignore case at all, choose <code>SC_CASEINSENSITIVEBEHAVIOUR_IGNORECASE</code> (1).</p>
 
+    <p><b id="SCI_AUTOCSETORDER">SCI_AUTOCSETORDER(int order)</b><br>
+    <b id="SCI_AUTOCGETORDER">SCI_AUTOCGETORDER</b><br>
+    The default setting <code>SC_ORDER_PRESORTED</code> (0) requires that the list be provided in alphabetical sorted order.
+   </p>
+    <p>Sorting the list can be done by Scintilla instead of the application with <code>SC_ORDER_PERFORMSORT</code> (1).
+    This will take additional time.
+   </p>
+    <p>Applications that wish to prioritize some values and show the list in order of priority instead
+    of alphabetical order can use <code>SC_ORDER_CUSTOM</code> (2).
+    This requires extra processing in <a class="message" href="#SCI_AUTOCSHOW">SCI_AUTOCSHOW</a> to create a sorted index.
+   </p>
+    <p>Setting the order should be done before calling <a class="message" href="#SCI_AUTOCSHOW">SCI_AUTOCSHOW</a>.
+   </p>
+
     <p><b id="SCI_AUTOCSETAUTOHIDE">SCI_AUTOCSETAUTOHIDE(bool autoHide)</b><br />
      <b id="SCI_AUTOCGETAUTOHIDE">SCI_AUTOCGETAUTOHIDE</b><br />
      By default, the list is cancelled if there are no viable matches (the user has typed
diff --git a/include/Scintilla.h b/include/Scintilla.h
index 48c7ff379..490cd3bf6 100644
--- a/include/Scintilla.h
+++ b/include/Scintilla.h
@@ -698,6 +698,11 @@ typedef sptr_t (*SciFnDirect)(sptr_t ptr, unsigned int iMessage, uptr_t wParam,
 #define SC_CASEINSENSITIVEBEHAVIOUR_IGNORECASE 1
 #define SCI_AUTOCSETCASEINSENSITIVEBEHAVIOUR 2634
 #define SCI_AUTOCGETCASEINSENSITIVEBEHAVIOUR 2635
+#define SC_ORDER_PRESORTED 0
+#define SC_ORDER_PERFORMSORT 1
+#define SC_ORDER_CUSTOM 2
+#define SCI_AUTOCSETORDER 2660
+#define SCI_AUTOCGETORDER 2661
 #define SCI_ALLOCATE 2446
 #define SCI_TARGETASUTF8 2447
 #define SCI_SETLENGTHFORENCODE 2448
diff --git a/include/Scintilla.iface b/include/Scintilla.iface
index 496f472ae..8d15e1c4c 100644
--- a/include/Scintilla.iface
+++ b/include/Scintilla.iface
@@ -1842,6 +1842,17 @@ set void AutoCSetCaseInsensitiveBehaviour=2634(int behaviour,)
 # Get auto-completion case insensitive behaviour.
 get int AutoCGetCaseInsensitiveBehaviour=2635(,)
 
+enu Ordering=SC_ORDER_
+val SC_ORDER_PRESORTED=0
+val SC_ORDER_PERFORMSORT=1
+val SC_ORDER_CUSTOM=2
+
+# Set the way autocompletion lists are ordered.
+set void AutoCSetOrder=2660(int order,)
+
+# Get the way autocompletion lists are ordered.
+get int AutoCGetOrder=2661(,)
+
 # Enlarge the document to a particular size of text bytes.
 fun void Allocate=2446(int bytes,)
 
diff --git a/src/AutoComplete.cxx b/src/AutoComplete.cxx
index bab123a99..d55af8504 100644
--- a/src/AutoComplete.cxx
+++ b/src/AutoComplete.cxx
@@ -10,7 +10,9 @@
 #include <stdio.h>
 #include <assert.h>
 
+#include <algorithm>
 #include <string>
+#include <vector>
 
 #include "Platform.h"
 
@@ -36,7 +38,8 @@ AutoComplete::AutoComplete() :
 	dropRestOfWord(false),
 	ignoreCaseBehaviour(SC_CASEINSENSITIVEBEHAVIOUR_RESPECTCASE),
 	widthLBDefault(100),
-	heightLBDefault(100) {
+	heightLBDefault(100),
+	autoSort(SC_ORDER_PRESORTED) {
 	lb = ListBox::Allocate();
 	stopChars[0] = '\0';
 	fillUpChars[0] = '\0';
@@ -101,8 +104,91 @@ char AutoComplete::GetTypesep() const {
 	return typesep;
 }
 
+struct Sorter {
+	AutoComplete *ac;
+	const char *list;
+	std::vector<int> indices;
+
+	Sorter(AutoComplete *ac_, const char *list_) : ac(ac_), list(list_) {
+		int i = 0;
+		while (list[i]) {
+			indices.push_back(i); // word start
+			while (list[i] != ac->GetTypesep() && list[i] != ac->GetSeparator() && list[i])
+				++i;
+			indices.push_back(i); // word end
+			if (list[i] == ac->GetTypesep()) {
+				while (list[i] != ac->GetSeparator() && list[i])
+					++i;
+			}
+			if (list[i] == ac->GetSeparator()) {
+				++i;
+				// preserve trailing separator as blank entry
+				if (!list[i]) {
+					indices.push_back(i);
+					indices.push_back(i);
+				}
+			}
+		}
+		indices.push_back(i); // index of last position
+	}
+
+	bool operator()(int a, int b) {
+		int lenA = indices[a * 2 + 1] - indices[a * 2];
+		int lenB = indices[b * 2 + 1] - indices[b * 2];
+		int len  = std::min(lenA, lenB);
+		int cmp;
+		if (ac->ignoreCase)
+			cmp = CompareNCaseInsensitive(list + indices[a * 2], list + indices[b * 2], len);
+		else
+			cmp = strncmp(list + indices[a * 2], list + indices[b * 2], len);
+		if (cmp == 0)
+			cmp = lenA - lenB;
+		return cmp < 0;
+	}
+};
+
 void AutoComplete::SetList(const char *list) {
-	lb->SetList(list, separator, typesep);
+	if (autoSort == SC_ORDER_PRESORTED) {
+		lb->SetList(list, separator, typesep);
+		sortMatrix.clear();
+		for (int i = 0; i < lb->Length(); ++i)
+			sortMatrix.push_back(i);
+		return;
+	}
+
+	Sorter IndexSort(this, list);
+	sortMatrix.clear();
+	for (int i = 0; i < (int)IndexSort.indices.size() / 2; ++i)
+		sortMatrix.push_back(i);
+	std::sort(sortMatrix.begin(), sortMatrix.end(), IndexSort);
+	if (autoSort == SC_ORDER_CUSTOM || sortMatrix.size() < 2) {
+		lb->SetList(list, separator, typesep);
+		PLATFORM_ASSERT(lb->Length() == static_cast<int>(sortMatrix.size()));
+		return;
+	}
+
+	std::string sortedList;
+	char item[maxItemLen];
+	for (size_t i = 0; i < sortMatrix.size(); ++i) {
+		int wordLen = IndexSort.indices[sortMatrix[i] * 2 + 2] - IndexSort.indices[sortMatrix[i] * 2];
+		strncpy(item, list + IndexSort.indices[sortMatrix[i] * 2], wordLen);
+		if ((i+1) == sortMatrix.size()) {
+			// Last item so remove separator if present
+			if ((wordLen > 0) && (item[wordLen-1] == separator))
+				wordLen--;
+		} else {
+			// Item before last needs a separator
+			if ((wordLen == 0) || (item[wordLen-1] != separator)) {
+				item[wordLen] = separator;
+				wordLen++;
+			}
+		}
+		item[wordLen] = '\0';
+		sortedList += item;
+	}
+	for (int i = 0; i < (int)sortMatrix.size(); ++i)
+		sortMatrix[i] = i;
+	lb->SetList(sortedList.c_str(), separator, typesep);
 }
 
 int AutoComplete::GetSelection() const {
@@ -149,7 +235,7 @@ void AutoComplete::Select(const char *word) {
 	while ((start <= end) && (location == -1)) { // Binary searching loop
 		int pivot = (start + end) / 2;
 		char item[maxItemLen];
-		lb->GetValue(pivot, item, maxItemLen);
+		lb->GetValue(sortMatrix[pivot], item, maxItemLen);
 		int cond;
 		if (ignoreCase)
 			cond = CompareNCaseInsensitive(word, item, lenWord);
@@ -158,7 +244,7 @@ void AutoComplete::Select(const char *word) {
 		if (!cond) {
 			// Find first match
 			while (pivot > start) {
-				lb->GetValue(pivot-1, item, maxItemLen);
+				lb->GetValue(sortMatrix[pivot-1], item, maxItemLen);
 				if (ignoreCase)
 					cond = CompareNCaseInsensitive(word, item, lenWord);
 				else
@@ -172,7 +258,7 @@ void AutoComplete::Select(const char *word) {
 				&& ignoreCaseBehaviour == SC_CASEINSENSITIVEBEHAVIOUR_RESPECTCASE) {
 				// Check for exact-case match
 				for (; pivot <= end; pivot++) {
-					lb->GetValue(pivot, item, maxItemLen);
+					lb->GetValue(sortMatrix[pivot], item, maxItemLen);
 					if (!strncmp(word, item, lenWord)) {
 						location = pivot;
 						break;
@@ -187,9 +273,24 @@ void AutoComplete::Select(const char *word) {
 			start = pivot + 1;
 		}
 	}
-	if (location == -1 && autoHide)
-		Cancel();
-	else
-		lb->Select(location);
+	if (location == -1) {
+		if (autoHide)
+			Cancel();
+		else
+			lb->Select(-1);
+	} else {
+		if (autoSort == SC_ORDER_CUSTOM) {
+			// Check for a logically earlier match
+			char item[maxItemLen];
+			for (int i = location + 1; i <= end; ++i) {
+				lb->GetValue(sortMatrix[i], item, maxItemLen);
+				if (CompareNCaseInsensitive(word, item, lenWord))
+					break;
+				if (sortMatrix[i] < sortMatrix[location] && !strncmp(word, item, lenWord))
+					location = i;
+			}
+		}
+		lb->Select(sortMatrix[location]);
+	}
 }
 
diff --git a/src/AutoComplete.h b/src/AutoComplete.h
index 4d27e6add..9977196a2 100644
--- a/src/AutoComplete.h
+++ b/src/AutoComplete.h
@@ -21,6 +21,7 @@ class AutoComplete {
 	char separator;
 	char typesep; // Type seperator
 	enum { maxItemLen=1000 };
+	std::vector<int> sortMatrix;
 
 public:
 
@@ -36,6 +37,11 @@ public:
 	unsigned int ignoreCaseBehaviour;
 	int widthLBDefault;
 	int heightLBDefault;
+	/** SC_ORDER_PRESORTED:   Assume the list is presorted; selection will fail if it is not alphabetical<br />
+	 *  SC_ORDER_PERFORMSORT: Sort the list alphabetically; start up performance cost for sorting<br />
+	 *  SC_ORDER_CUSTOM:      Handle non-alphabetical entries; start up performance cost for generating a sorted lookup table
+	 */
+	int autoSort;
 
 	AutoComplete();
 	~AutoComplete();
diff --git a/src/ScintillaBase.cxx b/src/ScintillaBase.cxx
index 4a0146f7b..35aa1c49e 100644
--- a/src/ScintillaBase.cxx
+++ b/src/ScintillaBase.cxx
@@ -794,6 +794,13 @@ sptr_t ScintillaBase::WndProc(unsigned int iMessage, uptr_t wParam, sptr_t lPara
 	case SCI_AUTOCGETCASEINSENSITIVEBEHAVIOUR:
 		return ac.ignoreCaseBehaviour;
 
+	case SCI_AUTOCSETORDER:
+		ac.autoSort = wParam;
+		break;
+
+	case SCI_AUTOCGETORDER:
+		return ac.autoSort;
+
 	case SCI_USERLISTSHOW:
 		listType = wParam;
 		AutoCompleteStart(0, reinterpret_cast<const char *>(lParam));