content: -- (c) 1999 by Martin Erwig
  -- | Threading Combinators.
  module Data.Graph.Inductive.Internal.Thread(
      -- * Types
      Split, SplitM, Thread, Collect,
      -- * Operations
      threadList', threadList, threadMaybe', threadMaybe, splitPar, splitParM
  ) where
  
  -- import Graph
  -- import GraphData
  -- import qualified Diet as D
  
  -- import ADT
  
  ----------------------------------------------------------------------
  -- CLASSES AND TYPES
  ----------------------------------------------------------------------
  
  {-
  class Thread t a b where
    split :: a -> t -> (b,t)
  
  
  instance Thread (Graph a b) Node (MContext a b) where
    split = match
  
  instance (D.Discrete a) => Thread (D.Diet a) a a where
    split x s = (x,D.delete x s)
  -}
  
  {-
     Make clear different notions:
  
     "thread" = data structure + split operation
     ...      = threadable data structure
     ...      = split operation
  
  -}
  
  
  ----------------------------------------------------------------------
  -- THREAD COMBINATORS
  ----------------------------------------------------------------------
  
  
  -- (A) split along a list of indexes and thread data structure
  --
  -- there are different ways to consume the returned elements:
  
  {-
  --  (1) simple collect in a list
  --
  foldT1' ys []     d = ys
  foldT1' ys (x:xs) d = foldT1' (y:ys) xs d'  where (y,d') = split x d
  foldT1 xs d = foldT1' [] xs d
  
  --  (2) combine by a function
  --
  foldT2' f ys []     d = ys
  foldT2' f ys (x:xs) d = foldT2' f (f y ys) xs d'  where (y,d') = split x d
  foldT2 f u xs d = foldT2' f u xs d
  -}
  
  
  -- Mnemonics:
  --
  --  t : thread type
  --  i : index type
  --  r : result type
  --  c : collection type
  --
  type Split t i r  = i -> t -> (r,t)
  type Thread t i r = (t,Split t i r)
  type Collect r c  = (r -> c -> c,c)
  
  --  (3) abstract from split
  --
  threadList' :: Collect r c -> Split t i r -> [i] -> t -> (c,t)
  threadList' (_,c) _ []         t = (c,t)
  threadList' (f,c) split (i:is) t = threadList' (f,f r c) split is t'
                                     where (r,t') = split i t
  
  {-
     Note: threadList' works top-down (or, from left),
           whereas dfs,gfold,... have been defined bottom-up (or from right).
  
     ==> therefore, we define a correpsonding operator for folding
         bottom-up/from right.
  -}
  threadList :: Collect r c -> Split t i r -> [i] -> t -> (c,t)
  threadList (_,c) _ []     t  = (c,t)
  threadList (f,c) split (i:is) t = (f r c',t'')
                                    where (r,t')   = split i t
                                          (c',t'') = threadList (f,c) split is t'
  
  
  
  -- (B) thread "maybes", ie, apply f to Just-values and continue
  --     threading with "continuation" c, and ignore Nothing-values, ie,
  --     stop threading and return current data structure.
  --
  -- threadMaybe' :: (r -> b) -> Split t i r -> (e -> f -> (Maybe i,t))
  --                 -> e -> f -> (Maybe b,t)
  
  type SplitM t i r = Split t i (Maybe r)
  
  threadMaybe' :: (r->a)->Split t i r->Split t j (Maybe i)->Split t j (Maybe a)
  threadMaybe' f cont split j t =
        case mi of Just i  -> (Just (f r),t'') where (r,t'') = cont i t'
                   Nothing -> (Nothing,t')
        where (mi,t') = split j t
  
  -- extension:  grant f access also to y, the result of split.
  --
  -- threadMaybe :: (a -> b -> c) -> (a -> d -> (b,d)) -> (e -> f -> (Maybe a,d))
  --                -> e -> f -> (Maybe c,d)
  -- threadMaybe :: (i->r->a)->Split t i r->Split t j (Maybe i)->Split t j (Maybe a)
  threadMaybe :: (i -> r -> a) -> Split t i r -> SplitM t j i -> SplitM t j a
  threadMaybe f cont split j t =
        case mi of Just i  -> (Just (f i r),t'') where (r,t'') = cont i t'
                   Nothing -> (Nothing,t')
        where (mi,t') = split j t
  
  
  -- (C) compose splits in parallel (is a kind of generalized zip)
  --
  -- splitPar :: (a -> b -> (c,d)) -> (e -> f -> (g,h))
  --             -> (a,e) -> (b,f) -> ((c,g),(d,h))
  splitPar :: Split t i r -> Split u j s -> Split (t,u) (i,j) (r,s)
  splitPar split split' (i,j) (t,u) = ((r,s),(t',u'))
                                      where (r,t') = split i t
                                            (s,u') = split' j u
  
  splitParM :: SplitM t i r -> Split u j s -> SplitM (t,u) (i,j) (r,s)
  splitParM splitm split (i,j) (t,u) =
            case mr of Just r  -> (Just (r,s),(t',u'))
                       Nothing -> (Nothing,(t',u))   -- ignore 2nd split
            where (mr,t') = splitm i t
                  (s,u')  = split j u
  
  
  -- (D) merge a thread with/into a computation
  --
  {-
     Example: assign consecutive numbers to the nodes of a tree
  
     Input: type d, thread (t,split), fold operation on d
  -}
  