tree.lisp

(defun subpennant-sym (i) (intern (format nil "subpennant-~D" i)))
(defun pennant-type-name (ty i) (intern (format nil "pennant-type-~D" i)))
(defmacro def-pennant (ty n)
  "A pennant is a balanced tree of depth N. (def-pennant 5 integer) expands to


; ... define pennant-type-{0..4}
(struct pennant-type-5
  (node :type integer)
  (subpennant-0 :type pennant-type-0)
  (subpennant-1 :type pennant-type-1)
  (subpennant-2 :type pennant-type-2)
  (subpennant-3 :type pennant-type-3)
  (subpennant-4 :type pennant-type-4))"

  (when (>= n 0)
    `(progn
      (def-pennant ,ty ,(- n 1))
      (defstruct ,(pennant-type-name ty n)
         (node nil :type ,ty)
         ,@(loop for i to n
                 collect `(,(subpennant-sym i) nil :type ,(pennant-type-name ty i)))))))

(def-pennant fixnum 4)