{-# 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 ------------------------------------------------------------