Am 18.06.2018 um 11:16 schrieb Urs Liska:
Am 18.06.2018 um 10:57 schrieb Jan-Peter Voigt:
Hi Urs,
there are self balancing trees like AVL or Red-Black, but I'd say
implementation cost is quite for this purpose to sort n<1000
elements. I might be wrong, but I'd prefer the sort method.
OK, this is why I ask.
(I assume with "implementation" cost you mean the additional time
needed for insertion/balancing, not the time *I* need for the
implementation?)
Yes I mean insertion cost, but I also mean weight of the code. You
have a complex structure to maintain.
The EE uses a tree that sorts by measure on the first level, by
moment on second and then by the edition-id-path. So there is a tree
structure, but on each level the child-list for each node is sorted
by the guile method sort, when it is displayed in order. To access
the elements it uses a hashtable.
In your case annotations should be at least partially sorted. The
question is, where/when do you need the sorted list?
When exporting annotations.
So this is a one time sorting task. Or twice, if you have two views.
While typesetting music, you need to insert access the elements by a
path moment/context or the like.
Yes. When an acknowledged grob has an annotation attached it will be
prepended to the list or inserted into the tree.
The list will be sorted for one view. I assume `reverse` a quite cheap
function.
To export a summary the order might be given by a path
piece/movement/measure/moment/context.
So do I get this right: you're suggestion that I *do* use a tree
structure, but not a BST but one where the hierarchy matches the
musical one > This means that assuming my current movement has 1000
measures, and an
average of five annotations per measure I wouldn't have one list of
5000 annotations but one of 1000 (to sort) and 1000 of five each.
And when I have 1000 measures where only 37 include 1-2 annotations
I'd have that list of 37 measures with sublists of 1-2 each.?
Yes. The tree-structure is for creating different views and for
directory lookup. If all annotations are fetched by an engraver it
might be OK to first collect them in one large list. And if you drop
them into a tree with the scheme of the desired view you don't need to
sort the list, but just the tree. If you already know the scheme of
the view while fetching the annotation events you can of course insert
the annotations immediatly in the tree. That insertion might be hidden
behind a method of an insert-collect-object. That way you can
interchange the implementation without touching the engraver ... and
perhaps I didn't study the ScholarLY code and that is already the case
;-)