Filter scala collection of objects with custom logic

Question

I need to filter a collection of objects (already sorted by, let's say, property A) removing items in which property B is out of order (marked in bold below): (Set of Tuples for simplicity)

case 1:

• input Seq((10, 10), (20, 20), (30, 36), (40, 30), (50, 40), (60, 50))
• expected output: Seq((10, 10), (20, 20), (30, 36), (50, 40), (60, 50))
• actual output: Seq((10,10), (20,20), (40,30), (50,40))

case 2:

• input: Seq((10, 10), (20, 20), (30, 36), (40, 40), (50, 30), (60, 50))
• expected output: Seq((10, 10), (20, 20), (30, 36), (40, 40), (60, 50))
• actual output: Seq((10,10), (20,20), (30,36), (50,30))

I'd appreciate any help.

This is what I have so far:

@RunWith(classOf[SpringRunner])
class OutOfOrderTest extends AnyWordSpec with Matchers with Debuggable {

  "OutOfOrderTest" should {

    def ooo(a: Seq[(Int, Int)]): Option[(Int, Int)] = {
      val x = a.head
      val y = a.tail.head
      if (x._2 <= y._2) Some(x) else None
    }

    "filter out of order simple" in {
      val bad = Seq((10, 10), (20, 20), (30, 36), (40, 30), (50, 40), (60, 50))

      val filtered = bad.sliding(2).collect { a =>
        ooo(a)
      }.filter(_.isDefined).map(_.get).toSeq
      filtered shouldEqual Seq((10, 10), (20, 20), (30, 36), (50, 40), (60, 50))
    }

    "filter out of order complex" in {
      val bad2 = Seq((10, 10), (20, 20), (30, 36), (40, 40), (50, 30), (60, 50))

      val filtered2 = bad2.sliding(2).collect { a =>
        ooo(a)
      }.filter(_.isDefined).map(_.get).toSeq
      filtered2 shouldEqual Seq((10, 10), (20, 20), (30, 36), (40, 40), (60, 50))
    }
  }
}

UPDATE 1

I'm using Sequences for performance (probably best to use Arrays, but I can deal with that later)

For simplicity I used Tuples here, but they are actually instances of a case class (Target) where 2 of the fields are represented by the tuple data.

Also this is one filter in a much bigger Spring-boot application, and I have to make a component out of it.

While there is no problem 'componentizing' (yes, we made that word up here in the office) the filter, the recursive function from @Luis will be hard to abstract as follows:

I'd like to test the three approaches as components So if I could I would mark the 3 answers as valid.

case class Target(rt: Double, ri: Double)

trait OutOfOrderRemover {
  def filter(targets: Seq[Target])
}

@Component
class RecurtsiveOOO extends OutOfOrderRemover {
  override def filter(targets: Seq[Target]): Seq[Target] = { }
}

Answer 1

IMHO, this is a perfect use case for tail-recursion.

def removeUnsortedElements[A, B](data: List[A])(orderBy: A => B)(implicit ev: Ordering[B]): List[A] = {
  import Ordering.Implicits._

  @annotation.tailrec
  def loop(remaining: List[A], previous: B, acc: List[A]): List[A] =
    remaining match {
      case a :: tail =>
        val next = orderBy(a)
        val newAcc =
          if (next >= previous) a :: acc
          else acc
        
        loop(
          remaining = tail,
          previous = next,
          acc = newAcc
        )
      
      case Nil =>
        acc.reverse
    }
  
  data match {
    case first :: tail =>
      loop(
        remaining = tail,
        previous = orderBy(first),
        acc = first :: Nil
      )
    
    case Nil =>
      Nil
  }
}

Which can be used like this:

val input1 = List((10, 10), (20, 20), (30, 36), (40, 30), (50, 40), (60, 50))
val output1 = removeUnsortedElements(input1)(_._2)
// output1: List[Int] = List((10,10), (20,20), (30,36), (50,40), (60,50))

val input2 = List((10, 10), (20, 20), (30, 36), (40, 40), (50, 30), (60, 50))
val output2 = removeUnsortedElements(input2)(_._2)
// output2: List[Int] = List((10,10), (20,20), (30,36), (40,40), (60,50))

---

You can see the code running here.

Answer 2

You can use foldLeft with empty collection accumulator, compare current value with accumulator head one, append current one if condition is met and then reverse the result:

val bad = ...
val filtered = bad.foldLeft(List.empty[(Int, Int)])((acc, t) => acc match {
    case head :: _ if head._2 > t._2 => acc
    case _ => t :: acc
  })
    .reverse

Answer 3

Here's my 2-cents.

This returns the desired results for both of the posted input examples.

input.head +: input.sliding(2).collect{
      case Seq((_,b1),(a2,b2)) if b1 <= b2 => (a2,b2)
    }.toSeq

Warning: Will throw if input is empty.