gnu-emacs-sources
[Top][All Lists]
Advanced

[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 🙁]



reply via email to

[Prev in Thread] Current Thread [Next in Thread]