gistfile1.txt

using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Runtime.InteropServices;

public class HuffmanNode {
	static int pad = Marshal.SizeOf (typeof (IntPtr)) * 2;
	static string fmt = String.Format ("*: 0x{{4:X{0}}} v: {{0:0}} c: {{1}} l: 0x{{2:X{0}}} r: 0x{{3:X{0}}}", pad);
	public char? v; public int c; public HuffmanNode l, r; 
	public static HuffmanNode operator + (HuffmanNode a, HuffmanNode b) { return new HuffmanNode { v = null, c = a.c + b.c, l = a, r = b }; }
	public static explicit operator int (HuffmanNode n) { return n == null ? 0 : n.GetHashCode (); }
	internal void Print () { Console.WriteLine (fmt, v ?? '-', c, (int) l, (int) r, GetHashCode ()); if (l != null) l.Print (); if (r != null) r.Print (); }
}

namespace Huffman {
	public class HuffmanCoder {
		public HuffmanNode r;
		
		public HuffmanCoder (string d) { r = GetTree (d); }	
		
		IEnumerable<HuffmanNode> Frequencies (string d) { return d.GroupBy (_ => _).OrderBy (_ => _.Count ()).ThenBy (_ => _.Key).Select (_ => new HuffmanNode { v = _.Key, c = _.Count () }); }
		HuffmanNode F (Queue<HuffmanNode> q1, Queue<HuffmanNode> q2) { return q2.Count == 0 || (q1.Count > 0 && q2.Count > 0 && q1.Peek ().v < q2.Peek ().v) ? q1.Dequeue () : q2.Dequeue (); }
		public void PrintTree () { r.Print (); }
		
		public HuffmanNode GetTree (string data) {
			Queue<HuffmanNode> p = new Queue<HuffmanNode> (Frequencies (data)), q = new Queue<HuffmanNode> ();
			while (p.Any () || q.Count > 1) { HuffmanNode l = F (p, q), r = F (p, q), t = l + r; q.Enqueue (t); }
			return q.Dequeue ();
		}	
	}
	
	class HuffmanTest {
		public static void Main (string[] args) {
			if (args.Length == 1) {
				new HuffmanCoder (File.ReadAllText (args[0])).PrintTree ();
			} else {
				string line;
				while ((line = Console.ReadLine ()) != string.Empty) new HuffmanCoder (line).PrintTree ();
			}
		}
	}
}