Filter scala collection of objects with custom logic-CodePudding

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))
    }
  }
}

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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