5784N/A{- |

5784N/AModule : $Header$

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

5784N/ACopyright : (c) Klaus Luettich and Uni Bremen 2005

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

5784N/A

5784N/AMaintainer : Christian.Maeder@dfki.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

5784N/A ( 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, Map.keysSet, elems

5784N/A ) where

5784N/A

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

5784N/A

5784N/Aimport qualified Data.Map as Map

5784N/Aimport qualified Data.List as List

5784N/Aimport Data.Maybe

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/A(\\) = difference

5784N/A

5784N/Adata ElemWOrd a = EWOrd

5784N/A { order :: Int

5784N/A , ele :: a }

5784N/A deriving Show

5784N/A

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

5784N/A x == y = compare x y == EQ

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, Ord k) => k -> OMap k a -> m a

5784N/Alookup k = maybe (fail "Common.OrderedMap.lookup")

5784N/A (return . ele) . Map.lookup k

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 = insertWithKey . const

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 = updateWithKey . const

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 = filterWithKey . const

5784N/A

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

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

5784N/A

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

5784N/Adifference m = fromList . toList . Map.difference m

5784N/A

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

5784N/Amap = mapWithKey . const

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 = partitionWithKey . const

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 -> p k . ele) 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

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

5784N/Aelems = List.map snd . toList

5784N/A