    -- (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

    instance Eq a => Eq (LPath a) where
      (LP [])        == (LP [])        = True
      (LP ((_,x):_)) == (LP ((_,y):_)) = x==y
      (LP _)         == (LP _)         = False

    instance Ord a => Ord (LPath a) where
      compare (LP [])        (LP [])        = EQ
      compare (LP ((_,x):_)) (LP ((_,y):_)) = compare x y
      compare _ _ = error "LPath: cannot compare to empty paths"

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

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

    -- | Find the first path in a tree that starts with the given node
    findP :: Node -> LRTree a -> [LNode a]
    findP _ []                                  = []
    findP v ((LP []):ps)                        = findP v ps
    findP v ((LP (p@((w,_):_))):ps) | v==w      = p
                                    | otherwise = findP v ps

    getPath :: Node -> RTree -> Path
    getPath v = reverse . first (\(w:_)->w==v)

    getLPath :: Node -> LRTree a -> LPath a
    getLPath v = LP . reverse . findP v

    getDistance :: Node -> LRTree a -> a
    getDistance v = snd . head . findP v

    getLPathNodes :: Node -> LRTree a -> Path
    getLPathNodes v = (\(LP p)->map fst p) . getLPath v