structure library

[Eray Ozkural]

Hi Roland,

QDict lacks the scalability and storage characteristics usually associated 
with "dictionary" datatype (meaning one that stores a set of strings, not one 
that stores atomic datatypes). I didn't read the source code, but from the 
documentation it doesn't seem to be using a trie, and that's what I'm 
implementing.

The trie isn't the optimal data structure for this purpose, the optimal one is 
actually a graph (representing a certain automata, it was published sometime 
in 2000 or 2001) and I don't have the time to implement that. The second best 
thing is a trie, it is one of those things that sophomore CS students might 
be given as projects. This code I had implemented while working on an 
advanced algorithm and I will contribute it because it was fast and pretty 
generic, and in C++.

For very small dictionaries I would expect QDict to be slightly faster.

I would be willing to implement other harder algorithms that might be of 
utility, for instance does anyone need a priority queue or a k-d tree? As an 
algorithms person, I don't like dealing with graphics-only things too much 
but such things are entertaining for me.

Two other structures that popped into my mind were a decent tree and graph 
datatype together with a framework for graphically interacting with them but 
that is a more distant project. I expect to use that for various plugins in 
the future.

The current trie code is definitely more easier than a decent graph 
implementation with visualization code. I will utilize it by converting some 
QDict code in kdevelop to KDict code.

At least I'm back in HEAD :)

Thanks,

-- 
Eray Ozkural <eozk at bicom-inc.com>
Software Engineer, BICOM Inc.
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C