(svn r24337) -Feature: Allow filtering for multiple words (separated by whitespace resp. quoted) in the sign list, content- and NewGRF-guis.

10 files changed, 259 insertions, 51 deletions

diff --git a/projects/openttd_vs100.vcxproj b/projects/openttd_vs100.vcxproj
index a6d93adf5..91c0a004f 100644
--- a/projects/openttd_vs100.vcxproj
+++ b/projects/openttd_vs100.vcxproj
@@ -360,6 +360,7 @@
     <ClCompile Include="..\src\station.cpp" />
     <ClCompile Include="..\src\strgen\strgen_base.cpp" />
     <ClCompile Include="..\src\string.cpp" />
+    <ClCompile Include="..\src\stringfilter.cpp" />
     <ClCompile Include="..\src\strings.cpp" />
     <ClCompile Include="..\src\subsidy.cpp" />
     <ClCompile Include="..\src\textbuf.cpp" />
@@ -566,6 +567,7 @@
     <ClInclude Include="..\src\strgen\strgen.h" />
     <ClInclude Include="..\src\string_func.h" />
     <ClInclude Include="..\src\string_type.h" />
+    <ClInclude Include="..\src\stringfilter_type.h" />
     <ClInclude Include="..\src\strings_func.h" />
     <ClInclude Include="..\src\strings_type.h" />
     <ClInclude Include="..\src\subsidy_base.h" />
diff --git a/projects/openttd_vs100.vcxproj.filters b/projects/openttd_vs100.vcxproj.filters
index 170a96978..0c21dc5e0 100644
--- a/projects/openttd_vs100.vcxproj.filters
+++ b/projects/openttd_vs100.vcxproj.filters
@@ -309,6 +309,9 @@
     <ClCompile Include="..\src\string.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="..\src\stringfilter.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
     <ClCompile Include="..\src\strings.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
@@ -927,6 +930,9 @@
     <ClInclude Include="..\src\string_type.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\stringfilter_type.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\strings_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
index 5105ec472..4e90a232b 100644
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -711,6 +711,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\stringfilter.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\strings.cpp"
 				>
 			</File>
@@ -1539,6 +1543,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\stringfilter_type.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\strings_func.h"
 				>
 			</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
index d063a5f43..dce0ee412 100644
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -708,6 +708,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\stringfilter.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\strings.cpp"
 				>
 			</File>
@@ -1536,6 +1540,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\stringfilter_type.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\strings_func.h"
 				>
 			</File>
diff --git a/source.list b/source.list
index af8da0c2e..2ef5a3067 100644
--- a/source.list
+++ b/source.list
@@ -70,6 +70,7 @@ spritecache.cpp
 station.cpp
 strgen/strgen_base.cpp
 string.cpp
+stringfilter.cpp
 strings.cpp
 subsidy.cpp
 textbuf.cpp
@@ -299,6 +300,7 @@ stdafx.h
 strgen/strgen.h
 string_func.h
 string_type.h
+stringfilter_type.h
 strings_func.h
 strings_type.h
 subsidy_base.h
diff --git a/src/network/network_content_gui.cpp b/src/network/network_content_gui.cpp
index f3ebfc4f4..6b6e796df 100644
--- a/src/network/network_content_gui.cpp
+++ b/src/network/network_content_gui.cpp
@@ -19,6 +19,7 @@
 #include "../game/game.hpp"
 #include "../base_media_base.h"
 #include "../sortlist_type.h"
+#include "../stringfilter_type.h"
 #include "../querystring_gui.h"
 #include "../core/geometry_func.hpp"
 #include "network_content_gui.h"
@@ -234,7 +235,7 @@ public:
 /** Window that lists the content that's at the content server */
 class NetworkContentListWindow : public QueryStringBaseWindow, ContentCallback {
 	/** List with content infos. */
-	typedef GUIList<const ContentInfo*> GUIContentList;
+	typedef GUIList<const ContentInfo *, StringFilter &> GUIContentList;
 
 	static const uint EDITBOX_MAX_SIZE   =  50; ///< Maximum size of the editbox in characters.
 	static const uint EDITBOX_MAX_LENGTH = 300; ///< Maximum size of the editbox in pixels.
@@ -245,6 +246,7 @@ class NetworkContentListWindow : public QueryStringBaseWindow, ContentCallback {
 	static GUIContentList::FilterFunction * const filter_funcs[]; ///< Filter functions.
 	GUIContentList content;      ///< List with content
 	bool auto_select;            ///< Automatically select all content when the meta-data becomes available
+	StringFilter string_filter;  ///< Filter for content list
 
 	const ContentInfo *selected; ///< The selected content info
 	int list_pos;                ///< Our position in the list
@@ -318,18 +320,20 @@ class NetworkContentListWindow : public QueryStringBaseWindow, ContentCallback {
 	}
 
 	/** Filter content by tags/name */
-	static bool CDECL TagNameFilter(const ContentInfo * const *a, const char *filter_string)
+	static bool CDECL TagNameFilter(const ContentInfo * const *a, StringFilter &filter)
 	{
+		filter.ResetState();
 		for (int i = 0; i < (*a)->tag_count; i++) {
-			if (strcasestr((*a)->tags[i], filter_string) != NULL) return true;
+			filter.AddLine((*a)->tags[i]);
 		}
-		return strcasestr((*a)->name, filter_string) != NULL;
+		filter.AddLine((*a)->name);
+		return filter.GetState();
 	}
 
 	/** Filter the content list */
 	void FilterContentList()
 	{
-		if (!this->content.Filter(this->edit_str_buf)) return;
+		if (!this->content.Filter(this->string_filter)) return;
 
 		/* update list position */
 		for (ConstContentIterator iter = this->content.Begin(); iter != this->content.End(); iter++) {
@@ -742,7 +746,8 @@ public:
 
 	virtual void OnOSKInput(int wid)
 	{
-		this->content.SetFilterState(!StrEmpty(this->edit_str_buf));
+		this->string_filter.SetFilterTerm(this->edit_str_buf);
+		this->content.SetFilterState(!this->string_filter.IsEmpty());
 		this->content.ForceRebuild();
 		this->InvalidateData();
 	}
diff --git a/src/newgrf_gui.cpp b/src/newgrf_gui.cpp
index a62003c8d..f832454e6 100644
--- a/src/newgrf_gui.cpp
+++ b/src/newgrf_gui.cpp
@@ -23,6 +23,7 @@
 #include "network/network.h"
 #include "network/network_content.h"
 #include "sortlist_type.h"
+#include "stringfilter_type.h"
 #include "querystring_gui.h"
 #include "core/geometry_func.hpp"
 #include "newgrf_text.h"
@@ -587,7 +588,7 @@ static void NewGRFConfirmationCallback(Window *w, bool confirmed);
  * Window for showing NewGRF files
  */
 struct NewGRFWindow : public QueryStringBaseWindow, NewGRFScanCallback {
-	typedef GUIList<const GRFConfig *> GUIGRFConfigList;
+	typedef GUIList<const GRFConfig *, StringFilter &> GUIGRFConfigList;
 
 	static const uint EDITBOX_MAX_SIZE   =  50;
 
@@ -599,6 +600,7 @@ struct NewGRFWindow : public QueryStringBaseWindow, NewGRFScanCallback {
 	GUIGRFConfigList avails;    ///< Available (non-active) grfs.
 	const GRFConfig *avail_sel; ///< Currently selected available grf. \c NULL is none is selected.
 	int avail_pos;              ///< Index of #avail_sel if existing, else \c -1.
+	StringFilter string_filter; ///< Filter for available grf.
 
 	GRFConfig *actives;         ///< Temporary active grf list to which changes are made.
 	GRFConfig *active_sel;      ///< Selected active grf item.
@@ -1297,7 +1299,8 @@ struct NewGRFWindow : public QueryStringBaseWindow, NewGRFScanCallback {
 	{
 		if (!this->editable) return;
 
-		this->avails.SetFilterState(!StrEmpty(this->edit_str_buf));
+		string_filter.SetFilterTerm(this->edit_str_buf);
+		this->avails.SetFilterState(!string_filter.IsEmpty());
 		this->avails.ForceRebuild();
 		this->InvalidateData(0);
 	}
@@ -1387,12 +1390,13 @@ private:
 	}
 
 	/** Filter grfs by tags/name */
-	static bool CDECL TagNameFilter(const GRFConfig * const *a, const char *filter_string)
+	static bool CDECL TagNameFilter(const GRFConfig * const *a, StringFilter &filter)
 	{
-		if (strcasestr((*a)->GetName(), filter_string) != NULL) return true;
-		if ((*a)->filename != NULL && strcasestr((*a)->filename, filter_string) != NULL) return true;
-		if ((*a)->GetDescription() != NULL && strcasestr((*a)->GetDescription(), filter_string) != NULL) return true;
-		return false;
+		filter.ResetState();
+		filter.AddLine((*a)->GetName());
+		filter.AddLine((*a)->filename);
+		filter.AddLine((*a)->GetDescription());
+		return filter.GetState();;
 	}
 
 	void BuildAvailables()
@@ -1423,7 +1427,7 @@ private:
 			}
 		}
 
-		this->avails.Filter(this->edit_str_buf);
+		this->avails.Filter(this->string_filter);
 		this->avails.Compact();
 		this->avails.RebuildDone();
 		this->avails.Sort();
diff --git a/src/signs_gui.cpp b/src/signs_gui.cpp
index 55a527136..6f23f81b9 100644
--- a/src/signs_gui.cpp
+++ b/src/signs_gui.cpp
@@ -22,6 +22,7 @@
 #include "viewport_func.h"
 #include "querystring_gui.h"
 #include "sortlist_type.h"
+#include "stringfilter_type.h"
 #include "string_func.h"
 #include "core/geometry_func.hpp"
 #include "hotkeys.h"
@@ -32,35 +33,23 @@
 #include "table/strings.h"
 #include "table/sprites.h"
 
-/**
- * Contains the necessary information to decide if a sign should
- * be filtered out or not. This struct is sent as parameter to the
- * sort functions of the GUISignList.
- */
-struct FilterInfo {
-	const char *string;  ///< String to match sign names against
-	bool case_sensitive; ///< Should case sensitive matching be used?
-};
-
 struct SignList {
 	/**
-	 * A GUIList contains signs and uses a custom data structure called #FilterInfo for
-	 * passing data to the sort functions.
+	 * A GUIList contains signs and uses a StringFilter for filtering.
 	 */
-	typedef GUIList<const Sign *, FilterInfo> GUISignList;
+	typedef GUIList<const Sign *, StringFilter &> GUISignList;
 
 	static const Sign *last_sign;
 	GUISignList signs;
 
-	char filter_string[MAX_LENGTH_SIGN_NAME_CHARS * MAX_CHAR_LENGTH]; ///< The match string to be used when the GUIList is (re)-sorted.
+	StringFilter string_filter;                                       ///< The match string to be used when the GUIList is (re)-sorted.
 	static bool match_case;                                           ///< Should case sensitive matching be used?
 
 	/**
 	 * Creates a SignList with filtering disabled by default.
 	 */
-	SignList()
+	SignList() : string_filter(&match_case)
 	{
-		filter_string[0] = '\0';
 	}
 
 	void BuildSignsList()
@@ -108,26 +97,28 @@ struct SignList {
 		this->last_sign = NULL;
 	}
 
-	/** Filter sign list by sign name (case sensitive setting in FilterInfo) */
-	static bool CDECL SignNameFilter(const Sign * const *a, FilterInfo filter_info)
+	/** Filter sign list by sign name */
+	static bool CDECL SignNameFilter(const Sign * const *a, StringFilter &filter)
 	{
 		/* Get sign string */
 		char buf1[MAX_LENGTH_SIGN_NAME_CHARS * MAX_CHAR_LENGTH];
 		SetDParam(0, (*a)->index);
 		GetString(buf1, STR_SIGN_NAME, lastof(buf1));
 
-		return (filter_info.case_sensitive ? strstr(buf1, filter_info.string) : strcasestr(buf1, filter_info.string)) != NULL;
+		filter.ResetState();
+		filter.AddLine(buf1);
+		return filter.GetState();
 	}
 
 	/** Filter sign list excluding OWNER_DEITY */
-	static bool CDECL OwnerDeityFilter(const Sign * const *a, FilterInfo filter_info)
+	static bool CDECL OwnerDeityFilter(const Sign * const *a, StringFilter &filter)
 	{
 		/* You should never be able to edit signs of owner DEITY */
 		return (*a)->owner != OWNER_DEITY;
 	}
 
 	/** Filter sign list by owner */
-	static bool CDECL OwnerVisibilityFilter(const Sign * const *a, FilterInfo filter_info)
+	static bool CDECL OwnerVisibilityFilter(const Sign * const *a, StringFilter &filter)
 	{
 		assert(!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS));
 		/* Hide sign if non-own signs are hidden in the viewport */
@@ -137,11 +128,10 @@ struct SignList {
 	/** Filter out signs from the sign list that does not match the name filter */
 	void FilterSignList()
 	{
-		FilterInfo filter_info = {this->filter_string, this->match_case};
-		this->signs.Filter(&SignNameFilter, filter_info);
-		if (_game_mode != GM_EDITOR) this->signs.Filter(&OwnerDeityFilter, filter_info);
+		this->signs.Filter(&SignNameFilter, this->string_filter);
+		if (_game_mode != GM_EDITOR) this->signs.Filter(&OwnerDeityFilter, this->string_filter);
 		if (!HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS)) {
-			this->signs.Filter(&OwnerVisibilityFilter, filter_info);
+			this->signs.Filter(&OwnerVisibilityFilter, this->string_filter);
 		}
 	}
 };
@@ -200,17 +190,8 @@ struct SignListWindow : QueryStringBaseWindow, SignList {
 	void SetFilterString(const char *new_filter_string)
 	{
 		/* check if there is a new filter string */
-		if (!StrEmpty(new_filter_string)) {
-			/* Copy new filter string */
-			strecpy(this->filter_string, new_filter_string, lastof(this->filter_string));
-
-			this->EnableWidget(WID_SIL_FILTER_CLEAR_BTN);
-		} else {
-			/* There is no new string -> clear this->filter_string */
-			this->filter_string[0] = '\0';
-
-			this->DisableWidget(WID_SIL_FILTER_CLEAR_BTN);
-		}
+		this->string_filter.SetFilterTerm(new_filter_string);
+		this->SetWidgetDisabledState(WID_SIL_FILTER_CLEAR_BTN, StrEmpty(new_filter_string));
 
 		/* Repaint the clear button since its disabled state may have changed */
 		this->SetWidgetDirty(WID_SIL_FILTER_CLEAR_BTN);
@@ -386,7 +367,7 @@ struct SignListWindow : QueryStringBaseWindow, SignList {
 		/* When there is a filter string, we always need to rebuild the list even if
 		 * the amount of signs in total is unchanged, as the subset of signs that is
 		 * accepted by the filter might has changed. */
-		if (data == 0 || data == -1 || !StrEmpty(this->filter_string)) { // New or deleted sign, changed visibility setting or there is a filter string
+		if (data == 0 || data == -1 || !this->string_filter.IsEmpty()) { // New or deleted sign, changed visibility setting or there is a filter string
 			/* This needs to be done in command-scope to enforce rebuilding before resorting invalid data */
 			this->signs.ForceRebuild();
 		} else { // Change of sign contents while there is no filter string
diff --git a/src/stringfilter.cpp b/src/stringfilter.cpp
new file mode 100644
index 000000000..616fd9854
--- /dev/null
+++ b/src/stringfilter.cpp
@@ -0,0 +1,120 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file stringfilter.cpp Searching and filtering using a stringterm. */
+
+#include "stdafx.h"
+#include "string_func.h"
+#include "stringfilter_type.h"
+
+static const WChar STATE_WHITESPACE = ' ';
+static const WChar STATE_WORD = 'w';
+static const WChar STATE_QUOTE1 = '\'';
+static const WChar STATE_QUOTE2 = '"';
+
+/**
+ * Set the term to filter on.
+ * @param str Filter term
+ */
+void StringFilter::SetFilterTerm(const char *str)
+{
+	this->word_index.Reset();
+	this->word_matches = 0;
+	free(this->filter_buffer);
+
+	assert(str != NULL);
+
+	char *dest = (char *)malloc(strlen(str) + 1);
+	this->filter_buffer = dest;
+
+	WChar state = STATE_WHITESPACE;
+	const char *pos = str;
+	WordState *word = NULL;
+	size_t len;
+	for (;; pos += len) {
+		WChar c;
+		len = Utf8Decode(&c, pos);
+
+		if (c == 0 || (state == STATE_WORD && IsWhitespace(c))) {
+			/* Finish word */
+			if (word != NULL) {
+				*(dest++) = '\0';
+				word = NULL;
+			}
+			state = STATE_WHITESPACE;
+			if (c != 0) continue; else break;
+		}
+
+		if (state == STATE_WHITESPACE) {
+			/* Skip whitespace */
+			if (IsWhitespace(c)) continue;
+			state = STATE_WORD;
+		}
+
+		if (c == STATE_QUOTE1 || c == STATE_QUOTE2) {
+			if (state == c) {
+				/* Stop quoting */
+				state = STATE_WORD;
+				continue;
+			} else if (state == STATE_WORD) {
+				/* Start quoting */
+				state = c;
+				continue;
+			}
+		}
+
+		/* Add to word */
+		if (word == NULL) {
+			word = this->word_index.Append();
+			word->start = dest;
+			word->match = false;
+		}
+
+		memcpy(dest, pos, len);
+		dest += len;
+	}
+}
+
+/**
+ * Reset the matching state to process a new item.
+ */
+void StringFilter::ResetState()
+{
+	this->word_matches = 0;
+	const WordState *end = this->word_index.End();
+	for (WordState *it = this->word_index.Begin(); it != end; ++it) {
+		it->match = false;
+	}
+}
+
+/**
+ * Pass another text line from the current item to the filter.
+ *
+ * You can call this multiple times for a single item, if the filter shall apply to multiple things.
+ * Before processing the next item you have to call ResetState().
+ *
+ * @param str Another line from the item.
+ */
+void StringFilter::AddLine(const char *str)
+{
+	if (str == NULL) return;
+
+	bool match_case = this->case_sensitive != NULL && *this->case_sensitive;
+	const WordState *end = this->word_index.End();
+	for (WordState *it = this->word_index.Begin(); it != end; ++it) {
+		if (!it->match) {
+			if ((match_case ? strstr(str, it->start) : strcasestr(str, it->start)) != NULL) {
+				it->match = true;
+				this->word_matches++;
+			}
+		}
+	}
+}
+
+
diff --git a/src/stringfilter_type.h b/src/stringfilter_type.h
new file mode 100644
index 000000000..7995ffdf6
--- /dev/null
+++ b/src/stringfilter_type.h
@@ -0,0 +1,72 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file stringfilter_type.h Searching and filtering using a stringterm. */
+
+#ifndef STRINGFILTER_TYPE_H
+#define STRINGFILTER_TYPE_H
+
+#include "core/smallvec_type.hpp"
+
+/**
+ * String filter and state.
+ *
+ * The filter takes a stringterm and parses it into words separated by whitespace.
+ * The whitespace-separation can be avoided by quoting words in the searchterm using " or '.
+ * The quotation characters can be nested or concatenated in a unix-shell style.
+ *
+ * When filtering an item, all words are checked for matches, and the filter matches if every word
+ * matched. So, effectively this is a AND search for all entered words.
+ *
+ * Once the filter is set up using SetFilterTerm, multiple items can be filtered consecutively.
+ *  1. For every item first call ResetState() which resets the matching-state.
+ *  2. Pass all lines of the item via AddLine() to the filter.
+ *  3. Check the matching-result for the item via GetState().
+ */
+struct StringFilter {
+private:
+	/** State of a single filter word */
+	struct WordState {
+		const char *start;                         ///< Word to filter for.
+		bool match;                                ///< Already matched?
+	};
+
+	const char *filter_buffer;                     ///< Parsed filter string. Words separated by 0.
+	SmallVector<WordState, 4> word_index;          ///< Word index and filter state.
+	uint word_matches;                             ///< Summary of filter state: Number of words matched.
+
+	const bool *case_sensitive;                    ///< Match case-sensitively (usually a static variable).
+
+public:
+	/**
+	 * Constructor for filter.
+	 * @param case_sensitive Pointer to a (usually static) variable controlling the case-sensitivity. NULL means always case-insensitive.
+	 */
+	StringFilter(const bool *case_sensitive = NULL) : filter_buffer(NULL), word_matches(0), case_sensitive(case_sensitive) {}
+	~StringFilter() { free(this->filter_buffer); }
+
+	void SetFilterTerm(const char *str);
+
+	/**
+	 * Check whether any filter words were entered.
+	 * @return true if no words were entered.
+	 */
+	bool IsEmpty() const { return this->word_index.Length() == 0; }
+
+	void ResetState();
+	void AddLine(const char *str);
+
+	/**
+	 * Get the matching state of the current item.
+	 * @return true if matched.
+	 */
+	bool GetState() const { return this->word_matches == this->word_index.Length(); }
+};
+
+#endif /* STRINGFILTER_TYPE_H */