Plaster
New
List
Login
text
default
anonymous
2021.12.29 12:46:17
;;; "Common" indexes of both children are never equal because if they were ;;; then they would be already common in the parent. (defun merge-branches-1 (common-1 common-2 merged-1-min merged-1-max merged-2-min merged-2-max) ;; This index doesn't require merging - that should be tested above. (assert (or common-1 common-2 merged-1-min merged-2-min)) ;; Two leaf nodes without ranges to merge. (when (and (null merged-1-min) (null merged-2-min)) (return-from merge-branches-1 (if (or (null common-1) (null common-2)) ;; One branch requires equality, the other doesn't. (values nil nil) (case (- common-2 common-1) (+1 (values common-1 common-2)) (-1 (values common-2 common-1)) (otherwise (values nil nil)))))) ;; First attempt merging COMMON-X with provided ranges. Initially COMMON-1 ;; is not adjacent with MERGED-1, but after merging COMMON-2 it may change. (macrolet ((try-merge (common min max) `(when (and ,common ,min ;; ,max (implicit) (<= (1- ,min) ,common (1+ ,max))) (setf ,min (min ,min ,common) ,max (max ,max ,common) ,common nil) t))) (when (try-merge common-1 merged-2-min merged-2-max) (try-merge common-2 merged-2-min merged-2-max)) (when (try-merge common-2 merged-1-min merged-1-max) (try-merge common-1 merged-1-min merged-1-max))) ;; After attempting to merge commons with ranges if either exists then it is ;; a game over, we can't merge them: (when (or common-1 common-2) (return-from merge-branches-1 (values nil nil))) ;; What is left is an attempt to merge both ranges. (cond ((null merged-1-min) (values merged-2-min merged-2-max)) ((null merged-2-min) (values merged-1-min merged-1-max)) ((or (< merged-1-max (1- merged-2-min)) (< merged-2-max (1- merged-1-min)) (> merged-1-min (1+ merged-2-max)) (> merged-2-min (1+ merged-1-max))) (values nil nil)) (t (values (min merged-1-min merged-2-min) (max merged-1-max merged-2-max)))))
Raw
Annotate
Repaste
Edit