(defpackage :fwoar.binary-tree
  (:use :cl )
  (:export ))
(in-package :fwoar.binary-tree)

(fw.lu:defclass+ bt ()
  ((left :initarg :left :accessor left)
   (value :initarg :value :accessor value)
   (right :initarg :right :accessor right)))
(defmethod print-object ((o bt) s)
  (format s "[~s < ~s > ~s]"
          (left o)
          (value o)
          (right o)))

(defgeneric visit (client tree))
(defun visit-in-order (client tree)
  (let ((left (left tree))
        (right (right tree)))
    (when left
      (visit-in-order client (left tree)))
    (visit client tree)
    (when right
      (visit-in-order client (right tree))))
  tree)

(fw.lu:defclass+ counter ()
  ((value :initform 0 :accessor value)))
(defmethod visit ((client counter) tree)
  (setf (value tree)
        (value client))
  (incf (value client)))

(fw.lu:defclass+ stragglers ()
  ((elts :initarg :elts :accessor elts)))
(defmethod visit ((client stragglers) tree)
  (declare (optimize (debug 3)))
  (fw.lu:with-accessors* (elts) client
    (when (and elts (null (left tree)))
      (let ((n-l (pop elts))
            (n-r (pop elts)))
        (setf (left tree) (bt nil n-l nil))
        (when n-r
          (setf (right tree) (bt nil n-r nil)))))))

(defmethod visit ((client (eql :print)) tree)
  (fresh-line)
  (prin1 (value tree))
  (princ #\tab)
  (prin1 tree)
  (terpri))

(defun dense-tree (levels cur)
  (if (null cur)
      (let ((layer (loop repeat (expt 2 (1- levels)) collect (bt nil nil nil))))
        (dense-tree (1- levels)
                    layer))
      (if (> levels 0)
          (dense-tree (1- levels)
                      (loop for (l r) on cur by #'cddr
                            collect (bt l nil r)))
          (car cur))))

(defun complete-bt-of-size (n)
  (let* ((l2_n (log n 2))
         (height (ceiling l2_n))
         (max-node-count (1- (expt 2 height)))
         (full-bt-size (1- (expt 2 (1- height))))
         (leftovers (- n full-bt-size)))
    (values height max-node-count full-bt-size leftovers)))