KDict: A replacement for QDict

[Eray Ozkural]

Hey there,

I implemented a replacement for QDict class, which in my opinion is not a very 
realistic implementation of a dictionary ADT.

I used a standard Trie structure (prefix tree) to implement a hopefully 
scalable sort of implementation. That is still sub-optimal but it is the most 
widely used data structure for this sort of ADT, actually it's an ordinary 
kind of project for a file organization or NLP course, etc. For very small 
number of words QDict might actually be more efficient but beyond that KDict 
should have better performance. (And KDict may still have room for 
optimization... Please don't try to turn any recursive functions to 
loop/stack combinations, I don't like that at all and gcc has tail-recursion 
optimization)

You can find the stuff in CVS HEAD, module: kdevelop/lib/structure

Of course the crucial question is whether there are any applications in KDE 
that might benefit from this data structure. I saw some QDict's in imap code 
and I'm sure it's used elsewhere but is there anything that tries to index a 
large number of words in-core?

Then it would be worthwhile to try this class out.

Thanks,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C