module MerkleTree where

import Hash (hash256)
import Control.Monad.State
import Control.Monad.Identity

type Tx   = String
type Hash = String
data Node = Empty |
            Leaf   {hash :: Hash, tx :: Tx} |
            Branch {hash :: Hash, left :: Node, right :: Node}
            deriving (Show, Eq)
type TreeState  = StateT [Node]

merkleTree :: [Tx] -> Node
merkleTree tx = evalState buildTree ls
    where ls = map toLeaf tx

buildTree :: TreeState Identity Node
buildTree = do
    s <- get
    if length s == 1
        then return $ head s
        else do
            ns <- newLayer
            put ns
            buildTree

newLayer :: TreeState Identity [Node]
newLayer = do
    s <- get
    if null s
        then return []
        else do
            n  <- newNode
            ns <- newLayer
            return $ n:ns

newNode :: TreeState Identity Node
newNode = state f
    where f [t]      = let h = hash256 $ hash t ++ hash t
                       in (Branch h t Empty,[])
          f (l:r:ts) = let h = hash256 $ hash l ++ hash r
                       in (Branch h l r,ts)



-- テスト用
toLeaf tx = Leaf (hash256 tx) tx
sample = ["a" ,"b", "c", "d", "e","f","g"]
leaves = map toLeaf sample
tree = merkleTree sample