Realtime filtering of listbox

Question

I would like to be able to filter a listbox containing 1000 strings, each 50 - 4000 characters in length, as the user types in the textbox without a delay.

I'm currently using a timer which updates the listbox after the TextChanged event of the textbox has not been triggered in 300ms. However, this is quite jerky and the ui sometimes freezes momentarily.

What is the normal way of implementing functionality similar to this?

Edit: I'm using winforms and .net2.

Thanks

Here is a stripped down version of the code I am currently using:

string separatedSearchString = this.filterTextBox.Text;

List<string> searchStrings = new List<string>(separatedSearchString.Split(new char[] { ';' }, 
                                              StringSplitOptions.RemoveEmptyEntries));

//this is a member variable which is cleared when new data is loaded into the listbox
if (this.unfilteredItems.Count == 0)
{
    foreach (IMessage line in this.logMessagesListBox.Items)
    {
        this.unfilteredItems.Add(line);
    }
}

StringComparison comp = this.IsCaseInsensitive
                        ? StringComparison.OrdinalIgnoreCase
                        : StringComparison.Ordinal;

List<IMessage> resultingFilteredItems = new List<IMessage>();

foreach (IMessage line in this.unfilteredItems)
{
    string message = line.ToString();
    if(searchStrings.TrueForAll(delegate(string item) { return message.IndexOf(item, comp) >= 0; }))
    {
        resultingFilteredItems.Add(line);
    }
}

this.logMessagesListBox.BeginUpdate();
this.logMessagesListBox.Items.Clear();
this.logMessagesListBox.Items.AddRange(resultingFilteredItems.ToArray());
this.logMessagesListBox.EndUpdate();

Answer 1

You can do two things:

1. Make you UI more responsive with a second thread which takes cares of the filtering. A really great new technology is Reactive Extensions (Rx) which will do exactly what you need.

   I can give a example. I guess you use WinForms? A part of you code would help.

   http://msdn.microsoft.com/en-us/devlabs/ee794896.aspx

   Here is a little teaser:

   Observable.Context = SynchronizationContext.Current;
   var textchanged = Observable.FromEvent<EventArgs>(textBox1, "TextChanged");
   
   
   textchanged.Throttle(300).Subscribe(ea =>
   {
       //Here 300 milisec. is gone without TextChanged fired. Do the filtering
   });
   

2. Make your filtering algorithm more efficient. Do you filter with something like StartWith or something like Contains?

   You can use something like a suffix tree or all the prefixes of the list items and make a lookup. But describe what you need precisely and I will find something simple - yet efficient enough. The UI is pretty heavy if you want to show 100.000 items in the ListBox but if you only take - say 100 - it is fast (uncomment the .Take(100) line). It can also be made a little better if the searching is done in another thread. It should be easy with Rx but I haven't tried it.

Update

Try something like this. It works fine here with 100.000 elements which is ~10 characters long. It uses Reactive Extensions (the link before).

Also, the algorithm is naive and can be made a lot faster if you want to.

private void Form1_Load(object sender, EventArgs e)
{
    Observable.Context = SynchronizationContext.Current;
    var textchanged = Observable.FromEvent<EventArgs>(textBox1, "TextChanged");

    //You can change 300 to something lower to make it more responsive
    textchanged.Throttle(300).Subscribe(filter);
}

private void filter(IEvent<EventArgs> e)
{
    var searchStrings = textBox1.Text.Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);

    //my randStrings is your unfiltered messages

    StringComparison comp = StringComparison.CurrentCulture; //Do what you want here

    var resultList = from line in randStrings
                     where searchStrings.All(item => line.IndexOf(item, comp) >= 0)
                     select line;

    //A lot faster but only gives you first 100 finds then uncomment:
    //resultList = resultList.Take(100);

    listBox1.BeginUpdate();
    listBox1.Items.Clear();
    listBox1.Items.AddRange(resultList.ToArray());
    listBox1.EndUpdate();
}

Answer 2

You can look into using a BindingSource for your List. It can do what you're looking for.

http://msdn.microsoft.com/en-us/library/system.windows.forms.bindingsource.filter.aspx

An example using a DataTable, but the same stuff can apply to a List.

http://msdn.microsoft.com/en-us/library/ya3sah92.aspx