Anonymous user
Algebraic data types: Difference between revisions
→Emacs Lisp: Add Emacs Lisp
(Added Go) |
(→Emacs Lisp: Add Emacs Lisp) |
||
Line 484:
{5, 0, :b, {4, -3, :b, nil, nil}, {6, -1, :b, nil, {7, 0, :r, nil, nil}}}}
{:found, {4, -3}}
</pre>
=={{header|Emacs Lisp}}==
The <code>pcase</code> syntax was added in Emacs 24.
<lang lisp>
(defun balance (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 ,a ,x (R ,b ,y ,c)) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))
(`(B ,a ,x (R (R ,b ,y ,c) ,z ,d)) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))
(`(B ,a ,x (R ,b ,y (R ,c ,z ,d))) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))
(_ tree)))
(defun insert- (x s)
(pcase s
(`nil `(R nil ,x nil))
(`(,color ,a ,y ,b) (cond ((< x y)
(balance `(,color ,(insert- x a) ,y ,b)))
((> x y)
(balance `(,color ,a ,y ,(insert- x b))))
(t
s)))
(_ (error "Expected tree: %S" s))))
(defun insert (x s)
(pcase (insert- x s)
(`(,_ ,a ,y ,b) `(B ,a ,y ,b))
(_ (error "Internal error: %S" s))))
(let ((s nil))
(dotimes (i 16)
(setq s (insert (1+ i) s)))
(pp s))
</lang>
Output:
<pre>
(B
(B
(B
(B nil 1 nil)
2
(B nil 3 nil))
4
(B
(B nil 5 nil)
6
(B nil 7 nil)))
8
(B
(B
(B nil 9 nil)
10
(B nil 11 nil))
12
(B
(B nil 13 nil)
14
(B nil 15
(R nil 16 nil)))))
</pre>
| |||