|
From: | Urs Liska |
Subject: | Binary Search Tree in Scheme |
Date: | Mon, 18 Jun 2018 10:18:00 +0200 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 |
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:
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:
Thanks |
[Prev in Thread] | Current Thread | [Next in Thread] |