module Autolib.Util.Doppelte

-- -- $Id$

( doppelte
, doppelteBy
)

where

import Autolib.Util.Hide
import Autolib.FiniteMap



doppelteBy :: Ord b => (a -> b) -> [a] -> [(a,a)]
doppelteBy :: forall b a. Ord b => (a -> b) -> [a] -> [(a, a)]
doppelteBy a -> b
f 
    = (((b, Hide a), (b, Hide a)) -> (a, a))
-> [((b, Hide a), (b, Hide a))] -> [(a, a)]
forall a b. (a -> b) -> [a] -> [b]
map ( \ ((b, Hide a)
x,(b, Hide a)
y) -> let unbox :: (a, Hide c) -> c
unbox = Hide c -> c
forall a. Hide a -> a
unHide (Hide c -> c) -> ((a, Hide c) -> Hide c) -> (a, Hide c) -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, Hide c) -> Hide c
forall a b. (a, b) -> b
snd in ((b, Hide a) -> a
forall {a} {c}. (a, Hide c) -> c
unbox (b, Hide a)
x, (b, Hide a) -> a
forall {a} {c}. (a, Hide c) -> c
unbox (b, Hide a)
y) )
    ([((b, Hide a), (b, Hide a))] -> [(a, a)])
-> ([a] -> [((b, Hide a), (b, Hide a))]) -> [a] -> [(a, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, Hide a)] -> [((b, Hide a), (b, Hide a))]
forall a. Ord a => [a] -> [(a, a)]
doppelte  
    ([(b, Hide a)] -> [((b, Hide a), (b, Hide a))])
-> ([a] -> [(b, Hide a)]) -> [a] -> [((b, Hide a), (b, Hide a))]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, Hide a)) -> [a] -> [(b, Hide a)]
forall a b. (a -> b) -> [a] -> [b]
map ( \ a
x -> (a -> b
f a
x, a -> Hide a
forall a. a -> Hide a
Hide a
x) )

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

suche :: Ord a => FiniteMap a a -> [a] -> [(a,a)]
suche :: forall a. Ord a => FiniteMap a a -> [a] -> [(a, a)]
suche FiniteMap a a
schon [] = []
suche FiniteMap a a
schon (a
x : [a]
xs) =
    case FiniteMap a a -> a -> Maybe a
forall k a. Ord k => FiniteMap k a -> k -> Maybe a
lookupFM FiniteMap a a
schon a
x of
        Just a
y -> (a
x, a
y) (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)]
suche FiniteMap a a
schon [a]
xs
	Maybe a
Nothing -> FiniteMap a a -> [a] -> [(a, a)]
forall a. Ord a => FiniteMap a a -> [a] -> [(a, a)]
suche (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
schon a
x a
x) [a]
xs