test of manual map/reduce in scala

huffman_times.scala

/*
def insert_char(char: Char, list: List[(Char, Int)]): List[(Char, Int)] = {
    if (list.isEmpty) 
      return List((char, 1))    
    if (char == list.head._1) 
      return (char, list.head._2 + 1) :: list.tail
    list.head :: insert_char(char, list.tail)    
  }
  */
def insert_char(char: Char, list: List[(Char, Int)]): List[(Char, Int)] = list match {
    case Nil => List((char, 1))    
    case x :: xs if (x._1 == char) => (x, x._2 + 1) :: xs
    case x :: xs => x :: insert_char(char, xs)    
}
     
/*  
def insert_chars(chars: List[Char], list: List[(Char, Int)]): List[(Char, Int)] = {
    if (chars.isEmpty) 
      return Nil
    if (chars.tail.isEmpty)
      return insert_char(chars.head, list)
    insert_chars(chars.tail, insert_char(chars.head, list))       	
}
*/

def insert_chars(chars: List[Char], list: List[(Char, Int)]): List[(Char, Int)] = chars match {
    case Nil => list
    case x :: xs =>  insert_chars(xs, insert_char(x, list))       	
}
  
def times(chars: List[Char]): List[(Char, Int)] = {
    val r = insert_chars(chars, List())
    r    
}


//Versão Giba
def times(chars: List[Char]): List[(Char, Int)] = {
    def iTimes(chs: List[Char], acc: HashMap[Char, Int]): HashMap[Char, Int] = {
      chs match {
        case Nil => acc
        case (x :: xs) => {
          iTimes(xs, acc.get(x) match {
            case Some(i) => acc + (x -> (i + 1))
            case _ => acc + (x -> 1)
          })
        }
      }
    }

    iTimes(chars, new HashMap[Char, Int]()).toList
  }


def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = 
    freqs.sortWith(_._2.compareTo(_._2) > 0 )