Skip to content

Instantly share code, notes, and snippets.

@bojanrajkovic
Created October 28, 2010 04:31
Show Gist options
  • Save bojanrajkovic/650639 to your computer and use it in GitHub Desktop.
Save bojanrajkovic/650639 to your computer and use it in GitHub Desktop.
using System; using System.IO; using System.Linq; using System.Collections.Generic;
public class HuffmanNode { public char? v; public int c; public HuffmanNode l, r; }
namespace Huffman {
class HuffmanCoder {
static int C<T> (IEnumerable<T> c) { return c.Count (); }
static T D<T> (Queue<T> q) { return q.Dequeue (); }
static T P<T> (Queue<T> q) { return q.Peek (); }
static void E<T> (Queue<T> q, T t) { q.Enqueue (t); }
public static Queue<HuffmanNode> GetTreeLINQ (string data) {
var p = new Queue<HuffmanNode> (data.GroupBy (_ => _).OrderBy (_ => C (_)).Select (_ => new HuffmanNode { v = _.Key, c = C (_) }));
var q = new Queue<HuffmanNode> ();
Func<Queue<HuffmanNode>, Queue<HuffmanNode>, HuffmanNode> f = (q1, q2) => { return C (q2) == 0 || (C (q1) > 0 && C (q2) > 0 && P (q1).v < P (q2).v) ? D (q1) : D (q2); };
while (C (p) >= 1 || C (q) > 1) { HuffmanNode l = f (p, q), r = f (p, q), t = new HuffmanNode { v = null, c = l.c + r.c, l = l, r = r }; E (q, t); }
return q;
}
public static void PrintNode (HuffmanNode n) {
Console.WriteLine ("Address: {4}, Data: {0}, {1}, {2}, {3}", n.v, n.c, n.l != null ? n.l.GetHashCode () : (int?)null, n.r != null ? n.r.GetHashCode () : (int?)null, n.GetHashCode ());
if (n.l != null) PrintNode (n.l);
if (n.r != null) PrintNode (n.r);
}
public static string HuffmanCodingLINQ (string d) {
var t = GetTreeLINQ (d);
PrintNode (P (t));
return string.Empty;
}
}
}
/**
With better type inference, GetTreeLinq could look like this:
public static Queue GetTreeLINQ (string data) {
p = new Queue (data.GroupBy (_ => _).OrderBy (_ => C (_)).Select (_ => new HuffmanNode { v = _.Key, c = C (_) })), q = new Queue ();
f = (q1, q2) => { return C (q2) == 0 || (C (q1) > 0 && C (q2) > 0 && P (q1).v < P (q2).v) ? D (q1) : D (q2); };
while (C (p) >= 1 || C (q) > 1) { var l = f (p, q), r = f (p, q), t = new HuffmanNode { v = null, c = l.c + r.c, l = l, r = r }; E (q, t); }
return q;
}
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment