-------------------------------------------------------------------------
-- 								
--         MakeTree.hs							
-- 								
          Turn a frequency table into a  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) 


-----------------------------------------------------------------------
 								
         MakeTree.hs							
 								
 								
 							
-----------------------------------------------------------------------
 Convert the trees to a list, then amalgamate into a single	
 tree.								
 The value of a tree.						
 Pair two trees.							
 Insert a tree in a list of trees sorted by ascending value.	
 	
 Make codes: amalgamate the whole list.				
          Turn a frequency table into a  tree 			
          ( c ) Addison - Wesley , 1996 - 2011 . 					

module MakeTree ( makeTree ) where

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


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)


value :: Tree -> Int

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


pair :: Tree -> Tree -> Tree

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


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


makeCodes :: [Tree] -> Tree

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

