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

-- FIXME: this is a duplicate of the OMap implementation, and will eventually
-- become the only OMap once we lift the key-in-values constraint of the
-- previous version.
module Data.SimpleOMap.Strict (
  OMap (Empty, (:<|:), (:|>:)),
  null,
  size,
  empty,
  singleton,
  lookup,
  member,
  (!?),
  fromSet,
  fromFoldable,
  fromFoldableDuplicates,
  toMap,
  assocList,
  elems,
  toStrictSeq,
  toStrictSeqOKeys,
  toStrictSeqOfPairs,
  invariantHolds,
  invariantHolds',
  (|>),
  (<|),
  (<||),
  (||>),
  (|><),
  (><|),
  elem,
  extractKeys,
  adjust,
  filter,
  decodeOMap,
) where

import Cardano.Ledger.Binary (
  DecCBOR,
  Decoder,
  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.Functor ((<&>))
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 GHC.Exts qualified as Exts
import GHC.Generics (Generic)
import NoThunks.Class (NoThunks (..))
import Prelude hiding (elem, filter, lookup, null, seq)

-- | A general-purpose finite, insert-ordered, map that is strict in its
-- keys and values.
--
-- The strictness is enforced by the underlying strict `Map`, 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 x. OMap k v -> Rep (OMap k v) x)
-> (forall x. Rep (OMap k v) x -> OMap k v) -> Generic (OMap k v)
forall x. Rep (OMap k v) x -> OMap k v
forall x. OMap k v -> Rep (OMap k v) x
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
$cfrom :: forall k v x. OMap k v -> Rep (OMap k v) x
from :: forall x. OMap k v -> Rep (OMap k v) x
$cto :: forall k v x. Rep (OMap k v) x -> OMap k v
to :: forall x. Rep (OMap k v) x -> OMap k v
Generic, OMap k v -> OMap k v -> Bool
(OMap k v -> OMap k v -> Bool)
-> (OMap k v -> OMap k v -> Bool) -> Eq (OMap k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => 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
/= :: 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 = StrictSeq (k, v) -> String
forall a. Show a => a -> String
show (StrictSeq (k, v) -> String)
-> (OMap k v -> StrictSeq (k, v)) -> OMap k v -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OMap k v -> StrictSeq (k, v)
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 = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
forall a. StrictSeq a
SSeq.Empty Map k v
forall k a. Map k a
Map.empty

instance Default (OMap k v) where
  def :: OMap k v
def = OMap k v
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) = StrictSeq k -> Int
forall a. StrictSeq a -> Int
SSeq.length StrictSeq k
sseq Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Map k v -> Int
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) =
  OMap k v -> Bool
forall k v. OMap k v -> Bool
invariantHolds OMap k v
omap Bool -> Bool -> Bool
&& (k -> Bool) -> StrictSeq k -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\k
k -> Maybe v -> Bool
forall a. Maybe a -> Bool
isJust (Maybe v -> Bool) -> Maybe v -> Bool
forall a b. (a -> b) -> a -> b
$ k -> Map k v -> Maybe v
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
_) = StrictSeq k -> Bool
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
_) = StrictSeq k -> Int
forall a. StrictSeq a -> Int
SSeq.length StrictSeq k
sseq

-- | \(O(1)\). Strict in its arguments.
singleton :: k -> v -> OMap k v
singleton :: forall k v. k -> v -> OMap k v
singleton !k
k !v
v = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (k -> StrictSeq k
forall a. a -> StrictSeq a
SSeq.singleton k
k) (k -> v -> Map k v
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) = k -> Map k v -> Maybe v
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
(!?) = (k -> OMap k v -> Maybe v) -> OMap k v -> k -> Maybe v
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> OMap k v -> Maybe v
forall k v. Ord k => k -> OMap k v -> Maybe v
lookup

-- | \(O(\log n)\). Checks membership before cons'ing.
cons :: Ord k => k -> v -> OMap k v -> OMap k v
cons :: forall k v. Ord k => k -> v -> OMap k v -> OMap k v
cons k
k v
v omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv)
  | k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = OMap k v
omap
  | Bool
otherwise = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (k
k k -> StrictSeq k -> StrictSeq k
forall a. a -> StrictSeq a -> StrictSeq a
SSeq.<| StrictSeq k
sseq) (k -> v -> Map k v -> Map k v
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.
(<|) :: Ord k => (k, v) -> OMap k v -> OMap k v
<| :: forall k v. Ord k => (k, v) -> OMap k v -> OMap k v
(<|) = (k -> v -> OMap k v -> OMap k v) -> (k, v) -> OMap k v -> OMap k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> OMap k v -> OMap k v
forall k v. Ord k => k -> v -> OMap k v -> OMap k v
cons

infixr 5 <|

-- | \(O(\log n)\). Checks membership before cons'ing. Overwrites a
-- duplicate.
cons' :: Ord k => k -> v -> OMap k v -> OMap k v
cons' :: forall k v. Ord k => k -> v -> OMap k v -> OMap k v
cons' k
k v
v (OMap StrictSeq k
sseq Map k v
kv)
  | k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq Map k v
kv'
  | Bool
otherwise = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (k
k k -> StrictSeq k -> StrictSeq k
forall a. a -> StrictSeq a -> StrictSeq a
SSeq.<| StrictSeq k
sseq) Map k v
kv'
  where
    kv' :: Map k v
kv' = k -> v -> Map k v -> Map k v
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.
(<||) :: Ord k => (k, v) -> OMap k v -> OMap k v
<|| :: forall k v. Ord k => (k, v) -> OMap k v -> OMap k v
(<||) = (k -> v -> OMap k v -> OMap k v) -> (k, v) -> OMap k v -> OMap k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> OMap k v -> OMap k v
forall k v. Ord k => k -> v -> OMap k v -> OMap k v
cons'

infixr 5 <||

-- TODO: export along with others that are hidden or remove them completely.

-- | \(O(\log n)\). Checks membership before snoc'ing.
snoc :: Ord k => OMap k v -> k -> v -> OMap k v
snoc :: forall k v. Ord k => OMap k v -> k -> v -> OMap k v
snoc omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv) k
k v
v
  | k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = OMap k v
omap
  | Bool
otherwise = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq StrictSeq k -> k -> StrictSeq k
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) (k -> v -> Map k v -> Map k v
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.
(|>) :: Ord k => OMap k v -> (k, v) -> OMap k v
OMap k v
omap |> :: forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
|> (k
k, v
v) = OMap k v -> k -> v -> OMap k v
forall k v. Ord k => OMap k v -> k -> v -> OMap k v
snoc OMap k v
omap k
k v
v

infixl 5 |>

-- | \(O(\log n)\). Checks membership before snoc'ing. Overwrites a
-- duplicate.
snoc' :: Ord k => OMap k v -> k -> v -> OMap k v
snoc' :: forall k v. Ord k => OMap k v -> k -> v -> OMap k v
snoc' (OMap StrictSeq k
sseq Map k v
kv) k
k v
v
  | k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq Map k v
kv'
  | Bool
otherwise = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq StrictSeq k -> k -> StrictSeq k
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) Map k v
kv'
  where
    kv' :: Map k v
kv' = k -> v -> Map k v -> Map k v
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.
(||>) :: Ord k => OMap k v -> (k, v) -> OMap k v
OMap k v
omap ||> :: forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
||> (k
k, v
v) = OMap k v -> k -> v -> OMap k v
forall k v. Ord k => OMap k v -> k -> v -> OMap k v
snoc' OMap k v
omap k
k v
v

infixl 5 ||>

-- | \(O(\log n)\).
uncons :: Ord k => OMap k v -> Maybe ((k, v), OMap k v)
uncons :: forall k v. Ord k => OMap k v -> Maybe ((k, v), OMap k v)
uncons (OMap StrictSeq k
sseq Map k v
kv) = case StrictSeq k
sseq of
  StrictSeq k
SSeq.Empty -> Maybe ((k, v), OMap k v)
forall a. Maybe a
Nothing
  k
k SSeq.:<| StrictSeq k
ks ->
    case k -> Map k v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv of
      Just v
v -> ((k, v), OMap k v) -> Maybe ((k, v), OMap k v)
forall a. a -> Maybe a
Just ((k
k, v
v), StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
ks (k -> Map k v -> Map k v
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k v
kv))
      Maybe v
Nothing -> String -> Maybe ((k, v), OMap k v)
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, (k, v))
unsnoc :: forall k v. Ord k => OMap k v -> Maybe (OMap k v, (k, v))
unsnoc (OMap StrictSeq k
sseq Map k v
kv) = case StrictSeq k
sseq of
  StrictSeq k
SSeq.Empty -> Maybe (OMap k v, (k, v))
forall a. Maybe a
Nothing
  StrictSeq k
ks SSeq.:|> k
k ->
    case k -> Map k v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
kv of
      Just v
v -> (OMap k v, (k, v)) -> Maybe (OMap k v, (k, v))
forall a. a -> Maybe a
Just (StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
ks (k -> Map k v -> Map k v
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k Map k v
kv), (k
k, v
v))
      Maybe v
Nothing -> String -> Maybe (OMap k v, (k, v))
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, Ord k) => f (k, v) -> OMap k v
fromFoldable :: forall (f :: * -> *) k v.
(Foldable f, Ord k) =>
f (k, v) -> OMap k v
fromFoldable = (OMap k v -> (k, v) -> OMap k v)
-> OMap k v -> f (k, v) -> OMap k v
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' OMap k v -> (k, v) -> OMap k v
forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
(|>) OMap k v
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, Ord k, Ord v) => f (k, v) -> (Set.Set (k, v), OMap k v)
fromFoldableDuplicates :: forall (f :: * -> *) k v.
(Foldable f, Ord k, Ord v) =>
f (k, v) -> (Set (k, v), OMap k v)
fromFoldableDuplicates = ((Set (k, v), OMap k v) -> (k, v) -> (Set (k, v), OMap k v))
-> (Set (k, v), OMap k v) -> f (k, v) -> (Set (k, v), OMap k v)
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (Set (k, v), OMap k v) -> (k, v) -> (Set (k, v), OMap k v)
forall k v.
(Ord k, Ord v) =>
(Set (k, v), OMap k v) -> (k, v) -> (Set (k, v), OMap k v)
snoc_ (Set (k, v)
forall a. Set a
Set.empty, OMap k v
forall k v. OMap k v
empty)
  where
    snoc_ :: (Ord k, Ord v) => (Set.Set (k, v), OMap k v) -> (k, v) -> (Set.Set (k, v), OMap k v)
    snoc_ :: forall k v.
(Ord k, Ord v) =>
(Set (k, v), OMap k v) -> (k, v) -> (Set (k, v), OMap k v)
snoc_ (Set (k, v)
duplicates, omap :: OMap k v
omap@(OMap StrictSeq k
sseq Map k v
kv)) (k
k, v
v) =
      if k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv
        then ((k, v) -> Set (k, v) -> Set (k, v)
forall a. Ord a => a -> Set a -> Set a
Set.insert (k
k, v
v) Set (k, v)
duplicates, OMap k v
omap)
        else (Set (k, v)
duplicates, StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap (StrictSeq k
sseq StrictSeq k -> k -> StrictSeq k
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k) (k -> v -> Map k v -> Map k v
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 :: Ord k => Set.Set (k, v) -> OMap k v
fromSet :: forall k v. Ord k => Set (k, v) -> OMap k v
fromSet = Set (k, v) -> OMap k v
forall (f :: * -> *) k v.
(Foldable f, Ord k) =>
f (k, 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 = OMap k v -> Map k v
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 StrictSeq k -> (k -> v) -> StrictSeq v
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \k
k -> let !v :: v
v = Map k v
kv Map k v -> k -> v
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 = OMap k v -> StrictSeq k
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 StrictSeq k -> (k -> (k, v)) -> StrictSeq (k, v)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \k
k -> let !v :: v
v = Map k v
kv Map k v -> k -> v
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) = k -> Map k v -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k v
kv

-- | \(O(\log n)\). Key-value pair membership check.
elem :: (Ord k, Eq v) => k -> v -> OMap k v -> Bool
elem :: forall k v. (Ord k, Eq v) => k -> v -> OMap k v -> Bool
elem k
k v
v = (v -> Maybe v
forall a. a -> Maybe a
Just v
v Maybe v -> Maybe v -> Bool
forall a. Eq a => a -> a -> Bool
==) (Maybe v -> Bool) -> (OMap k v -> Maybe v) -> OMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> OMap k v -> Maybe v
forall k v. Ord k => k -> OMap k v -> Maybe v
lookup k
k

-- | \(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) = Map k v -> Set k -> (Map k v, Map k v)
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' =
        (StrictSeq k -> k -> StrictSeq k)
-> StrictSeq k -> StrictSeq k -> StrictSeq k
forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl'
          (\StrictSeq k
accum k
k -> if k -> Set k -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member k
k Set k
ks then StrictSeq k
accum else StrictSeq k
accum StrictSeq k -> k -> StrictSeq k
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> k
k)
          StrictSeq k
forall a. StrictSeq a
SSeq.empty
          StrictSeq k
sseq
   in (StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq' Map k v
kv', Map k v
extractedKv)

-- | \(O(\log n)\). Like `Map.adjust`.
--
-- Update a value at a specific key with the result of the provided function.
-- Returns the original `OMap` unaltered when the key does not exist.
--
-- Examples:
--
-- >>> import Data.SimpleOMap.Strict
-- >>> let m = fromFoldable $ zip [1,2] ['a','b'] :: OMap Int Char
-- >>> m
-- StrictSeq {fromStrict = fromList [(1,'a'),(2,'b')]}
-- >>> adjust succ 1 m
-- StrictSeq {fromStrict = fromList [(1,'b'),(2,'b')]}
-- >>> adjust succ 3 m
-- StrictSeq {fromStrict = fromList [(1,'a'),(2,'b')]}
adjust :: Ord k => (v -> v) -> k -> OMap k v -> OMap k v
adjust :: forall k v. Ord k => (v -> v) -> k -> OMap k v -> OMap k v
adjust v -> v
f k
k (OMap StrictSeq k
sseq Map k v
kv) = StrictSeq k -> Map k v -> OMap k v
forall k v. StrictSeq k -> Map k v -> OMap k v
OMap StrictSeq k
sseq ((v -> v) -> k -> Map k v -> Map k v
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust v -> v
f k
k Map k v
kv)

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

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

infixr 5 :<|:

-- | \(O(\log n)\).
pattern (:|>:) :: Ord k => OMap k v -> (k, v) -> OMap k v
pattern xs $m:|>: :: forall {r} {k} {v}.
Ord k =>
OMap k v -> (OMap k v -> (k, v) -> r) -> ((# #) -> r) -> r
$b:|>: :: forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
:|>: x <- (unsnoc -> Just (xs, x))
  where
    OMap k v
xs :|>: (k, v)
x = OMap k v
xs OMap k v -> (k, v) -> OMap k v
forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
|> (k, 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.
(|><) :: Ord k => OMap k v -> OMap k v -> OMap k v
OMap k v
omapl |>< :: forall k v. Ord k => 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
  (k, v)
r :<|: OMap k v
rs -> (OMap k v
omapl OMap k v -> (k, v) -> OMap k v
forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
|> (k, v)
r) OMap k v -> OMap k v -> OMap k v
forall k v. Ord k => 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.
(><|) :: Ord k => OMap k v -> OMap k v -> OMap k v
OMap k v
omapl ><| :: forall k v. Ord k => 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 :|>: (k, v)
l -> OMap k v
ls OMap k v -> OMap k v -> OMap k v
forall k v. Ord k => OMap k v -> OMap k v -> OMap k v
><| ((k, v)
l (k, v) -> OMap k v -> OMap k v
forall k v. Ord k => (k, v) -> OMap k v -> OMap k v
<| OMap k v
omapr)

infixr 5 ><|

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

assocList :: Ord k => OMap k v -> [(k, v)]
assocList :: forall k v. Ord k => OMap k v -> [(k, v)]
assocList = StrictSeq (k, v) -> [(k, v)]
forall a. StrictSeq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (StrictSeq (k, v) -> [(k, v)])
-> (OMap k v -> StrictSeq (k, v)) -> OMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OMap k v -> StrictSeq (k, v)
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 = StrictSeq v -> [v]
forall a. StrictSeq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (StrictSeq v -> [v])
-> (OMap k v -> StrictSeq v) -> OMap k v -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OMap k v -> StrictSeq v
forall k v. Ord k => OMap k v -> StrictSeq v
toStrictSeq

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

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

instance Ord k => Monoid (OMap k v) where
  mempty :: OMap k v
mempty = OMap k v
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) = (k -> m) -> StrictSeq k -> m
forall m a. Monoid m => (a -> m) -> StrictSeq a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap (\k
k -> a -> m
f (Map k a
kv Map k a -> k -> a
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) = (k -> b -> b) -> b -> StrictSeq k -> b
forall a b. (a -> b -> b) -> b -> StrictSeq a -> b
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 Map k a -> k -> a
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) = (b -> k -> b) -> b -> StrictSeq k -> b
forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
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 Map k a -> k -> a
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) = (k -> b -> b) -> b -> StrictSeq k -> b
forall a b. (a -> b -> b) -> b -> StrictSeq a -> b
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 Map k a -> k -> a
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) = (b -> k -> b) -> b -> StrictSeq k -> b
forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
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 Map k a -> k -> a
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 = Map k a -> Int
forall k a. Map k a -> Int
Map.size (Map k a -> Int) -> (OMap k a -> Map k a) -> OMap k a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OMap k a -> Map k a
forall k v. OMap k v -> Map k v
omMap
  {-# INLINE length #-}
  null :: forall a. OMap k a -> Bool
null = Map k a -> Bool
forall k a. Map k a -> Bool
Map.null (Map k a -> Bool) -> (OMap k a -> Map k a) -> OMap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OMap k a -> Map k a
forall k v. OMap k v -> Map k v
omMap
  {-# INLINE null #-}

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

instance (Ord k, DecCBOR k, DecCBOR v, Eq v) => DecCBOR (OMap k v) where
  decCBOR :: forall s. Decoder s (OMap k v)
decCBOR = Decoder s (k, v) -> Decoder s (OMap k v)
forall k s v. Ord k => Decoder s (k, v) -> Decoder s (OMap k v)
decodeOMap Decoder s (k, v)
forall s. Decoder s (k, v)
forall a s. DecCBOR a => Decoder s a
decCBOR

decodeOMap :: Ord k => Decoder s (k, v) -> Decoder s (OMap k v)
decodeOMap :: forall k s v. Ord k => Decoder s (k, v) -> Decoder s (OMap k v)
decodeOMap Decoder s (k, v)
decKeyValue =
  Decoder s (Maybe Int)
-> ((k, v) -> OMap k v -> OMap k v)
-> (OMap k v -> (Int, OMap k v))
-> Decoder s (k, v)
-> Decoder s (OMap k v)
forall s a b c.
Monoid b =>
Decoder s (Maybe Int)
-> (a -> b -> b) -> (b -> (Int, c)) -> Decoder s a -> Decoder s c
decodeListLikeEnforceNoDuplicates
    Decoder s (Maybe Int)
forall s. Decoder s (Maybe Int)
decodeListLenOrIndef
    ((OMap k v -> (k, v) -> OMap k v) -> (k, v) -> OMap k v -> OMap k v
forall a b c. (a -> b -> c) -> b -> a -> c
flip OMap k v -> (k, v) -> OMap k v
forall k v. Ord k => OMap k v -> (k, v) -> OMap k v
(|>))
    (\OMap k v
omap -> (OMap k v -> Int
forall k v. OMap k v -> Int
size OMap k v
omap, OMap k v
omap))
    Decoder s (k, v)
decKeyValue

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