CODEWITHSUNDEEP
scala
stack0114106
stack0114106

Reputation: 8711

Scala - Get the nearest key value from both sides

I'm working on getting the nearest key value in both ways with a given input integer.

Example:

The defined map is as below.

val m = Map(10 -> "W",20 -> "W",30 -> "I",40 -> "A",50 -> "P",60 -> "S",70 -> "A",80 -> "A",90 -> "A",100 -> "I",110 -> "A",120 -> "E")

The keys are integers and they increase in order. If say, 95 is given as input, then I should get the tuple output as follows ((90->"A"), (100->"I"))

scala> m.map( x=> (x._1,x._2)).toList.sortBy(_._1).filter( _._1<=95 ).last
res74: (Int, String) = (90,A)

scala>  m.map( x=> (x._1,x._2)).toList.sortBy(_._1).filter( _._1>=95 ).head
res75: (Int, String) = (100,I)

scala>

The Map size will be big in real scenario(1K) and I want to avoid the sortBy(). Are there any possible foldLeft or map solutions available to this?.

Upvotes: 0

Views: 336

Answers (3)

Leo C
Leo C

Reputation: 22449

Here's one approach that leverages TreeMap's sorting and range query features as shown below:

def nearestValues(m: Map[Int, String], key: Int) = {
  import scala.collection.immutable.TreeMap
  val tm = TreeMap(m.toSeq: _*)

  Seq(tm.to(key).lastOption, tm.from(key).headOption).flatten.distinct
}

val m = Map(
  10 -> "W", 20 -> "W", 30 -> "I", 40 -> "A", 50 -> "P", 60 -> "S",
  70 -> "A", 80 -> "A", 90 -> "A", 100 -> "I", 110 -> "A", 120 -> "E"
)

nearestValues(m, 95)
// res1: Seq[(Int, String)] = List((90,A), (100,I))

nearestValues(m, 20)
// res2: Seq[(Int, String)] = List((20,W))

nearestValues(m, 125)
// res3: Seq[(Int, String)] = List((120,E))

Note that the above method returns a Seq rather than a Tuple to accommodate cases of exact or one-sided matches. To return a Tuple, one could go with something similar to the following:

def nearestValues(m: Map[Int, String], key: Int) = {
  import scala.collection.immutable.TreeMap
  val tm = TreeMap(m.toSeq: _*)

  Seq(tm.to(key).lastOption, tm.from(key).headOption) match {
    case Seq(None, None) => (0 -> "", 0 -> "")  // Default tuple for empty Map
    case Seq(x, None)    => (x.get, Int.MaxValue -> "")
    case Seq(None, y)    => (Int.MinValue -> "", y.get)
    case Seq(x, y)       => (x.get, y.get)
  }
}

nearestValues(m, 95)
// res1: ((Int, String), (Int, String)) = ((90,A),(100,I))

nearestValues(m, 20)
// res2: ((Int, String), (Int, String)) = ((20,W),(20,W))

nearestValues(m, 125)
// res3: ((Int, String), (Int, String)) = ((120,E),(2147483647,""))

UPDATE:

Starting Scala 2.13, methods to and from for TreeMap are replaced with rangeTo and rangeFrom, respectively.

Upvotes: 2

jwvh
jwvh

Reputation: 51271

Here's a pretty straight forward solution. No sorting required.

def nearest[V](m :Map[Int,V], k :Int) :Seq[(Int,V)] =
  m.get(k).fold {
    val (before, after) = m.keys.partition(_ < k)
    Seq(before.maxOption, after.minOption).flatten.map(x => (x,m(x)))
  }(v => Seq((k,v)))

testing:

val m = Map(10 -> "W",20 -> "W",30 -> "I",40 -> "A",50 -> "P",60 -> "S",70 -> "A",80 -> "A",90 -> "A",100 -> "I",110 -> "A",120 -> "E")
nearest(m, -7)   //res0: Seq[(Int, String)] = List((10,W))
nearest(m, 60)   //res1: Seq[(Int, String)] = List((60,S))
nearest(m, 93)   //res2: Seq[(Int, String)] = List((90,A), (100,I))
nearest(m, 121)  //res3: Seq[(Int, String)] = List((120,E))

Upvotes: 2

fenixil
fenixil

Reputation: 2124

You can use sorted collection as Leo C proposed, however that requires collection construction and then search, so complexity of such algorithm will be O(n*log n).

Approaching this task in algorithmic way, you can calculate the difference for the keys and then find the closest negative and positive values to 0. In this case complexity will be lower O(n).

Below example returns nearest keys from the left and the right excluding exact match (you may change that by changing a condition in the filter):

val data = Map(1-> "a", 5->"b")
val key = 4

val diffs = data.keys.map(_ - key)
val rightKeyOpt = diffs.filter(_ > 0).reduceOption(_ min _).map(_ + key)
val leftKeyOpt = diffs.filter(_ < 0).reduceOption(_ max _).map(_ + key)

val result = (leftKeyOpt.map(k=> k->data(k)), rightKeyOpt.map(k=> k->data(k)))

println (leftKeyOpt, rightKeyOpt)
println result

I bet this could be done in a single line if you need that very much:)

Upvotes: 1

Related Questions