[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNU ELPA] Rbit version 0.1
From: |
ELPA update |
Subject: |
[GNU ELPA] Rbit version 0.1 |
Date: |
Sun, 31 Mar 2024 05:51:58 -0400 |
Version 0.1 of package Rbit has just been released in GNU ELPA.
You can now find it in M-x list-packages RET.
Rbit describes itself as:
===================================
Red-black persistent interval trees
===================================
More at https://elpa.gnu.org/packages/rbit.html
## Summary:
Self-balancing interval trees (for non-overlapping intervals, i.e.
similar to Emacs's text-properties (rather than overlays), but not
linked to any kind of buffer nor string).
Following Chris Okasaki's algorithm from
"Red-black trees in a functional setting", JFP'99.
https://dl.acm.org/citation.cfm?id=968578.968583&coll=DL&dl=GUIDE
The above article presents an elegant functional/persistent implementation
of insertion in red-black trees. Here we have interval trees instead, so
it's a bit different and we support additional operations. Those extensions
aren't nearly as well thought out as Chris's algorithm, so they actually
don't guarantee we preserve the 2 invariants of red-black trees :-(
In practice, they should still usually give reasonably good algorithmic
properties, hopefully.
## Recent NEWS:
[Not provided 🙁]
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNU ELPA] Rbit version 0.1,
ELPA update <=