---
--  This module provides breadth-first-search for binary
--  trees.
--  @version 0.2
--  @see findBFS
module BFS where


import BTree

---
-- Performs a lookup in a tree using breadth-first-search.
-- The node values of the tree are viewed as (key, value) pairs.
-- The first node matching the value of <code>key</code> is used to
-- select the return value. If no matching key is found in the entire
-- tree, <code>Nothing</code> is returned.
--
-- @param tree    -  the tree holding (key, value) pairs.
-- @param key     -  the key to look for.
-- @return value  -  <code>Just v</code>, if <code>v</code> is
--                   associated with <code>key</code> in the tree,
--                    <code>Nothing</code> if no such element exists.
findBFS :: Eq a => BTree (a, b) -> a -> Maybe b
findBFS tree key = lookup key (breadthfirst tree)

---
-- Converts a tree to a &quot;breadth first list&quot;.
-- @param tree      -  the tree.
-- @return bfslist  -  the tree in bredth first order.
breadthfirst :: BTree a -> [a]
breadthfirst tree = bf [tree]
    where
    bf []                = []
    bf (Empty      : ts) = bf ts
    bf (Node v l r : ts) = v : bf (ts ++ [l,r])