Ordering a PriorityQueue by a field of a non-case class

Question

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?

Answer 1

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).