Search anywhere in list, not just the first letter

Question

What I want to do, is to search in a ComboBox, for a word, or a part of a word like this:

For example I have these entries in my combobox:

abc
Abc
Dabc
adbdcd

And when I search for "abc", it should show me every one in the list, except "

adbdcd"

I fill my combobox from a mysql database, so my items are in a "Collection".

I have autocomplete enabled (mode: SuggestAppend, source: ListItems)

This is the code, I am using right now:

private void comboBox1_KeyPress(object sender, KeyPressEventArgs e) { comboKeyPressed(); }

    private void comboBox1_TextChanged(object sender, EventArgs e)
    {
        if (comboBox1.Text.Length == 0) comboKeyPressed();
    }

    private void comboKeyPressed()
    {
        comboBox1.DroppedDown = true;

        object[] originalList = (object[])comboBox1.Tag;
        if (originalList == null)
        {
            // backup original list
            originalList = new object[comboBox1.Items.Count];
            comboBox1.Items.CopyTo(originalList, 0);
            comboBox1.Tag = originalList;
        }

        // prepare list of matching items
        string s = comboBox1.Text.ToLower();
        IEnumerable<object> newList = originalList;
        if (s.Length > 0)
        {
            newList = originalList.Where(item => item.ToString().ToLower().Contains(s));
        }

        // clear list (loop through it, otherwise the cursor would move to the beginning of the textbox...)
        while (comboBox1.Items.Count > 0)
        {
            comboBox1.Items.RemoveAt(0);
        }

        // re-set list
        comboBox1.Items.AddRange(newList.ToArray());
    }

The problem with this code, is if I search for "abc" in my example list, "adbdcd" will show up too. And this code randomly crashes my program when I hit backspace in the combobox.

Answer 1

This is the root cause of crash:

    while (comboBox1.Items.Count > 0)
    {
        // this is raising exception if you try to remove the last item
        // Check the doc of RemoveAt
        comboBox1.Items.RemoveAt(0);
    }

use that instead:

comboBox1.Items.Clear();

However what you are trying to achieve is still unclear. If Text of combox is empty, then nothing will ever happen apart from clearing and re adding the same items to the combo box.

My understanding is that you're trying to duplicate the completion behavior while having it enabled. It can raise exception too (AccessViolationException) since you try to modify the Items collection while the framework tries to do the same.

If you're not happy with the default auto completion behavior, disable it and try to implement it completely inside the comboKeyPressed method. It means then calling it whenever text is modified.

Modification of your code to make it work (Disable auto completion though):

    private void comboBox1_TextChanged(object sender, EventArgs e)
    {
        comboKeyPressed();
    }

    private void comboKeyPressed()
    {
        if (comboBox1.Text == lastFilter)
        {
            return;
        }

        object[] originalList = (object[]) comboBox1.Tag;
        if (originalList == null)
        {
            // backup original list
            originalList = new object[comboBox1.Items.Count];
            comboBox1.Items.CopyTo(originalList, 0);
            comboBox1.Tag = originalList;
        }

        // prepare list of matching items
        string s = comboBox1.Text.ToLower();
        IEnumerable<object> newList = originalList;
        if (s.Length > 0)
        {
            newList = originalList.Where(item => item.ToString().ToLower().Contains(s));
        }            
        // clear list (loop through it, otherwise the cursor would move to the beginning of the textbox...)
        comboBox1.Items.Clear();
        // re-set list
        comboBox1.Items.AddRange(newList.ToArray());

        comboBox1.Select(Text.Length -1, 0);

        lastFilter = comboBox1.Text;
        comboBox1.DroppedDown = true;
    }

Answer 2

So, you want fulltext search.

Where is your data coming from? What kind of data is it? What are the edge cases?

For databases, I like to use Sphinx for fulltext indexing.

For in-memory data, efficient fulltext search algorithms include Suffix Arrays, Suffix Trees, and Patricia Tries. Implementing them can be a fun (and time-consuming) challenge. Or you might find a suitable implementation online. You can find barebones implementations of these algorithms, as well as more polished implementations of fulltext search, such as Lucene.

To give you a sketch of how they work, imagine taking every possible suffix of every word that you store, e.g. needle:

• needle
• eedle
• edle
• dle
• le
• e

Put all these suffixes into an ordered data structure, such as a sorted array or list (for static data) or a B-tree or SortedDictionary (if data is added regularly). After inserting needle, it would contain:

• dle
• e
• edle
• eedle
• le
• needle

Now we can search for any part of a word (e.g. edl) using binary search or better, and see if we have a hit.

To extract more information than just whether or not we have a hit, we could add data to, for example, the values of the SortedDictionary. (We used the suffixes as keys.) Interesting data could be the entire word, or perhaps the original text and location where the word was encountered.

Answer 3

If the number of entries to search from is always low - perhaps no more than a few hundred - then a simple implementation will suffice.

// Select all words that contain our query string
var matchingWords = wordList.Where(word => word.Contains(query));

This is the naive, linear implementation that will become very slow for large data. For small data, though, it is super easy. Just feed the new subset to your combo box.

You might want to add case-insensitivity to the Contains() call, using its optional second parameter.