    -- (c) 2000-2005 by Martin Erwig [see file COPYRIGHT]
    -- | Inward directed trees as lists of paths.
    module Data.Graph.Inductive.Internal.RootPath (
        -- * Types
        RTree,LRTree,
        -- * Operations
        getPath,getLPath,
        getDistance,
        getLPathNodes
    ) where

    import Data.Graph.Inductive.Graph

    type LRTree a = [LPath a]
    type RTree = [Path]

    first :: ([a] -> Bool) -> [[a]] -> [a]
    first :: ([a] -> Bool) -> [[a]] -> [a]
    first p :: [a] -> Bool
    p xss :: [[a]]
    xss  = case ([a] -> Bool) -> [[a]] -> [[a]]
    forall a. (a -> Bool) -> [a] -> [a]
    filter [a] -> Bool
    p [[a]]
    xss of
                     []   -> []
                     x :: [a]
    x:_  -> [a]
    x

    -- | Find the first path in a tree that starts with the given node.
    --
    --   Returns an empty list if there is no such path.
    findP :: Node -> LRTree a -> [LNode a]
    findP :: Node -> LRTree a -> [LNode a]
    findP _ []                                = []
    findP v :: Node
    v (LP []:ps :: LRTree a
    ps)                        = Node -> LRTree a -> [LNode a]
    forall a. Node -> LRTree a -> [LNode a]
    findP Node
    v LRTree a
    ps
    findP v :: Node
    v (LP (p :: [LNode a]
    p@((w :: Node
    w,_):_)):ps :: LRTree a
    ps) | Node
    vNode -> Node -> Bool
    forall a. Eq a => a -> a -> Bool
    ==Node
    w      = [LNode a]
    p
                                  | Bool
    otherwise = Node -> LRTree a -> [LNode a]
    forall a. Node -> LRTree a -> [LNode a]
    findP Node
    v LRTree a
    ps

    getPath :: Node -> RTree -> Path
    getPath :: Node -> RTree -> Path
    getPath v :: Node
    v = Path -> Path
    forall a. [a] -> [a]
    reverse (Path -> Path) -> (RTree -> Path) -> RTree -> Path
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Path -> Bool) -> RTree -> Path
    forall a. ([a] -> Bool) -> [[a]] -> [a]
    first (\(w :: Node
    w:_)->Node
    wNode -> Node -> Bool
    forall a. Eq a => a -> a -> Bool
    ==Node
    v)

    getLPath :: Node -> LRTree a -> LPath a
    getLPath :: Node -> LRTree a -> LPath a
    getLPath v :: Node
    v = [LNode a] -> LPath a
    forall a. [LNode a] -> LPath a
    LP ([LNode a] -> LPath a)
    -> (LRTree a -> [LNode a]) -> LRTree a -> LPath a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [LNode a] -> [LNode a]
    forall a. [a] -> [a]
    reverse ([LNode a] -> [LNode a])
    -> (LRTree a -> [LNode a]) -> LRTree a -> [LNode a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Node -> LRTree a -> [LNode a]
    forall a. Node -> LRTree a -> [LNode a]
    findP Node
    v

    -- | Return the distance to the given node in the given tree.
    --
    --   Returns 'Nothing' if the given node is not reachable.
    getDistance :: Node -> LRTree a -> Maybe a
    getDistance :: Node -> LRTree a -> Maybe a
    getDistance v :: Node
    v t :: LRTree a
    t = case Node -> LRTree a -> [LNode a]
    forall a. Node -> LRTree a -> [LNode a]
    findP Node
    v LRTree a
    t of
      []      -> Maybe a
    forall a. Maybe a
    Nothing
      (_,d :: a
    d):_ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    d

    getLPathNodes :: Node -> LRTree a -> Path
    getLPathNodes :: Node -> LRTree a -> Path
    getLPathNodes v :: Node
    v = (\(LP p :: [LNode a]
    p)->(LNode a -> Node) -> [LNode a] -> Path
    forall a b. (a -> b) -> [a] -> [b]
    map LNode a -> Node
    forall a b. (a, b) -> a
    fst [LNode a]
    p) (LPath a -> Path) -> (LRTree a -> LPath a) -> LRTree a -> Path
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Node -> LRTree a -> LPath a
    forall a. Node -> LRTree a -> LPath a
    getLPath Node
    v