1 files changed, 83 insertions, 15 deletions
diff --git a/Scala/patmat/src/main/scala/patmat/Huffman.scala b/Scala/patmat/src/main/scala/patmat/Huffman.scala
index a40c212..9796fdd 100644
--- a/Scala/patmat/src/main/scala/patmat/Huffman.scala
+++ b/Scala/patmat/src/main/scala/patmat/Huffman.scala
@@ -26,9 +26,15 @@ object Huffman {
 
   // Part 1: Basics
 
-  def weight(tree: CodeTree): Int = ??? // tree match ...
+  def weight(tree: CodeTree): Int = tree match {
+    case Leaf(c, w) => w
+    case Fork(l, r, c, w) => w
+  }
 
-  def chars(tree: CodeTree): List[Char] = ??? // tree match ...
+  def chars(tree: CodeTree): List[Char] = tree match {
+    case Leaf(c, w) => c :: Nil
+    case Fork(l, r, c, w) => c
+  }
 
   def makeCodeTree(left: CodeTree, right: CodeTree) =
     Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right))
@@ -71,7 +77,10 @@ object Huffman {
    *       println("integer is  : "+ theInt)
    *   }
    */
-  def times(chars: List[Char]): List[(Char, Int)] = ???
+  def times(chars: List[Char]): List[(Char, Int)] = {
+    def counts(chs: List[Char]): List[Int] = if (chs.isEmpty) Nil else chars.count(c => c == chs.head) :: counts(chs.tail)
+    chars.distinct.zip(counts(chars.distinct))
+  }
 
   /**
    * Returns a list of `Leaf` nodes for a given frequency table `freqs`.
@@ -80,12 +89,17 @@ object Huffman {
    * head of the list should have the smallest weight), where the weight
    * of a leaf is the frequency of the character.
    */
-  def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = ???
+  def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = {
+    freqs.sortWith((p1, p2) => p1._2 < p2._2).map(p => new Leaf(p._1, p._2))
+  }
 
   /**
    * Checks whether the list `trees` contains only one single code tree.
    */
-  def singleton(trees: List[CodeTree]): Boolean = ???
+  def singleton(trees: List[CodeTree]): Boolean = trees match {
+    case x :: Nil => true
+    case _ => false
+  }
 
   /**
    * The parameter `trees` of this function is a list of code trees ordered
@@ -99,7 +113,16 @@ object Huffman {
    * If `trees` is a list of less than two elements, that list should be returned
    * unchanged.
    */
-  def combine(trees: List[CodeTree]): List[CodeTree] = ???
+  def combine(trees: List[CodeTree]): List[CodeTree] = {
+    def insert(x: Fork, xs: List[CodeTree]): List[CodeTree] = xs match {
+      case List() => x :: Nil
+      case y :: ys => if ( weight(x) < weight(y) ) x :: xs else y :: insert(x, ys)
+    }
+    trees match {
+      case x :: y :: xs => insert(makeCodeTree(x, y), xs)
+      case _ => trees
+    }
+  }
 
   /**
    * This function will be called in the following way:
@@ -118,7 +141,8 @@ object Huffman {
    *    the example invocation. Also define the return type of the `until` function.
    *  - try to find sensible parameter names for `xxx`, `yyy` and `zzz`.
    */
-  def until(xxx: ???, yyy: ???)(zzz: ???): ??? = ???
+  def until(done: List[CodeTree] => Boolean, reduce: List[CodeTree] => List[CodeTree])(trees: List[CodeTree]): List[CodeTree] =
+    if (done(trees)) trees else until(done, reduce)(reduce(trees))
 
   /**
    * This function creates a code tree which is optimal to encode the text `chars`.
@@ -126,7 +150,8 @@ object Huffman {
    * The parameter `chars` is an arbitrary text. This function extracts the character
    * frequencies from that text and creates a code tree based on them.
    */
-  def createCodeTree(chars: List[Char]): CodeTree = ???
+  def createCodeTree(chars: List[Char]): CodeTree =
+    until(singleton,combine)(makeOrderedLeafList(times(chars))).head
 
 
 
@@ -138,7 +163,16 @@ object Huffman {
    * This function decodes the bit sequence `bits` using the code tree `tree` and returns
    * the resulting list of characters.
    */
-  def decode(tree: CodeTree, bits: List[Bit]): List[Char] = ???
+  def decode(tree: CodeTree, bits: List[Bit]): List[Char] = {
+    def decodeRec (subTree: CodeTree, bits: List[Bit], chars: List[Char]): List[Char] = subTree match {
+      case Leaf(c, w) => decodeRec(tree, bits, chars ::: c :: Nil)
+      case Fork(l, r, c, w) => bits match {
+        case b :: bs => if (b == 0) decodeRec(l, bs, chars) else decodeRec(r, bs, chars)
+        case _ => chars
+      }
+    }
+    decodeRec(tree, bits, Nil)
+  }
 
   /**
    * A Huffman coding tree for the French language.
@@ -156,7 +190,7 @@ object Huffman {
   /**
    * Write a function that returns the decoded secret
    */
-  def decodedSecret: List[Char] = ???
+  def decodedSecret: List[Char] = decode(frenchCode, secret)
 
 
 
@@ -166,7 +200,20 @@ object Huffman {
    * This function encodes `text` using the code tree `tree`
    * into a sequence of bits.
    */
-  def encode(tree: CodeTree)(text: List[Char]): List[Bit] = ???
+  def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
+    def checkSub(sub: CodeTree, char: Char): Boolean = sub match {
+      case Leaf(c, w) => c == char
+      case Fork(l, r, c, w) => c.contains(char)
+    }
+    def encodeRec(subTree: CodeTree, text: List[Char], bits: List[Bit]): List[Bit] = text match {
+      case Nil => bits
+      case _ => subTree match {
+        case Leaf(c, w) => encodeRec(tree, text.tail, bits)
+        case Fork(l, r, c, w) => if (checkSub(l,text.head)) encodeRec(l, text, bits ::: 0 :: Nil) else encodeRec(r, text, bits ::: 1 :: Nil)
+      }
+    }
+    encodeRec(tree, text, Nil)
+  }
 
 
   // Part 4b: Encoding using code table
@@ -177,7 +224,10 @@ object Huffman {
    * This function returns the bit sequence that represents the character `char` in
    * the code table `table`.
    */
-  def codeBits(table: CodeTable)(char: Char): List[Bit] = ???
+  def codeBits(table: CodeTable)(char: Char): List[Bit] = table match {
+    case Nil => Nil
+    case (c, bits) :: xs => if (c == char) bits else codeBits(xs)(char)
+  }
 
   /**
    * Given a code tree, create a code table which contains, for every character in the
@@ -187,14 +237,25 @@ object Huffman {
    * a valid code tree that can be represented as a code table. Using the code tables of the
    * sub-trees, think of how to build the code table for the entire tree.
    */
-  def convert(tree: CodeTree): CodeTable = ???
+  def convert(tree: CodeTree): CodeTable = {
+    def prependBit(bit: Bit, table: CodeTable) = {
+      table.map(x => (x._1, bit :: x._2))
+    }
+    def convertRec(subTree: CodeTree, table: CodeTable, bits: Bit): CodeTable = subTree match {
+      case Leaf(c, w) => (c, Nil) :: Nil
+      case Fork(l, r, c, w) => {
+        mergeCodeTables(prependBit(0,convertRec(l, table, 0)), prependBit(1,convertRec(r, table, 1)))
+      }
+    }
+    convertRec(tree, Nil, 2)
+  }
 
   /**
    * This function takes two code tables and merges them into one. Depending on how you
    * use it in the `convert` method above, this merge method might also do some transformations
    * on the two parameter code tables.
    */
-  def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = ???
+  def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = a ::: b
 
   /**
    * This function encodes `text` according to the code tree `tree`.
@@ -202,5 +263,12 @@ object Huffman {
    * To speed up the encoding process, it first converts the code tree to a code table
    * and then uses it to perform the actual encoding.
    */
-  def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = ???
+  def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = {
+    val codeTable = convert(tree)
+    def encodeRec(text: List[Char], bits: List[Bit]): List[Bit] = text match {
+      case Nil => bits
+      case x :: xs => encodeRec(xs, bits ::: codeBits(codeTable)(x))
+    }
+    encodeRec(text, Nil)
+  }
 }