Reputation: 2289
I'm currently trying to implement the huffman algorithm using scala. To do this, I'd figured I'd use a PriorityQueue for the ordering of the different Nodes in the tree based on their weight. Thus, I have to create a PriorityQueue of BinarySearchTree Nodes. However, Scala only lets me order by a field of a case class.
This is want I want:
class BinarySearchTree(weight: Int)
case class ForkNode(left: BinarySearchTree, right: BinarySearchTree, chars: List[Char], weight: Int) extends BinarySearchTree(weight)
case class LeafNode(char: Char, weight: Int) extends BinarySearchTree(weight)
def createBST(inputFile: ListMap[Char,Int]): BinarySearchTree = {
def weightOrder(t2: BinarySearchTree) = t2.weight
val nodeMap:PriorityQueue[BinarySearchTree] = PriorityQueue(Ordering.by(weightOrder))
null
}
But it doesn't compile. However, def weightOrder(t2: ForkNode) = t2.weight
does compile, but that is not what I want.
How can I order my priority queue based on a field in a non-case class?
Upvotes: 0
Views: 242
Reputation: 51271
This is incomplete but compiles.
import scala.collection.immutable.ListMap
import collection.mutable.PriorityQueue
class BinarySearchTree(val weight: Int) //weight is now member data
case class ForkNode( left: BinarySearchTree
, right: BinarySearchTree
, chars: List[Char]
, override val weight: Int //now needs override
) extends BinarySearchTree(weight)
case class LeafNode( char: Char
, override val weight: Int //now needs override
) extends BinarySearchTree(weight)
def createBST(inputFile: ListMap[Char,Int]): BinarySearchTree = {
def weightOrder(t2: BinarySearchTree) = t2.weight
val bst: BinarySearchTree = LeafNode('c',2) //build something of proper type
val nodeMap:PriorityQueue[BinarySearchTree] =
PriorityQueue(bst)(Ordering.by(weightOrder)) //create PriorityQueue
null //etc.
}
PriorityQueue
is mutable and type invariant so if you want a PriorityQueue[BinarySearchTree]
then the constructor argument must be of type BinarySearchTree
and not a derived type (i.e. a Node).
Upvotes: 1