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)
{
string idx = GetAlphaIndex(key);
SortedList<string, string> list = null;
if (!alphabet.TryGetValue(idx, out list))
{
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;
if (start.Length == 0)
{
foreach (SortedList<string, string> list in alphabet.Values)
{
string[] keys = new String[list.Count];
list.Keys.CopyTo(keys, 0);
listBox1.Items.AddRange(keys);
}
}
else
{
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);
foreach (string s in keys)
{
bool bCanStop = false;
StringComparison sct = StringComparison.OrdinalIgnoreCase;
if (bCaseSensitive)
sct = StringComparison.Ordinal;
if (s.StartsWith(start, sct))
{
bCanStop = true;
listBox1.Items.Add(s);
}
else
{
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!