Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

[Mark Summerfield]

Hi,

At present KDE uses kaccelgen.h to automatically generate keyboard
accelerators.

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:
http://www.qtrac.eu/accelerator.pdf
I also have a GUI program that uses it:
http://www.qtrac.eu/accelerator.html

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., www.qtrac.eu


-------------- next part --------------
A non-text attachment was scrubbed...
Name: kaccelgen.h
Type: text/x-c++hdr
Size: 19157 bytes
Desc: not available
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080609/bcceac4e/attachment.h>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kaccelgen-patch
Type: text/x-diff
Size: 23855 bytes
Desc: not available
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080609/bcceac4e/attachment.diff>