CODEWITHSUNDEEP
scala
Johnny Everson
Johnny Everson

Reputation: 8601

How to find element based on different priority conditions?

How would be an elegant Scala solution to find an element that matches any of a group of conditions, but each condition having different priorities?

case class A(p1:Int, p2:Int)

List(A(2,3), A(4,4), A(3,5))

Say I want to query: find a item that p1 == p2, if you don't find it, give me item with p2 > p1 , if you don't find it, give the p1 = square(p2) and so on. Always => Bool

My first guess is a recursive find function that tries one condition each loop, but I would like to know if there is better/simpler ways to do that.

Ideally, if the item matches more conditions it should be selected, but still respecting conditions priority.

Upvotes: 1

Views: 512

Answers (3)

Régis Jean-Gilles
Régis Jean-Gilles

Reputation: 32719

l.find{x => x.p1 == x.p2}.getOrElse(l.maxBy(_.p2))

UPDATE: in your updated question you say "give me item with biggest p2, if you don't find it, give the lowest p1 and so on". But there is always a biggest value, by definition (unless the list is empty, but I gather the list can't be empty). So this is really just "give me item with biggest p2" (hence the above solution).

UPDATE 2: so the question changed again, and is now "find a item that p1 == p2, if you don't find it, give me item with p2 > p1 , if you don't find it, give the p1 = square(p2) and so on". I guess you really need a generic solution after all. So here's my take:

// The list of predicates, in order of priority 
// (you can add/remove predicates as you see fit)
val predicates = List[A => Boolean]( 
  x => x.p1 == x.p2, 
  x => x.p2 > x.p1, 
  x => x.p1 ==  x.p2*x.p2
)

val indexedPredicates = predicates.reverse.zipWithIndex
def score( x: A ): Option[Int] = indexedPredicates.find(_._1(x)).map(_._2)
def priorityFind( l: List[A] ): A = l.maxBy(score)

The idea is that you attribute a score to each element: None if the element does not match any predicate, Some(0) if it matches the last predicate, Some(1) if it matches the last but one predicate, and so on. Then you just take the one with the highest score (None is "smaller" than any Some instance, so this is consistent with what we want).

If you want to handle properly the case where no element matches any predicate, you would change priorityFind like this:

def priorityFind( l: List[A] ): Option[A] = {
  val filtered = l.view.flatMap{x => score(x).map(x -> _) }
  if ( filtered.isEmpty ) None
  else Some( filtered.maxBy(_._2)._1 )
}

Upvotes: 6

Felix
Felix

Reputation: 8495

Okay, I came up with this:

case class A(p1:Int, p2:Int)
val list = List(A(3,2), A(4,4), A(10,2), A(4,2))
val filter:PartialFunction[A,A] = {
  case a@A(p1,p2) if p1==p2 => a
  case a@A(p1,p2) if p2>p1 => a
  case a@A(p1,p2) if p1==p2*p2 => a
}

list.collect(filter).foreach(println)

Now, if you need the best fit, I would make a ranking function instead which maps A => Int and then sort by it. You can save some work by filtering first and then sorting with your ranking afterwards. (The collect takes list.size time whereas sorting takes list.size * log(list.size) on average)

Upvotes: 0

maxmc
maxmc

Reputation: 4216

list.find(i => i.p1 == i.p2).getOrElse(list.sortBy(-_.p2).head)

Update, should fit your new requirements.

  list.find(i => i.p1 == i.p2).getOrElse(
  list.find(i => i.p2 > i.p1).getOrElse(
  list.find(i => i.p1 == i.p2 * i.p2)))

Upvotes: 1

Related Questions