fork download 
  1. object Main{
  2.   abstract sealed class Node[A]{
  3.     val freq: Int
  4.   }
  5.  
  6.   case class Leaf[A](element: A, freq: Int) extends Node[A]
  7.   case class Branch[A](left: Node[A], right: Node[A]) extends Node[A]{
  8.     val freq = left.freq + right.freq
  9.   }
  10.  
  11.   def huffman[A](ls: List[(A, Int)]): List[(A, String)] = {
  12.     def makeTree(ls: List[Node[A]]): Node[A] = ls match{
  13.       case Nil => throw new IllegalArgumentException
  14.       case top :: Nil => top
  15.       case _ => {
  16. 	val last = ls.sortBy(_.freq).slice(0, 2)
  17. 	makeTree(Branch(last(0), last(1)) :: ls filterNot {last.contains})
  18.       }
  19.     }
  20.     def huffmanCode(n: Node[A], code: String): List[(A, String)] = n match{
  21.       case Leaf(element, freq) => List((element, code))
  22.       case Branch(left, right) => huffmanCode(left, code + "0") ::: huffmanCode(right, code + "1")
  23.       case _ => throw new IllegalArgumentException
  24.     }
  25.     val top = makeTree(ls map {n => Leaf(n._1, n._2): Node[A]})
  26.     huffmanCode(top, "")
  27.   }
  28.  
  29.   def main(args: Array[String]){
  30.     println(huffman(List(("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5))))
  31.   }
  32. }
  33.  
Success #stdin #stdout 0.2s 211712KB
comments (?)
stdin 
Standard input is empty
stdout 
List((a,0), (c,100), (b,101), (f,1100), (e,1101), (d,111))
https://ideone.com/qcFZ7
language:
Scala (scala 2.12.8)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!