You are looking at historical revision 39572 of this page. It may differ significantly from its current revision.

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.

• egg

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

<syntax>

   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.