Inserting missing values into a list

Question

Let's say we have a list of ranges associated with some value, say a List[(Int, Int, Foo)]. The ranges are guaranteed to be disjoint, and thus will never overlap. The ranges do not cover the full range of a given string. I want to associate each Foo with some part of the string, so that the string can be split into sections of (String, Option[Foo]).

My idea is to convert this List[(Int, Int, Foo)] into a List[(Int, Int, Option[Foo])] such that every missing range is filled in and associated with a None. This new list can then be mapped over to associate each Foo with some part of the string.

Some concrete code

case class Foo(i: Int)
val str = "a" * 99 // A random string of length 99
val input = List((5, 10, Foo(1)), (56, 60, Foo(2))
// ???
val filledInValues = List(
  (0, 4, None),
  (5, 10, Some(Foo(1))),
  (11, 55, None),
  (56, 60, Some(Foo(2))),
  (61, 98, None)
)
val res = filledInValues map { case (start, end, f) =>
  (str.substring(start, end), f)
}

How should I get from input to filledInValues, or from input to res?

Answer 1

This one was fun.

case class Foo(x:Int)

val xs = List((5, 10, Foo(1)), (56, 60, Foo(2)))
val str = "a" * 99 // A random string of length 99

// change the Foo to Option[Foo]. We do this now so we can use None
// in the sentinels we're about to add.

val ys = xs.map{case(a,b,c) => (a, b, Option(c))}

// Add dummy/sentinel elements to start and end
val zs = (-1, -1, None:Option[Foo])::(ys:+ ((str.length, str.length, None:Option[Foo])))

// Now take each pair and if there's a gap, use the first, then  a (n, m, None) element
// if no gap, just the first of the pair
zs.sliding(2).flatMap{
  case List(a,b) => 
    if (a._2+1 != b._1)
         List(a, (a._2 + 1, b._1 -1, None:Option[Foo]))
    else
         List(a)
  }.toList.tail
// and drop the dummy element from the beginning
// Note because we never return the second of the pair, the end sentinel 
// value gets discarded automatically

 //> res0:= List((0,4,None),
                 (5,10,Some(Foo(1))),
                 (11,55,None),
                 (56,60,Some(Foo(2))),
                 (61,98,None))