| 1 |
;;; |
| 2 |
;;; rbtree.scm - Red-Black Tree |
| 3 |
;;; |
| 4 |
|
| 5 |
;; Red-black tree is now provided as a builtin <tree-map> object. |
| 6 |
;; This module is for backward compatibility. |
| 7 |
|
| 8 |
(define-module util.rbtree |
| 9 |
(use gauche.sequence) |
| 10 |
(export <rbtree> make-rbtree rbtree? |
| 11 |
rbtree-get rbtree-put! rbtree-delete! |
| 12 |
rbtree-exists? rbtree-empty? |
| 13 |
rbtree-push! rbtree-pop! rbtree-update! |
| 14 |
rbtree-min rbtree-max |
| 15 |
rbtree-extract-min! rbtree-extract-max! |
| 16 |
rbtree-copy rbtree-num-entries |
| 17 |
rbtree-keys rbtree-values |
| 18 |
rbtree-fold rbtree-fold-right |
| 19 |
rbtree->alist alist->rbtree |
| 20 |
) |
| 21 |
) |
| 22 |
(select-module util.rbtree) |
| 23 |
|
| 24 |
(define <rbtree> <tree-map>) |
| 25 |
(define make-rbtree make-tree-map) |
| 26 |
(define rbtree? tree-map?) |
| 27 |
(define rbtree-get tree-map-get) |
| 28 |
(define rbtree-put! tree-map-put!) |
| 29 |
(define rbtree-delete! tree-map-delete!) |
| 30 |
(define rbtree-exists? tree-map-exists?) |
| 31 |
(define rbtree-empty? tree-map-empty?) |
| 32 |
(define rbtree-push! tree-map-push!) |
| 33 |
(define rbtree-pop! tree-map-pop!) |
| 34 |
(define rbtree-update! tree-map-update!) |
| 35 |
(define rbtree-num-entries tree-map-num-entries) |
| 36 |
(define rbtree->alist tree-map->alist) |
| 37 |
(define alist->rbtree alist->tree-map) |
| 38 |
(define rbtree-keys tree-map-keys) |
| 39 |
(define rbtree-values tree-map-values) |
| 40 |
|
| 41 |
(define (rbtree-min tree . args) |
| 42 |
(or (tree-map-min tree) |
| 43 |
(get-optional args (error "tree is empty:" tree)))) |
| 44 |
(define (rbtree-max tree . args) |
| 45 |
(or (tree-map-max tree) |
| 46 |
(get-optional args (error "tree is empty:" tree)))) |
| 47 |
(define (rbtree-extract-min! tree . args) |
| 48 |
(or (tree-map-pop-min! tree) |
| 49 |
(get-optional args (error "tree is empty:" tree)))) |
| 50 |
(define (rbtree-extract-max! tree . args) |
| 51 |
(or (tree-map-pop-max! tree) |
| 52 |
(get-optional args (error "tree is empty:" tree)))) |
| 53 |
|
| 54 |
(define rbtree-copy tree-map-copy) |
| 55 |
(define rbtree-fold tree-map-fold) |
| 56 |
(define rbtree-fold-right tree-map-fold-right) |
| 57 |
|
| 58 |
(define rbtree-check (with-module gauche.internal %tree-map-check-consistency)) |