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

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

3 files changed, 123 insertions, 9 deletions

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));