Improve 'quick open' search time

2 files changed, 36 insertions, 17 deletions

diff --git a/editor/quick_open.cpp b/editor/quick_open.cpp
index c71cc5af3f..b92ebed167 100644
--- a/editor/quick_open.cpp
+++ b/editor/quick_open.cpp
@@ -171,33 +171,50 @@ void EditorQuickOpen::_parse_fs(EditorFileSystemDirectory *efsd, Vector<Pair<Str
 			Pair<String, Ref<Texture> > pair;
 			pair.first = file;
 			pair.second = get_icon((has_icon(efsd->get_file_type(i), ei) ? efsd->get_file_type(i) : ot), ei);
+			list.push_back(pair);
+		}
+	}
+
+	if (add_directories) {
+		for (int i = 0; i < efsd->get_subdir_count(); i++) {
 
-			if (search_text != String() && list.size() > 0) {
+			_parse_fs(efsd->get_subdir(i), list);
+		}
+	}
+}
 
-				float this_sim = _path_cmp(search_text, file);
-				float other_sim = _path_cmp(list[0].first, file);
-				int pos = 1;
+Vector<Pair<String, Ref<Texture> > > EditorQuickOpen::_sort_fs(Vector<Pair<String, Ref<Texture> > > &list) {
 
-				while (pos < list.size() && this_sim <= other_sim) {
-					other_sim = _path_cmp(list[pos++].first, file);
-				}
+	String search_text = search_box->get_text();
+	Vector<Pair<String, Ref<Texture> > > sorted_list;
 
-				pos = this_sim >= other_sim ? pos - 1 : pos;
-				list.insert(pos, pair);
+	if (search_text == String() || list.size() == 0)
+		return sorted_list;
 
-			} else {
+	Vector<float> scores;
+	scores.resize(list.size());
+	for (int i = 0; i < list.size(); i++)
+		scores[i] = _path_cmp(search_text, list[i].first);
 
-				list.push_back(pair);
-			}
-		}
-	}
+	while (list.size() > 0) {
 
-	if (add_directories) {
-		for (int i = 0; i < efsd->get_subdir_count(); i++) {
+		float best_score = 0.0f;
+		int best_idx = 0;
 
-			_parse_fs(efsd->get_subdir(i), list);
+		for (int i = 0; i < list.size(); i++) {
+			float current_score = scores[i];
+			if (current_score > best_score) {
+				best_score = current_score;
+				best_idx = i;
+			}
 		}
+
+		sorted_list.push_back(list[best_idx]);
+		list.remove(best_idx);
+		scores.remove(best_idx);
 	}
+
+	return sorted_list;
 }
 
 void EditorQuickOpen::_update_search() {
@@ -208,6 +225,7 @@ void EditorQuickOpen::_update_search() {
 	Vector<Pair<String, Ref<Texture> > > list;
 
 	_parse_fs(efsd, list);
+	list = _sort_fs(list);
 
 	for (int i = 0; i < list.size(); i++) {
 		TreeItem *ti = search_options->create_item(root);
diff --git a/editor/quick_open.h b/editor/quick_open.h
index 3f64dd8cf0..5b91965920 100644
--- a/editor/quick_open.h
+++ b/editor/quick_open.h
@@ -49,6 +49,7 @@ class EditorQuickOpen : public ConfirmationDialog {
 
 	void _sbox_input(const Ref<InputEvent> &p_ie);
 	void _parse_fs(EditorFileSystemDirectory *efsd, Vector<Pair<String, Ref<Texture> > > &list);
+	Vector<Pair<String, Ref<Texture> > > _sort_fs(Vector<Pair<String, Ref<Texture> > > &list);
 	float _path_cmp(String search, String path) const;
 
 	void _confirmed();