content: module Data.Graph.Inductive.Internal.RootPath
         (RTree, LRTree, 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};
     
    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}
  