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