    {-# 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 :: forall k v. (k, v) -> OMap k v
    singleton kv :: (k, v)
    kv@(k
    k, v
    v) = Map k (Tag, v) -> Map Tag (k, v) -> OMap k v
    forall k v. Map k (Tag, v) -> Map Tag (k, v) -> OMap k v
    OMap (k -> (Tag, v) -> Map k (Tag, v)
    forall k a. k -> a -> Map k a
    M.singleton k
    k (Tag
    0, v
    v)) (Tag -> (k, v) -> Map Tag (k, v)
    forall k a. k -> a -> Map k a
    M.singleton Tag
    0 (k, v)
    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 :: forall k v.
    Ord k =>
    (Maybe v -> Maybe v) -> k -> OMap k v -> OMap k v
    alter Maybe v -> Maybe v
    f k
    k om :: OMap k v
    om@(OMap Map k (Tag, v)
    tvs Map Tag (k, v)
    kvs) = case k -> Map k (Tag, v) -> Maybe (Tag, v)
    forall k a. Ord k => k -> Map k a -> Maybe a
    M.lookup k
    k Map k (Tag, v)
    tvs of
    	Just (Tag
    t, v
    _) -> Map k (Tag, v) -> Map Tag (k, v) -> OMap k v
    forall k v. Map k (Tag, v) -> Map Tag (k, v) -> OMap k v
    OMap
    		((Maybe (Tag, v) -> Maybe (Tag, v))
    -> k -> Map k (Tag, v) -> Map k (Tag, v)
    forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    M.alter ((v -> (Tag, v)) -> Maybe v -> Maybe (Tag, v)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Tag
    t,) (Maybe v -> Maybe (Tag, v))
    -> (Maybe (Tag, v) -> Maybe v) -> Maybe (Tag, v) -> Maybe (Tag, v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe v -> Maybe v
    f (Maybe v -> Maybe v)
    -> (Maybe (Tag, v) -> Maybe v) -> Maybe (Tag, v) -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Tag, v) -> v) -> Maybe (Tag, v) -> Maybe v
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Tag, v) -> v
    forall a b. (a, b) -> b
    snd) k
    k Map k (Tag, v)
    tvs)
    		((Maybe (k, v) -> Maybe (k, v))
    -> Tag -> Map Tag (k, v) -> Map Tag (k, v)
    forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    M.alter ((v -> (k, v)) -> Maybe v -> Maybe (k, v)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (k
    k,) (Maybe v -> Maybe (k, v))
    -> (Maybe (k, v) -> Maybe v) -> Maybe (k, v) -> Maybe (k, v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe v -> Maybe v
    f (Maybe v -> Maybe v)
    -> (Maybe (k, v) -> Maybe v) -> Maybe (k, v) -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((k, v) -> v) -> Maybe (k, v) -> Maybe v
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (k, v) -> v
    forall a b. (a, b) -> b
    snd) Tag
    t Map Tag (k, v)
    kvs)
    	Maybe (Tag, v)
    Nothing -> OMap k v -> (v -> OMap k v) -> Maybe v -> OMap k v
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe OMap k v
    om ((OMap k v
    om OMap k v -> (k, v) -> OMap k v
    forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
    |>) ((k, v) -> OMap k v) -> (v -> (k, v)) -> v -> OMap k v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k
    k, )) (Maybe v -> OMap k v) -> Maybe v -> OMap k v
    forall a b. (a -> b) -> a -> b
    $ Maybe v -> Maybe v
    f Maybe v
    forall a. Maybe a
    Nothing