Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm Scala beginner, so if anyone would be so kind and 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 to Scala mindset, get to know tricks and tips. I have background in PHP and JavaScript, and Scala is quite harder to learn, but way more elegant, so I want to master it

share|improve this question
1  
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? –  Alex L Jun 12 at 22:43
    
It would be more Scala-ish to build an immutable heap. –  toto2 Jun 13 at 1:19
    
Also, if you want some inspiration, you can look at scalaz Heap and the Scala PriorityQueue. –  toto2 Jun 13 at 1:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.