Sign in to follow this  
Toolmaker

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

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
There'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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Mike.Popoloski
There 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 this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by Mike.Popoloski
There 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 this post


Link to post
Share on other sites
Quote:
Original post by Mike.Popoloski
EDIT: 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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
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.


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Mike.Popoloski
InlineComparer


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by ranakor
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 ><

The source for it is in his post.

Share this post


Link to post
Share on other sites
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.

for more information visit http://www.macrotesting.com

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by ranakor
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 ><

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this