Identify Continuous Intervals in a Scala Sequence

Question

Assume that I have a Sequence of joda time intervals:

Seq(
  Interval(00, 01),
  Interval(01, 02),
  Interval(02, 04),
  Interval(04, 06),
  Interval(07, 09), // continuous sequence is broken
  Interval(09, 10),
  Interval(11, 14), // continuous sequence is broken
  Interval(15, 20), // continuous sequence is broken
  Interval(20, 24)
)

I want to go over this Sequence and get back a Seq[Seq[Interval]] that gives me the continuous Sequences and non continuous Sequences like:

Seq(
 Seq(Interval(00,01),Interval(01,02),Interval(02,04)Interval(04,06)),
 Seq(Interval(07,09),Interval(09,10)),
 Seq(Interval(11,14)),
 Seq(Interval(15,20),Interval(20,24))
)

I did come up with some recursion, but it just cuts off after it finds one non continuous interval! Any clues?

Answer 1

I believe this is a candidate for foldLeft. Iterate over the intervals building the required structure as you go. I find it easier to add new items to the head of the seq, hence the use of reverse at the end:

case class Interval(a: Int, b: Int)

val intervals = Seq(
    Interval(0, 1),
    Interval(1, 2),
    Interval(2, 4),
    Interval(4, 6),
    Interval(7, 9), // continuous sequence is broken
    Interval(9, 10),
    Interval(11, 14), // continuous sequence is broken
    Interval(15, 20), // continuous sequence is broken
    Interval(20, 24)
)

intervals.foldLeft(Seq[Seq[Interval]]()){(acc, i) => 
    if(acc.isEmpty){
        Seq(Seq(i))
    }else {
        if(acc.head.head.b == i.a) {
            (i +: acc.head) +: acc.tail
        } else {
            Seq(i) +: acc
        }
    }
}.map(_.reverse).reverse.foreach(println)

Produces:

List(Interval(0,1), Interval(1,2), Interval(2,4), Interval(4,6))
List(Interval(7,9), Interval(9,10))
List(Interval(11,14))
List(Interval(15,20), Interval(20,24))

EDIT:

alternative using pattern matching:

intervals.foldLeft(Seq[Seq[Interval]]()){
    case (Seq(Seq()), i) => Seq(Seq(i))
    case (h :: tail, i) if h.head.b == i.a => (i +: h) +: tail
    case (acc, i) => Seq(i) +: acc
}.map(_.reverse).reverse.foreach(println)

Answer 2

I would recommend using foldLeft and Vectors to accumulate the result. Because i find it a bit more readable appending the values instead of prepending and then reversing everything:

val testData = Seq(
  new Interval(0L, 1L),
  new Interval(1L, 2L),
  new Interval(2L, 4L),
  new Interval(4L, 6L),
  new Interval(7L, 9L), // continuous sequence is broken
  new Interval(9L, 10L),
  new Interval(11L, 14L), // continuous sequence is broken
  new Interval(15L, 20L), // continuous sequence is broken
  new Interval(20L, 24L)
)

val resultVector = testData.foldLeft(Vector.empty[Vector[Interval]]) {
  case (Vector(), current) => 
      Vector(Vector(current))
    case (init :+ last, current) if last.last.getEndMillis == current.getStartMillis =>
      init :+ (last :+ current)
    case (result, current) =>
      result :+ Vector(current)
}

To make the result more readable I added this:

val readable = resultVector.map(_.map(interv => s"(${interv.getStartMillis} -> ${interv.getEndMillis})")).mkString("\n")

And the output is:

readable: String = Vector((0 -> 1), (1 -> 2), (2 -> 4), (4 -> 6))
  Vector((7 -> 9), (9 -> 10))
  Vector((11 -> 14))
  Vector((15 -> 20), (20 -> 24))