#!/usr/bin/python

#
# Program na vytvorenie Huffmanovho kodu
#


#
# utriedenie zoznamu vzostupne podla pravdepodobnosti
#
def sort(tbl):
  for i in range(0,len(tbl)):
    for j in range(i+1,len(tbl)):
      if tbl[i][0] > tbl[j][0]:
        temp = tbl[i]
        tbl[i] = tbl[j]
        tbl[j] = temp

#
# vytvorenie Huffmanovho kodu
#
def huffman(p):
  # pole kodovych slov
  code = [ "" for i in range(0, len(p)) ]
  # pomocne pole usporiadanych dvojic (prvadepodobnost, zoznam znakov)
  tbl = [ [p[i], [i]] for i in range(0, len(p))]

  # opakujem pokial neostane len jeden prvok (korenovy vrchol)
  while len(tbl) > 1:

    # usporiadam pole podla pravdepodobnosti
    sort(tbl)

    # vsetkym znakom s 1. najmensou pravdep. vlozim na zaciatok kod. slova 0
    for i in tbl[0][1]:
      code[i] = '0' + code[i]

    # vsetkym znakom s 2. najmensou pravdep. vlozim na zaciatok kod. slova 1
    for i in tbl[1][1]:
      code[i] = '1' + code[i]

    # zlucim prve dva prvky pomocneho pola
    # pravdepodobnosti scitam a zoznam znakov zjednotim
    tbl[0][0] += tbl[1][0]
    tbl[0][1].extend(tbl[1][1])
    tbl.remove(tbl[1])

  # hotovo
  return code

# pravdepodobnosti znakov zdroja
p = [0.11,0.20,0.15,0.07,0.18,0.19,0.01,0.09]

# Huffmanov kod pre zadane pravdepodobnosti
c = huffman(p)

# vypis tabulky a vypocet dlzky kodu
l = 0.0
for i in range(0,len(p)):
  print '%2d %.4f %2d %7.4f %-10s' % (i, p[i], len(c[i]), p[i] * len(c[i]), c[i])
  l += p[i] * len(c[i])
print '-----------------------------'
print 'l(K) = %.4f' % (l)