Debian Codegraph @

lib/util/rbtree.scm

raw
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))