Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

Mark Summerfield mark at
Mon Jun 9 13:52:35 BST 2008


At present KDE uses kaccelgen.h to automatically generate keyboard

The algorithm used is very easy to understand, but produces poor
results---for example, in many real use cases it can only generate
accelerators for half or fewer of the strings it is given.

I have created a completely different algorithm that is more
sophisticated (but still perfectly understandable) and that can produce
optimal results every time. One theoretical drawback is that my
algorithm can take a lot longer to run than the current one---O(n!) vs.
O(n). But by tuning my algorithm for speed it still equals or betters
the existing algorithm in all the cases I've tested and has a runtime
performance of single or double figure milliseconds---so it is fast
enough to generate menu accelerators dynamically.

I have a short draft document (6 pages) that explains the logic and time
complexity of my algorithm and gives some comparison data:
I also have a GUI program that uses it:

I have made a version of the algorithm as a drop-in replacement for the
one in kaccelgen with the same API (plus two optional parameters, the
second of which tunes the algorithm for speed). It also includes two
additional functions: is_valid() that takes a list of strings with
accelerators and quality() which provides a kind of quality measure.

I've attached a patch so you can try it out (+ my kaccelgen.h since I v.
rarely use patches so may have done the patch wrong).

I also have a main.cpp and some test input and output for regression
testing which I can give you if you want.

If the patch is accepted I am willing to maintain it, i.e., I'll get a
KDE developer account etc. (well assuming you'll let me:-)

PS I cc'd Aaron because he suggested I send the patch to this list and
told me about KDE's preferred license etc.

Mark Summerfield, Qtrac Ltd.,

-------------- next part --------------
A non-text attachment was scrubbed...
Name: kaccelgen.h
Type: text/x-c++hdr
Size: 19157 bytes
Desc: not available
URL: <>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kaccelgen-patch
Type: text/x-diff
Size: 23855 bytes
Desc: not available
URL: <>

More information about the kde-core-devel mailing list