using System.IO;
using System.Collections;
using System.Windows.Forms;

module M {
    
    variant Tree {
        | Nodet {
            Left : Tree;
            Elem : int;
            Ch : int;
            Right : Tree;
          }
        | Nilt
    }
    
    meld (t1 : Tree, t2 : Tree) : Tree {
        match ((t1, t2)) {
            | (Tree.Nodet(_, n, c, _), Tree.Nodet(_, n', _, _)) => Tree.Nodet(t1, n + n', c, t2);
            | (Tree.Nodet(_, _, _, _), Tree.Nilt) => t1;
            | (Tree.Nilt, Tree.Nodet(_, _, _, _)) => t2;
            | (Tree.Nilt, Tree.Nilt) => Tree.Nilt();
        }
    }

    code_help(t : Tree, i : string, ar : array [string]) : void {
       match(t) {
            | Tree.Nodet(Tree.Nilt, _, c, Tree.Nilt) => ar[c] = i; //printf("Kod dla litery %c : %s\n", (c:>char), i);
            | Tree.Nodet(l, _, _, r) => code_help(l, i + "0", ar); code_help(r, i + "1", ar);
            | _ => ();
       }
    }

    code (t : Tree) : array [string] {
        def ar = array(257);
        for(mutable i = 0; i <= 256; i = i + 1)
           ar[i] = ""; 
        code_help(t, "", ar);
        ar;
    }

   variant Heap {
      | Nodeh { 
            Left : Heap;
            t : Tree;
            Right : Heap;
            h : int;
            n : int;
        }
      | Nilh
   }
   
   pow2(n : int) : int {
      if (n == 0) 1 
      else {def m = pow2(n/2); if ((n % 2) == 0) m*m else 2*m*m}
   }
   
   insert(heap : Heap, tree: Tree) : Heap {
      match(tree){ |Tree.Nodet(_, e, _, _) => 
      match(heap) {
         | Heap.Nilh => Heap.Nodeh(Heap.Nilh(), tree, Heap.Nilh(), 1, 1);
         | Heap.Nodeh(Heap.Nilh, (Tree.Nodet(_, e', _, _)) as tree', Heap.Nilh, 1, 1) =>    
              if (e < e') Heap.Nodeh(Heap.Nodeh(Heap.Nilh(), tree', Heap.Nilh(), 1, 1), tree, Heap.Nilh(), 2, 2)
              else Heap.Nodeh(Heap.Nodeh(Heap.Nilh(), tree, Heap.Nilh(), 1, 1), tree', Heap.Nilh(), 2, 2);
         | Heap.Nodeh(lh, (Tree.Nodet(_, e', _, _)) as tree', rh, h, n) => def m = pow2(h);
              if (n == m - 1)  
                  if (e' < e) Heap.Nodeh(insert(lh, tree), tree', rh, h+1, n+1)
                  else Heap.Nodeh(insert(lh, tree'), tree, rh, h+1, n+1)
              else if (n < 3*m/4 - 1)
                  if (e' < e) Heap.Nodeh(insert(lh, tree), tree', rh, h, n+1)
                  else Heap.Nodeh(insert(lh, tree'), tree, rh, h, n+1)
              else 
                  if (e' < e) Heap.Nodeh(lh, tree', insert(rh, tree), h, n+1)
                  else Heap.Nodeh(lh, tree, insert(rh, tree'), h, n+1);
         | _ => Heap.Nilh();
      }
      | _ => Heap.Nilh();}
      
   }

   union(heap1 : Heap, heap2 : Heap) : Heap {
      match(heap2) {
            | Heap.Nodeh(lh, tree, rh, _, _) => 
              def h = union(union(insert(heap1, tree), lh), rh);
               h;
            | Heap.Nilh => heap1;
      }
   }
   
   min(heap : Heap) : Tree {
      match(heap) {
            | Heap.Nodeh(_, tree, _, _, _) => tree;
            | _ => Tree.Nilt();
      }
   }
   
   extract_min(heap : Heap) : Heap{
      match(heap) {
            | Heap.Nodeh(lh, _, rh, _, _) => union(lh, rh);
            | Heap.Nilh => Heap.Nilh();
      }
   }

   make_heap_of_trees(ar : array [int]) : Heap {
      mutable heap = Heap.Nilh();
      for(mutable i = 1; i <= 256; i = i + 1) {
         when(ar[i] > 0)
            heap = insert(heap, Tree.Nodet(Tree.Nilt(), ar[i], i, Tree.Nilt()));
      };
      heap;
   }
   
   rawHoofman(heap : Heap) : Tree {
      mutable h = heap;
      mutable t1 = Tree.Nilt();
      mutable t2 = Tree.Nilt();
      mutable m = 0;
      
      match(h){
         | Heap.Nodeh(_, _, _, _, n) => m = n;
         | _ => m = 0;
      };
      while(m > 1) {
         t1 = min(h);
         h = extract_min(h);
         t2 = min(h);
         h = extract_min(h);
         t1 = meld(t1, t2);
         h = insert(h, t1);
         match(h){
            | Heap.Nodeh(_, _, _, _, n) => m = n;
            | _ => m = 0;
         };
      };
      t1;
   }
   
   hoofman(ar : array [int]) : array [string] {
      def heap = make_heap_of_trees(ar);
      def tree = rawHoofman(heap);
      def ar = code(tree);
      ar;
   }
   
   count(f : Stream) : array [int] {
   def ar = array(257);
   mutable c = f.ReadByte();
   while (c != -1)
   {
      ar[c] = ar[c] + 1;
      c = f.ReadByte();
   };
   ar;
   }
   
   str8ToByte(bufor : array[char]) : int {
   mutable r = 0;
   for(mutable i = 0; i <= 7; i = i + 1) 
      if(bufor[i] == '0')
         r = r*2
      else
         r = r*2 + 1;
   r;
   }
   
   
   
   header(a : array [string], f : Stream) : void {
      mutable str = "";
      mutable c = ' ';
      
      for(mutable i = 0; i <= 255; i = i + 1) {
         str = a[i];
         c = (str.Length :> char);
         f.WriteByte((c :> System.Byte));           //wypisz ilosc bitow kodu
         nodeToDisc(str, f);
      }
   }
   
   nodeToDisc(bbufor : string, f : Stream) : void {
      mutable byteQuantity = bbufor.Length/8;   
      def byteChar = array(9);
      mutable d = 0;
      mutable bufor = bbufor;
      
      while(byteQuantity > 0) {
         bufor.CopyTo(0, byteChar, 0, 8);
         bufor = bufor.Remove(0, 8);
         d = str8ToByte(byteChar);
         f.WriteByte((d :> System.Byte));
         byteQuantity = byteQuantity - 1;      
      };
   
      mutable l = bufor.Length;
      when(l > 0) {
         for(mutable i = l + 1; i <= 8; i = i + 1) 
            bufor = bufor + "0";
         bufor.CopyTo(0, byteChar, 0, 8);
         d = str8ToByte(byteChar);
         f.WriteByte((d :> System.Byte));
      };
   }
   
   compress(a : array [string], f : Stream, f2 : Stream) : void {
   mutable c = f.ReadByte();
   mutable bufor = "";
   mutable k = 0;
   def byteChar = array(9);
   mutable d = 0;
   
   while(c != -1) {
   bufor = bufor + a[c];
   k = bufor.Length/8;
   
   
   while(k > 0) {
      bufor.CopyTo(0, byteChar, 0, 8);
      bufor = bufor.Remove(0, 8);
      d = str8ToByte(byteChar);
      f2.WriteByte((d :> System.Byte));
      k = k - 1;      
   };
   c = f.ReadByte();
   };
   
   k = bufor.Length;
   when(k > 0) {
      for(mutable i = k; i <= 8; i = i + 1) 
            bufor = bufor + "0";
      bufor.CopyTo(0, byteChar, 0, 8);
      d = str8ToByte(byteChar);
      f2.WriteByte((d :> System.Byte));
   };
   f2.WriteByte((k :> System.Byte));
   }
   
  
   
   Main () : void {
   
      mutable openFileDialog = OpenFileDialog();
      openFileDialog.InitialDirectory = Application.StartupPath;
      openFileDialog.Filter = "*.*|*.*";
      when (openFileDialog.ShowDialog() == DialogResult.OK)
      {
         def f = File.Open(openFileDialog.FileName, FileMode.Open, FileAccess.Read, FileShare.None);
         def frequency = count(f);
         def codes = hoofman(frequency);
         f.Position = (0 :> System.Int64);
         def f2 = FileStream(openFileDialog.FileName + ".dwo", FileMode.Create);
         header(codes, f2); /*AHTUNG f ma byc plikiem wyjsciowym!!! */
         compress(codes, f, f2);
         f.Close();
         f2.Close();
      }
   }
}