Coalesce a list of overlapping and adjacent start/end tuples.

coalesce.ml

open Core.Std

(**
 * Coalesce a list of overlapping and adjacent start/end tuples.
 *
 * let ranges = [(2,3); (1,2); (5,11); (4,10); (3,3)];;
 * coalesce_ranges ranges;;
 * - : (int * int) list = [(1, 11)]
 **)
let coalesce_ranges ?(cmp=compare) ranges = 
  let sorted = List.sort cmp ranges in
  let coalesce' acc r = 
    match acc, r with
    | [], _ -> [r]
    | (a,b) :: tl, (x,y) ->
        if (b + 1) >= x then (a, max b y) :: tl
        else r :: acc
  in
  List.fold_left ~f:coalesce' ~init:[] sorted
;;