Hi all,
as you know I'm currently reviewing the scholarLY package, not only for
new features but also for its coding - which blatantly shows how it was
initially done directly from within my learning curve ;-)
One thing I'd like to change is the storage/handling of annotations. The
current implementation does the following:
* an engraver creates an annotation (an alist) and appends it to a
global "annotations" variable (OK, simple improvement: don't append
but cons to the beginning)
* in a later stage sort this "annotations" list and export the
annotations.
This looks very inefficient, and I think it should be much better to
store the annotations in a binary search tree and have them sorted upon
insertion already. (Or am I misunderstanding this? One thing I'm unaware
of is how efficient Guile's "stable-sort" works on a simple (linked) list).
On https://gist.github.com/tushar-sharma/c476003598c03373e52c I found a
clean and simple implementation of a BST which looks like I can very
easily make if work in LilyPond (I can't test because I'm not at my PC
at the moment, but I'm talking about the general algorithms anyway).
This should let me insert the annotations in sorted order (replacing the
<, >, and = with appropriate functions to sort annotations according to
the configured requests), and it's not hard to add a function to walk
the tree from left to right.
However - and now the question starts - if I'm not mistaken the
annotations encountered by the engraver will be somewhat (or
completely?) sorted by musical moment, which will be the requested sort
order most of the time but not always. And if elements that are inserted
in that BST are already sorted the tree will be totally unbalanced, and
the insertion time is as bad (or worse) as simply appending to a list.
So if annotations would always be sorted by moment I would probably go
back to the simple linked list, but they may be sorted differently and
also by multiple keys (e.g. first by part, then by annotation type and
only then by moment).
I could make a switch and choose the storage data structure based on the
requested sorting (moment => list, everything else => BST), or I could
use a BST that realigns itself after each insertion.
I would be glad about any opinions/recommendations:
* Is it worth the effort looking into this (often there will be only a
couple of dozens of annotations per score, but three-digit numbers
shouldn't be unusual, and I have already encountered scores with
four-digit numbers of annotations)?
* Is my idea of a self-balancing BST the right direction?
* If so, which type of BST would be good to investigate (both in terms
of performance and implementation complexity)?
Thanks
Urs
_______________________________________________
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user
