let find_regions ?(max_gap=0) pred tal =
  if any_overlap (List.map ~f:fst tal) then
    failwith "overlapping ranges not allowed"
  ;
  let tal = List.sort tal ~cmp:(fun (u,_) (v,_) ->
    match compare_positional u v with
    | Some x -> x
    | None -> assert false
  ) in

  (* see below for meaning of [curr] *)
  let insert (curr : (t * int) option) ans =
    match curr with
    | None -> ans
    | Some (v,gap) ->
      let x = v.lo in
      let y = v.hi - gap in
      if x <= y then
        {lo=x; hi=y}::ans
      else
        failwithf "gap = %d, range = %s" gap (to_string v) () in

  (* curr = Some (v,gap) means [v] is region built up thus far,
   *        with last [gap] elements failing pred, [0 <= gap <= max_gap].
   * curr = None means no region currently being built *)
  let rec loop (curr : (t * int) option) ans tal =
    match tal with
    | [] -> insert curr ans
    | (t,a)::tal ->
      match curr with
      | None ->
        let curr = if pred a then Some(t,0) else None in
        loop curr ans tal
      | Some (curr_v, curr_gap) ->
        let extra_gap = t.lo - curr_v.hi - 1 in
        let t,pred,tal =
          if extra_gap > 0 then
            {lo=(curr_v.hi + 1); hi=(t.lo - 1)}, false, ((t,a)::tal)
          else
            t, pred a, tal
        in
        let curr_v = {lo=curr_v.lo; hi=t.hi} in
        let curr_gap = if pred then 0 else size t + curr_gap in
        let curr = Some (curr_v, curr_gap) in
        if curr_gap > max_gap
        then loop None (insert curr ans) tal
        else loop curr ans tal
  in
  List.rev (loop None [] tal)