Golomb forests

gistfile1.cl

(defun fullness. (tree size)
  (cond ((null. size)
	 '(1))
	((null. (cdr tree))
	     (fullness. (car tree) (minus1. size)))
	('t (+. (ash+. '(1) (minus1. size))  (fullness. (cdr tree) (minus1. size))))))

(defun length. (glf size)
  (cond ((null. glf) '())
	((or. (null. (cdr glf))
	     (eq 'sen2 (cdr glf)))
	 (minus1. (+. (ash+. '(1) size)
		     (+. (fullness. (car glf) size)
			 (cond ((eq '() (cdr glf))
				'())
			       ('t '(1)))))))
	('t (length. (cdr glf) (plus1. size)))))

(defun tree-nth. (number tree size)
  (cond ((null. size)
	 tree)
	((>. (ash+. '(1) (minus1. size)) number)
	 (tree-nth. number (car tree) (minus1. size)))
	('t (tree-nth. (-. number (ash+. '(1) (minus1. size))) (cdr tree) (minus1. size)))))

(defun g-nth. (x glf size)
  (cond ((>. (minus1. (ash+. '(0 1) size)) x)
	 (tree-nth. (-. x (minus1. (ash+. '(1) size))) (car glf) size))
	('t (g-nth. x (cdr glf) (plus1. size)))))

(defun tree-add. (elt tree size number)
  (cond ((null. size)
	 elt)
	((>. (ash+. '(1) (minus1. size)) number)
	 (cons (tree-add. elt (car tree) (minus1. size) number) '()))
	('t (cons (car tree) (tree-add. elt (cdr tree) (minus1. size) (-. number (ash+. '(1) (minus1. size))))))))

(defun sentinel-change. (glf)
  (cond ((null. (cdr glf))
	 (cons (car glf) 'sen2))
	('t (cons (car glf) (sentinel-change. (cdr glf))))))

(defun g-add. (elt glf size number)
  (cond ((eq 'sen2 glf)
	 (cons (tree-add. elt '() size '()) '()))
	((and. (eq '0 (car number)) (null. elt))
	 (sentinel-change. glf))
	((>. (-. (ash+. '(0 1) size) '(1)) number)
	 (cons (tree-add. elt (car glf) size (-. number (-. (ash+. '(1) size) '(1)))) '()))
	('t (cons (car glf) (g-add. elt (cdr glf) (plus1. size) number)))))