#+(and) "
P65 (**) Layout a binary tree (2)
    [p65]   

    An alternative layout method is depicted in the illustration
    opposite. Find out the rules and write the corresponding Prolog
    predicate. Hint: On a given level, the horizontal distance between
    neighboring nodes is constant.
   
    Use the same conventions as in problem P64 and test your predicate in an appropriate way.

"


;; The rule seems to be that the ordinate is the depth of the node,
;; and the abscissa of a node is offset from the parent by 2^height of the node.
;; 
;; The abscissa of the leftmost node is fixed to 1,
;; and the ordinate of the root is fixed to 1.
;; 
;; height of the tree = depth of node + height of node.


(load "p54a")



(defun binary-tree-count-leftmosts (tree)
  (if (binary-tree-empty-p tree)
      0
      (+ 1 (binary-tree-count-leftmosts (binary-tree-left tree)))))


(defun layout-node-p65 (node abscissa depth height)
  "
The abscissa of the NODE is given by ABSCISSA, and the ordinate by DEPTH.
The abscissa of the children is offset by (expt 2 height).
"
  (setf (layout-binary-tree-x node) abscissa
        (layout-binary-tree-y node) depth)
  (let* ((height-1 (1- height))
         (depth+1  (1+ depth))
         (offset   (expt 2 height-1)))
    (unless (binary-tree-empty-p (binary-tree-left node))
      (layout-node-p65 (binary-tree-left node)
                       (- abscissa offset)
                       depth+1
                       height-1))
    (unless (binary-tree-empty-p (binary-tree-right node))
      (layout-node-p65 (binary-tree-right node)
                       (+ abscissa offset)
                       depth+1
                       height-1)))
  node)


(defun layout-binary-tree-p65 (tree)
  (let ((height (binary-tree-height tree)))
    (layout-node-p65 (binary-tree-to-layout-binary-tree tree)
                     (1+ (- (expt 2 (1- height))
                            (expt 2 (- height (binary-tree-count-leftmosts tree)))))
                     1
                     (1- height))))


(assert (= 4 (binary-tree-count-leftmosts (construct '(n k c a e d g m u p q) (function string<)))))
(assert (= 5 (binary-tree-height          (construct '(n k c a e d g m u p q) (function string<)))))
(assert (equal (layout-binary-tree-p65    (construct '(n k c a e d g m u p q) (function string<)))
               '(N (K (C (A NIL NIL 1 4)
                       (E (D NIL NIL 4 5)
                          (G NIL NIL 6 5) 5 4) 3 3)
                    (M NIL NIL 11 3) 7 2)
                 (U (P NIL
                       (Q NIL NIL 21 4) 19 3)
                    NIL 23 2) 15 1)))


;; (list
;;  (draw-laid-out-tree (layout-binary-tree-p65 (complete-binary-tree 7)))
;;  (draw-laid-out-tree (layout-binary-tree-p65 (construct '(n k c a e d g m u p q)   (function string<))))
;;  (draw-laid-out-tree (layout-binary-tree-p65 (construct '(n k c a h g e m u p s q) (function string<)))))
;; 
;; (                                
;;         1                       
;;        / \                      
;;     2       3                   
;;    / \     / \                  
;;   4   5   6   7                 
;; 
;;                                                                                                  
;;                               N                                                                 
;;                              / \                                                                
;;               K                               U                                                 
;;              / \                             /                                                  
;;       C               M               P                                                         
;;      / \                               \                                                        
;;   A       E                               Q                                                     
;;          / \                                                                                    
;;         D   G                                                                                   
;; 
;;                                                                                                                                                                                          
;;                                                           N                                                                                                                             
;;                                                          / \                                                                                                                            
;;                           K                                                               U                                                                                             
;;                          / \                                                             /                                                                                              
;;           C                               M                               P                                                                                                             
;;          / \                                                               \                                                                                                            
;;   A               H                                                               S                                                                                                     
;;                  /                                                               /                                                                                                      
;;               G                                                               Q                                                                                                         
;;              /                                                                                                                                                                          
;;             E                                                                                                                                                                           
;; )

;;;; THE END ;;;;