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}
