---
-- This module provides binary trees and
-- some important manipulation functions for them.
-- @version 0.1
module BTree where


import Countable
import List (nub)


-- documentation is below, using an @doc tag.
data BTree a = Empty | Node a (BTree a) (BTree a)



--- @doc BTree
-- A binary tree.
-- A binary tree can either be empty or it can consist of a node
-- and two subtrees. The empty tree is represented by <code>Empty</code>,
-- whereas <code>Node value left right</code> represents a node with
-- value <code>value</code> and the left and right subtrees <code>left</code>
-- and <code>right</code>.
-- To construct the tree
-- <pre>
--            1
--           / \
--          2   3
--             /
--            4
-- </pre>
-- one can write:
-- <pre>
-- tree = Node 1 (Node 2 Empty
--                       Empty)
--               (Node 3 (Node 4 Empty Empty)
--                       Empty)
-- </pre>
--
-- @cons Empty                  -  the empty tree.
-- @cons Node value left right  -  a node of the tree.





---
-- Performs a general calculation on a binary tree.
-- If the given tree is empty, the value of <code>init</code> is returned.
-- For a non-empty tree, the function <code>f</code> is applied to the
-- the result of the recursive application of <code>btreeop</code> to the
-- left subtree, the top node's value, and the result of the
-- recursive application of <code>btreeop</code> on the right subtree
-- (in that order). The result of the application of <code>f</code> to
-- those three values is returned.
--
-- @param f     -  the combining function.
-- @param init  -  the initial value.
-- @param tree  -  the tree to traverse.
-- @return res  -  the result of the recursive tree traversal.
btreeop :: (b -> a -> b -> b) -> b -> BTree a -> b
btreeop _ init  Empty = init
btreeop f init (Node v left right) =
    f (btreeop f init left) v (btreeop f init right) 

---
-- Converts a tree to a list using inorder.
-- The empty tree is converted to the empty list.
-- For non-empty tree the left subtree is converted to a list, followed
-- by the node's value, followed by the inorder representation of the right
-- subtree.
--
-- @param tree    - the tree to be converted.
-- @return inlist - the inorder representation of the tree.

inorder :: BTree a -> [a]
inorder = btreeop (\x y z -> x ++ (y:z)) []

---
-- Converts a tree to preorder.
--
-- @param tree     - the tree to be converted.
-- @return prelist - the preorder representation of the tree.
preorder :: BTree a -> [a]
preorder = btreeop (\x y z -> y:(x++z)) []

---
-- Make binary trees countable.
instance Eq a => Countable (BTree a) where
    ---
    -- Counts the number of different components in the tree.
    -- Each value in the tree is considered to be one component; but
    -- duplicte values are only counted once.
    -- @param tree     - the tree to count.
    -- @return numcomp - the number of components in the tree.
    count = count . nub . inorder 


---
-- Loads a binary tree from disk.
-- The given file is opened and a binary tree with integers as node values
-- is loaded from it. The resulting tree is returned.
--
-- @param file    -  the name of the file to load.
-- @monadic tree  -  the binary tree read from disk.
loadBTree :: String -> IO (BTree Integer)
loadBTree file = return Empty