Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

llrb-syntax

A syntax-rules macro expanding into left-leaning red-black tree code. Pure and mutating versions.

Overview

A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations. [wikipedia].

The macro is independent of data structures used to implement nodes of the trees. Users must pass accessors and a syntax or procedure to update an existing node (for the mutating version) respectively create a fresh node as well as names for the procedures to be defined.

Examples

See the llrb-tree egg.

API

   define-llrbtree/positional
   (FEATURES)
   UPDATE
   init-root-node!		;; defined
   t-lookup		;; defined
   t-min			;; defined
   t-fold			;; defined
   t-for-each		;; defined
   t-insert		;; defined
   t-delete		;; defined
   t-delete-min		;; defined
   t-empty?		;; defined

   ;; These syntax is used expand to code for comparision
   ;; expressions.
   t-k-eq?			;; key<>node-key "equal"
   t-eq?			;; node-key<>node-key "equal"
   t-k-<?			;; key<>node-key "less then"
   t-<?			;; node<>node "less then"
   ;; Accessors to the elements of the tree.
   left
   right
   color

</syntax>

FEATURES: {ordered, pure, leftmost} – configures the generated code.

UPDATE

The "update*" syntax must accept a node structure and key-value pairs. Keys are color:, left: and right:

"update" : If feature "pure" is set, "update" must expand to a newly allocated node, otherwise is MUST expand to a side effect full update of the original node.