{-
 - Tree data type. Every node is accessible from any other node.
 -}
module Hmpf.Tree 
                ( mkTree 
		, Tree 
		, up 
		, top 
		, branches 
		, build 
		, index 
		, isLeaf 
		, isRoot 
		, val 
		, path 
		, flatten ) where

import Data.List (elemIndex)
import Data.Maybe (fromJust)

data Tree a = Root (Branch a) |
              Node (Tree a) a (Branch a)

type Branch a = [Tree a]


instance Eq a => Eq (Tree a) where
 t == t' = (flatten t) == (flatten t')

up :: Tree a -> Tree a 
up (Node t _ _) = t
up x = x

top (Root b) = Root b
top (Node p _ _) = top p

branches :: Tree a -> [Tree a]
branches (Root b) = b
branches (Node _ _ b) = b

--True if it is the root node
isRoot (Root _) = True
isRoot _ = False

--True if the node has no children
isLeaf t = (length . branches $ t ) == 0

val :: Tree a -> Maybe a
val (Node r x b) = Just x
val _ = Nothing

mkTree :: ( a -> [(b, a)] ) -> a -> Tree b
mkTree f x = 
 let root = Root children
     children = map (mkBranches root f) (f x)
 in root

mkBranches :: Tree b -> ( a -> [(b,a)] ) -> (b, a) -> Tree b
mkBranches root f (n,x)  = 
 let node = Node root n children
     children = map (mkBranches node f) (f x)
 in node


build :: Eq a => [[a]] -> [(a,[[a]])]
build lst = 
 let lst' = filter (not.null) $ lst
 in case lst' of
     [] -> []
     (x:xs) -> let c = head x
                   lst'' = map tail . filter (\i -> head i ==c) $ (x:xs)
		   rest = filter (\i -> head i/=c) (x:xs)
	       in (c,lst''):(build rest)


path :: Tree a -> [a]
path t =
 case val t of
  Nothing -> []
  Just x  -> x:(path . up $ t )

flatten :: Tree a -> [[a]]
flatten tree = 
 case val tree of
  Nothing -> rest
  Just x -> case (branches tree) of
             [] -> [[x]]
	     _  -> map (x:) rest
 where
  rest = concat . map flatten . branches $ tree

index :: Eq a => Tree a -> Int
index (Root _) = 0
index tree = fromJust . elemIndex tree . branches . up $ tree




eol = '^'

t = mkTree build . map ( ++[eol] ) $ ["li","lic"]