-- (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 [a] -> Bool
p [[a]]
xss  = case ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter [a] -> Bool
p [[a]]
xss of
                 []   -> []
                 [a]
x:[[a]]
_  -> [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 Node
_ []                                = []
findP Node
v (LP []:LRTree a
ps)                        = Node -> LRTree a -> [LNode a]
forall a. Node -> LRTree a -> [LNode a]
findP Node
v LRTree a
ps
findP Node
v (LP (p :: [LNode a]
p@((Node
w,a
_):[LNode a]
_)):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 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 (\(Node
w:Path
_)->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 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 Node
v 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
  (Node
_,a
d):[LNode a]
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
d

getLPathNodes :: Node -> LRTree a -> Path
getLPathNodes :: Node -> LRTree a -> Path
getLPathNodes Node
v = (\(LP [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