# [.net] .NET dictionary with (string) key completion?

## Recommended Posts

Toolmaker    967
I'm currently looking for a .NET dictionary which uses strings for keys, and offers the ability to auto-complete the string keys. The kind of behaviour I would like to achieve is somewhat like this: If I add 2 keys to the dictionary, says 'apple' and 'cherry', and I want to look up a value in the dictionary, that it would work if I supplied a partial key, as in 'app', which would auto complete to 'apple', and return the value stored with the key. Right now, if I want to achieve this kind of behavior I need to add all variations to the dictionary, which technically would work, but requires a lot of additional work for me since these dictionaries change regularly. Toolmaker

##### Share on other sites
SiCrane    11839
There's probably a better way that this, but I'd just use C++/CLI to expose an instance of cliext::map<> with a string key. When you need to check for a partial key use lower_bound().

##### Share on other sites
If I understood correctly, you want something akin to this

var strings = new Dictionary<string, string>{{"ABC", "1"}, {"DEF", "2"}, {"GHI", "3"}, {"JKL", "4"}, {"A2", "5"}, {"D2", "6"}, {"G2", "7"}, {"J2", "3"}};var result = from s in strings             where s.Key.StartsWith("A")	     select s.Value;			result.ToList().ForEach(Console.WriteLine);

I believe internally StartsWith behaves like the solution described by SiCrane.

(If strings was a list, the query would be just
var result = from s in strings where s.StartsWith("A") select s;result.ToList().ForEach(Console.WriteLine);
)

[Edited by - Naurava kulkuri on June 18, 2009 8:04:25 AM]

##### Share on other sites
Mike.Popoloski    3258
Quote:
 Original post by SiCraneThere's probably a better way that[sic] this, but I'd just use C++/CLI to expose an instance of cliext::map<> with a string key. When you need to check for a partial key use lower_bound().

There is actually a much better way to do this [grin]

Dictionary (and a few other collections) allow you to specify an implementation of IEqualityComparer, which you can easily override to allow any sort of key matching function you want. Naurava kulkuri's approach will work for this specific example, but the equality comparer method will be used throughout the Dictionary's methods.

While you could just derive a new class from IEqualityComparer each time, I prefer using the following generic class so that you can specify the comparison method inline using lambdas/anonymous delegates. Your mileage may vary.
class InlineComparer<T> : IEqualityComparer<T>{	readonly Func<T, T, bool> equals;	readonly Func<T, int> getHashCode;	public StuffComparer(Func<T, T, bool> equals, Func<T, int> getHashCode)	{		this.equals = equals;		this.getHashCode = getHashCode;	}	public bool Equals(T x, T y)	{		return equals(x, y);	}	public int GetHashCode(T obj)	{		return getHashCode(obj);	} }

The solution to your example then becomes:
var dictionary = new Dictionary<string, string>(new InlineComparer<string>(    (s1, s2) => s1.StartsWith(s2),    s => s.GetHashCode()));// use however you want

##### Share on other sites
smr    2468
How does this work when there are multiple keys matching the queried key? It seems that you'd just get one of the matching items at random to me.

##### Share on other sites
SiCrane    11839
Quote:
 Original post by Mike.PopoloskiThere is actually a much better way to do this [grin]

Doesn't that violate the conditions for IEqualityComparer? The equality condition isn't symmetric or transitive, and Equals(x, y) doesn't imply GetHashCode(x) == GetHashCode(y).

##### Share on other sites
Mike.Popoloski    3258
Quote:
Original post by SiCrane
Quote:
 Original post by Mike.PopoloskiThere is actually a much better way to do this [grin]

Doesn't that violate the conditions for IEqualityComparer? The equality condition isn't symmetric or transitive, and Equals(x, y) doesn't imply GetHashCode(x) == GetHashCode(y).

Yeah, I realized that a little while ago. I wonder if it would work if you just did s1.StartsWith(s2) || s2.StartsWith(s1)

EDIT: Just did a little more reading, and obviously no this will not work. Ignore me completely [grin]

##### Share on other sites
Quote:
 Original post by Mike.PopoloskiEDIT: Just did a little more reading, and obviously no this will not work. Ignore me completely [grin]
I'm not sure what you were after, but there's a similar kind of an approach discussed at Stack Overflow. Related to this this on implementing a generic comparer in C# (and .NET). I'm guessing your idea was related to this, but in any case, a few quick links to follow if someone is pondering over these and feels puzzled what it could be. :)

On a related note, there's a rather neat way on implementing a generic INotifyPropertyChanged system with ideas related to these. Very short and to the point.

##### Share on other sites
Nypyren    12065
I would search around to see if anyone has already written a Trie for .Net (which they probably have).

A Trie is exactly what you want if you intend to use the autocompletion primarily instead of the string hash primarily as the lookup method.

##### Share on other sites
Toolmaker    967
Quote:
 Original post by NypyrenI would search around to see if anyone has already written a Trie for .Net (which they probably have).A Trie is exactly what you want if you intend to use the autocompletion primarily instead of the string hash primarily as the lookup method.

That's an interesting one... Currently I use a list with the linq selection statement. It works, but I'm not sure if it's fast enough in the future. But it'll has to prove itself.

Toolmaker

##### Share on other sites
ernow    732
Did you know that there is something like this in WinForms? Just add a textbox to a form and have a look at the autocomplete properties. Using reflector you would be able to find out how they(-> MS) did it.

##### Share on other sites
ranakor    439
Quote:
 Original post by Mike.PopoloskiInlineComparer

Opened up vstudio only to see this not offered and nothing on google , did you mistype the type name or did you just make me dream that my linq life would be simlified for nothing? /cry ><

##### Share on other sites
Spodi    642
I love making data structures and I've never made a Trie before, so I decided to take an hour and give it a shot. Its not the most beautiful or best performing Trie, but it'll work just fine for an auto-complete:

http://www.vbgore.com/temp/cstrie.rar

Just a few side notes:
* I initially wrote it to not require parent references, but that ended up being quite ugly and just not worth it.
* It'll sort the results only with alphanumeric characters. Will have to implement your own IComparer<char> if you want any better sorting.
* I don't think it makes any guarantee on depth, so you might need to change it to compare on the TrieNode and take depth into consideration.
* You can easily sacrifice memory for performance by either fully resolving the Value property just once, or adding a "checkpoint", such as fully resolving every node on different levels (ie Depth % 5 == 0).
* You can get rid of the Trie completely, and just use the TrieNodes if you move the helper functions in the Trie to a public static class. All the actual work is done in the TrieNode.

##### Share on other sites
SiCrane    11839
Quote:
 Original post by ranakorOpened up vstudio only to see this not offered and nothing on google , did you mistype the type name or did you just make me dream that my linq life would be simlified for nothing? /cry ><

The source for it is in his post.

##### Share on other sites
satykumar    100
For Xcode 3, copy ODCompletionDictionary.xcplugin to one of these locations:
/Library/Application Support/Developer/Shared/Xcode/Plug-ins/
~/Library/Application Support/Developer/Shared/Xcode/Plug-ins/

For Xcode 2, copy ODCompletionDictionary.pbplugin to one of these locations:
/Library/Application Support/Apple/Developer Tools/Plug-ins/
~/Library/Application Support/Apple/Developer Tools/Plug-ins/

Finally, quit and restart Xcode. After successful installation Completion Dictionary logs its version number to the Console whenever the plugin gets loaded into Xcode.

##### Share on other sites
ranakor    439
Quote:
Original post by SiCrane
Quote:
 Original post by ranakorOpened up vstudio only to see this not offered and nothing on google , did you mistype the type name or did you just make me dream that my linq life would be simlified for nothing? /cry ><

The source for it is in his post.

Err uhm lol , it's pretty sad that i actually looked at his post quite a bit , missing that 2nd window before asking lol... Ok back to hiding in my cave

## Create an account

Register a new account