Algebraic data types: Difference between revisions
Content added Content deleted
(→Emacs Lisp: Add Emacs Lisp) |
(→Emacs Lisp: Use rbt- namespace) |
||
| Line 491: | Line 491: | ||
<lang lisp> |
<lang lisp> |
||
(defun balance (tree) |
(defun rbt-balance (tree) |
||
(pcase tree |
(pcase tree |
||
(`(B (R (R ,a ,x ,b) ,y ,c) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d))) |
(`(B (R (R ,a ,x ,b) ,y ,c) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d))) |
||
| Line 499: | Line 499: | ||
(_ tree))) |
(_ tree))) |
||
(defun insert- (x s) |
(defun rbt-insert- (x s) |
||
(pcase s |
(pcase s |
||
(`nil `(R nil ,x nil)) |
(`nil `(R nil ,x nil)) |
||
(`(,color ,a ,y ,b) (cond ((< x y) |
(`(,color ,a ,y ,b) (cond ((< x y) |
||
(balance `(,color ,(insert- x a) ,y ,b))) |
(rbt-balance `(,color ,(rbt-insert- x a) ,y ,b))) |
||
((> x y) |
((> x y) |
||
(balance `(,color ,a ,y ,(insert- x b)))) |
(rbt-balance `(,color ,a ,y ,(rbt-insert- x b)))) |
||
(t |
(t |
||
s))) |
s))) |
||
(_ (error "Expected tree: %S" s)))) |
(_ (error "Expected tree: %S" s)))) |
||
(defun insert (x s) |
(defun rbt-insert (x s) |
||
(pcase (insert- x s) |
(pcase (rbt-insert- x s) |
||
(`(,_ ,a ,y ,b) `(B ,a ,y ,b)) |
(`(,_ ,a ,y ,b) `(B ,a ,y ,b)) |
||
(_ (error "Internal error: %S" s)))) |
(_ (error "Internal error: %S" s)))) |
||
| Line 517: | Line 517: | ||
(let ((s nil)) |
(let ((s nil)) |
||
(dotimes (i 16) |
(dotimes (i 16) |
||
(setq s (insert (1+ i) s))) |
(setq s (rbt-insert (1+ i) s))) |
||
(pp s)) |
(pp s)) |
||
</lang> |
</lang> |
||