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