class Node
    # binary tree representation
    attr_accessor :value, :left, :right
    def initialize(value=nil, left=nil, right=nil)
        @value, @left, @right = value, left, right
    end
    def leaf?
        return @left == nil && @right == nil
    end
end

def occurrences(text)
    # return an ordered array of [occurrences, character] descending order
    occ = Hash.new(0)
    text.scan /./m do |b| occ[b] += 1 end 
    return occ.keys.map {|k| [occ[k], k]}.sort
end

def huffman(occlist)
    # build a huffman encoding binary tree from the occurance list
    if occlist.empty? then
        puts "warning: no occurrences provided to build huffman tree"
        return nil
    end

    # create the initial queue with leaves, trees contain assoc lists
    leaves = occlist.map {|entry| Node.new([entry]) }
    interior = []
    deq = lambda {
        if (leaves.length > 0) then leaves.delete_at 0 
        else interior.delete_at 0 end
    }

    # create interior nodes
    while leaves.length + interior.length > 1
        l, r = deq.call, deq.call
        node = Node.new(l.value + r.value, l, r)
        interior << node
    end

    deq.call
end

def bits(ht, sym)
    # given a tree and symbol return an array of encoded bits  
    def bits_internal(ht, sym, enc)
        return enc, nil if not ht
        return enc, ht.value if ht.leaf?

        if ht.left.value.rassoc(sym) != nil
            enc << 0
            bits_internal(ht.left, sym, enc)
        else
            enc << 1
            bits_internal(ht.right, sym, enc)
        end
    end

    if ht.value.rassoc(sym) == nil
        puts "warning: no binary encoding for: '#{sym}'"
        return []
    end

    enc, value = bits_internal(ht, sym, [])
    if value[0][1] != sym 
        puts "warning: binary encoding: #{enc.inspect}, value: #{value.inspect} does not match '#{sym}'"
        return []    
    else
        return enc
    end
end

def decode(ht, bits)
    if ht.leaf? 
        return ht.value[0][1]
    end

    case bits[0]
        when 0 
            decode(ht.left, bits[1..bits.length-1])
        when 1 
            decode(ht.right, bits[1..bits.length-1])
    end
end

if $0 == __FILE__

text = <<TEXT
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Sed est nulla, suscipit vel, tempus sit amet, viverra sit amet, dui. Nunc ultrices, purus vulputate luctus sodales, mauris augue elementum diam, in ornare neque nisi pharetra lectus. In hac habitasse platea dictumst. Phasellus justo turpis, laoreet id, semper at, convallis a, nisi. Duis iaculis erat et mauris. Donec a arcu. Ut sed risus vel mi mollis vehicula. Aenean laoreet, lorem dapibus aliquam ultrices, ante velit vestibulum sem, vel molestie arcu elit sit amet nunc. Vivamus venenatis placerat dui. Mauris porttitor varius velit. 
TEXT

# build a huffman encoding tree
ht = huffman(occurrences(text))

# measure the compression
bitsum = 0
for c in text.scan /./m
    bitsum += bits(ht, c).length
end

orig = text.length
new = bitsum / 8.0
printf("original %s bytes, huffman encoded: %s bytes, ratio: %.2f%%", 
    orig, new, new/orig*100)

end