ScalaFistes

TontonMartin.scala

object FuncourseWithUncleMartin{
  
 */
object Setsss{

  def contains(s: Set, elem: Int): Boolean = s(elem)

  def singleton(elem: Int): Set =  Set(elem)//(x :Int) => x == elem
 
  def union(s: Set, t: Set): Set = (x : Int) => s(x) || t(x)
 
  def intersect(s: Set, t: Set): Set = (x : Int) => s(x) && t(x)
  
  def diff(s: Set, t: Set): Set = (x: Int) => s(x) && !t(x)

  def filter(s: Set, p: Int => Boolean): Set = (x :Int) =>p(x) && s(x)
 
  val bound = 1000

  def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (s(a) && !p(a)) false
      else if (a > bound) true
      else iter(a+1)
    }
    iter(-bound)
  }

 
 def exists(s: Set, p: Int => Boolean): Boolean = {
     def iter(a: Int): Boolean = {
      if (s(a) && p(a)) true
      else if (a > bound) false
      else iter(a+1)
    }
     iter(-bound)
  
  }

  def exists(s: Set, p: Int => Boolean): Boolean = ! forall(s, (i:Int) => !p(i))
 
  def map(s: Set, f: Int => Int): Set = {
    def iterate (x : Int) : Set = {
      if (x > bound ) ((y:Int) => false)
      else if (s(x)) union(singleton(f(x)),iterate(x +1))
      else iterate(x+1)
    }
    iterate(-bound)
  }
  

 
  def pascal(c: Int, r: Int): Int =  if (c == r || c==0 || r==1) 1 else pascal(c-1,r-1) + pascal(c,r-1)
 
  def balance(chars: List[Char]): Boolean = balance_aux(chars, Nil)

  def balance_aux(chars : List[Char], stack : List[Char]) : Boolean = (chars, stack) match {
      case (Nil, Nil) => true
      case (Nil, _) => false
      case (h :: tail, stack) => h match {
          case '(' => balance_aux(tail, h :: stack)
          case ')' => !stack.isEmpty && balance_aux(tail, stack.tail)
          case  _  => balance_aux(tail, stack)
          }
     }
 
  def countChange(money: Int, coins: List[Int]): Int = (money, coins) match {
    case (0,_) => 1
    case (_, Nil) => 0
    case (_ , h :: tail) => if (money < 0) 0 else countChange(money , tail) + countChange(money - h , coins)
  }
 //NonEMpty
    
   def filter0(p : Tweet => Boolean, accu : TweetSet) : TweetSet = 
      if (isEmpty) accu  
      else if (p(elem)) new NonEmpty(elem,left.filter0(p, accu),right.filter0(p,accu))
           else (remove(elem)).filter0(p,accu)
    
    
  override def union(that: TweetSet): TweetSet = 
    if (that.isEmpty) this 
    else (that.head, that.tail.isEmpty) match {
    		case (_ , true) => if (!contains(that.head)) incl(that.head)else this
    		case (_, false) => if (!contains(that.head)) incl(that.head).union(that.tail) else union(that.tail)
  }

 
   override def ascendingByRetweet0(accu : Trending): Trending = 
     if (isEmpty) accu
     else if (tail.isEmpty) (accu + head)
     else remove(findMin).ascendingByRetweet0(accu + findMin)

   //EMpty
  def filter0(p: Tweet => Boolean, accu: TweetSet): TweetSet = new Empty
  
  override def union(that: TweetSet): TweetSet = that
  
  override def ascendingByRetweet0(trend : Trending): Trending = new EmptyTrending
  
  object GoogleVsApple {
  val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
  
  val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")

  val googleTweets = TweetReader.allTweets.filter((x:Tweet) => x.text.contains("google"))

  val appleTweets = TweetReader.allTweets.filter((x:Tweet) => x.text.contains("apple"))
  
  val trending: Trending = (googleTweets union appleTweets).ascendingByRetweet
}


}

package patmat

import common._
import scala.util.Sorting
import scala.annotation.tailrec

/**
 * Assignment 4: Huffman coding
 *
 */
object Huffman {

  /**
   * A huffman code is represented by a binary tree.
   *
   * Every `Leaf` node of the tree represents one character of the alphabet that the tree can encode.
   * The weight of a `Leaf` is the frequency of appearance of the character.
   *
   * The branches of the huffman tree, the `Fork` nodes, represent a set containing all the characters
   * present in the leaves below it. The weight of a `Fork` node is the sum of the weights of these
   * leaves.
   */
  abstract class CodeTree
  case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
  case class Leaf(char: Char, weight: Int) extends CodeTree



  // Part 1: Basics
  def weight(tree: CodeTree): Int = tree match {
    case Leaf(c,w) => w
    case Fork(left ,right ,chrs,w)=>weight(left) + weight(right)
  }
  
  def chars(tree: CodeTree): List[Char] = tree match{
    case Leaf(char, w) => List(char)
    case Fork(left, right, charList, w) => chars(left) ::: chars(right)
    
  }

  def makeCodeTree(left: CodeTree, right: CodeTree) =
    Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right))




  // Part 2: Generating Huffman trees

  /**
   * In this assignment, we are working with lists of characters. This function allows
   * you to easily create a character list from a given string.
   */
  def string2Chars(str: String): List[Char] = str.toList

  /**
   * This function computes for each unique character in the list `chars` the number of
   * times it occurs. For example, the invocation
   *
   *   times(List('a', 'b', 'a'))
   *
   * should return the following (the order of the resulting list is not important):
   *
   *   List(('a', 2), ('b', 1))
   *
   * The type `List[(Char, Int)]` denotes a list of pairs, where each pair consists of a
   * character and an integer. Pairs can be constructed easily using parentheses:
   *
   *   val pair: (Char, Int) = ('c', 1)
   *
   * In order to access the two elements of a pair, you can use the accessors `_1` and `_2`:
   *
   *   val theChar = pair._1
   *   val theInt  = pair._2
   *
   * Another way to deconstruct a pair is using pattern matching:
   *
   *   pair match {
   *     case (theChar, theInt) =>
   *       println("character is: "+ theChar)
   *       println("integer is  : "+ theInt)
   *   }
   */
 def times(chars: List[Char]): List[(Char, Int)] = chars match {
    case Nil => Nil
    case e :: tail => (e, chars.count(_ == e)) :: times(tail.filterNot (_ == e))
  }

  /**
   * Returns a list of `Leaf` nodes for a given frequency table `freqs`.
   *
   * The returned list should be ordered by ascending weights (i.e. the
   * 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] = {
    val sortedFreqs = Sorting.stableSort(freqs, 
                                        (e1 : (Char, Int), e2 : (Char, Int)) => e1._2 <= e2._2)
                                        .toList
    sortedFreqs map (e => Leaf(e._1, e._2))
  }

  /**
   * Checks whether the list `trees` contains only one single code tree.
   */
  def singleton(trees: List[CodeTree]): Boolean = trees match {
     case leaf :: Nil => true
     case _ => false
  }

  /**
   * The parameter `trees` of this function is a list of code trees ordered
   * by ascending weights.
   *
   * This function takes the first two elements of the list `trees` and combines
   * them into a single `Fork` node. This node is then added back into the
   * remaining elements of `trees` at a position such that the ordering by weights
   * is preserved.
   *
   * If `trees` is a list of less than two elements, that list should be returned
   * unchanged.
   */
   def combine(trees: List[CodeTree]): List[CodeTree] = {
    Sorting.stableSort(trees, (t1 : CodeTree , t2: CodeTree) => weight(t1) <= weight(t2)).toList
    if (trees.size <= 2) trees
    else {
        val ftree = makeCodeTree(trees(0), trees(1))
        List(ftree) ::: trees.tail.tail
    }
    
 }

  /**
   * This function will be called in the following way:
   *
   *   until(singleton, combine)(trees)
   *
   * where `trees` is of type `List[CodeTree]`, `singleton` and `combine` refer to
   * the two functions defined above.
   *
   * In such an invocation, `until` should call the two functions until the list of
   * code trees contains only one single tree, and then return that singleton list.
   *
   * Hint: before writing the implementation,
   *  - start by defining the parameter types such that the above example invocation
   *    is valid. The parameter types of `until` should match the argument types of
   *    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(s: List[CodeTree] => Boolean, c: List[CodeTree]=> List[CodeTree])(treeList: List[CodeTree]): List[CodeTree] = treeList match {
//    			case Nil => Nil
//    			case e :: Nil => treeList
//    			case e:: tail => if (singleton(tail)) List(makeCodeTree(e, tail(0)))
//    											 else {  
//    											     val lst = until(s,c)(tail);
//    											     List(makeCodeTree(e, lst(0)))
//    											 }
//    }
//   
   def until(s: List[CodeTree] => Boolean, c: List[CodeTree]=> List[CodeTree])(treeList: List[CodeTree]): List[CodeTree]=
     treeList match {
     case Nil => Nil
     case a :: Nil => treeList
     case a::a1:: q =>  if (s(q)) c(makeCodeTree(a, a1) :: q)
     					else c(makeCodeTree(a,a1) :: until(s,c)(q))
   }
  
  
   /**
* This function creates a code tree which is optimal to encode the text `chars`.
*
* 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 = {
    val freqs = times(chars)
   (until(singleton, combine)(combine(makeOrderedLeafList(freqs))))(0)
//    freqs match {
//      case Nil => throw new Exception("Empty car List, can't create an empty code Tree")
//      case (c,w)::Nil => Leaf(c,w)
//      case a::q => {
//                val lst = combine(makeOrderedLeafList(freqs))
//                until(singleton, combine)(lst)(0)
//                
//      }
//    }
  }
  
  
  
  // Part 3: Decoding

  type Bit = Int

  /**
   * This function decodes the bit sequence `bits` using the code tree `tree` and returns
   * the resulting list of characters.
   * Decoding  starts at the root of the tree. Given a sequence of bits to decode, 
   * we successively read the bits, and for each 0, we choose the left branch, 
   * and for each 1 we choose the right branch. When we reach a leaf, 
   * we decode the corresponding character and then start again at the root of the tree. 
   * As an example, given the Huffman tree above, the sequence of bits, 10001010 corresponds to BAC.
   * Implementation
   */
  
  //def decode(tree: CodeTree, bits: List[Bit]) : List[Char]= decode_aux (tree, bits, List.empty)
  
  @tailrec
  def decode_aux (tree: CodeTree, bits: List[Bit], ret : List[Char]) : List[Char]= (tree, bits) match {
    case (Fork(l,r,ch,w), Nil) => throw new Exception ("Bad Encoding")
    case (Leaf(c,w), Nil) => (c::ret).reverse
    case (Leaf(c,w), _) => decode_aux(tree, bits.tail,c::ret)
    case (Fork(l,r,ch,w), a::q) => if (a == 0) decode_aux(l,q,ret) else decode_aux(r,q,ret)
    
  }
  
 
  def decode (tree: CodeTree, bits: List[Bit] ): List[Char] = {
  def decode1 (bits: List[Bit], current: CodeTree): List[Char] = bits match {
    case Nil => Nil
    case head :: tail => {
      val br =chooseBranch (head, current) 
      br match {
      case Leaf(symbol,w) => symbol :: decode1(tail, tree)
      case Fork(l,r,c,w) => decode1(tail, br)
    }
    }

  }
  decode1 (bits, tree)
}
   def chooseBranch (bit: Bit, branch: CodeTree) = 
      (bit, branch) match {
        case (_, Leaf(w,c)) => branch
        case (0, Fork(l,r,c,w)) => l
        case (1 , Fork(l,r,c,w)) =>r
      }
  /**
   * A Huffman coding tree for the French language.
   * Generated from the data given at
   *   http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d%27apparition_des_lettres_en_fran%C3%A7ais
   */
  val frenchCode: CodeTree = Fork(Fork(Fork(Leaf('s',121895),Fork(Leaf('d',56269),Fork(Fork(Fork(Leaf('x',5928),Leaf('j',8351),List('x','j'),14279),Leaf('f',16351),List('x','j','f'),30630),Fork(Fork(Fork(Fork(Leaf('z',2093),Fork(Leaf('k',745),Leaf('w',1747),List('k','w'),2492),List('z','k','w'),4585),Leaf('y',4725),List('z','k','w','y'),9310),Leaf('h',11298),List('z','k','w','y','h'),20608),Leaf('q',20889),List('z','k','w','y','h','q'),41497),List('x','j','f','z','k','w','y','h','q'),72127),List('d','x','j','f','z','k','w','y','h','q'),128396),List('s','d','x','j','f','z','k','w','y','h','q'),250291),Fork(Fork(Leaf('o',82762),Leaf('l',83668),List('o','l'),166430),Fork(Fork(Leaf('m',45521),Leaf('p',46335),List('m','p'),91856),Leaf('u',96785),List('m','p','u'),188641),List('o','l','m','p','u'),355071),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u'),605362),Fork(Fork(Fork(Leaf('r',100500),Fork(Leaf('c',50003),Fork(Leaf('v',24975),Fork(Leaf('g',13288),Leaf('b',13822),List('g','b'),27110),List('v','g','b'),52085),List('c','v','g','b'),102088),List('r','c','v','g','b'),202588),Fork(Leaf('n',108812),Leaf('t',111103),List('n','t'),219915),List('r','c','v','g','b','n','t'),422503),Fork(Leaf('e',225947),Fork(Leaf('i',115465),Leaf('a',117110),List('i','a'),232575),List('e','i','a'),458522),List('r','c','v','g','b','n','t','e','i','a'),881025),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u','r','c','v','g','b','n','t','e','i','a'),1486387)

  /**
   * What does the secret message say? Can you decode it?
   * For the decoding use the `frenchCode' Huffman tree defined above.
   */
  val secret: List[Bit] = List(0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1)

  /**
   * Write a function that returns the decoded secret
   */
  def decodedSecret: List[Char] = decode(frenchCode, secret)



  // Part 4a: Encoding using Huffman tree

  /**
   * This function encodes `text` using the code tree `tree`
   * into a sequence of bits.
   * For a given Huffman tree, one can obtain the encoded representation of a character 
   * by traversing from the root of the tree to the leaf containing the character. 
   * Along the way, when a left branch is chosen, a 0 is added to the representation, 
   * and when a right branch is chosen, 1 is added to the representation. 
   * Thus, for the Huffman tree above, the character D is encoded as 1011.
   */
  
  def encode(tree: CodeTree)(text: List[Char]): List[Bit] =  {
    
     def encodeChar (tree : CodeTree, Char char , ret : List[Bit]) : List[Bit]= {
       tree match {
         case Leaf(c,w) => if (c == char ) ret else (encodeChar)
         case Fork (l,r,chs,w) => 
       }
     }
  }


//  def successiveMerge (leafSet: List[Tree]): Tree = leafSet match {
//  case head :: Nil => head // when 1, we have 1 tree, rather than a set of leaves
//  case head :: tail => successiveMerge (adjoinSet (makeCodeTree (head, tail.first), tail.tail))
//  case Nil => throw new RuntimeException("Invalid leaf set: "+leafSet)

  // Part 4b: Encoding using code table

  type CodeTable = List[(Char, List[Bit])]

  /**
   * This function returns the bit sequence that represents the character `char` in
   * the code table `table`.
   */
  def codeBits(table: CodeTable)(char: Char): List[Bit] = ???

  /**
   * Given a code tree, create a code table which contains, for every character in the
   * code tree, the sequence of bits representing that character.
   *
   * Hint: think of a recursive solution: every sub-tree of the code tree `tree` is itself
   * 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 = ???

  /**
   * 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 = ???

  /**
   * This function encodes `text` according to the code tree `tree`.
   *
   * 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 main(args: Array[String]) {
    println (decodedSecret)
  
    
    
}
}