content: -- ------------------------------------------------------------
  
  {- |
     Module     : Data.Tree.Class
     Copyright  : Copyright (C) 2005 Uwe Schmidt
     License    : MIT
  
     Maintainer : Uwe Schmidt (uwe\@fh-wedel.de)
     Stability  : experimental
     Portability: portable
  
     Interface definition for trees
  -}
  
  -- ------------------------------------------------------------
  
  module Data.Tree.Class
      ( module Data.Tree.Class )
  where
  
  -- | The interface for trees
  
  class Tree t where
      -- | tree construction: a new tree is constructed by a node attribute and a list of children
      mkTree              ::              a -> [t a] -> t a
  
      -- | leaf construction: leafs don't have any children
      --
      -- definition: @ mkLeaf n = mkTree n [] @
  
      mkLeaf              ::                       a -> t a
      mkLeaf n            = mkTree n []
      {-# INLINE mkLeaf #-}
  
      -- | leaf test: list of children empty?
  
      isLeaf              ::                     t a -> Bool
      isLeaf              = null . getChildren
      {-# INLINE isLeaf #-}
  
      -- | innner node test: @ not . isLeaf @
  
      isInner             ::                     t a -> Bool
      isInner             = not . isLeaf
      {-# INLINE isInner #-}
  
      -- | select node attribute
  
      getNode             ::                     t a -> a
  
      -- | select children
  
      getChildren         ::                     t a -> [t a]
  
      -- | edit node attribute
  
      changeNode          ::         (a -> a) -> t a -> t a
  
      -- | edit children
  
      changeChildren      :: ([t a] -> [t a]) -> t a -> t a
  
      -- | substitute node: @ setNode n = changeNode (const n) @
  
      setNode             ::                a -> t a -> t a
      setNode n           = changeNode (const n)
      {-# INLINE setNode #-}
  
      -- | substitute children: @ setChildren cl = changeChildren (const cl) @
  
      setChildren         ::            [t a] -> t a -> t a
      setChildren cl      = changeChildren (const cl)
      {-# INLINE setChildren #-}
  
      -- | fold for trees
  
      foldTree            ::  (a -> [b] -> b) -> t a -> b
  
      -- | all nodes of a tree
  
      nodesTree           ::                     t a -> [a]
      nodesTree           = foldTree (\ n rs -> n : concat rs)
      {-# INLINE nodesTree #-}
  
      -- | depth of a tree
  
      depthTree           ::                     t a -> Int
      depthTree           = foldTree (\ _ rs -> 1 + maximum (0 : rs))
  
      -- | number of nodes in a tree
  
      cardTree            ::                     t a -> Int
      cardTree            = foldTree (\ _ rs -> 1 + sum rs)
  
      -- | format tree for readable trace output
      --
      -- a /graphical/ representation of the tree in text format
  
      formatTree          ::    (a -> String) -> t a -> String
      formatTree nf n     = formatNTree' nf (showString "---") (showString "   ") n ""
  
  -- ------------------------------------------------------------
  -- |
  -- convert a tree into a pseudo graphical string representation
  
  formatNTree'    :: Tree t => (a -> String) -> (String -> String) -> (String -> String) -> t a -> String -> String
  
  formatNTree' node2String pf1 pf2 tree
      = formatNode
        . formatChildren pf2 l
      where
      n           = getNode     tree
      l           = getChildren tree
      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        = formatNTree' node2String pf0'
          indent1 = "+---"
          indent2 = "|   "
          indent3 = "    "
          indent4 = "|\n"
  
  -- eof ------------------------------------------------------------
  