Scala-fy a java function?

Question

I've recently switched my assignment from Java to Scala. However, it still looks like java. For example, the function below does a search on a range tree, and inside there I do some "isInstanceOf" checks.

However - replacing them with "match" seems like it would only take up more space. Can anyone suggest some improvements on how to "scalify" this code?

def rangeSearch2D(treeRoot: Node, lower: Data2D, upper: Data2D, 
         visited: Visited): Seq[Data2D] = {

    if (treeRoot == null) {
      // return empty list
  return Vector()
}
// increment visit count
if (visited != null)
  visited.visit2D(treeRoot)

var results = ArrayBuffer[Data2D]()

// Find nearest common ancestor with value between lower.x and upper.x
var common: Node = commonAncestor(treeRoot, lower, upper, visited)

if (common.isInstanceOf[LeafNode]) {
  return Vector(common.asInstanceOf[LeafNode].data)
}

/** Common non-leaf node, must process subtree */
/** Process left subtree */
var current = common.left

while (!current.isInstanceOf[LeafNode]) {
  if (visited != null)
    visited.visit2D(current)

  //Find a path from current to lower.x
  if (lower.x <= current.midRange) {
    results.appendAll(rangeSearch1D(current.right.subTree, 
                        lower, upper, visited))
    current = current.left
  } else {
    current = current.right
  }
}
//Check if current leaf node is in range
if (inRange(current, lower, upper)) {

  results.append(current.asInstanceOf[LeafNode].data)
}
/** Process right subtree */
current = common.right

while (!current.isInstanceOf[LeafNode]) {
  if (visited != null)
    visited.visit2D(current)

  //Find a path from current to upper.x
  if (upper.x >= current.midRange) {

    results.appendAll(rangeSearch1D(current.left.subTree, 
                        lower, upper, visited))
    current = current.right
  } else {
    current = current.left
  }
}
//Check if current leaf node is in range
    if (inRange(current, lower, upper)) {
      results.append(current.asInstanceOf[LeafNode].data)
    }

    return results
  }

Answer 1

To Scala-fy the code above there are a few fairly general steps you could take:

• Reduce the number of if statements and replace casts and type tests with pattern matching

• Eliminate while statements with recursive functions / methods or library methods (such as folds)

• Eliminate vars by passing accumulators into function / method calls and assign the result to recover the final accumulation

• Reduce assignments by using values returned by multi-block statements such as if and try catch

• Eliminate nulls using Option types

• Eliminate the return keyword to guard against missing permutations

• Only leave out an else block / statement if it performs a No-Op (the compiler should catch broken assignments from an if without an else)

• Use extractors, if possible, to decompose hierarchies easily in pattern matches.

• If the code doesn't read well refactor and introduce well named helper functions / methods

Answer 2

A first step could be something like this, but I'm sure there are more opportunities (e.g. breaking the method in smaller steps [and avoiding things like currentN by this], finding a way to unify loop0 and loop1, which are ugly, replacing the ArrayBuffer by an immutable structure, making visited an Option).

  def rangeSearch2D(treeRoot: Node, lower: Data2D, upper: Data2D, visited: Visited): Seq[Data2D] = 
  if (treeRoot == null) Vector() // return empty list
  else {

    // increment visit count
    if (visited != null)
      visited.visit2D(treeRoot)

    val results = ArrayBuffer[Data2D]()

    // Find nearest common ancestor with value between lower.x and upper.x
    val (current0,current2) = commonAncestor(treeRoot, lower, upper, visited) match {
      case leafNode:LeafNode => return Vector(leafNode.data)
      case common => (common.left, common.right)
    }     

    def loop0(current: Node):Node = current match {
      case _:LeafNode => current
      case _ =>  if (visited != null) visited.visit2D(current)
        if (lower.x <= current.midRange) {
          results.appendAll(rangeSearch1D(current.right.subTree, 
                                          lower, upper, visited))
          current.left
        } else current.right
    }

    val current1 = loop0(current0)


    //Check if current leaf node is in range
    if (inRange(current1, lower, upper))  results.append(current1.asInstanceOf[LeafNode].data)

    def loop1(current: Node):Node = current match {
      case _:LeafNode => current
      case _ =>  if (visited != null) visited.visit2D(current)
        if (upper.x >= current.midRange) {
          results.appendAll(rangeSearch1D(current.left.subTree, 
                                          lower, upper, visited))
          current.right
        } else current.left
    }

    val current3 = loop1(current2)

    //Check if current leaf node is in range
    if (inRange(current3, lower, upper)) 
      results.append(current3.asInstanceOf[LeafNode].data)

    results
  }

Answer 3

Well, first you can get rid of null, replacing the parameters that might be null with Option. In the code, you then change

if (visited != null)
  visited.visit2D(x)

with

visited foreach (_ visit2D x)

Both while loops can be replaced with recursive functions. Instead of adding the result to a mutable variable, you can pass it as an immutable accumulator parameter in the recursive function.

If Node has an extractor, you could use a case guard to make the midrange test. Doesn't add much, but is more idiomatic.

I get the feeling that both while loops can be subsumed into a single recursion, but I haven't considered the algorithm enough to decided about that. If so, you could get away with the common early return.

By the way, there's a bug there, since there might not be a common ancestor within the range.