tijlleenders / ZinZen-scheduler

The calendar engine for the ZinZen web app.
https://github.com/tijlleenders/ZinZen
GNU Affero General Public License v3.0
10 stars 4 forks source link

Use a maple tree inspired data structure for the Calendar #469

Open tijlleenders opened 1 month ago

tijlleenders commented 1 month ago

Is your feature request related to a problem? Please describe. I'm always frustrated when:

Resolving this issue would also allow for #394 while maintaining/improving performance.

Describe the solution you'd like Make Calendar data storage and finding/counting of Slots more efficient by using ranges.
There have been thoughts about this (using ranges in a B-Tree or adapting interval tree) - but so far I've never encountered an example of an implementation specifically designed for storing non-overlapping ranges and the gaps in between. Maple Tree seems to fit. Linking to that via FFI or more likely rewriting it in Rust (as a separate Rust crate so others can use it too) could be a solution. The ZinZen use case, unlike Linux, is single-user - and can be optimized differently. Also, it needs to store information on the number of claims per null range - and which activity claimed wich range.

Describe alternatives you've considered

Additional context lib/maple_tree.c
lib/test_maple_tree.c