Click here to Skip to main content
Click here to Skip to main content

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

, 19 Jun 2005
Rate this:
Please Sign up or sign in to vote.
The search list is a composition of SortedLists that will let you find your data in no time. This is indicated when you need filtered full scans in large lists.

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!

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Luciano Bargmann
Web Developer
Brazil Brazil
Interested in C#, ASP.NET and games programming;

Comments and Discussions

 
GeneralVery Good... PinmemberMasudur18-Feb-08 21:51 
GeneralExcellent Demo Pinmemberganesan balachandar20-Dec-06 4:24 
GeneralRe: Excellent Demo PinmemberLuciano Bargmann20-Dec-06 7:04 
GeneralRe: Excellent Demo Pinmemberganesan balachandar20-Dec-06 7:07 
GeneralVery usefull function PinmemberRoberto 'Obi-Wan' Colnaghi Junior23-Oct-06 9:58 
QuestionForget something? Pinmemberfwsouthern19-Jun-05 18:27 
AnswerRe: Forget something? PinmemberLuciano Bargmann21-Jun-05 7:14 
GeneralRe: Forget something? Pinmembertbenami16-Aug-06 23:37 
AnswerRe: Forget something? PinmemberLuciano Bargmann17-Aug-06 9:37 
I re-downloaded the code and its all there... In the zip root you will find SearchList.sln and SearchList folder; inside SearchList folder you have the project files, and a bin folder containing the executable you may have run.
 
Although this algorithm did his job on fastening things up on my project, I realise that when writing such a public article I should have given some numbers to allow comparison on how fast (or not) this can get. I just forgive myself cause this was my first article ever. Smile | :)
 
I think I will revisit the code and add the performance numbers to the this article.
 
BTW, I can send you the project files if you want.
 
HunterKiller

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 19 Jun 2005
Article Copyright 2005 by Luciano Bargmann
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid