1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TupleSections #-}
-- | An 'OMap' behaves much like a 'M.Map', with mostly the same asymptotics, but
-- also remembers the order that keys were inserted. All operations whose
-- asymptotics are worse than 'M.Map' have documentation saying so.
module Data.Map.Ordered
( OMap
-- * Trivial maps
, empty, singleton
-- * Insertion
-- | Conventions:
--
-- * The open side of an angle bracket points to an 'OMap'
--
-- * The pipe appears on the side whose indices take precedence if both sides contain the same key
--
-- * The left argument's indices are lower than the right argument's indices
--
-- * If both sides contain the same key, the tuple's value wins
, (<|), (|<), (>|), (|>)
, (<>|), (|<>), unionWithL, unionWithR
, Bias(Bias, unbiased), L, R
-- * Deletion/Update
, delete, filter, (\\)
, (|/\), (/\|), intersectionWith
, alter
-- * Query
, null, size, member, notMember, lookup
-- * Indexing
, Index, findIndex, elemAt
-- * List conversions
, fromList, assocs, toAscList
-- * 'M.Map' conversion
, toMap
) where
import qualified Data.Map as M
import Data.Map.Ordered.Internal
import Data.Map.Util
import Prelude hiding (filter, lookup, null)
singleton :: (k, v) -> OMap k v
singleton kv@(k, v) = OMap (M.singleton k (0, v)) (M.singleton 0 kv)
-- | Alter the value (or its absence) associated with a key.
--
-- @since 0.2.3
alter :: Ord k => (Maybe v -> Maybe v) -> k -> OMap k v -> OMap k v
alter f k om@(OMap tvs kvs) = case M.lookup k tvs of
Just (t, _) -> OMap
(M.alter (fmap (t,) . f . fmap snd) k tvs)
(M.alter (fmap (k,) . f . fmap snd) t kvs)
Nothing -> maybe om ((om |>) . (k, )) $ f Nothing
|
