{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ViewPatterns #-}

module Data.OMap.Strict (
  HasOKey (okeyL),
  OMap (Empty, (:<|:), (:|>:)),
  null,
  size,
  empty,
  singleton,
  lookup,
  member,
  (!?),
  mapUnsafe,
  fromSet,
  fromFoldable,
  fromFoldableDuplicates,
  toMap,
  assocList,
  elems,
  toStrictSeq,
  toStrictSeqOKeys,
  toStrictSeqOfPairs,
  invariantHolds,
  invariantHolds',
  (|>),
  (<|),
  (<||),
  (||>),
  (|><),
  (><|),
  elem,
  extractKeys,
  adjust,
  filter,
)
where

import Cardano.Ledger.Binary (
  DecCBOR,
  EncCBOR (encCBOR),
  decodeListLenOrIndef,
  decodeListLikeEnforceNoDuplicates,
  encodeStrictSeq,
 )
import Cardano.Ledger.Binary.Decoding (DecCBOR (decCBOR))
import Control.DeepSeq (NFData (..))
import Data.Aeson (ToJSON (..))
import Data.Default (Default (..))
import Data.Foldable qualified as F
import Data.Map.Strict qualified as Map
import Data.MapExtras qualified as MapE
import Data.Maybe (isJust)
import Data.Sequence.Strict qualified as SSeq
import Data.Set qualified as Set
import Data.Typeable (Typeable)
import GHC.Exts qualified as Exts
import GHC.Generics (Generic)
import Lens.Micro
import NoThunks.Class (NoThunks (..))
import Prelude hiding (elem, filter, lookup, null, seq)

-- | Class of types that can be mapped by a lens or a projection to an
-- Ord type.
--
-- For a type @V@, defines a lens from @V@ to and Ord type @K@.
class Ord k => HasOKey k v | v -> k where
  okeyL :: Lens' v k

-- | A general-purpose finite, insert-ordered, map that is strict in its
-- keys and values.
--
-- The strictness is enforced by the underlying strict `Map` that can
-- be looked-up by a projection or lens. and the ordering is maintained
-- by the constructing functions, leveraging `StrictSeq` to hold the
-- insert-order of the keys.
--
-- TODO: DecShareCBOR instance
data OMap k v = OMap
  { forall k v. OMap k v -> StrictSeq k
omSSeq :: !(SSeq.StrictSeq k)
  , forall k v. OMap k v -> Map k v
omMap :: !(Map.Map k v)
  }
  deriving (forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (OMap k v) x -> OMap k v
forall k v x. OMap k v -> Rep (OMap k v) x
$cto :: forall k v x. Rep (OMap k v) x -> OMap k v
$cfrom :: forall k v x. OMap k v -> Rep (OMap k v) x
Generic, OMap k v -> OMap k v -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => OMap k v -> OMap k v -> Bool
/= :: OMap k v -> OMap k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => OMap k v -> OMap k v -> Bool
== :: OMap k v -> OMap k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => OMap k v -> OMap k v -> Bool
Eq)

instance (Show v, Ord k, Show k) => Show (OMap k v) where
  show :: OMap k v -> String
show = forall a. Show a => a -> String
show forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => OMap k v -> StrictSeq (k, v)
toStrictSeqOfPairs

deriving instance (NoThunks k, NoThunks v) => NoThunks (OMap k v)

deriving instance (NFData k, NFData v) => NFData (OMap k v)

-- | \(O(1)\).
empty :: OMap k v
empty :: forall k v. OMap k v
empty = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap forall a. StrictSeq a
SSeq.Empty forall k a. Map k a
Map.empty

instance Default (OMap k v) where
  def :: OMap k v
def = forall k v. OMap k v
empty

-- | \(O(1)\). Shallow invariant using just `length` and `size`.
invariantHolds :: OMap k v -> Bool
invariantHolds :: forall k v. OMap k v -> Bool
invariantHolds (OMap StrictSeq k
sseq Map k v
kv) = forall a. StrictSeq a -> Int
SSeq.length StrictSeq k
sseq forall a. Eq a => a -> a -> Bool
== forall k a. Map k a -> Int
Map.size Map k v
kv

-- | \(O(n \log n)\). Deep, costly invariant using membership check for each
-- value. By the pigeon-hole principle, this check is exhaustive.
invariantHolds' :: Ord k => OMap k v -> Bool
invariantHolds' :: forall k v. Ord k => OMap k v -> Bool
invariantHolds' omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv) =
  forall k v. OMap k v -> Bool
invariantHolds OMap k v
omap Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\k
k -> forall a. Maybe a -> Bool
isJust forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv) StrictSeq k
sseq

-- | \(O(1)\).
null :: OMap k v -> Bool
null :: forall k v. OMap k v -> Bool
null (OMap StrictSeq k
sseq Map k v
_) = forall a. StrictSeq a -> Bool
SSeq.null StrictSeq k
sseq

-- | \(O(1)\).
size :: OMap k v -> Int
size :: forall k v. OMap k v -> Int
size (OMap StrictSeq k
sseq Map k v
_) = forall a. StrictSeq a -> Int
SSeq.length StrictSeq k
sseq

-- | \(O(1)\). Strict in its arguments.
singleton :: HasOKey k v => v -> OMap k v
singleton :: forall k v. HasOKey k v => v -> OMap k v
singleton !v
v =
  let k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL
   in forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (forall a. a -> StrictSeq a
SSeq.singleton k
k) (forall k a. k -> a -> Map k a
Map.singleton k
k v
v)

-- | \(O(\log n)\). If the key is not present 'lookup' returns
-- 'Nothing'.
lookup :: Ord k => k -> OMap k v -> Maybe v
lookup :: forall k v. Ord k => k -> OMap k v -> Maybe v
lookup k
k (OMap StrictSeq k
_seq Map k v
kv) = forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv

-- | `flip`ed version of `lookup`
(!?) :: Ord k => OMap k v -> k -> Maybe v
!? :: forall k v. Ord k => OMap k v -> k -> Maybe v
(!?) = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall k v. Ord k => k -> OMap k v -> Maybe v
lookup

-- | \(O(\log n)\). Checks membership before cons'ing.
cons :: HasOKey k v => v -> OMap k v -> OMap k v
cons :: forall k v. HasOKey k v => v -> OMap k v -> OMap k v
cons v
v omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv)
  | forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = OMap k v
omap
  | Bool
otherwise = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (k
k forall a. a -> StrictSeq a -> StrictSeq a
SSeq.<| StrictSeq k
sseq) (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v Map k v
kv)
  where
    k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL

-- | \(O(\log n)\). Checks membership before cons'ing.
(<|) :: HasOKey k v => v -> OMap k v -> OMap k v
<| :: forall k v. HasOKey k v => v -> OMap k v -> OMap k v
(<|) = forall k v. HasOKey k v => v -> OMap k v -> OMap k v
cons

infixr 5 <|

-- | \(O(\log n)\). Checks membership before cons'ing. Overwrites a
-- duplicate.
cons' :: HasOKey k v => v -> OMap k v -> OMap k v
cons' :: forall k v. HasOKey k v => v -> OMap k v -> OMap k v
cons' v
v (OMap StrictSeq k
sseq Map k v
kv)
  | forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq Map k v
kv'
  | Bool
otherwise = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (k
k forall a. a -> StrictSeq a -> StrictSeq a
SSeq.<| StrictSeq k
sseq) Map k v
kv'
  where
    k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL
    kv' :: Map k v
kv' = forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v Map k v
kv

-- | \(O(\log n)\). Checks membership before cons'ing. Overwrites a
-- duplicate.
(<||) :: HasOKey k v => v -> OMap k v -> OMap k v
<|| :: forall k v. HasOKey k v => v -> OMap k v -> OMap k v
(<||) = forall k v. HasOKey k v => v -> OMap k v -> OMap k v
cons'

infixr 5 <||

-- | \(O(\log n)\). Checks membership before snoc'ing.
snoc :: HasOKey k v => OMap k v -> v -> OMap k v
snoc :: forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv) v
v
  | forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = OMap k v
omap
  | Bool
otherwise = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v Map k v
kv)
  where
    k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL

-- | \(O(\log n)\). Checks membership before snoc'ing.
(|>) :: HasOKey k v => OMap k v -> v -> OMap k v
|> :: forall k v. HasOKey k v => OMap k v -> v -> OMap k v
(|>) = forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc

infixl 5 |>

-- | \(O(\log n)\). Checks membership before snoc'ing. Overwrites a
-- duplicate.
snoc' :: HasOKey k v => OMap k v -> v -> OMap k v
snoc' :: forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc' (OMap StrictSeq k
sseq Map k v
kv) v
v
  | forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq Map k v
kv'
  | Bool
otherwise = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) Map k v
kv'
  where
    k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL
    kv' :: Map k v
kv' = forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v Map k v
kv

-- | \(O(\log n)\). Checks membership before snoc'ing. Overwrites a
-- duplicate.
(||>) :: HasOKey k v => OMap k v -> v -> OMap k v
||> :: forall k v. HasOKey k v => OMap k v -> v -> OMap k v
(||>) = forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc'

infixl 5 ||>

-- | \(O(\log n)\).
uncons :: Ord k => OMap k v -> Maybe (v, OMap k v)
uncons :: forall k v. Ord k => OMap k v -> Maybe (v, OMap k v)
uncons (OMap StrictSeq k
sseq Map k v
kv) = case StrictSeq k
sseq of
  StrictSeq k
SSeq.Empty -> forall a. Maybe a
Nothing
  k
k SSeq.:<| StrictSeq k
ks ->
    case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv of
      Just v
v -> forall a. a -> Maybe a
Just (v
v, forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
ks (forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k v
kv))
      Maybe v
Nothing -> forall a. HasCallStack => String -> a
error String
"Invariant falsified! In OMap, key from sequence not found in corresponding map"

-- | \(O(\log n)\).
unsnoc :: Ord k => OMap k v -> Maybe (OMap k v, v)
unsnoc :: forall k v. Ord k => OMap k v -> Maybe (OMap k v, v)
unsnoc (OMap StrictSeq k
sseq Map k v
kv) = case StrictSeq k
sseq of
  StrictSeq k
SSeq.Empty -> forall a. Maybe a
Nothing
  StrictSeq k
ks SSeq.:|> k
k ->
    case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv of
      Just v
v -> forall a. a -> Maybe a
Just (forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
ks (forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k v
kv), v
v)
      Maybe v
Nothing -> forall a. HasCallStack => String -> a
error String
"Invariant falsified! In OMap, key from sequence not found in corresponding map"

-- | \(O(n \log n)\). Checks membership before snoc'ing.
-- De-duplicates the StrictSeq without overwriting.
-- Starts from the left or head, using `foldl'`
fromFoldable :: (Foldable f, HasOKey k v) => f v -> OMap k v
fromFoldable :: forall (f :: * -> *) k v.
(Foldable f, HasOKey k v) =>
f v -> OMap k v
fromFoldable = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc forall k v. OMap k v
empty

-- | \(O(n \log n)\). Checks membership before snoc'ing.
-- De-duplicates the StrictSeq and collects and returns the duplicates found.
-- Starts from the left or head, using `foldl'`
fromFoldableDuplicates :: (Foldable f, HasOKey k v, Ord v) => f v -> (Set.Set v, OMap k v)
fromFoldableDuplicates :: forall (f :: * -> *) k v.
(Foldable f, HasOKey k v, Ord v) =>
f v -> (Set v, OMap k v)
fromFoldableDuplicates = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' forall k v.
(HasOKey k v, Ord v) =>
(Set v, OMap k v) -> v -> (Set v, OMap k v)
snoc_ (forall a. Set a
Set.empty, forall k v. OMap k v
empty)
  where
    snoc_ :: (HasOKey k v, Ord v) => (Set.Set v, OMap k v) -> v -> (Set.Set v, OMap k v)
    snoc_ :: forall k v.
(HasOKey k v, Ord v) =>
(Set v, OMap k v) -> v -> (Set v, OMap k v)
snoc_ (Set v
duplicates, omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv)) v
v =
      let k :: k
k = v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL
       in if forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv
            then (forall a. Ord a => a -> Set a -> Set a
Set.insert v
v Set v
duplicates, OMap k v
omap)
            else (Set v
duplicates, forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v Map k v
kv))

-- | \(O(n \log n)\).
fromSet :: HasOKey k v => Set.Set v -> OMap k v
fromSet :: forall k v. HasOKey k v => Set v -> OMap k v
fromSet = forall (f :: * -> *) k v.
(Foldable f, HasOKey k v) =>
f v -> OMap k v
fromFoldable

-- | \(O(1)\).
toMap :: OMap k v -> Map.Map k v
toMap :: forall k v. OMap k v -> Map k v
toMap = forall k v. OMap k v -> Map k v
omMap

-- | \(O(n \log n)\).
toStrictSeq :: Ord k => OMap k v -> SSeq.StrictSeq v
toStrictSeq :: forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq (OMap StrictSeq k
sseq Map k v
kv) = StrictSeq k
sseq forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \k
k -> let !v :: v
v = Map k v
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k in v
v

-- | \(O(1)\).
toStrictSeqOKeys :: OMap k v -> SSeq.StrictSeq k
toStrictSeqOKeys :: forall k v. OMap k v -> StrictSeq k
toStrictSeqOKeys = forall k v. OMap k v -> StrictSeq k
omSSeq

-- | \(O(n \log n)\).
toStrictSeqOfPairs :: Ord k => OMap k v -> SSeq.StrictSeq (k, v)
toStrictSeqOfPairs :: forall k v. Ord k => OMap k v -> StrictSeq (k, v)
toStrictSeqOfPairs (OMap StrictSeq k
sseq Map k v
kv) = StrictSeq k
sseq forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \k
k -> let !v :: v
v = Map k v
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k in (k
k, v
v)

-- | \(O(\log n)\). Key membership check.
member :: Ord k => k -> OMap k v -> Bool
member :: forall k v. Ord k => k -> OMap k v -> Bool
member k
k (OMap StrictSeq k
_sseq Map k v
kv) = forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv

-- | \(O(\log n)\). Value membership check.
elem :: (HasOKey k v, Eq v) => v -> OMap k v -> Bool
elem :: forall k v. (HasOKey k v, Eq v) => v -> OMap k v -> Bool
elem v
v = (forall a. a -> Maybe a
Just v
v forall a. Eq a => a -> a -> Bool
==) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => k -> OMap k v -> Maybe v
lookup (v
v forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL)

-- | \(O(n)\). Given a `Set` of @k@s, and an `OMap` @k@ @v@ return
-- a pair of `Map` and `OMap` where the @k@s in the `Set` have been
-- removed from the `OMap` and presented as a separate `Map`.
extractKeys :: Ord k => Set.Set k -> OMap k v -> (OMap k v, Map.Map k v)
extractKeys :: forall k v. Ord k => Set k -> OMap k v -> (OMap k v, Map k v)
extractKeys Set k
ks (OMap StrictSeq k
sseq Map k v
kv) =
  let (Map k v
kv', Map k v
extractedKv) = forall k a. Ord k => Map k a -> Set k -> (Map k a, Map k a)
MapE.extractKeys Map k v
kv Set k
ks
      sseq' :: StrictSeq k
sseq' =
        forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl'
          (\StrictSeq k
accum k
k -> if forall a. Ord a => a -> Set a -> Bool
Set.member k
k Set k
ks then StrictSeq k
accum else StrictSeq k
accum forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k)
          forall a. StrictSeq a
SSeq.empty
          StrictSeq k
sseq
   in (forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq' Map k v
kv', Map k v
extractedKv)

-- | \(O(n)\). Like `Map.adjust`.
--
-- Returns the original `OMap` unaltered when the key does not exist.
--
-- If the key exists, then the function is applied to the value, but we need to consider
-- three possible cases:
--
--     1. The modified value's `okeyL` is unaltered
--            - we return omap with the adjusted value,
--     2. The modified value's `okeyL` is altered, but not a duplicate
--            - we return the omap with adjusted key (in place) and value
--     3. The modified value's `okeyL` is altered and is a duplicate
--            - we return the omap with the old key deleted from the sequence but
--              without inserting the new key since it is a duplicate, and
--              deleting old value and inserting the new value in place of its duplicate.
--
-- Examples:
--
-- >>> import Data.OMap.Strict
-- >>> import Lens.Micro
-- >>> instance HasOKey Int (Int, Char) where okeyL = _1
-- >>> let m = fromFoldable $ zip [1,2] ['a','b'] :: OMap Int (Int, Char)
-- >>> m
-- StrictSeq {fromStrict = fromList [(1,(1,'a')),(2,(2,'b'))]}
-- >>> let adjustingFn (k, v) = (k, succ v) -- Changes the value
-- >>> let overwritingAdjustingFn (k,v) = (succ k, v) -- Changes the `okeyL`.
-- >>> adjust adjustingFn 1 m
-- StrictSeq {fromStrict = fromList [(1,(1,'b')),(2,(2,'b'))]}
-- >>> adjust overwritingAdjustingFn  1 m
-- StrictSeq {fromStrict = fromList [(2,(2,'a'))]}
adjust :: HasOKey k v => (v -> v) -> k -> OMap k v -> OMap k v
adjust :: forall k v. HasOKey k v => (v -> v) -> k -> OMap k v -> OMap k v
adjust v -> v
f k
k omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv) =
  case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv of
    Maybe v
Nothing -> OMap k v
omap
    Just v
v ->
      let v' :: v
v' = v -> v
f v
v
          k' :: k
k' = v
v' forall s a. s -> Getting a s a -> a
^. forall k v. HasOKey k v => Lens' v k
okeyL
       in if k
k' forall a. Eq a => a -> a -> Bool
== k
k
            then forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq (forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v' Map k v
kv)
            else
              let kv' :: Map k v
kv' = forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k' v
v' forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k v
kv
                  (StrictSeq k
lseq, StrictSeq k
rseq) = case forall a. (a -> Bool) -> StrictSeq a -> (StrictSeq a, StrictSeq a)
SSeq.spanl (forall a. Eq a => a -> a -> Bool
/= k
k) StrictSeq k
sseq of
                    (StrictSeq k
l, k
_ SSeq.:<| StrictSeq k
r) -> (StrictSeq k
l, StrictSeq k
r)
                    (StrictSeq k, StrictSeq k)
_ -> forall a. HasCallStack => String -> a
error String
"Impossible: supplied key expected to be in the sequence"
               in case forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k' Map k v
kv of
                    Maybe v
Nothing -> forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
lseq forall a. Semigroup a => a -> a -> a
<> (k
k' forall a. a -> StrictSeq a -> StrictSeq a
SSeq.:<| StrictSeq k
rseq)) Map k v
kv'
                    Just v
_ -> forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
lseq forall a. Semigroup a => a -> a -> a
<> StrictSeq k
rseq) Map k v
kv'

-- | This mapping function is only safe when the key stored in the new value matches the
-- key stored in the new value. This invariant is not checked for performance reasons
mapUnsafe :: (v1 -> v2) -> OMap k v1 -> OMap k v2
mapUnsafe :: forall v1 v2 k. (v1 -> v2) -> OMap k v1 -> OMap k v2
mapUnsafe v1 -> v2
f (OMap StrictSeq k
sseq Map k v1
kv) = forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq (forall a b k. (a -> b) -> Map k a -> Map k b
Map.map v1 -> v2
f Map k v1
kv)

-- | \(O(1)\)
pattern Empty :: OMap k v
pattern $bEmpty :: forall k v. OMap k v
$mEmpty :: forall {r} {k} {v}. OMap k v -> ((# #) -> r) -> ((# #) -> r) -> r
Empty <- (null -> True)
  where
    Empty = forall k v. OMap k v
empty

-- | \(O(\log n)\).
pattern (:<|:) :: (HasOKey k v, Ord k) => v -> OMap k v -> OMap k v
pattern x $b:<|: :: forall k v. (HasOKey k v, Ord k) => v -> OMap k v -> OMap k v
$m:<|: :: forall {r} {k} {v}.
(HasOKey k v, Ord k) =>
OMap k v -> (v -> OMap k v -> r) -> ((# #) -> r) -> r
:<|: xs <- (uncons -> Just (x, xs))
  where
    v
x :<|: OMap k v
xs = v
x forall k v. HasOKey k v => v -> OMap k v -> OMap k v
<| OMap k v
xs

infixr 5 :<|:

-- | \(O(\log n)\).
pattern (:|>:) :: (HasOKey k v, Ord k) => OMap k v -> v -> OMap k v
pattern xs $b:|>: :: forall k v. (HasOKey k v, Ord k) => OMap k v -> v -> OMap k v
$m:|>: :: forall {r} {k} {v}.
(HasOKey k v, Ord k) =>
OMap k v -> (OMap k v -> v -> r) -> ((# #) -> r) -> r
:|>: x <- (unsnoc -> Just (xs, x))
  where
    OMap k v
xs :|>: v
x = OMap k v
xs forall k v. HasOKey k v => OMap k v -> v -> OMap k v
|> v
x

infixl 5 :|>:

{-# COMPLETE Empty, (:|>:) #-}
{-# COMPLETE Empty, (:<|:) #-}

-- | \( O(n \log m) \). For every uncons-ed element from the sequence on the right,
-- check its membership in the sequence on the left, before snoc'ing it.
-- Preserve order. Remove duplicates from sequence on the right.
(|><) :: HasOKey k v => OMap k v -> OMap k v -> OMap k v
OMap k v
omapl |>< :: forall k v. HasOKey k v => OMap k v -> OMap k v -> OMap k v
|>< OMap k v
omapr = case OMap k v
omapr of
  OMap k v
Empty -> OMap k v
omapl
  v
r :<|: OMap k v
rs -> (OMap k v
omapl forall k v. HasOKey k v => OMap k v -> v -> OMap k v
|> v
r) forall k v. HasOKey k v => OMap k v -> OMap k v -> OMap k v
|>< OMap k v
rs

infixl 5 |><

-- | \( O(m \log n) \). For every unsnoc-ed element from the sequence on the left,
-- check its membership in the sequence on the right, before cons'ing it.
-- Preserve order. Remove duplicates from sequence on the left.
(><|) :: HasOKey k v => OMap k v -> OMap k v -> OMap k v
OMap k v
omapl ><| :: forall k v. HasOKey k v => OMap k v -> OMap k v -> OMap k v
><| OMap k v
omapr = case OMap k v
omapl of
  OMap k v
Empty -> OMap k v
omapr
  OMap k v
ls :|>: v
l -> OMap k v
ls forall k v. HasOKey k v => OMap k v -> OMap k v -> OMap k v
><| (v
l forall k v. HasOKey k v => v -> OMap k v -> OMap k v
<| OMap k v
omapr)

infixr 5 ><|

instance HasOKey k v => Exts.IsList (OMap k v) where
  type Item (OMap k v) = v
  fromList :: [Item (OMap k v)] -> OMap k v
fromList = forall (f :: * -> *) k v.
(Foldable f, HasOKey k v) =>
f v -> OMap k v
fromFoldable
  toList :: OMap k v -> [Item (OMap k v)]
toList = forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList

assocList :: Ord k => OMap k v -> [(k, v)]
assocList :: forall k v. Ord k => OMap k v -> [(k, v)]
assocList = forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => OMap k v -> StrictSeq (k, v)
toStrictSeqOfPairs

elems :: Ord k => OMap k v -> [v]
elems :: forall k v. Ord k => OMap k v -> [v]
elems = forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq

instance (HasOKey k v, ToJSON v) => ToJSON (OMap k v) where
  toJSON :: OMap k v -> Value
toJSON = forall a. ToJSON a => a -> Value
toJSON forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq
  toEncoding :: OMap k v -> Encoding
toEncoding = forall a. ToJSON a => a -> Encoding
toEncoding forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq

instance HasOKey k v => Semigroup (OMap k v) where
  <> :: OMap k v -> OMap k v -> OMap k v
(<>) = forall k v. HasOKey k v => OMap k v -> OMap k v -> OMap k v
(|><)

instance HasOKey k v => Monoid (OMap k v) where
  mempty :: OMap k v
mempty = forall k v. OMap k v
empty

instance Ord k => Foldable (OMap k) where
  foldMap :: forall m a. Monoid m => (a -> m) -> OMap k a -> m
foldMap a -> m
f (OMap StrictSeq k
sseq Map k a
kv) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap (\k
k -> a -> m
f (Map k a
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k)) StrictSeq k
sseq
  {-# INLINEABLE foldMap #-}
  foldr :: forall a b. (a -> b -> b) -> b -> OMap k a -> b
foldr a -> b -> b
f b
z (OMap StrictSeq k
sseq Map k a
kv) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr (\k
k -> a -> b -> b
f (Map k a
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k)) b
z StrictSeq k
sseq
  {-# INLINEABLE foldr #-}
  foldl :: forall b a. (b -> a -> b) -> b -> OMap k a -> b
foldl b -> a -> b
f b
z (OMap StrictSeq k
sseq Map k a
kv) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl (\b
acc k
k -> b -> a -> b
f b
acc (Map k a
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k)) b
z StrictSeq k
sseq
  {-# INLINEABLE foldl #-}
  foldr' :: forall a b. (a -> b -> b) -> b -> OMap k a -> b
foldr' a -> b -> b
f b
z (OMap StrictSeq k
sseq Map k a
kv) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr' (\k
k -> a -> b -> b
f (Map k a
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k)) b
z StrictSeq k
sseq
  {-# INLINEABLE foldr' #-}
  foldl' :: forall b a. (b -> a -> b) -> b -> OMap k a -> b
foldl' b -> a -> b
f b
z (OMap StrictSeq k
sseq Map k a
kv) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\b
acc k
k -> b -> a -> b
f b
acc (Map k a
kv forall k a. Ord k => Map k a -> k -> a
Map.! k
k)) b
z StrictSeq k
sseq
  {-# INLINEABLE foldl' #-}
  length :: forall a. OMap k a -> Int
length = forall k a. Map k a -> Int
Map.size forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. OMap k v -> Map k v
omMap
  {-# INLINE length #-}
  null :: forall a. OMap k a -> Bool
null = forall k a. Map k a -> Bool
Map.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. OMap k v -> Map k v
omMap
  {-# INLINE null #-}

instance (Typeable k, EncCBOR v, Ord k) => EncCBOR (OMap k v) where
  encCBOR :: OMap k v -> Encoding
encCBOR OMap k v
omap = forall a. (a -> Encoding) -> StrictSeq a -> Encoding
encodeStrictSeq forall a. EncCBOR a => a -> Encoding
encCBOR (forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq OMap k v
omap)

instance (Typeable k, HasOKey k v, DecCBOR v, Eq v) => DecCBOR (OMap k v) where
  decCBOR :: forall s. Decoder s (OMap k v)
decCBOR =
    forall s a b c.
Monoid b =>
Decoder s (Maybe Int)
-> (a -> b -> b) -> (b -> (Int, c)) -> Decoder s a -> Decoder s c
decodeListLikeEnforceNoDuplicates
      forall s. Decoder s (Maybe Int)
decodeListLenOrIndef
      (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall k v. HasOKey k v => OMap k v -> v -> OMap k v
snoc)
      (\OMap k v
omap -> (forall k v. OMap k v -> Int
size OMap k v
omap, OMap k v
omap))
      forall a s. DecCBOR a => Decoder s a
decCBOR

-- | \( O(n \log n) \)
filter :: Ord k => (v -> Bool) -> OMap k v -> OMap k v
filter :: forall k v. Ord k => (v -> Bool) -> OMap k v -> OMap k v
filter v -> Bool
f (OMap StrictSeq k
sseq Map k v
kv) =
  let kv' :: Map k v
kv' = forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter v -> Bool
f Map k v
kv
      sseq' :: StrictSeq k
sseq' =
        forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\StrictSeq k
accum k
k -> if forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv' then StrictSeq k
accum forall a. StrictSeq a -> a -> StrictSeq a
SSeq.:|> k
k else StrictSeq k
accum) forall a. StrictSeq a
SSeq.empty StrictSeq k
sseq
   in forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq' Map k v
kv'