-- | -- Module : Data.Edison.Assoc.AssocList -- Copyright : Copyright (c) 2006, 2008 Robert Dockins -- License : MIT; see COPYRIGHT file for terms and conditions -- -- Maintainer : robdockins AT fastmail DOT fm -- Stability : stable -- Portability : GHC, Hugs (MPTC and FD) -- -- The standard library "Data.Map" repackaged as an Edison -- associative collection. module Data.Edison.Assoc.StandardMap ( -- * Type of standard finite maps FM, -- * AssocX operations empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll, deleteSeq,null,size,member,count,lookup,lookupM,lookupAll, lookupAndDelete,lookupAndDeleteM,lookupAndDeleteAll, lookupWithDefault,adjust,adjustAll,adjustOrInsert,adjustAllOrInsert, adjustOrDelete,adjustOrDeleteAll,strict,strictWith, map,fold,fold',fold1,fold1',filter,partition,elements,structuralInvariant, -- * FiniteMapX operations fromSeqWith,fromSeqWithKey,insertWith,insertWithKey,insertSeqWith, insertSeqWithKey,unionl,unionr,unionWith,unionSeqWith,intersectionWith, difference,properSubset,subset,properSubmapBy,submapBy,sameMapBy, properSubmap,submap,sameMap, -- * OrdAssocX operations minView, minElem, deleteMin, unsafeInsertMin, maxView, maxElem, deleteMax, unsafeInsertMax, foldr, foldr', foldl, foldl', foldr1, foldr1', foldl1, foldl1', unsafeFromOrdSeq, unsafeAppend, filterLT, filterLE, filterGT, filterGE, partitionLT_GE, partitionLE_GT, partitionLT_GT, -- * Assoc operations toSeq,keys,mapWithKey,foldWithKey,foldWithKey',filterWithKey,partitionWithKey, -- * OrdAssoc operations minViewWithKey, minElemWithKey, maxViewWithKey, maxElemWithKey, foldrWithKey, foldrWithKey', foldlWithKey, foldlWithKey', toOrdSeq, -- * FiniteMap operations unionWithKey,unionSeqWithKey,intersectionWithKey, -- * Documentation moduleName ) where import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,filter) import qualified Prelude import qualified Data.Edison.Assoc as A import qualified Data.Edison.Seq as S import qualified Data.Edison.Seq.ListSeq as L import Data.Edison.Assoc.Defaults import Data.Int import Test.QuickCheck (Arbitrary(..), CoArbitrary(..)) import qualified Data.Map as DM type FM = DM.Map moduleName :: String moduleName = "Data.Edison.Assoc.StandardMap" empty :: FM k a singleton :: Ord k => k -> a -> FM k a fromSeq :: (Ord k,S.Sequence seq) => seq (k,a) -> FM k a insert :: Ord k => k -> a -> FM k a -> FM k a insertSeq :: (Ord k,S.Sequence seq) => seq (k,a) -> FM k a -> FM k a union :: Ord k => FM k a -> FM k a -> FM k a unionSeq :: (Ord k,S.Sequence seq) => seq (FM k a) -> FM k a delete :: Ord k => k -> FM k a -> FM k a deleteAll :: Ord k => k -> FM k a -> FM k a deleteSeq :: (Ord k,S.Sequence seq) => seq k -> FM k a -> FM k a null :: FM k a -> Bool size :: FM k a -> Int member :: Ord k => k -> FM k a -> Bool count :: Ord k => k -> FM k a -> Int lookup :: Ord k => k -> FM k a -> a lookupAll :: (Ord k,S.Sequence seq) => k -> FM k a -> seq a lookupM :: (Ord k,Monad m) => k -> FM k a -> m a lookupWithDefault :: Ord k => a -> k -> FM k a -> a lookupAndDelete :: Ord k => k -> FM k a -> (a, FM k a) lookupAndDeleteM :: (Ord k,Monad m) => k -> FM k a -> m (a, FM k a) lookupAndDeleteAll :: (Ord k,S.Sequence seq) => k -> FM k a -> (seq a,FM k a) adjust :: Ord k => (a->a) -> k -> FM k a -> FM k a adjustAll :: Ord k => (a->a) -> k -> FM k a -> FM k a adjustOrInsert :: Ord k => (a -> a) -> a -> k -> FM k a -> FM k a adjustAllOrInsert :: Ord k => (a -> a) -> a -> k -> FM k a -> FM k a adjustOrDelete :: Ord k => (a -> Maybe a) -> k -> FM k a -> FM k a adjustOrDeleteAll :: Ord k => (a -> Maybe a) -> k -> FM k a -> FM k a strict :: Ord k => FM k a -> FM k a strictWith :: Ord k => (a -> b) -> FM k a -> FM k a map :: (Ord k,Functor (FM k)) => (a -> b) -> FM k a -> FM k b fold :: Ord k => (a -> b -> b) -> b -> FM k a -> b fold1 :: Ord k => (a -> a -> a) -> FM k a -> a fold' :: Ord k => (a -> b -> b) -> b -> FM k a -> b fold1' :: Ord k => (a -> a -> a) -> FM k a -> a filter :: Ord k => (a -> Bool) -> FM k a -> FM k a partition :: Ord k => (a -> Bool) -> FM k a -> (FM k a,FM k a) elements :: (Ord k,S.Sequence seq) => FM k a -> seq a minView :: (Ord k,Monad m) => FM k a -> m (a, FM k a) minElem :: Ord k => FM k a -> a deleteMin :: Ord k => FM k a -> FM k a unsafeInsertMin :: Ord k => k -> a -> FM k a -> FM k a maxView :: (Ord k,Monad m) => FM k a -> m (a, FM k a) maxElem :: Ord k => FM k a -> a deleteMax :: Ord k => FM k a -> FM k a unsafeInsertMax :: Ord k => k -> a -> FM k a -> FM k a foldr :: Ord k => (a -> b -> b) -> b -> FM k a -> b foldl :: Ord k => (b -> a -> b) -> b -> FM k a -> b foldr1 :: Ord k => (a -> a -> a) -> FM k a -> a foldl1 :: Ord k => (a -> a -> a) -> FM k a -> a foldr' :: Ord k => (a -> b -> b) -> b -> FM k a -> b foldl' :: Ord k => (b -> a -> b) -> b -> FM k a -> b foldr1' :: Ord k => (a -> a -> a) -> FM k a -> a foldl1' :: Ord k => (a -> a -> a) -> FM k a -> a unsafeFromOrdSeq :: (Ord k,S.Sequence seq) => seq (k,a) -> FM k a unsafeAppend :: Ord k => FM k a -> FM k a -> FM k a filterLT :: Ord k => k -> FM k a -> FM k a filterGT :: Ord k => k -> FM k a -> FM k a filterLE :: Ord k => k -> FM k a -> FM k a filterGE :: Ord k => k -> FM k a -> FM k a partitionLT_GE :: Ord k => k -> FM k a -> (FM k a,FM k a) partitionLE_GT :: Ord k => k -> FM k a -> (FM k a,FM k a) partitionLT_GT :: Ord k => k -> FM k a -> (FM k a,FM k a) fromSeqWith :: (Ord k,S.Sequence seq) => (a -> a -> a) -> seq (k,a) -> FM k a fromSeqWithKey :: (Ord k,S.Sequence seq) => (k -> a -> a -> a) -> seq (k,a) -> FM k a insertWith :: Ord k => (a -> a -> a) -> k -> a -> FM k a -> FM k a insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> FM k a -> FM k a insertSeqWith :: (Ord k,S.Sequence seq) => (a -> a -> a) -> seq (k,a) -> FM k a -> FM k a insertSeqWithKey :: (Ord k,S.Sequence seq) => (k -> a -> a -> a) -> seq (k,a) -> FM k a -> FM k a unionl :: Ord k => FM k a -> FM k a -> FM k a unionr :: Ord k => FM k a -> FM k a -> FM k a unionWith :: Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k a unionSeqWith :: (Ord k,S.Sequence seq) => (a -> a -> a) -> seq (FM k a) -> FM k a intersectionWith :: Ord k => (a -> b -> c) -> FM k a -> FM k b -> FM k c difference :: Ord k => FM k a -> FM k b -> FM k a properSubset :: Ord k => FM k a -> FM k b -> Bool subset :: Ord k => FM k a -> FM k b -> Bool properSubmapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool submapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool sameMapBy :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool properSubmap :: (Ord k,Eq a) => FM k a -> FM k a -> Bool submap :: (Ord k,Eq a) => FM k a -> FM k a -> Bool sameMap :: (Ord k,Eq a) => FM k a -> FM k a -> Bool toSeq :: (Ord k,S.Sequence seq) => FM k a -> seq (k,a) keys :: (Ord k,S.Sequence seq) => FM k a -> seq k mapWithKey :: Ord k => (k -> a -> b) -> FM k a -> FM k b foldWithKey :: Ord k => (k -> a -> b -> b) -> b -> FM k a -> b foldWithKey' :: Ord k => (k -> a -> b -> b) -> b -> FM k a -> b filterWithKey :: Ord k => (k -> a -> Bool) -> FM k a -> FM k a partitionWithKey :: Ord k => (k -> a -> Bool) -> FM k a -> (FM k a,FM k a) minViewWithKey :: (Ord k,Monad m) => FM k a -> m ((k, a), FM k a) minElemWithKey :: Ord k => FM k a -> (k,a) maxViewWithKey :: (Ord k,Monad m) => FM k a -> m ((k, a), FM k a) maxElemWithKey :: Ord k => FM k a -> (k,a) foldrWithKey :: (k -> a -> b -> b) -> b -> FM k a -> b foldlWithKey :: (b -> k -> a -> b) -> b -> FM k a -> b foldrWithKey' :: (k -> a -> b -> b) -> b -> FM k a -> b foldlWithKey' :: (b -> k -> a -> b) -> b -> FM k a -> b toOrdSeq :: (Ord k,S.Sequence seq) => FM k a -> seq (k,a) unionWithKey :: Ord k => (k -> a -> a -> a) -> FM k a -> FM k a -> FM k a unionSeqWithKey :: (Ord k,S.Sequence seq) => (k -> a -> a -> a) -> seq (FM k a) -> FM k a intersectionWithKey :: Ord k => (k -> a -> b -> c) -> FM k a -> FM k b -> FM k c structuralInvariant :: Ord k => FM k a -> Bool structuralInvariant = DM.valid empty = DM.empty singleton = DM.singleton fromSeq = fromSeqUsingInsertSeq insert = DM.insert insertSeq = insertSeqUsingFoldr union = DM.union unionSeq = DM.unions . S.toList delete = DM.delete deleteAll = DM.delete -- by finite map property deleteSeq = deleteSeqUsingFoldr null = DM.null size = DM.size member = DM.member count = countUsingMember lookup k m = maybe (error (moduleName ++ ".lookup: failed")) id (DM.lookup k m) lookupM k m = maybe (fail (moduleName ++ ".lookupM: failed")) return (DM.lookup k m) lookupAll = lookupAllUsingLookupM lookupWithDefault = DM.findWithDefault lookupAndDelete = lookupAndDeleteDefault lookupAndDeleteM = lookupAndDeleteMDefault lookupAndDeleteAll = lookupAndDeleteAllDefault adjust = DM.adjust adjustAll = DM.adjust adjustOrInsert = adjustOrInsertUsingMember adjustAllOrInsert = adjustOrInsertUsingMember adjustOrDelete = DM.update adjustOrDeleteAll = DM.update strict xs = DM.fold (flip const) () xs `seq` xs strictWith f xs = DM.fold (\x z -> f x `seq` z) () xs `seq` xs map = fmap fold = DM.fold fold' f x xs = L.foldl' (flip f) x (DM.elems xs) fold1 f xs = L.foldr1 f (DM.elems xs) fold1' f xs = L.foldl1' (flip f) (DM.elems xs) filter = DM.filter partition = DM.partition elements = elementsUsingFold minView m = if DM.null m then fail (moduleName ++ ".minView: failed") else let ((_,x),m') = DM.deleteFindMin m in return (x,m') minElem = snd . DM.findMin deleteMin = DM.deleteMin unsafeInsertMin = DM.insert maxView m = if DM.null m then fail (moduleName ++ ".maxView: failed") else let ((_,x),m') = DM.deleteFindMax m in return (x,m') maxElem = snd . DM.findMax deleteMax = DM.deleteMax unsafeInsertMax = DM.insert foldr f x m = L.foldr f x (DM.elems m) foldl f x m = L.foldl f x (DM.elems m) foldr1 f m = L.foldr1 f (DM.elems m) foldl1 f m = L.foldl1 f (DM.elems m) foldr' f x m = L.foldr' f x (DM.elems m) foldl' f x m = L.foldl' f x (DM.elems m) foldr1' f m = L.foldr1' f (DM.elems m) foldl1' f m = L.foldl1' f (DM.elems m) unsafeFromOrdSeq = DM.fromAscList . S.toList unsafeAppend = DM.union filterLT k = fst . DM.split k filterGT k = snd . DM.split k filterLE k m = let (lt, mx, _ ) = DM.splitLookup k m in maybe lt (\x -> insert k x lt) mx filterGE k m = let (_ , mx, gt) = DM.splitLookup k m in maybe gt (\x -> insert k x gt) mx partitionLT_GE k m = let (lt, mx, gt) = DM.splitLookup k m in (lt, maybe gt (\x -> insert k x gt) mx) partitionLE_GT k m = let (lt, mx, gt) = DM.splitLookup k m in (maybe lt (\x -> insert k x lt) mx, gt) partitionLT_GT = DM.split fromSeqWith f s = DM.fromListWith f (S.toList s) fromSeqWithKey f s = DM.fromListWithKey f (S.toList s) insertWith = DM.insertWith insertWithKey = insertWithKeyUsingInsertWith insertSeqWith = insertSeqWithUsingInsertWith insertSeqWithKey = insertSeqWithKeyUsingInsertWithKey unionl = DM.union unionr = flip DM.union unionWith = DM.unionWith unionSeqWith = unionSeqWithUsingReduce intersectionWith = DM.intersectionWith difference = DM.difference properSubset = DM.isProperSubmapOfBy (\_ _ -> True) subset = DM.isSubmapOfBy (\_ _ -> True) properSubmapBy = DM.isProperSubmapOfBy submapBy = DM.isSubmapOfBy sameMapBy = sameMapByUsingOrdLists properSubmap = A.properSubmap submap = A.submap sameMap = A.sameMap toSeq = toSeqUsingFoldWithKey keys = keysUsingFoldWithKey mapWithKey = DM.mapWithKey foldWithKey = DM.foldWithKey foldWithKey' f x m = L.foldl' (\b (k,a) -> f k a b) x (DM.toList m) filterWithKey = DM.filterWithKey partitionWithKey = DM.partitionWithKey minViewWithKey m = if DM.null m then fail (moduleName ++ ".minViewWithKey: failed") else return (DM.deleteFindMin m) minElemWithKey = DM.findMin maxViewWithKey m = if DM.null m then fail (moduleName ++ ".maxViewWithKey: failed") else return (DM.deleteFindMax m) maxElemWithKey = DM.findMax foldrWithKey = DM.foldWithKey foldrWithKey' f x m = L.foldr' (\(k,a) b -> f k a b) x (DM.toAscList m) foldlWithKey f x m = L.foldl (\b (k,a) -> f b k a) x (DM.toAscList m) foldlWithKey' f x m = L.foldl' (\b (k,a) -> f b k a) x (DM.toAscList m) toOrdSeq = S.fromList . DM.toAscList unionWithKey = DM.unionWithKey unionSeqWithKey = unionSeqWithKeyUsingReduce intersectionWithKey = DM.intersectionWithKey instance Ord k => A.AssocX (FM k) k where {empty = empty; singleton = singleton; fromSeq = fromSeq; insert = insert; insertSeq = insertSeq; union = union; unionSeq = unionSeq; delete = delete; deleteAll = deleteAll; deleteSeq = deleteSeq; null = null; size = size; member = member; count = count; lookup = lookup; lookupM = lookupM; lookupAll = lookupAll; lookupAndDelete = lookupAndDelete; lookupAndDeleteM = lookupAndDeleteM; lookupAndDeleteAll = lookupAndDeleteAll; lookupWithDefault = lookupWithDefault; adjust = adjust; adjustAll = adjustAll; adjustOrInsert = adjustOrInsert; adjustAllOrInsert = adjustAllOrInsert; adjustOrDelete = adjustOrDelete; adjustOrDeleteAll = adjustOrDeleteAll; fold = fold; fold' = fold'; fold1 = fold1; fold1' = fold1'; filter = filter; partition = partition; elements = elements; strict = strict; strictWith = strictWith; structuralInvariant = structuralInvariant; instanceName _ = moduleName} instance Ord k => A.OrdAssocX (FM k) k where {minView = minView; minElem = minElem; deleteMin = deleteMin; unsafeInsertMin = unsafeInsertMin; maxView = maxView; maxElem = maxElem; deleteMax = deleteMax; unsafeInsertMax = unsafeInsertMax; foldr = foldr; foldr' = foldr'; foldl = foldl; foldl' = foldl'; foldr1 = foldr1; foldr1' = foldr1'; foldl1 = foldl1; foldl1' = foldl1'; unsafeFromOrdSeq = unsafeFromOrdSeq; unsafeAppend = unsafeAppend; filterLT = filterLT; filterGT = filterGT; filterLE = filterLE; filterGE = filterGE; partitionLT_GE = partitionLT_GE; partitionLE_GT = partitionLE_GT; partitionLT_GT = partitionLT_GT} instance Ord k => A.FiniteMapX (FM k) k where {fromSeqWith = fromSeqWith; fromSeqWithKey = fromSeqWithKey; insertWith = insertWith; insertWithKey = insertWithKey; insertSeqWith = insertSeqWith; insertSeqWithKey = insertSeqWithKey; unionl = unionl; unionr = unionr; unionWith = unionWith; unionSeqWith = unionSeqWith; intersectionWith = intersectionWith; difference = difference; properSubset = properSubset; subset = subset; properSubmapBy = properSubmapBy; submapBy = submapBy; sameMapBy = sameMapBy} instance Ord k => A.OrdFiniteMapX (FM k) k instance Ord k => A.Assoc (FM k) k where {toSeq = toSeq; keys = keys; mapWithKey = mapWithKey; foldWithKey = foldWithKey; foldWithKey' = foldWithKey'; filterWithKey = filterWithKey; partitionWithKey = partitionWithKey} instance Ord k => A.OrdAssoc (FM k) k where {minViewWithKey = minViewWithKey; minElemWithKey = minElemWithKey; maxViewWithKey = maxViewWithKey; maxElemWithKey = maxElemWithKey; foldrWithKey = foldrWithKey; foldrWithKey' = foldrWithKey'; foldlWithKey = foldlWithKey; foldlWithKey' = foldlWithKey'; toOrdSeq = toOrdSeq} instance Ord k => A.FiniteMap (FM k) k where {unionWithKey = unionWithKey; unionSeqWithKey = unionSeqWithKey; intersectionWithKey = intersectionWithKey} instance Ord k => A.OrdFiniteMap (FM k) k instance (Ord k,Arbitrary k,Arbitrary a) => Arbitrary (FM k a) where arbitrary = do xs <- arbitrary return (Prelude.foldr (uncurry insert) empty xs) instance (Ord k,CoArbitrary k,CoArbitrary a) => CoArbitrary (FM k a) where coarbitrary mp = coarbitrary (A.toList mp)