    {-# LANGUAGE DeriveDataTypeable #-}

    -- ------------------------------------------------------------

    {- |
       Module     : Data.Tree.NTree.TypeDefs
       Copyright  : Copyright (C) 2005-2008 Uwe Schmidt
       License    : MIT

       Maintainer : Uwe Schmidt (uwe\@fh-wedel.de)
       Stability  : experimental
       Portability: portable

       Interface definition for trees

       n-ary tree structure (rose trees)

    -}

    -- ------------------------------------------------------------

    module Data.Tree.NTree.TypeDefs
        ( module Data.Tree.Class
        , module Data.Tree.NTree.TypeDefs
        )
    where

    import Control.DeepSeq

    import Data.Tree.Class
    import Data.Typeable

    -- | n-ary ordered tree (rose trees)
    --
    -- a tree consists of a node and a possible empty list of children.
    -- If the list of children is empty, the node is a leaf, else it's
    -- an inner node.
    --
    -- NTree implements Eq, Ord, Show and Read

    data NTree  a	= NTree a (NTrees a)
        deriving
        (Eq, Ord, Show, Read, Typeable)

    -- | shortcut for a sequence of n-ary trees

    type NTrees   a	= [NTree a]

    -- ------------------------------------------------------------

    instance (NFData a) => NFData (NTree a) where
        rnf (NTree n cl)			= rnf n `seq` rnf cl

    -- | NTree implements class Functor

    instance Functor NTree where
        fmap f ~(NTree n cl)		= NTree (f n) (map (fmap f) cl)

    -- | Implementation of "Data.Tree.Class" interface for rose trees

    instance Tree NTree where
        mkTree n cl				= NTree n cl

        getNode           ~(NTree n _ )	= n
        getChildren       ~(NTree _ cl)	= cl

        changeNode     cf ~(NTree n cl)	= NTree (cf n) cl
        changeChildren cf ~(NTree n cl)	= NTree n (cf cl)

        foldTree        f ~(NTree n cs)	= f n (map (foldTree f) cs)

        nodesTree		= foldTree (\ n rs -> n : concat rs)
        depthTree		= foldTree (\ _ rs -> 1 + maximum (0 : rs))
        cardTree		= foldTree (\ _ rs -> 1 + sum rs)
        formatTree nf n	= formatNTreeF nf (showString "---") (showString "   ") n ""

    -- ------------------------------------------------------------
    -- |
    -- convert a tree into a pseudo graphical string reprsentation

    formatNTreeF	:: (node -> String) -> (String -> String) -> (String -> String) -> NTree node -> String -> String

    formatNTreeF node2String pf1 pf2 (NTree n l)
        = formatNode
          . formatChildren pf2 l
        where
        formatNode	= pf1 . foldr (.) id (map trNL (node2String n)) . showNL
        trNL '\n'	= showNL . pf2
        trNL c	= showChar c
        showNL	= showChar '\n'
        formatChildren _ []
    	= id
        formatChildren pf (t:ts)
    	| null ts
    	    = pfl'
    	      . formatTr pf2' t
    	| otherwise
    	    = pfl'
    	      . formatTr pf1' t
    	      . formatChildren pf ts
    	where
    	pf0'	= pf . showString indent1
    	pf1'	= pf . showString indent2
    	pf2'	= pf . showString indent3
    	pfl'	= pf . showString indent4
    	formatTr	= formatNTreeF node2String pf0'
    	indent1 = "+---"
    	indent2 = "|   "
    	indent3 = "    "
    	indent4 = "|\n"

    -- eof ------------------------------------------------------------