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