I'm using Scala 2.11 and Scala IDE. And I have the following problem: I have 2 files one with the implementation fo Weight Biased Leftist Heap and a driver, which is an object, with its main method.
WBLHeap.scala
package heaps
abstract class WBLHeap[+A] {
/**
* O(1)
* @return weight of the heap
*/
def weight() : Int
/**
*
*/
def isWeightedLeftist(): Boolean
/**
* For any WBLT with n elements, the length of its right spine
* is <= floor(log2(n+1))
*/
def rightSpine() : List[A]
/**
* O(log(n))
* @return A WBLHeap with the heap this and the heap h
*/
def merge[B >: A](h: WBLHeap[B]) : WBLHeap[B]
case object EmptyHeap extends WBLHeap[Nothing] {
def weight(): Int = 0
def isWeightedLeftist(): Boolean = true
def rightSpine() : List[Nothing] = List()
def merge[B >: Nothing](h: WBLHeap[B]) : WBLHeap[B] = h
}
case class Node[A](elem: A, weightNode: Int, left: WBLHeap[A], right: WBLHeap[A]) extends WBLHeap[A] {
def weight(): Int = weightNode
def isWeightedLeftist(): Boolean =
left.weight >= right.weight && left.isWeightedLeftist() &&
right.isWeightedLeftist()
def rightSpine() : List[A] = elem :: right.rightSpine()
def merge[B >: A](h: WBLHeap[B]) : WBLHeap[B] = h match {
case EmptyHeap => this
case Node(e, w, l: WBLHeap[B], r: WBLHeap[B]) if this.weightNode <= w => buildNode(elem, left, r.merge(h) )
case Node(e: B, w, l: WBLHeap[B], r: WBLHeap[B]) if this.weightNode > w => buildNode(e, l, this.merge(r))
//There is a warning here but I don't know why.
//abstract type pattern A is unchecked since it is eliminated by erasure
}
private def buildNode[B >: A](x: B, h1: WBLHeap[B], h2: WBLHeap[B]): WBLHeap[B] = {
val w1 = h1.weight()
val w2 = h2.weight()
val newWeight = w1 + w2 + 1
if(w1 >= w2)
return new Node[B](x, newWeight, h1, h2)
else
return new Node[B](x, newWeight, h2, h1)
}
}
}
Driver.scala
package heaps
object Driver {
def main(args:Array[String]) = {
val h = new Node[Char]('b', 2,
new Node[Char]('c', 1, EmptyHeap(), EmptyHeap()),
EmptyHeap())
}
}
In the line: "val h = new Node[Char]('b', 2, ", I have an error: not found: type Node. It also happens everytime I use the object EmptyHeap.
Does anybody know what I am doing wrong?
Thank you!
