SearchList: a quick sorted list, implemented using .NET Generics

• Download source code - 16.4 Kb

Introduction

I am writing an editor for Torque Script files, and I wanted to add Intellisense to it. The problem is that I have this huge list of functions and properties available to script and I need to sort and list them as fast as possible. A full scan was inevitable as I wanted to show every item that started with the characters entered by the user. A very good friend (Hello Daniel!) suggested this approach, and here is the implementation of this fast sorted list. In this article, I haven't implemented the search list as a class, but you could do it easily. My goal was to find a solution to the problem and as it ended up very nice, I decided to share it.

SearchList Implementation

The idea is quite simple with the use of .NET Generics: Have an index list that will group your keys for fast access, as it will reduce the final amount of keys to search. The search list is declared like this:

SortedList <string, SortedList<string, string>> alphabet;

The alphabet variable is our index list. It will keep the first character of all keys added to the internal lists, hence its name. The value of alphabet is another list, our "real" list, that will contain the keys and values we want to store. So, let's say we have these function names:

InitDedicatedClient
OnCycleExec
OnExit
OnGameDurationEnd

Using the AddToList() method, we add these values. Two keys will be created in alphabet: "i" and "o". Here is the method listing:

private function AddToList(string key, string value)
{
    // get index (first character)
    string idx = GetAlphaIndex(key);
 
    // find sub-list
    SortedList<string, string> list = null;
 
    if (!alphabet.TryGetValue(idx, out list))
    {
        // new index
        list = new SortedList<string, string>();    
 
        alphabet.Add(idx, list);
    }
 
    try
    {
        list.Add(key, value);
    }
    catch
    {
        System.Diagnostics.Debug.Write("Key [" + key + "] already exists!");
    }
}

The alphabet["i"] value is a SortedList containing one key: InitDedicatedClient. alphabet["o"] will have a SortedList with three keys: OnCycleExec, OnExit and OnGameDurationEnd.

Searching for values

In my project, I need to do a full scan and filter the words that start with the characters typed in the editor. This is done inside this function:

private void RefreshList()
{
    listBox1.Visible = false;
    listBox1.Items.Clear();
    string start = textBox1.Text;

    // add items to listbox
    if (start.Length == 0)
    {
        // add all items, no filter
        foreach (SortedList<string, string> list in alphabet.Values)
        {
            string[] keys = new String[list.Count];
            list.Keys.CopyTo(keys, 0);
            listBox1.Items.AddRange(keys);
        }
    }
    else
    {
        // get from alphabet the SortedList that contains our keys
        string idx = GetAlphaIndex(start);
        SortedList<string, string> list = null;

        if (alphabet.TryGetValue(idx, out list))
        {
            string[] keys = new String[list.Count];
            list.Keys.CopyTo(keys, 0);

            //do a fullscan looking for matches
            foreach (string s in keys)
            {
                bool bCanStop = false;
                StringComparison sct = StringComparison.OrdinalIgnoreCase;
                if (bCaseSensitive)
                    sct = StringComparison.Ordinal;

                if (s.StartsWith(start, sct))
                {
                    // found item that match;
                    // from now on, stop loop after first mismatch
                    bCanStop = true;
                    listBox1.Items.Add(s);
                }
                else
                {
                    // mismatch: Can stop searching for matches?
                    if (bCanStop)
                        break;
                }
            }
        }
    }
    listBox1.Visible = true;
}

Thank you!

Please feel free to add any comments. If you are going to use this code, please mail me and add a reference to this article in your application credits. Thanks for reading and... That's all folks!