Advertisement
Guest User

Untitled

a guest
Sep 25th, 2018
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.40 KB | None | 0 0
  1. (defun make-tree (depth)
  2. (make-array (- (expt 2 depth) 1)))
  3.  
  4. (defun root (tree)
  5. (cons 0 tree))
  6.  
  7.  
  8. (defun index-of-level (l) (- (expt 2 l) 1))
  9. (defun width-of-level (l) (expt 2 l))
  10. (defun level-of-node (n) (truncate (log (+ n 1) 2)))
  11. (defun offset-of-node (n) (- n (index-of-level (level-of-node n))))
  12.  
  13. (defun print-examples ()
  14. (loop for n below 32 do (format t "~3D ~3D ~3D ~3D ~3D~%"
  15. n
  16. (offset-of-node n)
  17. (level-of-node n)
  18. (index-of-level (level-of-node n))
  19. (width-of-level (level-of-node n)))))
  20.  
  21.  
  22. (defun (setf data) (new-data node) (setf (aref (cdr node) (car node)) new-data))
  23. (defun data (node) (aref (cdr node) (car node)))
  24. (defun child (node child) (+ child (* 2 (offset-of-node node)) (index-of-level (+ 1 (level-of-node node)))))
  25. (defun left (node) (cons (child (car node) 0) (cdr node)))
  26. (defun right (node) (cons (child (car node) 1) (cdr node)))
  27.  
  28. (let* ((tree (make-tree 3))
  29. (root (root tree)))
  30. (setf (data (left (left root))) 0
  31. (data (left root)) 1
  32. (data (right (left root))) 2
  33. (data root) 3
  34. (data (left (right root))) 4
  35. (data (right root)) 5
  36. (data (right (right root))) 6)
  37. tree)
  38.  
  39. --> #(3 1 5 0 2 4 6)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement