2

Given a list of cons cells, what is an efficient way to merge overlapping ranges?

When any values minimum or maximum are within the bounds (inclusive) of any of the other cons cells in the list, these should be merged until there are no more cells to merge.

Either into a new list or destructively modifying the list.

(merge-overlapping-ranges nil) => nil
(merge-overlapping-ranges '((0 . 1))) => '((0 . 1))
(merge-overlapping-ranges '((0 . 5) (6 . 9))) => '((0 . 5) (6 . 9))
(merge-overlapping-ranges '((0 . 5) (5 . 9))) => '((0 . 9))
(merge-overlapping-ranges '((5 . 9) (0 . 5))) => '((0 . 9))
(merge-overlapping-ranges '((1 . 9) (3 . 8))) => ((1 . 9))
(merge-overlapping-ranges '((0 . 9) (0 . 9))) => ((0 . 9))
(merge-overlapping-ranges
 '((1 . 2) (3 . 4) (5 . 6) (7 . 8) (1 . 100))) => '((1 . 100))
3
  • I know this is a rhetorical question since you answered it as soon as you asked it, but you should expand the question to at least provide a minimal but non-trivial example of the list you are talking about and what the result should be, since (IIUC) the answer does not apply to any old list. How do you expect a future visitor to figure out if the answer applies to their problem? Alternatively, how would you expect somebody else (other than you) to answer the question based just on the description above? I, for one, would not be able to answer it without further clarification.
    – NickD
    Sep 30 at 20:26
  • In particular, specifying the behavior in corner cases should be part of the question.
    – NickD
    Sep 30 at 20:27
  • Thanks for the feedback, updated the question.
    – ideasman42
    Oct 2 at 10:19
2

This is a function to merge overlapping ranges, although it's possible there is a more efficient way to do this.

(defun merge-overlapping-ranges (ranges)
  "Destructively modify and return RANGES with overlapping values removed.

Where RANGES is an unordered list of (min . max) cons cells."
  (cond
   ((cdr ranges)
    ;; Simple < sorting of cons cells.
    (setq ranges (sort ranges (lambda (x y)
                                (or (< (car x) (car y))
                                    (and (= (car x) (car y))
                                         (< (cdr x) (cdr y)))))))
    ;; Step over `ranges', de-duplicating & adjusting elements as needed.
    (let ((ranges-iter ranges)
          (ranges-next (cdr ranges)))
      (while ranges-next
        (let ((head (car ranges-iter))
              (next (car ranges-next)))
          (cond
           ((< (cdr head) (car next))
            (setq ranges-iter ranges-next)
            (setq ranges-next (cdr ranges-next)))
           (t
            (when (< (cdr head) (cdr next))
              (setcdr head (cdr next)))
            (setq ranges-next (cdr ranges-next))
            (setcdr ranges-iter ranges-next)))))
      ranges))

   (t ;; No need for complex logic single/empty lists.
    ranges)))

(defun test-merge-ranges (args)
  (princ (format "(merge-overlapping-ranges %s) => %S\n"
         (format "%S" args) (merge-overlapping-ranges args)
         #'external-debugging-output)))

(test-merge-ranges nil)
(test-merge-ranges '((0 . 1)))
(test-merge-ranges '((0 . 5) (6 . 9)))
(test-merge-ranges '((0 . 5) (5 . 9)))
(test-merge-ranges '((5 . 9) (0 . 5)))
(test-merge-ranges '((1 . 9) (3 . 8)))
(test-merge-ranges '((1 . 9) (3 . 8)))
(test-merge-ranges '((0 . 9) (0 . 9)))
(test-merge-ranges '((1 . 2) (3 . 4) (5 . 6) (7 . 8) (1 . 100)))

When run as a script produces: emacs --script merge-overlapping-ranges.el

(merge-overlapping-ranges nil) => nil
(merge-overlapping-ranges ((0 . 1))) => ((0 . 1))
(merge-overlapping-ranges ((0 . 5) (6 . 9))) => ((0 . 5) (6 . 9))
(merge-overlapping-ranges ((0 . 5) (5 . 9))) => ((0 . 9))
(merge-overlapping-ranges ((5 . 9) (0 . 5))) => ((0 . 9))
(merge-overlapping-ranges ((1 . 9) (3 . 8))) => ((1 . 9))
(merge-overlapping-ranges ((0 . 9) (0 . 9))) => ((0 . 9))
(merge-overlapping-ranges ((1 . 2) (3 . 4) (5 . 6) (7 . 8) (1 . 100))) => ((1 . 100))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.