Benutzer:Dirk Huenniger/huffman

import Data.List
data Tree = Leaf Integer Char | Node Integer Tree Tree 

instance Eq Tree
 where
  (==) n1 n2  = x == y  
    where
      x= fn n1
      y= fn n2


instance Ord Tree
 where
  compare n1 n2  
         | x == y    =  EQ
         | x <= y    =  LT
         | otherwise =  GT
    where
      x= fn n1
      y= fn n2


fn n= case n of 
        Node i n1 n2 -> i
        Leaf i c -> i

basetree x = map  (\(c,i)-> Leaf i c) x

takefirst x = (y,delete y x)
  where y = minimum x

step [x] = x
step x = step $ (Node ((fn y) + (fn z)) y z):zs
  where
   (y,ys)=takefirst x
   (z,zs)=takefirst ys

output (Node _ n1 n2) = (f n1 '0')++ (f n2 '1') 
  where 
    f n r = (map (\(c,x)->(c,r:x)) (output n))
output (Leaf _ c) = [(c,[])]

huffman = sort .output . step . basetree

main = print $ huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]

import java.util.*;

public class Hello {
  public static void main(String[] args) {
    Tree[] array = {new Leaf('a',45),new Leaf('b',13),new Leaf('c',12),new Leaf('d',16),
                    new Leaf('e',9),new Leaf('f',5)};
    ArrayList<Tree> list = new ArrayList<Tree>(Arrays.asList(array));
    while (list.size()>1){
      Collections.sort(list);
      Tree x= list.remove(0);
      Tree y= list.remove(0);
      list.add(Node.sum(x,y));
    }
    Tree tree = list.get(0);
    List<Pair> pairlist = tree.flatten();
    Collections.sort(pairlist);
    System.out.println(pairlist);
  }
}

abstract class Tree implements Comparable<Tree> {
  protected int num;
  protected Tree(int num){
    this.num=num;
  }
  public int compareTo(Tree o){
    return this.num-o.num;
  }
  public abstract List<Pair> flatten();
}

class Leaf extends Tree {
  private char c;
  public Leaf(char c, int num){
    super(num);
    this.c=c;
  }
  public List<Pair> flatten(){
    ArrayList<Pair> list = new ArrayList<Pair>();
    list.add(new Pair(c,""));
    return list;
  };
}

class Node extends Tree {
  private Tree t1,t2;
  public Node(Tree t1,Tree t2, int num) {
    super(num);
    this.t1=t1;
    this.t2=t2;
  }
  static Node sum(Tree t1,Tree t2){
    return new Node(t1,t2,t1.num+t2.num);
  }
  private static List<Pair> flattenhelper(List<Pair> l, String s){
    List<Pair> list= new ArrayList<Pair>();
    for (Pair p:l) {
      list.add(new Pair(p.c,s+p.s));
    }
    return list;
  }  
  public List<Pair> flatten(){
    List<Pair> list= flattenhelper( t1.flatten(),"0");
    list.addAll(flattenhelper( t2.flatten(),"1"));
    return list;
  };
}


class Pair implements Comparable<Pair>{ 
  public char c; 
  public String s; 
  public Pair(char c,String s) { 
    this.c=c;
    this.s=s;
  } 
  public int compareTo(Pair o){
    if (this.c-o.c!=0) {
      return this.c-o.c;
    } else {
      return this.s.compareTo(o.s);
    }
  }
  public String toString(){
    return "("+(new Character(c)).toString()+","+s+")";
  }
}