content: -- ------------------------------------------------------------
  
  {- |
     Module     : 
     Copyright  : Copyright (C) 2011 Uwe Schmidt
     License    : MIT
  
     Maintainer : Uwe Schmidt (uwe\@fh-wedel.de)
     Stability  : experimental
     Portability: portable
  
     Space and time efficient editing of rose trees
  -}
  
  -- ------------------------------------------------------------
  
  module Data.Tree.NTree.Edit
  where
  
  import Data.Maybe
  
  import Data.Tree.NTree.TypeDefs
  
  -- import           Debug.Trace
  
  
  -- | editNTreeBottomUp is a space optimized tree edit function
  --
  -- The nodes in a tree are visited bottom up. An edit function is applied to
  -- all nodes. A Nothing result of the editing function indicates no changes.
  -- This is used to share the input tree within the resulting tree.
  --
  -- The following law holds:
  --
  -- > editNTreeBottomUp (const Nothing) t == [t]
  --
  -- In this case the resulting tree does not only represent the same value
  -- but it is the same machine value (relative to some evaluations of closures
  -- during the tree walk
  --
  -- With a simple fold like editing function the whole tree would be reconstructed
  -- in memory
  
  editNTreeBottomUp               :: (NTree a -> Maybe [NTree a]) -> NTree a -> [NTree a]
  editNTreeBottomUp f t0          = maybe [t0] id . editNTreeBU $ t0
      where
  
   -- editNTreeBU                 :: NTree a -> Maybe [NTree a]
      editNTreeBU t@(NTree n cs)
          | isNothing r'
            &&
            isJust cl'            = Just [t']                     -- children have been change but not the node itself
          | otherwise             = r'                            -- nothing has been changes or node has been changed 
          where
          cl'                     = editNTreesBU cs               -- the edited children
          t'                      = case cl' of                   -- the node to be processed with f
                                    Nothing       -> t            -- possibly with the new children (bottom up)
                                    Just cs'      -> NTree n cs'
          r'                      = f t'                          -- the edited result
  
   -- editNTreesBU                :: [NTree a] -> Maybe [NTree a]
      editNTreesBU []             = Nothing
      editNTreesBU (t : ts)       = mergeRes
                                    (editNTreeBU  t )
                                    (editNTreesBU ts)
          where
          mergeRes r'             = case r' of
                                    Nothing       -> maybe Nothing (Just . (t :))
                                    Just ts'      -> Just . (ts' ++) . fromMaybe ts
  
  
  -- | A space optimized map for NTrees
  --
  -- Subtrees, that are not changed are reused in the resulting tree
  -- See also: editNTreeBottomUp
  
  mapNTree'                       :: (a -> Maybe a) -> NTree a -> NTree a
  mapNTree' f t0                  = maybe t0 id . map' $ t0
      where
  
      -- map'                     :: NTree a -> Maybe (NTree a)
      map' (NTree n cs)           = mergeRes (f n) (maps' cs)
          where
          mergeRes Nothing Nothing        = Nothing
          mergeRes Nothing (Just cs')     = Just (NTree n             cs')
          mergeRes (Just n') cl           = Just (NTree n' (fromMaybe cs cl))
  
      -- maps'                    :: [NTree a] -> Maybe [NTree a]
      maps' []                    = Nothing
      maps' (t : ts)              = mergeRes
                                    (map'  t )
                                    (maps' ts)
          where
          mergeRes r'             = case r' of
                                    Nothing       -> maybe Nothing (Just . (t :))
                                    Just t'       -> Just . (t' :) . fromMaybe ts
  
  -- eof ------------------------------------------------------------