Fancy search function

Dewald

I'm hoping someone can nudge my thoughts in the right direction here. I'm trying to implement a semi-advanced search function. Basically, what I have is, a DataGridView and a TextBox. The DataGridView ``was populated manualy (ie. not databinded to a DB or something) and has two columns, one for Scientific Name and one for Common Name (I'm listing species of birds or fish or whatever in the grid). I would now like to have the user type any part of a name into the `TextBox` and after every keypress the first row in the DataGridView that matches the text gets highlighted. One (not so elegant) way of doing this would be to override the `TextChanged` event of the `TextBox` and do a `foreach` on all the rows in the `DataGridView`, looking for the entered text in each row and then highlighting it if a matchis found. The problem is that the grid can have several thousand entries and a `foreach` search might take much too long. Any ideas will be appreciated.``

Gulfraz Khan

ur scenario may be different, but, i used the following method in one of my application. dgv refers to a DataGridView object BindingSource bs = new BindingSource(); //u may create a custom data source and then populate it bs.DataSource = YourDataSource; dgv.DataSource = bs.DataSource; bs.Position = bs.Find("PropertyToBeSearchedIn", "TextToBeSearched");

Guffa

Dewald wrote:

The problem is that the grid can have several thousand entries and a foreach search might take much too long.

Why do you think so? Have you tried it? I have a project with a ListView showing an event log where I filter the rows. I changed the filter to look for part of a string (in a rather inefficient way; creating temporary strings for each item), but with 90000 items the time for searching them all is still hardly noticable. Your only alternatives to looping the data when the user enters the string, is to do the searching beforehand by setting up some kind of tree, where you can find all items containing the character "a", then among those items all items that contain "ab", et.c. It would perhaps take a few seconds to search through all the data, but then it would be fast to find the items in the tree.

Despite everything, the person most likely to be fooling you next is yourself.

Guffa

Intrigued by the idea of a search trea, I tried to build a simple class that does it:

public class SearchTree<T> {

private class UniqueList<Key> : IEnumerable<Key> {

	private Dictionary<Key, byte> \_list;

	public UniqueList() {
		\_list = new Dictionary<Key, byte>();
	}

	public void Add(Key value) {
		\_list\[value\] = 1;
	}

	public Key\[\] ToArray() {
		Key\[\] result = new Key\[\_list.Count\];
		int index = 0;
		foreach (Key value in \_list.Keys) {
			result\[index++\] = value;
		}
		return result;
	}

	public IEnumerator<Key> GetEnumerator() {
		return \_list.Keys.GetEnumerator();
	}

	System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
		return \_list.Keys.GetEnumerator();
	}

}

private class NodeList : Dictionary<char, SearchNode> {

	public new SearchNode this\[char c\] {
		get {
			SearchNode node;
			if (!this.TryGetValue(c, out node)) {
				node = new SearchNode();
				this.Add(c, node);
			}
			return node;
		}
	}

}

private class SearchNode : NodeList {

	private UniqueList<T> \_indexes;

	public SearchNode() {
		\_indexes = new UniqueList<T>();
	}

	public void Add(string word, int pos, T index) {
		\_indexes.Add(index);
		if (pos < word.Length) {
			this\[word\[pos\]\].Add(word, pos + 1, index);
		}
	}

	public T\[\] FindWord(string text) {
		if (text.Length == 0) {
			return \_indexes.ToArray();
		} else {
			SearchNode node;
			if (this.TryGetValue(text\[0\], out node)) {
				return node.FindWord(text.Substring(1));
			}
			return null;
		}
	}

}

NodeList \_nodes;

public SearchTree() {
	\_nodes = new NodeList();
}

public void AddWord(string word, T index) {
	for (int i = 0; i < word.Length; i++) {
		\_nodes\[word\[i\]\].Add(word, i + 1, index);
	}
}

public T\[\] FindWord(string text) {
	if (text.Length > 0) {
		return \_nodes\[text\[0\]\].FindWord(text.Substring(1));
	}
	return null;
}

}

Creation of a search tree (from the string array lines):

SearchTree<int> tree = new SearchTree<int>();
for (int i = 0; i < lines.Length; i++) {
foreach (string word in lines[i].Split(' ')) {
tree.AddWord(word, i);
}
}

Usage:

int[] result = tree.FindWord("a");

The result is an array of indexes for the lines where the words were found (or null if nothing was found). I made some test data by copying text from some art

DaveyM69

Bookmarked for further use (I can think of plenty of applications) - 5 from me :-D You should make this into an article.

Dave
BTW, in software, hope and pray is not a viable strategy. (Luc Pattyn)

nelsonpaixao

Why not with a db???:confused: that´s not hard at all, and easier! Create a textbox_textchanged event and trigger a store procedure from there!!! I already done it, but with help of a db.:confused:

Dewald

Excellent idea and thanks for the post. I will definitely try this out in some other projects as well. As a matter of interest, you were quite right in your original post that an exhaustive search (with something like foreach) really doesn't take as much time as one would have thought. I'm amazed at how quickly it runs through 9000 entries. Thanks again.