module Autolib.Util.Mehrfache where

-- -- $Id$

import Autolib.FiniteMap

mehrfacheBy :: Ord b => (a -> b) -> [a] -> [[a]]
-- nicht lazy genug:
{-
mehrfacheBy f xs 
    = filter ( (1 <) . length )
    $ eltsFM
    $ addListToFM_C (++) emptyFM
    $ do { x <- xs ; return ( f x, [x] ) }
-}

mehrfacheBy :: forall b a. Ord b => (a -> b) -> [a] -> [[a]]
mehrfacheBy a -> b
f [a]
xs = Map b a -> [a] -> [[a]]
helper Map b a
forall {k} {a}. Map k a
emptyFM [a]
xs where
    helper :: Map b a -> [a] -> [[a]]
helper Map b a
fm [] = []
    helper Map b a
fm ( a
x : [a]
xs ) =
        let fx :: b
fx = a -> b
f a
x
	    fm' :: Map b a
fm' = Map b a -> b -> a -> Map b a
forall {k} {a}. Ord k => Map k a -> k -> a -> Map k a
addToFM Map b a
fm b
fx a
x
        in  ( case Map b a -> b -> Maybe a
forall k a. Ord k => FiniteMap k a -> k -> Maybe a
lookupFM Map b a
fm (a -> b
f a
x) of
	          Maybe a
Nothing -> [[a]] -> [[a]]
forall a. a -> a
id 
	          Just a
y  -> ( [ a
y, a
x ] [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: )
	     ) ( Map b a -> [a] -> [[a]]
helper Map b a
fm' [a]
xs )