5784N/A{- |

5784N/AModule : $Header$

5784N/ADescription : ordered maps (these keep insertion order)

5784N/ACopyright : (c) Klaus L�ttich and Uni Bremen 2005

5784N/ALicense : similar to LGPL, see HetCATS/LICENSE.txt or LIZENZ.txt

5784N/A

5784N/AMaintainer : luettich@tzi.de

5784N/AStability : provisional

5784N/APortability : portable

5784N/A

5784N/AOrdered maps (these keep insertion order)

5784N/A

5784N/Aordered maps keep the ordering if converted from a list and of all

5784N/Ainsert operations which are implemented; toList uses the

5784N/Ainsertion\/conversion order for the creation of the new list

5784N/A

5784N/A-}

5784N/A

5784N/Amodule Common.OrderedMap ( OMap

5784N/A , ElemWOrd(..)

5784N/A , Map.empty, Map.null, Map.size

5784N/A , Map.member

5784N/A , lookup

5784N/A , insert,insertWith,insertWithKey

5784N/A , map, mapWithKey

5784N/A , delete,(\\),difference

5784N/A , update, updateWithKey

5784N/A , filter, filterWithKey

5784N/A , partition, partitionWithKey

5784N/A , fromList, toList

5784N/A , keys, Rel.keysSet

5784N/A ) where

5784N/A

5784N/Aimport Prelude hiding (lookup,map,filter,foldr,foldl,null)

5784N/A

5784N/Aimport qualified Common.Lib.Map as Map

5784N/Aimport qualified Common.Lib.Rel as Rel

5784N/Aimport qualified Data.List as List

5784N/Aimport Data.Maybe

5784N/Aimport Control.Monad

5784N/A

5784N/Ainfix 9 \\ -- add a comment for cpp

5784N/A

5784N/A(\\) :: Ord k => OMap k a -> OMap k b -> OMap k a

5784N/Am1 \\ m2 = difference m1 m2

5784N/A

5784N/Adata ElemWOrd a = EWOrd { order :: Int

5784N/A , ele :: a}

5784N/A deriving Show

5784N/A

5784N/Ainstance Eq a => Eq (ElemWOrd a) where

5784N/A x == y = ele x == ele y

5784N/A

5784N/Ainstance Ord a => Ord (ElemWOrd a) where

5784N/A compare x y = ele x `compare` ele y

5784N/A

5784N/Atype OMap a b = Map.Map a (ElemWOrd b)

5784N/A

5784N/Alookup :: (Monad m,Functor m,Ord k) => k -> OMap k a -> m a

5784N/Alookup k m = liftM ele $ Map.lookup k m

5784N/A

5784N/Ainsert :: Ord k => k -> a -> OMap k a -> OMap k a

5784N/Ainsert k e m = Map.insertWith (\ ne oe -> oe {ele = ele ne})

5784N/A k (EWOrd (Map.size m) e) m

5784N/A

5784N/AinsertWith :: Ord k => (a -> a -> a) -> k -> a -> OMap k a -> OMap k a

5784N/AinsertWith f k e m = insertWithKey (\ _k x y -> f x y) k e m

5784N/A

5784N/AinsertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> OMap k a -> OMap k a

5784N/AinsertWithKey f k e m =

5784N/A Map.insertWithKey (\ k1 eo1 eo2 -> eo2 { ele = f k1 (ele eo1) (ele eo2)})

5784N/A k (EWOrd (Map.size m) e) m

5784N/A

5784N/Adelete :: Ord k => k -> OMap k a -> OMap k a

5784N/Adelete k m =

5784N/A if Map.size dm == Map.size m

5784N/A then dm

5784N/A else updateOrder (order $ fromJust $ Map.lookup k m) dm

5784N/A where dm = Map.delete k m

5784N/A

5784N/AupdateOrder :: Ord k =>

5784N/A Int -- ^ order of removed element

5784N/A -> OMap k a -> OMap k a

5784N/AupdateOrder dOrder = Map.map updateOrd

5784N/A where updateOrd e

5784N/A | order e < dOrder = e

5784N/A | order e == dOrder = error "Something strange happened"

5784N/A | order e > dOrder = e { order = order e - 1}

5784N/A | otherwise = error "Never happens"

5784N/A

5784N/Aupdate :: Ord k => (a -> Maybe a) -> k -> OMap k a -> OMap k a

5784N/Aupdate f k m = updateWithKey (\ _k x -> f x) k m

5784N/A

5784N/AupdateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> OMap k a -> OMap k a

5784N/AupdateWithKey f k m1 =

5784N/A let m2 = Map.updateWithKey (\ k1 e -> case f k1 (ele e) of

5784N/A Nothing -> Nothing

5784N/A Just x -> Just (e {ele = x})) k m1

5784N/A in if Map.size m2 == Map.size m1

5784N/A then m2

5784N/A else updateOrder (order $ fromJust $ Map.lookup k m1) m2

5784N/A

5784N/Afilter :: Ord k => (a -> Bool) -> OMap k a -> OMap k a

5784N/Afilter p = filterWithKey (\ _k x -> p x)

5784N/A

5784N/AfilterWithKey :: Ord k => (k -> a -> Bool) -> OMap k a -> OMap k a

5784N/AfilterWithKey p = fromList . toList . Map.filterWithKey (\k e -> p k (ele e))

5784N/A

5784N/Adifference :: Ord k => OMap k a -> OMap k b -> OMap k a

5784N/Adifference m1 m2 = fromList $ toList $ Map.difference m1 m2

5784N/A

5784N/Amap :: Ord k => (a -> b) -> OMap k a -> OMap k b

5784N/Amap f = mapWithKey (\ _k x -> f x)

5784N/A

5784N/AmapWithKey :: (k -> a -> b) -> OMap k a -> OMap k b

5784N/AmapWithKey f = Map.mapWithKey ( \ k x -> x {ele = f k (ele x)})

5784N/A

5784N/Apartition :: Ord k => (a -> Bool) -> OMap k a -> (OMap k a,OMap k a)

5784N/Apartition p = partitionWithKey (\ _k a -> p a)

5784N/A

5784N/ApartitionWithKey :: Ord k => (k -> a -> Bool) -> OMap k a

5784N/A -> (OMap k a,OMap k a)

5784N/ApartitionWithKey p m = case Map.partitionWithKey (\ k x -> p k (ele x)) m of

5784N/A (x,y) -> (updOrder x,updOrder y)

5784N/A where updOrder = fromList . toList

5784N/A

5784N/AfromList :: Ord k => [(k,a)] -> OMap k a

5784N/AfromList = List.foldl ins Map.empty

5784N/A where ins m (k,e) = insert k e m

5784N/A

5784N/AtoList :: Ord k => OMap k a -> [(k,a)]

5784N/AtoList = List.map (\ (k,e) -> (k,ele e)) . List.sortBy comp . Map.toList

5784N/A where comp (_,x) (_,y) = compare (order x) (order y)

5784N/A

5784N/Akeys :: Ord k => OMap k a -> [k]

5784N/Akeys = List.map fst . toList

5784N/A