-------------------------------------------------------------------------
--                              
--         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 :: [(Char, Int)] -> Tree
makeTree = [Tree] -> Tree
makeCodes ([Tree] -> Tree)
-> ([(Char, Int)] -> [Tree]) -> [(Char, Int)] -> Tree
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Char, Int)] -> [Tree]
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 :: [(Char, Int)] -> [Tree]
toTreeList = ((Char, Int) -> Tree) -> [(Char, Int)] -> [Tree]
forall a b. (a -> b) -> [a] -> [b]
map ((Char -> Int -> Tree) -> (Char, Int) -> Tree
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Char -> Int -> Tree
Leaf)

-- The value of a tree.                     

value :: Tree -> Int

value :: Tree -> Int
value (Leaf Char
_ Int
n)   = Int
n
value (Node Int
n Tree
_ Tree
_) = Int
n

-- Pair two trees.                          

pair :: Tree -> Tree -> Tree

pair :: Tree -> Tree -> Tree
pair Tree
t1 Tree
t2 = Int -> Tree -> Tree -> Tree
Node (Int
v1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
v2) Tree
t1 Tree
t2
             where
             v1 :: Int
v1 = Tree -> Int
value Tree
t1
             v2 :: Int
v2 = Tree -> Int
value Tree
t2

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

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

insTree :: Tree -> [Tree] -> [Tree]
insTree Tree
t [] = [Tree
t]
insTree Tree
t (Tree
t1:[Tree]
ts) 
  | (Tree -> Int
value Tree
t Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Tree -> Int
value Tree
t1)    = Tree
tTree -> [Tree] -> [Tree]
forall a. a -> [a] -> [a]
:Tree
t1Tree -> [Tree] -> [Tree]
forall a. a -> [a] -> [a]
:[Tree]
ts
  | Bool
otherwise                = Tree
t1 Tree -> [Tree] -> [Tree]
forall a. a -> [a] -> [a]
: Tree -> [Tree] -> [Tree]
insTree Tree
t [Tree]
ts
--  
-- Amalgamate the front two elements of the list of trees.      

amalgamate :: [ Tree ] -> [ Tree ]

amalgamate :: [Tree] -> [Tree]
amalgamate ( Tree
t1 : Tree
t2 : [Tree]
ts )
  = Tree -> [Tree] -> [Tree]
insTree (Tree -> Tree -> Tree
pair Tree
t1 Tree
t2) [Tree]
ts

-- Make codes: amalgamate the whole list.               

makeCodes :: [Tree] -> Tree

makeCodes :: [Tree] -> Tree
makeCodes [Tree
t] = Tree
t
makeCodes [Tree]
ts = [Tree] -> Tree
makeCodes ([Tree] -> [Tree]
amalgamate [Tree]
ts)