fleurer

module BTree where
 
data BTree a b = Empty 
               | BNode {
                    kv :: (a, b), 
                    left :: BTree a b,
                    right :: BTree a b
               } 
               deriving(Show, Eq)
 
insert :: (Ord a) => (a, b) -> BTree a b -> BTree a b
insert (k,v) Empty = BNode (k, v) Empty Empty
insert (k,v) pnode@(BNode (pk, _) lnode rnode) 
    | k == pk   = pnode { kv = (k,v) }
    | k <  pk   = pnode { left  = insert (k,v) lnode }
    | k >  pk   = pnode { right = insert (k,v) rnode }
 
find :: (Ord a) => a -> BTree a b -> Maybe b
find k Empty = Nothing
find k (BNode (pk,pv) lnode rnode)
    | k == pk = Just pv
    | k <= pk = find k lnode
    | k >  pk = find k rnode
find _ _ = Nothing
 
remove :: (Ord a) => a -> BTree a b -> BTree a b
remove k Empty = Empty
remove k pnode@(BNode (pk,pv) lnode rnode) 
    | k == pk = merge lnode rnode
    | k <= pk = pnode { left = remove k lnode }
    | k >  pk = pnode { right = remove k rnode }
 
merge :: (Ord a) => BTree a b -> BTree a b -> BTree a b
merge lnode rnode = fromList $ (toList lnode) ++ (toList rnode)
 
--helper
isEmpty Empty = True 
isEmpty _     = False
 
fromList :: (Ord a) => [(a,b)] -> BTree a b
fromList = foldl (flip insert) Empty 
 
toList :: BTree a b -> [(a,b)]
toList Empty = [] 
toList (BNode (k,v) lnode rnode) = 
    (toList lnode) ++ [(k,v)] ++ (toList rnode)
 
-- for test
root = fromList $ [
    (4, "fleurer"), 
    (10, "ssword"), 
    (100, "ssword"), 
    (2, "xx")]