6
\$\begingroup\$

I'm a Scala beginner, so it'd be great if anyone would be so kind to give some feedback.

package heap

import scala.collection.mutable.ListBuffer

class Heap[T](compareFunction: (T, T) => Int) {

private val HIGHER = 1
private val LOWER = -1

private val heapRepresentation = new ListBuffer[T]()

private def lastIndex = heapRepresentation.size - 1

private def valueOf(index: Int): T = heapRepresentation(index)

def add(item: T): Heap[T] = {
    heapRepresentation.append(item)
    bubbleUp(lastIndex)
    this
}

def swap(index1: Int, index2: Int) {
    val temp = valueOf(index1)
    heapRepresentation.update(index1, valueOf(index2))
    heapRepresentation.update(index2, temp)
}

def bubbleUp(currentIndex: Int) {
    def getParent(i: Int) = (i - 1) / 2

    if (currentIndex > 0) {
        val parentIndex = getParent(currentIndex)

        compareFunction(valueOf(currentIndex), valueOf(parentIndex)) match {
            case LOWER =>
                swap(currentIndex, parentIndex)
                bubbleUp(parentIndex)
            case _ =>
        }
    }
}

def bubbleDown(currentIndex: Int) {
    getLowerChild(currentIndex) match {
        case Some((lowerChildIndex, lowerChildValue)) =>
            if (compareFunction(valueOf(currentIndex), lowerChildValue) == HIGHER) {
                swap(currentIndex, lowerChildIndex)
                bubbleDown(lowerChildIndex)
            }
        case None =>
    }
}

def getLowerChild(index: Int): Option[(Int, T)] = {
    def getChildrenIndices(parentIndex: Int): (Int, Int) = (2 * parentIndex + 1, 2 * parentIndex + 2)

    val (leftChildIndex, rightChildIndex) = getChildrenIndices(index)

    val areChildrenInBoundsOfHeap = (rightChildIndex <= lastIndex) && (leftChildIndex <= lastIndex)
    if (!areChildrenInBoundsOfHeap) return None

    val (leftChildValue, rightChildValue) = (heapRepresentation(leftChildIndex), heapRepresentation(rightChildIndex))

    compareFunction(leftChildValue, rightChildValue) match {
        case LOWER => Some((leftChildIndex, leftChildValue))
        case _ => Some((rightChildIndex, rightChildValue))
    }
}

def pop: Option[T] = heapRepresentation.size match {
    case 0 => None
    case _ =>

        val firstValue = heapRepresentation(0)
        if (heapRepresentation.size == 1) {
            heapRepresentation.remove(0)
            return Some(firstValue)
        }
        swap(0, lastIndex)
        heapRepresentation.remove(lastIndex)
        bubbleDown(0)
        Some(firstValue)
}


override def toString = {
    s"[$heapRepresentation](${heapRepresentation.size})"
}

}

Usage of heap class

def compareInts(first: Int, second: Int): Int =
    if (first > second) 1
    else if (first == second) 0
    else -1

val heap = new Heap[Int](compareInts)

for (i <- 0 to 3) {
    heap.add((Math.random() * 100).toInt)
}
heap
heap.pop
heap.pop
heap.pop
heap.pop


def compareStrings(first: String, second: String): Int =
    if (first > second) 1
    else if (first == second) 0
    else -1
var heap2 = new Heap[String](compareStrings)
heap2.add("a")
heap2.add("cc")
heap2.add("")

heap2.pop
heap2.pop
heap2.pop
heap2.pop

Right now, I would like to get a Scala mindset, and get to know the tricks and tips. I have a background in PHP and JavaScript, and Scala is quite harder to learn, but way more elegant, so I want to master it!

\$\endgroup\$
  • 2
    \$\begingroup\$ Perhaps you could add some background to your script? What should it do? Are you looking for a focus on a specific part or concept? \$\endgroup\$ – Alex L Jun 12 '14 at 22:43
  • 1
    \$\begingroup\$ It would be more Scala-ish to build an immutable heap. \$\endgroup\$ – toto2 Jun 13 '14 at 1:19
  • 1
    \$\begingroup\$ Also, if you want some inspiration, you can look at scalaz Heap and the Scala PriorityQueue. \$\endgroup\$ – toto2 Jun 13 '14 at 1:23
5
\$\begingroup\$

Writing utility classes is hard enough without reinventing everything from scratch each time. Whenever possible, class authors should take advantage of available tools. In this case, Scala has a trait for ordering objects in a collection: scala.math.Ordering and it should be used for the compareFunction which will undoubtedly require some adjustment of the code.

For the most part, the code is well laid out and easy to follow. Good job! Note that standard indentation for Scala code is two spaces. It's hard to tell if the four space indentation is what is used in the code, or if it was an artifact of transferring the code into this question.

While Scala pattern matching is a great tool, it is possible to over user it. I think that using it in the pop method is not just overkill, but also results in code that is harder to read. I would write it like this:

def pop: Option[T] =  match {
  if (heapRepresentation.isEmpty) None
  else {
    val firstValue = heapRepresentation(0)
    if (heapRepresentation.size == 1) {
       heapRepresentation.remove(0)
    }
    else {
      swap(0, lastIndex)
      heapRepresentation.remove(lastIndex)
      bubbleDown(0)
    }
    Some(firstValue)
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.