summaryrefslogtreecommitdiffstats
path: root/Scala/patmat/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'Scala/patmat/src/main')
-rw-r--r--Scala/patmat/src/main/scala/patmat/Huffman.scala98
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)
+ }
}