{-# LANGUAGE TupleSections    #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies     #-}

-- | This module doesn't respect the PVP!
-- Breaking changes may happen at any minor version (>= *.*.m.*)

module Data.POSet.Internal where

import           Algebra.PartialOrd
import           Control.DeepSeq    (NFData (rnf))
import qualified Data.List          as List
import           Data.POMap.Lazy    (POMap)
import qualified Data.POMap.Lazy    as POMap
import           GHC.Exts           (coerce)
import qualified GHC.Exts
import           Text.Read          (Lexeme (Ident), Read (..), lexP, parens,
                                     prec, readListPrecDefault)

-- $setup
-- This is some setup code for @doctest@.
-- >>> :set -XGeneralizedNewtypeDeriving
-- >>> import           Algebra.PartialOrd
-- >>> import           Data.POSet
-- >>> :{
--   newtype Divisibility
--     = Div Int
--     deriving (Eq, Num)
--   instance Show Divisibility where
--     show (Div a) = show a
--   instance PartialOrd Divisibility where
--     Div a `leq` Div b = b `mod` a == 0
--   type DivSet = POSet Divisibility
--   default (Divisibility, DivSet)
-- :}

-- | A set of partially ordered values @k@.
newtype POSet k
  = POSet (POMap k ())

--
-- * Instances
--

instance PartialOrd k => Eq (POSet k) where
  POSet POMap k ()
a == :: POSet k -> POSet k -> Bool
== POSet POMap k ()
b = POMap k ()
a POMap k () -> POMap k () -> Bool
forall a. Eq a => a -> a -> Bool
== POMap k ()
b

instance PartialOrd k => PartialOrd (POSet k) where
  POSet POMap k ()
a leq :: POSet k -> POSet k -> Bool
`leq` POSet POMap k ()
b = POMap k ()
a POMap k () -> POMap k () -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` POMap k ()
b

instance Show a => Show (POSet a) where
  showsPrec :: Int -> POSet a -> ShowS
showsPrec Int
p POSet a
xs = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> ShowS
forall a. Show a => a -> ShowS
shows (POSet a -> [a]
forall k. POSet k -> [k]
toList POSet a
xs)

instance (Read a, PartialOrd a) => Read (POSet a) where
  readPrec :: ReadPrec (POSet a)
readPrec = ReadPrec (POSet a) -> ReadPrec (POSet a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (POSet a) -> ReadPrec (POSet a))
-> ReadPrec (POSet a) -> ReadPrec (POSet a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (POSet a) -> ReadPrec (POSet a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (POSet a) -> ReadPrec (POSet a))
-> ReadPrec (POSet a) -> ReadPrec (POSet a)
forall a b. (a -> b) -> a -> b
$ do
    Ident String
"fromList" <- ReadPrec Lexeme
lexP
    [a] -> POSet a
forall k. PartialOrd k => [k] -> POSet k
fromList ([a] -> POSet a) -> ReadPrec [a] -> ReadPrec (POSet a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec

  readListPrec :: ReadPrec [POSet a]
readListPrec = ReadPrec [POSet a]
forall a. Read a => ReadPrec [a]
readListPrecDefault

instance NFData a => NFData (POSet a) where
  rnf :: POSet a -> ()
rnf (POSet POMap a ()
m) = POMap a () -> ()
forall a. NFData a => a -> ()
rnf POMap a ()
m

instance Foldable POSet where
  foldr :: (a -> b -> b) -> b -> POSet a -> b
foldr a -> b -> b
f = (b -> POMap a () -> b) -> b -> POSet a -> b
coerce ((a -> () -> b -> b) -> b -> POMap a () -> b
forall k a b. (k -> a -> b -> b) -> b -> POMap k a -> b
POMap.foldrWithKey @_ @() (\a
k ()
_ b
acc -> a -> b -> b
f a
k b
acc))
  {-# INLINE foldr #-}
  foldl :: (b -> a -> b) -> b -> POSet a -> b
foldl b -> a -> b
f = (b -> POMap a () -> b) -> b -> POSet a -> b
coerce ((b -> a -> () -> b) -> b -> POMap a () -> b
forall b k a. (b -> k -> a -> b) -> b -> POMap k a -> b
POMap.foldlWithKey @_ @_ @() (\b
k a
acc ()
_ -> b -> a -> b
f b
k a
acc))
  {-# INLINE foldl #-}
  null :: POSet a -> Bool
null POSet a
m = POSet a -> Int
forall a. POSet a -> Int
size POSet a
m Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
  {-# INLINE null #-}
  length :: POSet a -> Int
length = POSet a -> Int
forall a. POSet a -> Int
size
  {-# INLINE length #-}

instance PartialOrd k => GHC.Exts.IsList (POSet k) where
  type Item (POSet k) = k
  fromList :: [Item (POSet k)] -> POSet k
fromList = [Item (POSet k)] -> POSet k
forall k. PartialOrd k => [k] -> POSet k
fromList
  toList :: POSet k -> [Item (POSet k)]
toList = POSet k -> [Item (POSet k)]
forall k. POSet k -> [k]
toList

--
-- * Query
--

-- | \(\mathcal{O}(1)\). The number of elements in this set.
size :: POSet k -> Int
size :: POSet k -> Int
size = (POMap k () -> Int) -> POSet k -> Int
coerce (POMap k () -> Int
forall k v. POMap k v -> Int
POMap.size @_ @())
{-# INLINE size #-}

-- | \(\mathcal{O}(w)\).
-- The width \(w\) of the chain decomposition in the internal
-- data structure.
-- This is always at least as big as the size of the biggest possible
-- anti-chain.
width :: POSet k -> Int
width :: POSet k -> Int
width = (POMap k () -> Int) -> POSet k -> Int
coerce (POMap k () -> Int
forall k v. POMap k v -> Int
POMap.width @_ @())
{-# INLINE width #-}

-- | \(\mathcal{O}(w\log n)\).
-- Is the key a member of the map? See also 'notMember'.
member :: PartialOrd k => k -> POSet k -> Bool
member :: k -> POSet k -> Bool
member = (k -> POMap k () -> Bool) -> k -> POSet k -> Bool
coerce (PartialOrd k => k -> POMap k () -> Bool
forall k v. PartialOrd k => k -> POMap k v -> Bool
POMap.member @_ @())
{-# INLINE member #-}

-- | \(\mathcal{O}(w\log n)\).
-- Is the key not a member of the map? See also 'member'.
notMember :: PartialOrd k => k -> POSet k -> Bool
notMember :: k -> POSet k -> Bool
notMember = (k -> POMap k () -> Bool) -> k -> POSet k -> Bool
coerce (PartialOrd k => k -> POMap k () -> Bool
forall k v. PartialOrd k => k -> POMap k v -> Bool
POMap.notMember @_ @())
{-# INLINE notMember #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the largest set of keys smaller than the given one and
-- return the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupLT 3 (fromList [3, 5])
-- []
-- >>> lookupLT 6 (fromList [3, 5])
-- [3]
lookupLT :: PartialOrd k => k -> POSet k -> [k]
lookupLT :: k -> POSet k -> [k]
lookupLT k
k = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (k -> POMap k () -> [(k, ())]
forall k v. PartialOrd k => k -> POMap k v -> [(k, v)]
POMap.lookupLT @_ @() k
k)
{-# INLINE lookupLT #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the largest key smaller or equal to the given one and return
-- the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupLE 2  (fromList [3, 5])
-- []
-- >>> lookupLE 3  (fromList [3, 5])
-- [3]
-- >>> lookupLE 10 (fromList [3, 5])
-- [5]
lookupLE :: PartialOrd k => k -> POSet k -> [k]
lookupLE :: k -> POSet k -> [k]
lookupLE k
k = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (k -> POMap k () -> [(k, ())]
forall k v. PartialOrd k => k -> POMap k v -> [(k, v)]
POMap.lookupLE @_ @() k
k)
{-# INLINE lookupLE #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the smallest key greater or equal to the given one and return
-- the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupGE 3 (fromList [3, 5])
-- [3]
-- >>> lookupGE 5 (fromList [3, 10])
-- [10]
-- >>> lookupGE 6 (fromList [3, 5])
-- []
lookupGE :: PartialOrd k => k -> POSet k -> [k]
lookupGE :: k -> POSet k -> [k]
lookupGE k
k = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (k -> POMap k () -> [(k, ())]
forall k v. PartialOrd k => k -> POMap k v -> [(k, v)]
POMap.lookupGE @_ @() k
k)
{-# INLINE lookupGE #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the smallest key greater than the given one and return the
-- corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupGT 3 (fromList [6, 5])
-- [6]
-- >>> lookupGT 5 (fromList [3, 5])
-- []
lookupGT :: PartialOrd k => k -> POSet k -> [k]
lookupGT :: k -> POSet k -> [k]
lookupGT k
k = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (k -> POMap k () -> [(k, ())]
forall k v. PartialOrd k => k -> POMap k v -> [(k, v)]
POMap.lookupGT @_ @() k
k)
{-# INLINE lookupGT #-}

-- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
-- @(s1 `isSubsetOf` s2)@ tells whether @s1@ is a subset of @s2@.
isSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool
isSubsetOf :: POSet k -> POSet k -> Bool
isSubsetOf = (POMap k () -> POMap k () -> Bool) -> POSet k -> POSet k -> Bool
coerce ((PartialOrd k, Eq ()) => POMap k () -> POMap k () -> Bool
forall k v. (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
POMap.isSubmapOf @_ @())
{-# INLINE isSubsetOf #-}

-- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
-- Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool
isProperSubsetOf :: POSet k -> POSet k -> Bool
isProperSubsetOf = (POMap k () -> POMap k () -> Bool) -> POSet k -> POSet k -> Bool
coerce ((PartialOrd k, Eq ()) => POMap k () -> POMap k () -> Bool
forall k v. (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
POMap.isProperSubmapOf @_ @())
{-# INLINE isProperSubsetOf #-}

--
-- * Construction
--

-- | \(\mathcal{O}(1)\). The empty set.
empty :: POSet k
empty :: POSet k
empty = POMap k () -> POSet k
forall k. POMap k () -> POSet k
POSet POMap k ()
forall k v. POMap k v
POMap.empty
{-# INLINE empty #-}

-- | \(\mathcal{O}(1)\). A set with a single element.
singleton :: k -> POSet k
singleton :: k -> POSet k
singleton k
k = POMap k () -> POSet k
forall k. POMap k () -> POSet k
POSet (k -> () -> POMap k ()
forall k v. k -> v -> POMap k v
POMap.singleton k
k ())
{-# INLINE singleton #-}
-- INLINE means we don't need to SPECIALIZE

-- | \(\mathcal{O}(w\log n)\).
-- If the key is already present in the map, the associated value is
-- replaced with the supplied value. 'insert' is equivalent to
-- @'insertWith' 'const'@.
insert :: (PartialOrd k) => k -> POSet k -> POSet k
insert :: k -> POSet k -> POSet k
insert k
k = (POMap k () -> POMap k ()) -> POSet k -> POSet k
coerce (k -> () -> POMap k () -> POMap k ()
forall k v. PartialOrd k => k -> v -> POMap k v -> POMap k v
POMap.insert k
k ())
{-# INLINE insert #-}

-- | \(\mathcal{O}(w\log n)\).
-- Delete an element from a set.
delete :: (PartialOrd k) => k -> POSet k -> POSet k
delete :: k -> POSet k -> POSet k
delete = (k -> POMap k () -> POMap k ()) -> k -> POSet k -> POSet k
coerce (PartialOrd k => k -> POMap k () -> POMap k ()
forall k v. PartialOrd k => k -> POMap k v -> POMap k v
POMap.delete @_ @())
{-# INLINE delete #-}

--
-- * Combine
--

-- ** Union

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- The union of two sets, preferring the first set when
-- equal elements are encountered.
union :: PartialOrd k => POSet k -> POSet k -> POSet k
union :: POSet k -> POSet k -> POSet k
union = (POMap k () -> POMap k () -> POMap k ())
-> POSet k -> POSet k -> POSet k
coerce (PartialOrd k => POMap k () -> POMap k () -> POMap k ()
forall k v. PartialOrd k => POMap k v -> POMap k v -> POMap k v
POMap.union @_ @())
{-# INLINE union #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\).
-- The union of a list of sets: (@'unions' == 'foldl' 'union' 'empty'@).
unions :: PartialOrd k => [POSet k] -> POSet k
unions :: [POSet k] -> POSet k
unions = ([POMap k ()] -> POMap k ()) -> [POSet k] -> POSet k
coerce (PartialOrd k => [POMap k ()] -> POMap k ()
forall k v. PartialOrd k => [POMap k v] -> POMap k v
POMap.unions @_ @())
{-# INLINE unions #-}

-- ** Difference

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Difference of two sets.
difference :: PartialOrd k => POSet k -> POSet k -> POSet k
difference :: POSet k -> POSet k -> POSet k
difference = (POMap k () -> POMap k () -> POMap k ())
-> POSet k -> POSet k -> POSet k
coerce (PartialOrd k => POMap k () -> POMap k () -> POMap k ()
forall k a b. PartialOrd k => POMap k a -> POMap k b -> POMap k a
POMap.difference @_ @() @())
{-# INLINE difference #-}

-- ** Intersection

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- The intersection of two sets.
-- Elements of the result come from the first set, so for example
--
-- >>> data AB = A | B deriving Show
-- >>> instance Eq AB where _ == _ = True
-- >>> instance PartialOrd AB where _ `leq` _ = True
-- >>> singleton A `intersection` singleton B
-- fromList [A]
-- >>> singleton B `intersection` singleton A
-- fromList [B]
intersection :: PartialOrd k => POSet k -> POSet k -> POSet k
intersection :: POSet k -> POSet k -> POSet k
intersection = (POMap k () -> POMap k () -> POMap k ())
-> POSet k -> POSet k -> POSet k
coerce (PartialOrd k => POMap k () -> POMap k () -> POMap k ()
forall k a b. PartialOrd k => POMap k a -> POMap k b -> POMap k a
POMap.intersection @_ @() @())
{-# INLINE intersection #-}

--
-- * Filter
--

-- | \(\mathcal{O}(n)\).
-- Filter all elements that satisfy the predicate.
filter :: (k -> Bool) -> POSet k -> POSet k
filter :: (k -> Bool) -> POSet k -> POSet k
filter k -> Bool
f = (POMap k () -> POMap k ()) -> POSet k -> POSet k
coerce ((k -> () -> Bool) -> POMap k () -> POMap k ()
forall k v. (k -> v -> Bool) -> POMap k v -> POMap k v
POMap.filterWithKey @_ @() (\k
k ()
_ -> k -> Bool
f k
k))
{-# INLINE filter #-}

-- | \(\mathcal{O}(n)\).
-- Partition the set into two sets, one with all elements that satisfy
-- the predicate and one with all elements that don't satisfy the predicate.
partition :: (k -> Bool) -> POSet k -> (POSet k, POSet k)
partition :: (k -> Bool) -> POSet k -> (POSet k, POSet k)
partition k -> Bool
f = (POMap k () -> (POMap k (), POMap k ()))
-> POSet k -> (POSet k, POSet k)
coerce ((k -> () -> Bool) -> POMap k () -> (POMap k (), POMap k ())
forall k v. (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
POMap.partitionWithKey @_ @() (\k
k ()
_ -> k -> Bool
f k
k))
{-# INLINE partition #-}

-- | \(\mathcal{O}(log n)\). Take while a predicate on the keys holds.
-- The user is responsible for ensuring that for all elements @j@ and @k@ in the set,
-- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
--
-- @
-- takeWhileAntitone p = 'filter' p
-- @
--
-- @since 0.0.1.0
takeWhileAntitone :: (k -> Bool) -> POSet k -> POSet k
takeWhileAntitone :: (k -> Bool) -> POSet k -> POSet k
takeWhileAntitone = ((k -> Bool) -> POMap k () -> POMap k ())
-> (k -> Bool) -> POSet k -> POSet k
coerce ((k -> Bool) -> POMap k () -> POMap k ()
forall k v. (k -> Bool) -> POMap k v -> POMap k v
POMap.takeWhileAntitone @_ @())

-- | \(\mathcal{O}(log n)\). Drop while a predicate on the keys holds.
-- The user is responsible for ensuring that for all elements @j@ and @k@ in the set,
-- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
--
-- @
-- dropWhileAntitone p = 'filter' (not . p)
-- @
--
-- @since 0.0.1.0
dropWhileAntitone :: (k -> Bool) -> POSet k -> POSet k
dropWhileAntitone :: (k -> Bool) -> POSet k -> POSet k
dropWhileAntitone = ((k -> Bool) -> POMap k () -> POMap k ())
-> (k -> Bool) -> POSet k -> POSet k
coerce ((k -> Bool) -> POMap k () -> POMap k ()
forall k v. (k -> Bool) -> POMap k v -> POMap k v
POMap.dropWhileAntitone @_ @())

-- | \(\mathcal{O}(log n)\). Divide a set at the point where a predicate on the keys stops holding.
-- The user is responsible for ensuring that for all elements @j@ and @k@ in the set,
-- @j \< k ==\> p j \>= p k@.
--
-- @
-- spanAntitone p xs = 'partition' p xs
-- @
--
-- Note: if @p@ is not actually antitone, then @spanAntitone@ will split the set
-- at some /unspecified/ point where the predicate switches from holding to not
-- holding (where the predicate is seen to hold before the first element and to fail
-- after the last element).
--
-- @since 0.0.1.0
spanAntitone :: (k -> Bool) -> POSet k -> (POSet k, POSet k)
spanAntitone :: (k -> Bool) -> POSet k -> (POSet k, POSet k)
spanAntitone = ((k -> Bool) -> POMap k () -> (POMap k (), POMap k ()))
-> (k -> Bool) -> POSet k -> (POSet k, POSet k)
coerce ((k -> Bool) -> POMap k () -> (POMap k (), POMap k ())
forall k v. (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)
POMap.spanAntitone @_ @())

--
-- * Map
--

-- | \(\mathcal{O}(wn\log n)\).
-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
--
-- It's worth noting that the size of the result may be smaller if,
-- for some @(x,y)@, @x \/= y && f x == f y@
map :: PartialOrd k2 => (k1 -> k2) -> POSet k1 -> POSet k2
map :: (k1 -> k2) -> POSet k1 -> POSet k2
map = ((k1 -> k2) -> POMap k1 () -> POMap k2 ())
-> (k1 -> k2) -> POSet k1 -> POSet k2
coerce (PartialOrd k2 => (k1 -> k2) -> POMap k1 () -> POMap k2 ()
forall k2 k1 v.
PartialOrd k2 =>
(k1 -> k2) -> POMap k1 v -> POMap k2 v
POMap.mapKeys @_ @_ @())
{-# INLINE map #-}

-- | \(\mathcal{O}(n)\).
-- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly increasing.
-- /The precondition is not checked./
-- Semi-formally, for every chain @ls@ in @s@ we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapMonotonic f s == map f s
mapMonotonic :: (k1 -> k2) -> POSet k1 -> POSet k2
mapMonotonic :: (k1 -> k2) -> POSet k1 -> POSet k2
mapMonotonic = ((k1 -> k2) -> POMap k1 () -> POMap k2 ())
-> (k1 -> k2) -> POSet k1 -> POSet k2
coerce ((k1 -> k2) -> POMap k1 () -> POMap k2 ()
forall k1 k2 v. (k1 -> k2) -> POMap k1 v -> POMap k2 v
POMap.mapKeysMonotonic @_ @_ @())
{-# INLINE mapMonotonic #-}

--
-- * Folds
--

-- | \(\mathcal{O}(n)\).
-- A strict version of 'foldr'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POSet a -> b
foldr' :: (a -> b -> b) -> b -> POSet a -> b
foldr' a -> b -> b
f = (b -> POMap a () -> b) -> b -> POSet a -> b
coerce ((a -> () -> b -> b) -> b -> POMap a () -> b
forall k a b. (k -> a -> b -> b) -> b -> POMap k a -> b
POMap.foldrWithKey' @_ @()  (\a
k ()
_ b
acc -> a -> b -> b
f a
k b
acc))
{-# INLINE foldr' #-}

-- | \(\mathcal{O}(n)\).
-- A strict version of 'foldl'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POSet a -> b
foldl' :: (b -> a -> b) -> b -> POSet a -> b
foldl' b -> a -> b
f = (b -> POMap a () -> b) -> b -> POSet a -> b
coerce ((b -> a -> () -> b) -> b -> POMap a () -> b
forall b k a. (b -> k -> a -> b) -> b -> POMap k a -> b
POMap.foldlWithKey' @_ @_ @()  (\b
k a
acc ()
_ -> b -> a -> b
f b
k a
acc))
{-# INLINE foldl' #-}

--
-- * Min/Max
--

-- | \(\mathcal{O}(w\log n)\).
-- The minimal keys of the set.
lookupMin :: PartialOrd k => POSet k -> [k]
lookupMin :: POSet k -> [k]
lookupMin = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (PartialOrd k => POMap k () -> [(k, ())]
forall k v. PartialOrd k => POMap k v -> [(k, v)]
POMap.lookupMin @_ @())
{-# INLINE lookupMin #-}

-- | \(\mathcal{O}(w\log n)\).
-- The maximal keys of the set.
lookupMax :: PartialOrd k => POSet k -> [k]
lookupMax :: POSet k -> [k]
lookupMax = ((k, ()) -> k) -> [(k, ())] -> [k]
forall a b. (a -> b) -> [a] -> [b]
List.map @(_,()) (k, ()) -> k
forall a b. (a, b) -> a
fst ([(k, ())] -> [k]) -> (POSet k -> [(k, ())]) -> POSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (POMap k () -> [(k, ())]) -> POSet k -> [(k, ())]
coerce (PartialOrd k => POMap k () -> [(k, ())]
forall k v. PartialOrd k => POMap k v -> [(k, v)]
POMap.lookupMax @_ @())
{-# INLINE lookupMax #-}

--
-- * Conversion
--

-- | \(\mathcal{O}(n)\).
-- The elements of a set in unspecified order.
elems :: POSet k -> [k]
elems :: POSet k -> [k]
elems = (POMap k () -> [k]) -> POSet k -> [k]
coerce (POMap k () -> [k]
forall k v. POMap k v -> [k]
POMap.keys @_ @())
{-# INLINE elems #-}

-- | \(\mathcal{O}(n)\).
-- The elements of a set in unspecified order.
toList :: POSet k -> [k]
toList :: POSet k -> [k]
toList = (POMap k () -> [k]) -> POSet k -> [k]
coerce (POMap k () -> [k]
forall k v. POMap k v -> [k]
POMap.keys @_ @())
{-# INLINE toList #-}

-- | \(\mathcal{O}(wn\log n)\).
-- Build a set from a list of keys.
fromList :: (PartialOrd k) => [k] -> POSet k
fromList :: [k] -> POSet k
fromList = ([(k, ())] -> POMap k ()) -> [(k, ())] -> POSet k
coerce (PartialOrd k => [(k, ())] -> POMap k ()
forall k v. PartialOrd k => [(k, v)] -> POMap k v
POMap.fromList @_ @()) ([(k, ())] -> POSet k) -> ([k] -> [(k, ())]) -> [k] -> POSet k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> (k, ())) -> [k] -> [(k, ())]
forall a b. (a -> b) -> [a] -> [b]
List.map (, ())
{-# INLINE fromList #-}