Scala: Splitting Lists into multiple parts

I have simplified the types a bit, the code just illustrates the concept. The performance is probably better without the toList conversion.

type MyTuple = (String, Int)

val sorted: List[MyTuple] = List(
    ("a", 1),
    ("a", 2),
    ("a", 3),
    ("b", 7),
    ("b", 9),
    ("c", 13),
    ("c", 15),
    ("c", 16)
)

def test(a: MyTuple, b: MyTuple): Boolean = b._2 - a._2 > 3

// We prepend the head so that the first sliding pair will have distance 0
val lists = (sorted.head :: sorted)
  .sliding(2)
  .map { case List(a, b) => (b, test(a, b)) }
  .toList

def split(list: List[(MyTuple, Boolean)]): List[List[MyTuple]] = list match {
  case Nil => Nil
  case head :: tail => {
    val (l1, l2) = tail.span(!_._2)
    (head :: l1).map(_._1) :: split(l2)
  }
}

val splitLists = split(lists).map(_.map(_._1))
println(splitLists.mkString("\n"))

Output:

List(a, a, a)
List(b, b)
List(c, c, c)

For convenience, I've substitued Ints for Dates, but the prinicpal is the same.

   val data = List(
      ("a","a", 10),
      ("a","b", 30),
      ("a","b", 11),
      ("a","b", 33),
      ("s","c", 37),
      ("a","c", 26),
      ("a","d", 22),
      ("m","a", 18),
      ("t","a", 15)
    )
    val sortedData = data.sortWith ((a,b)=> a._3 < b._3)
    println(s"$sortedData")
    val splitPass = sortedData.foldLeft(List[(String, String,Int)](), List[List[(String, String,Int)]](), sortedData.head._3){
      case ((cl, acc, ld),nt) =>
        if (nt._3-ld>3)
          (List(nt), cl.reverse ::acc, nt._3)
        else
          (nt:: cl, acc, nt._3)
    }
    val (fl, fa, _) = splitPass
    val res = (if (fl.isEmpty) fa else fl :: fa).reverse
    println(s"$res")

This gives the sorted list:

List((a,a,10), (a,b,11), (t,a,15), (m,a,18), (a,d,22), (a,c,26), (a,b,30), (a,b,33), (s,c,37))

and the result list:

List(List((a,a,10), (a,b,11)), List((t,a,15), (m,a,18)), List((a,d,22)), List((a,c,26)), List((a,b,30), (a,b,33)), List((s,c,37)))

What this does is a single pass through the sorted list, building an accumulator consisting of (List of items in the current group, List of completed groups, Int[Date] of last added item). This is seeded with two empty lists and the Date of the first item in the list.

For each item in the source list, if it's close to the previous one, it gets added to the Current group, if it's far from the previous item, the current group is closed and added to the completed gorups list, and the current item becoes the first item in a new list, and the current item's date becomes the reference date for the next check. If you wanted to break where the date was different to far from the earliest in the current group, it is easy to change the else branch to pass ld instead of nt._3.

At the end, you need to add any uncompleted group to the final collection of groups.

The two '.reverse's are necessary because the lists are, in the typcial functional style, built backwards (becuase it's cheaper that way) and reversed at completion.

Here is a very clean linear-time (single-pass) approach:

type Date = Int  // For simplicity in the example

val sorted: List[(String,String,Date)] = List(("a1", "b1", 1),
                                              ("a1", "b1", 2),
                                              ("a1", "b1", 6),
                                              ("a1", "b1", 8),
                                              ("a1", "b1", 10),
                                              ("a1", "b1", 15),
                                              ("a1", "b1", 16))

val result = sorted.sliding(2).foldLeft(Vector(Vector(sorted.head))) { 
  case (z, List(t1, t2)) => 
    if (t2._3 - t1._3 > 3) z :+ Vector(t2)
    else                   z.init :+ (z.last :+ t2)
}

result.foreach(println)
// Vector((a1,b1,1), (a1,b1,2))
// Vector((a1,b1,6), (a1,b1,8), (a1,b1,10))
// Vector((a1,b1,15), (a1,b1,16))

You can handle the special cases where sorted.length() < 2 separately.