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

module Data.OSet.Strict (
  OSet (Empty, (:<|:), (:|>:)),
  null,
  size,
  empty,
  singleton,
  lookup,
  member,
  (!?),
  fromList,
  fromStrictSeq,
  fromStrictSeqDuplicates,
  toStrictSeq,
  toSet,
  fromSet,
  fromFoldable,
  fromFoldableDuplicates,
  invariantHolds,
  invariantHolds',
  (|>),
  (<|),
  (|><),
  (><|),
  filter,
) where

import Cardano.Ledger.Binary (
  DecCBOR (decCBOR),
  EncCBOR (encCBOR),
  decodeSetLikeEnforceNoDuplicates,
  encodeStrictSeq,
  encodeTag,
  setTag,
 )
import Control.DeepSeq (NFData)
import Data.Aeson (ToJSON (toJSON))
import Data.Foldable qualified as F
import Data.Sequence.Strict qualified as SSeq
import Data.Set qualified as Set
import GHC.Exts qualified as GHC (IsList (..))
import GHC.Generics (Generic)
import NoThunks.Class (NoThunks)
import Prelude hiding (filter, lookup, null, seq)

-- | A general-purpose finite, ordered, set that is strict in its
-- values.
--
-- The strictness is enforced by the underlying `StrictSeq` from base,
-- and the uniqueness of the values is enforced in this module, by the
-- constructing functions by leveraging an accompanying `Set`.
--
-- TODO: @aniketd Implement DecShareCBOR
data OSet a = OSet
  { forall a. OSet a -> StrictSeq a
osSSeq :: !(SSeq.StrictSeq a)
  , forall a. OSet a -> Set a
osSet :: !(Set.Set a)
  }
  deriving stock (OSet a -> OSet a -> Bool
(OSet a -> OSet a -> Bool)
-> (OSet a -> OSet a -> Bool) -> Eq (OSet a)
forall a. Eq a => OSet a -> OSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => OSet a -> OSet a -> Bool
== :: OSet a -> OSet a -> Bool
$c/= :: forall a. Eq a => OSet a -> OSet a -> Bool
/= :: OSet a -> OSet a -> Bool
Eq, Eq (OSet a)
Eq (OSet a) =>
(OSet a -> OSet a -> Ordering)
-> (OSet a -> OSet a -> Bool)
-> (OSet a -> OSet a -> Bool)
-> (OSet a -> OSet a -> Bool)
-> (OSet a -> OSet a -> Bool)
-> (OSet a -> OSet a -> OSet a)
-> (OSet a -> OSet a -> OSet a)
-> Ord (OSet a)
OSet a -> OSet a -> Bool
OSet a -> OSet a -> Ordering
OSet a -> OSet a -> OSet a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (OSet a)
forall a. Ord a => OSet a -> OSet a -> Bool
forall a. Ord a => OSet a -> OSet a -> Ordering
forall a. Ord a => OSet a -> OSet a -> OSet a
$ccompare :: forall a. Ord a => OSet a -> OSet a -> Ordering
compare :: OSet a -> OSet a -> Ordering
$c< :: forall a. Ord a => OSet a -> OSet a -> Bool
< :: OSet a -> OSet a -> Bool
$c<= :: forall a. Ord a => OSet a -> OSet a -> Bool
<= :: OSet a -> OSet a -> Bool
$c> :: forall a. Ord a => OSet a -> OSet a -> Bool
> :: OSet a -> OSet a -> Bool
$c>= :: forall a. Ord a => OSet a -> OSet a -> Bool
>= :: OSet a -> OSet a -> Bool
$cmax :: forall a. Ord a => OSet a -> OSet a -> OSet a
max :: OSet a -> OSet a -> OSet a
$cmin :: forall a. Ord a => OSet a -> OSet a -> OSet a
min :: OSet a -> OSet a -> OSet a
Ord, Int -> OSet a -> ShowS
[OSet a] -> ShowS
OSet a -> String
(Int -> OSet a -> ShowS)
-> (OSet a -> String) -> ([OSet a] -> ShowS) -> Show (OSet a)
forall a. Show a => Int -> OSet a -> ShowS
forall a. Show a => [OSet a] -> ShowS
forall a. Show a => OSet a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> OSet a -> ShowS
showsPrec :: Int -> OSet a -> ShowS
$cshow :: forall a. Show a => OSet a -> String
show :: OSet a -> String
$cshowList :: forall a. Show a => [OSet a] -> ShowS
showList :: [OSet a] -> ShowS
Show, (forall x. OSet a -> Rep (OSet a) x)
-> (forall x. Rep (OSet a) x -> OSet a) -> Generic (OSet a)
forall x. Rep (OSet a) x -> OSet a
forall x. OSet a -> Rep (OSet a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (OSet a) x -> OSet a
forall a x. OSet a -> Rep (OSet a) x
$cfrom :: forall a x. OSet a -> Rep (OSet a) x
from :: forall x. OSet a -> Rep (OSet a) x
$cto :: forall a x. Rep (OSet a) x -> OSet a
to :: forall x. Rep (OSet a) x -> OSet a
Generic)
  deriving (Context -> OSet a -> IO (Maybe ThunkInfo)
Proxy (OSet a) -> String
(Context -> OSet a -> IO (Maybe ThunkInfo))
-> (Context -> OSet a -> IO (Maybe ThunkInfo))
-> (Proxy (OSet a) -> String)
-> NoThunks (OSet a)
forall a. NoThunks a => Context -> OSet a -> IO (Maybe ThunkInfo)
forall a. NoThunks a => Proxy (OSet a) -> String
forall a.
(Context -> a -> IO (Maybe ThunkInfo))
-> (Context -> a -> IO (Maybe ThunkInfo))
-> (Proxy a -> String)
-> NoThunks a
$cnoThunks :: forall a. NoThunks a => Context -> OSet a -> IO (Maybe ThunkInfo)
noThunks :: Context -> OSet a -> IO (Maybe ThunkInfo)
$cwNoThunks :: forall a. NoThunks a => Context -> OSet a -> IO (Maybe ThunkInfo)
wNoThunks :: Context -> OSet a -> IO (Maybe ThunkInfo)
$cshowTypeOf :: forall a. NoThunks a => Proxy (OSet a) -> String
showTypeOf :: Proxy (OSet a) -> String
NoThunks, OSet a -> ()
(OSet a -> ()) -> NFData (OSet a)
forall a. NFData a => OSet a -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall a. NFData a => OSet a -> ()
rnf :: OSet a -> ()
NFData)

instance Ord a => Semigroup (OSet a) where
  <> :: OSet a -> OSet a -> OSet a
(<>) = OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
(|><)

instance Ord a => Monoid (OSet a) where
  mempty :: OSet a
mempty = OSet a
forall a. OSet a
empty

instance Ord a => GHC.IsList (OSet a) where
  type Item (OSet a) = a
  fromList :: [Item (OSet a)] -> OSet a
fromList = [a] -> OSet a
[Item (OSet a)] -> OSet a
forall a. Ord a => [a] -> OSet a
fromList
  toList :: OSet a -> [Item (OSet a)]
toList = StrictSeq a -> [a]
forall a. StrictSeq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (StrictSeq a -> [a]) -> (OSet a -> StrictSeq a) -> OSet a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq

instance Foldable OSet where
  foldMap :: forall m a. Monoid m => (a -> m) -> OSet a -> m
foldMap a -> m
f = (a -> m) -> Seq a -> m
forall m a. Monoid m => (a -> m) -> Seq a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap a -> m
f (Seq a -> m) -> (OSet a -> Seq a) -> OSet a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldMap #-}
  foldr :: forall a b. (a -> b -> b) -> b -> OSet a -> b
foldr a -> b -> b
f b
z = (a -> b -> b) -> b -> Seq a -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr a -> b -> b
f b
z (Seq a -> b) -> (OSet a -> Seq a) -> OSet a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldr #-}
  foldl :: forall b a. (b -> a -> b) -> b -> OSet a -> b
foldl b -> a -> b
f b
z = (b -> a -> b) -> b -> Seq a -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl b -> a -> b
f b
z (Seq a -> b) -> (OSet a -> Seq a) -> OSet a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldl #-}
  foldr' :: forall a b. (a -> b -> b) -> b -> OSet a -> b
foldr' a -> b -> b
f b
z = (a -> b -> b) -> b -> Seq a -> b
forall a b. (a -> b -> b) -> b -> Seq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr' a -> b -> b
f b
z (Seq a -> b) -> (OSet a -> Seq a) -> OSet a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldr' #-}
  foldl' :: forall b a. (b -> a -> b) -> b -> OSet a -> b
foldl' b -> a -> b
f b
z = (b -> a -> b) -> b -> Seq a -> b
forall b a. (b -> a -> b) -> b -> Seq a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' b -> a -> b
f b
z (Seq a -> b) -> (OSet a -> Seq a) -> OSet a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldl' #-}
  foldr1 :: forall a. (a -> a -> a) -> OSet a -> a
foldr1 a -> a -> a
f = (a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
F.foldr1 a -> a -> a
f (Seq a -> a) -> (OSet a -> Seq a) -> OSet a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldr1 #-}
  foldl1 :: forall a. (a -> a -> a) -> OSet a -> a
foldl1 a -> a -> a
f = (a -> a -> a) -> Seq a -> a
forall a. (a -> a -> a) -> Seq a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
F.foldl1 a -> a -> a
f (Seq a -> a) -> (OSet a -> Seq a) -> OSet a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINEABLE foldl1 #-}
  length :: forall a. OSet a -> Int
length = Seq a -> Int
forall a. Seq a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length (Seq a -> Int) -> (OSet a -> Seq a) -> OSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINE length #-}
  null :: forall a. OSet a -> Bool
null = Seq a -> Bool
forall a. Seq a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
F.null (Seq a -> Bool) -> (OSet a -> Seq a) -> OSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict (StrictSeq a -> Seq a)
-> (OSet a -> StrictSeq a) -> OSet a -> Seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq
  {-# INLINE null #-}

instance EncCBOR a => EncCBOR (OSet a) where
  encCBOR :: OSet a -> Encoding
encCBOR (OSet StrictSeq a
seq Set a
_set) = Word -> Encoding
encodeTag Word
setTag Encoding -> Encoding -> Encoding
forall a. Semigroup a => a -> a -> a
<> (a -> Encoding) -> StrictSeq a -> Encoding
forall a. (a -> Encoding) -> StrictSeq a -> Encoding
encodeStrictSeq a -> Encoding
forall a. EncCBOR a => a -> Encoding
encCBOR StrictSeq a
seq

instance (Show a, Ord a, DecCBOR a) => DecCBOR (OSet a) where
  decCBOR :: forall s. Decoder s (OSet a)
decCBOR = (a -> OSet a -> OSet a)
-> (OSet a -> (Int, OSet a)) -> Decoder s a -> Decoder s (OSet a)
forall s a b c.
Monoid b =>
(a -> b -> b) -> (b -> (Int, c)) -> Decoder s a -> Decoder s c
decodeSetLikeEnforceNoDuplicates ((OSet a -> a -> OSet a) -> a -> OSet a -> OSet a
forall a b c. (a -> b -> c) -> b -> a -> c
flip OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
snoc) (\OSet a
oset -> (OSet a -> Int
forall a. OSet a -> Int
size OSet a
oset, OSet a
oset)) Decoder s a
forall s. Decoder s a
forall a s. DecCBOR a => Decoder s a
decCBOR

instance ToJSON a => ToJSON (OSet a) where
  toJSON :: OSet a -> Value
toJSON = [a] -> Value
forall a. ToJSON a => a -> Value
toJSON ([a] -> Value) -> (OSet a -> [a]) -> OSet a -> Value
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OSet a -> [a]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList

-- | \( O(1) \). Shallow invariant using just `length` and `size`.
invariantHolds :: OSet a -> Bool
invariantHolds :: forall a. OSet a -> Bool
invariantHolds (OSet StrictSeq a
seq Set a
set) = StrictSeq a -> Int
forall a. StrictSeq a -> Int
SSeq.length StrictSeq a
seq Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Set a -> Int
forall a. Set a -> Int
Set.size Set a
set

-- | \( O(n \log n) \). Deep invariant using set membership check for
-- each value. By the pigeon-hole principle, this check is exhaustive.
invariantHolds' :: Ord a => OSet a -> Bool
invariantHolds' :: forall a. Ord a => OSet a -> Bool
invariantHolds' oset :: OSet a
oset@(OSet StrictSeq a
seq Set a
set) =
  OSet a -> Bool
forall a. OSet a -> Bool
invariantHolds OSet a
oset Bool -> Bool -> Bool
&& (a -> Bool) -> Seq a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
set) (StrictSeq a -> Seq a
forall a. StrictSeq a -> Seq a
SSeq.fromStrict StrictSeq a
seq)

-- | \( O(1) \).
null :: OSet a -> Bool
null :: forall a. OSet a -> Bool
null (OSet StrictSeq a
_ Set a
set) = Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
set

-- | \( O(1) \).
size :: OSet a -> Int
size :: forall a. OSet a -> Int
size (OSet StrictSeq a
_ Set a
set) = Set a -> Int
forall a. Set a -> Int
Set.size Set a
set

-- | \( O(1) \).
empty :: OSet a
empty :: forall a. OSet a
empty = StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet StrictSeq a
forall a. StrictSeq a
SSeq.Empty Set a
forall a. Set a
Set.empty

-- | \( O(1) \). Strict in its argument.
singleton :: a -> OSet a
singleton :: forall a. a -> OSet a
singleton !a
x = StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet (a -> StrictSeq a
forall a. a -> StrictSeq a
SSeq.singleton a
x) (a -> Set a
forall a. a -> Set a
Set.singleton a
x)

-- | \( O(\log(\min(i,n-i))) \). The element at the specified position,
-- counting from 0. If the specified position is negative or at least
-- the length of the sequence, 'lookup' returns 'Nothing'.
lookup :: Int -> OSet a -> Maybe a
lookup :: forall a. Int -> OSet a -> Maybe a
lookup Int
i (OSet StrictSeq a
seq Set a
_set) = Int -> StrictSeq a -> Maybe a
forall a. Int -> StrictSeq a -> Maybe a
SSeq.lookup Int
i StrictSeq a
seq

-- | `flip`ed version of `lookup`
(!?) :: OSet a -> Int -> Maybe a
!? :: forall a. OSet a -> Int -> Maybe a
(!?) = (Int -> OSet a -> Maybe a) -> OSet a -> Int -> Maybe a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Int -> OSet a -> Maybe a
forall a. Int -> OSet a -> Maybe a
lookup

-- | \( O(\log n) \). Checks membership before cons'ing.
cons :: Ord a => a -> OSet a -> OSet a
cons :: forall a. Ord a => a -> OSet a -> OSet a
cons a
x oset :: OSet a
oset@(OSet StrictSeq a
seq Set a
set) =
  if a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
set
    then OSet a
oset
    else StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet (a
x a -> StrictSeq a -> StrictSeq a
forall a. a -> StrictSeq a -> StrictSeq a
SSeq.<| StrictSeq a
seq) (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set a
set)

(<|) :: Ord a => a -> OSet a -> OSet a
<| :: forall a. Ord a => a -> OSet a -> OSet a
(<|) = a -> OSet a -> OSet a
forall a. Ord a => a -> OSet a -> OSet a
cons

infixr 5 <|

-- | \( O(\log n) \). Checks membership before snoc'ing.
snoc :: Ord a => OSet a -> a -> OSet a
snoc :: forall a. Ord a => OSet a -> a -> OSet a
snoc oset :: OSet a
oset@(OSet StrictSeq a
seq Set a
set) a
x =
  if a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
set
    then OSet a
oset
    else StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet (StrictSeq a
seq StrictSeq a -> a -> StrictSeq a
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> a
x) (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set a
set)

(|>) :: Ord a => OSet a -> a -> OSet a
|> :: forall a. Ord a => OSet a -> a -> OSet a
(|>) = OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
snoc

infixl 5 |>

-- | \( O(\log n) \).
uncons :: Ord a => OSet a -> Maybe (a, OSet a)
uncons :: forall a. Ord a => OSet a -> Maybe (a, OSet a)
uncons (OSet StrictSeq a
seq Set a
set) = case StrictSeq a
seq of
  StrictSeq a
SSeq.Empty -> Maybe (a, OSet a)
forall a. Maybe a
Nothing
  a
x SSeq.:<| StrictSeq a
xs' -> (a, OSet a) -> Maybe (a, OSet a)
forall a. a -> Maybe a
Just (a
x, StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet StrictSeq a
xs' (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.delete` Set a
set))

-- | \( O(\log n) \).
unsnoc :: Ord a => OSet a -> Maybe (OSet a, a)
unsnoc :: forall a. Ord a => OSet a -> Maybe (OSet a, a)
unsnoc (OSet StrictSeq a
seq Set a
set) = case StrictSeq a
seq of
  StrictSeq a
SSeq.Empty -> Maybe (OSet a, a)
forall a. Maybe a
Nothing
  StrictSeq a
xs' SSeq.:|> a
x -> (OSet a, a) -> Maybe (OSet a, a)
forall a. a -> Maybe a
Just (StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet StrictSeq a
xs' (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.delete` Set a
set), a
x)

-- | \(O(n \log n)\). Convert to an OSet from a List.
fromList :: Ord a => [a] -> OSet a
fromList :: forall a. Ord a => [a] -> OSet a
fromList = [a] -> OSet a
forall (f :: * -> *) a. (Foldable f, Ord a) => f a -> OSet a
fromFoldable

-- | Using a `Foldable` instance of the source data structure convert it to an `OSet`
fromFoldable :: (Foldable f, Ord a) => f a -> OSet a
fromFoldable :: forall (f :: * -> *) a. (Foldable f, Ord a) => f a -> OSet a
fromFoldable = (OSet a -> a -> OSet a) -> OSet a -> f a -> OSet a
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' OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
snoc OSet a
forall a. OSet a
empty

-- | \(O(n \log n)\). Checks membership before snoc-ing.
-- De-duplicates the StrictSeq without overwriting.
fromStrictSeq :: Ord a => SSeq.StrictSeq a -> OSet a
fromStrictSeq :: forall a. Ord a => StrictSeq a -> OSet a
fromStrictSeq = StrictSeq a -> OSet a
forall (f :: * -> *) a. (Foldable f, Ord a) => f a -> OSet a
fromFoldable

-- | \(O(n \log n)\). Checks membership before snoc-ing.
-- Returns a 2-tuple, with `fst` as a `Set` of duplicates found
-- and the `snd` as the de-duplicated `OSet` without overwriting.
fromFoldableDuplicates :: (Foldable f, Ord a) => f a -> (Set.Set a, OSet a)
fromFoldableDuplicates :: forall (f :: * -> *) a.
(Foldable f, Ord a) =>
f a -> (Set a, OSet a)
fromFoldableDuplicates = ((Set a, OSet a) -> a -> (Set a, OSet a))
-> (Set a, OSet a) -> f a -> (Set a, OSet a)
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 a, OSet a) -> a -> (Set a, OSet a)
forall a. Ord a => (Set a, OSet a) -> a -> (Set a, OSet a)
snoc' (Set a
forall a. Set a
Set.empty, OSet a
forall a. OSet a
empty)
  where
    snoc' :: Ord a => (Set.Set a, OSet a) -> a -> (Set.Set a, OSet a)
    snoc' :: forall a. Ord a => (Set a, OSet a) -> a -> (Set a, OSet a)
snoc' (!Set a
duplicates, !oset :: OSet a
oset@(OSet StrictSeq a
seq Set a
set)) a
x =
      if a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
set
        then (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set a
duplicates, OSet a
oset)
        else (Set a
duplicates, StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet (StrictSeq a
seq StrictSeq a -> a -> StrictSeq a
forall a. StrictSeq a -> a -> StrictSeq a
SSeq.|> a
x) (a
x a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set a
set))

-- | \(O(n \log n)\). Checks membership before snoc-ing.
-- Returns a 2-tuple, with `fst` as a `Set` of duplicates found
-- and the `snd` as the de-duplicated `OSet` without overwriting.
-- Starts from the left or head, using `foldl'`
fromStrictSeqDuplicates :: Ord a => SSeq.StrictSeq a -> (Set.Set a, OSet a)
fromStrictSeqDuplicates :: forall a. Ord a => StrictSeq a -> (Set a, OSet a)
fromStrictSeqDuplicates = StrictSeq a -> (Set a, OSet a)
forall (f :: * -> *) a.
(Foldable f, Ord a) =>
f a -> (Set a, OSet a)
fromFoldableDuplicates

-- | \( O(1) \) -  Extract underlying strict sequence
toStrictSeq :: OSet a -> SSeq.StrictSeq a
toStrictSeq :: forall a. OSet a -> StrictSeq a
toStrictSeq = OSet a -> StrictSeq a
forall a. OSet a -> StrictSeq a
osSSeq

-- | \( O(1) \) -  Extract underlying Set
toSet :: OSet a -> Set.Set a
toSet :: forall a. OSet a -> Set a
toSet = OSet a -> Set a
forall a. OSet a -> Set a
osSet

-- | \( O(n) \).
fromSet :: Set.Set a -> OSet a
fromSet :: forall a. Set a -> OSet a
fromSet Set a
set = StrictSeq a -> Set a -> OSet a
forall a. StrictSeq a -> Set a -> OSet a
OSet ([a] -> StrictSeq a
forall a. [a] -> StrictSeq a
SSeq.fromList ([a] -> StrictSeq a) -> [a] -> StrictSeq a
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
Set.elems Set a
set) Set a
set

-- | \(O(\log n)\). Membership check.
member :: Ord a => a -> OSet a -> Bool
member :: forall a. Ord a => a -> OSet a -> Bool
member a
x (OSet StrictSeq a
_seq Set a
set) = a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
set

-- | \( O(n \log n) \)
filter :: Ord a => (a -> Bool) -> OSet a -> OSet a
filter :: forall a. Ord a => (a -> Bool) -> OSet a -> OSet a
filter a -> Bool
f = (OSet a -> a -> OSet a) -> OSet a -> OSet a -> OSet a
forall b a. (b -> a -> b) -> b -> OSet a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\OSet a
xs a
x -> if a -> Bool
f a
x then OSet a
xs OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
|> a
x else OSet a
xs) OSet a
forall a. OSet a
empty

pattern Empty :: OSet a
pattern $mEmpty :: forall {r} {a}. OSet a -> ((# #) -> r) -> ((# #) -> r) -> r
$bEmpty :: forall a. OSet a
Empty <- (null -> True)
  where
    Empty = OSet a
forall a. OSet a
empty

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

infixr 5 :<|:

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

infixl 5 :|>:

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

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

-- | \( O(n\log(m*n)) \). For every uncons-ed element from the sequence on the right,
-- checks its membership in the sequence on the left, before snoc'ing it.
-- Preserves order. Remove duplicates from sequence on the right.
(|><) :: Ord a => OSet a -> OSet a -> OSet a
OSet a
osetl |>< :: forall a. Ord a => OSet a -> OSet a -> OSet a
|>< OSet a
osetr = case OSet a
osetr of
  OSet a
Empty -> OSet a
osetl
  a
r :<|: OSet a
rs -> (OSet a
osetl OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
|> a
r) OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
|>< OSet a
rs

infixl 5 |><

-- | \( O(m\log(m+n)) \). For every unsnoc-ed element from the sequence on the left,
-- checks its membership in the sequence on the right, before cons'ing it.
-- Preserves order. Remove duplicates from sequence on the left.
(><|) :: Ord a => OSet a -> OSet a -> OSet a
OSet a
osetl ><| :: forall a. Ord a => OSet a -> OSet a -> OSet a
><| OSet a
osetr = case OSet a
osetl of
  OSet a
Empty -> OSet a
osetr
  OSet a
ls :|>: a
l -> OSet a
ls OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
><| (a
l a -> OSet a -> OSet a
forall a. Ord a => a -> OSet a -> OSet a
<| OSet a
osetr)

infixr 5 ><|