How does Ordering.by(_.toLowerCase) work for a case insensitive lookup in a TreeMap in Scala?

user_1474572 0
Viewed 58

So, I had to implement a case insensitive look up for a Map and I used a TreeMap to achieve this:

val treeMap = TreeMap(someOtherMap.toArray: _*)(Ordering.by(_.toLowerCase))

and treeMap.get("FOo") and treeMap.get("foo") return the same results as expected. My question is, how does the (Ordering.by(_.toLowerCase)) additional parameter help in the get()? I'm looking at the source code here and it goes RB.get(key).

How does the additional Ordering.by() exactly help in case-insensitive lookups? Does it take the lookup key, convert to lowercase, and look up keys in the Map in lowercase and then match and return the value? (Extremely naive explanation, I know but I can't seem to reason how otherwise)

New to Scala and hence trying to understand the internal workings here :)

treemap scala
1 Answers

If you dig a bit more into RB.get(key), which is an implementation of a Red-black Tree data structure, you'll see the following code in method scala.collection.immutable.RedBlackTree#lookup

  @tailrec
  def lookup[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
    val cmp = ordering.compare(x, tree.key)
    if (cmp < 0) lookup(tree.left, x)
    else if (cmp > 0) lookup(tree.right, x)
    else tree
  }

It uses ordering to see if key tree.key is more or less than provided x key. In your case, the ordering.compare will return 0 when comparing foo and FOo because of _.toLowerCase and this will match the current node in the tree and the last else tree returns the value associated with key foo.

user_48038420
Related