module Autolib.Util.BFS 

( meetings
-- for testing
, generator
, duplicates
)

where

import Autolib.FiniteMap
import Data.Maybe
import Autolib.Set

-- | compute bfs ordering, emit any duplicates
-- assume that there are not many of them
-- or, we stop the program as soon as we have seen only a few
meetings :: Ord a => Int -- ^ höchstens soviele generieren
	          -> ( a -> [a] ) -> a -> [(a, a)]
meetings :: forall a. Ord a => Int -> (a -> [a]) -> a -> [(a, a)]
meetings Int
schranke a -> [a]
f a
top = [a] -> [(a, a)]
forall a. Ord a => [a] -> [(a, a)]
duplicates 
	       ([a] -> [(a, a)]) -> [a] -> [(a, a)]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
schranke
	       ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> [a]) -> [a] -> [a]
forall a. (a -> [a]) -> [a] -> [a]
generator a -> [a]
f [ a
top ]

generator :: ( a -> [a] ) -> [a] -> [a]
generator :: forall a. (a -> [a]) -> [a] -> [a]
generator a -> [a]
f [] = []
generator a -> [a]
f [a]
todo =
    [a]
todo [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ (a -> [a]) -> [a] -> [a]
forall a. (a -> [a]) -> [a] -> [a]
generator a -> [a]
f ( do t <- [a]
todo ; f t )

duplicates :: Ord a => [a] -> [(a,a)]
duplicates :: forall a. Ord a => [a] -> [(a, a)]
duplicates = FiniteMap a a -> [a] -> [(a, a)]
forall a. Ord a => FiniteMap a a -> [a] -> [(a, a)]
weeder FiniteMap a a
forall {k} {a}. Map k a
emptyFM

weeder :: Ord a => FiniteMap a a -> [a] -> [(a, a)]
weeder :: forall a. Ord a => FiniteMap a a -> [a] -> [(a, a)]
weeder FiniteMap a a
done [] = []
weeder FiniteMap a a
done ((a
x :: a) : [a]
xs) =
    ( do ( old :: a ) <- Maybe a -> [a]
forall a. Maybe a -> [a]
maybeToList (Maybe a -> [a]) -> Maybe a -> [a]
forall a b. (a -> b) -> a -> b
$ FiniteMap a a -> a -> Maybe a
forall k a. Ord k => FiniteMap k a -> k -> Maybe a
lookupFM FiniteMap a a
done a
x
         return ( old, x )
    ) [(a, a)] -> [(a, a)] -> [(a, a)]
forall a. [a] -> [a] -> [a]
++ FiniteMap a a -> [a] -> [(a, a)]
forall a. Ord a => FiniteMap a a -> [a] -> [(a, a)]
weeder ( FiniteMap a a -> a -> a -> FiniteMap a a
forall {k} {a}. Ord k => Map k a -> k -> a -> Map k a
addToFM FiniteMap a a
done a
x a
x ) [a]
xs