-------------------------------------------------------------------------
-- 								
--         MakeTree.hs							
-- 								
--         Turn a frequency table into a Huffman tree			
-- 								
--         (c) Addison-Wesley, 1996-2011.					
-- 							
-------------------------------------------------------------------------

module MakeTree ( makeTree ) where

import Types ( Tree(Leaf,Node), Bit(L,R), HCode, Table )

-- Convert the trees to a list, then amalgamate into a single	
-- tree.								

makeTree :: [ (Char,Int) ] -> Tree

makeTree = makeCodes . toTreeList

-- Huffman codes are created bottom up: look for the least		
-- two frequent letters, make these a new "isAlpha" (i.e. tree)	
-- and repeat until one tree formed.				

-- The function toTreeList makes the initial data structure.		

toTreeList :: [ (Char,Int) ] -> [ Tree ]

toTreeList = map (uncurry Leaf)

-- The value of a tree.						

value :: Tree -> Int

value (Leaf _ n)   = n
value (Node n _ _) = n

-- Pair two trees.							

pair :: Tree -> Tree -> Tree

pair t1 t2 = Node (v1+v2) t1 t2
             where
             v1 = value t1
             v2 = value t2

-- Insert a tree in a list of trees sorted by ascending value.	

insTree :: Tree -> [Tree] -> [Tree]

insTree t [] = [t]
insTree t (t1:ts) 
  | (value t <= value t1)    = t:t1:ts
  | otherwise                = t1 : insTree t ts
-- 	
-- Amalgamate the front two elements of the list of trees.		

amalgamate :: [ Tree ] -> [ Tree ]

amalgamate ( t1 : t2 : ts )
  = insTree (pair t1 t2) ts

-- Make codes: amalgamate the whole list.				

makeCodes :: [Tree] -> Tree

makeCodes [t] = t
makeCodes ts = makeCodes (amalgamate ts)