{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}

-- | An 'OSet' behaves much like a 'Set', with mostly the same asymptotics, but
-- also remembers the order that values were inserted. All operations whose
-- asymptotics are worse than 'Set' have documentation saying so.
module Data.Set.Ordered
	( OSet
	-- * Trivial sets
	, empty, singleton
	-- * Insertion
	-- | Conventions:
	--
	-- * The open side of an angle bracket points to an 'OSet'
	--
	-- * The pipe appears on the side whose indices take precedence for keys that appear on both sides
	--
	-- * The left argument's indices are lower than the right argument's indices
	, (<|), (|<), (>|), (|>)
	, (<>|), (|<>)
	, Bias(Bias, unbiased), L, R
	-- * Query
	, null, size, member, notMember
	-- * Deletion
	, delete, filter, (\\), (|/\), (/\|)
	-- * Indexing
	, Index, findIndex, elemAt
	-- * List conversions
	, fromList, toAscList
	-- * 'Set' conversion
	, toSet
	) where

import Control.Monad (guard)
import Data.Data
import Data.Foldable (Foldable, foldl', foldMap, foldr, toList)
import Data.Function (on)
import Data.Hashable (Hashable(..))
import Data.Map (Map)
import Data.Map.Util
import Data.Monoid (Monoid(..))
#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup(..))
#endif
import Data.Set (Set) -- so the haddocks link to the right place
import Prelude hiding (filter, foldr, lookup, null)
import qualified Data.Map as M
import qualified GHC.Exts as Exts

data OSet a = OSet !(Map a Tag) !(Map Tag a)
	deriving Typeable -- ^ @since 0.2

-- | Values appear in insertion order, not ascending order.
instance Foldable OSet where foldMap :: forall m a. Monoid m => (a -> m) -> OSet a -> m
foldMap a -> m
f (OSet Map a Int
_ Map Int a
vs) = (a -> m) -> Map Int a -> m
forall m a. Monoid m => (a -> m) -> Map Int a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Map Int a
vs
instance         Eq   a  => Eq   (OSet a) where == :: OSet a -> OSet a -> Bool
(==)    = [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
(==)    ([a] -> [a] -> Bool) -> (OSet a -> [a]) -> OSet a -> OSet a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` OSet a -> [a]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
instance         Ord  a  => Ord  (OSet a) where compare :: OSet a -> OSet a -> Ordering
compare = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([a] -> [a] -> Ordering)
-> (OSet a -> [a]) -> OSet a -> OSet a -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` OSet a -> [a]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
instance         Show a  => Show (OSet a) where showsPrec :: Int -> OSet a -> ShowS
showsPrec = (OSet a -> [a]) -> Int -> OSet a -> ShowS
forall a b. Show a => (b -> [a]) -> Int -> b -> ShowS
showsPrecList OSet a -> [a]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
instance (Ord a, Read a) => Read (OSet a) where readsPrec :: Int -> ReadS (OSet a)
readsPrec = ([a] -> OSet a) -> Int -> ReadS (OSet a)
forall a b. Read a => ([a] -> b) -> Int -> ReadS b
readsPrecList [a] -> OSet a
forall a. Ord a => [a] -> OSet a
fromList
-- | @since 0.2.3
instance     Hashable a  => Hashable (OSet a) where hashWithSalt :: Int -> OSet a -> Int
hashWithSalt Int
s = Int -> [a] -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s ([a] -> Int) -> (OSet a -> [a]) -> OSet a -> Int
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]
toList

-- This instance preserves data abstraction at the cost of inefficiency.
-- We provide limited reflection services for the sake of data abstraction.
-- | @since 0.2
instance (Data a, Ord a) => Data (OSet a) where
	gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> OSet a -> c (OSet a)
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
f forall g. g -> c g
z OSet a
set = ([a] -> OSet a) -> c ([a] -> OSet a)
forall g. g -> c g
z [a] -> OSet a
forall a. Ord a => [a] -> OSet a
fromList c ([a] -> OSet a) -> [a] -> c (OSet a)
forall d b. Data d => c (d -> b) -> d -> c b
`f` OSet a -> [a]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList OSet a
set
	toConstr :: OSet a -> Constr
toConstr OSet a
_     = Constr
fromListConstr
	gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (OSet a)
gunfold forall b r. Data b => c (b -> r) -> c r
k forall r. r -> c r
z Constr
c  = case Constr -> Int
constrIndex Constr
c of
		Int
1 -> c ([a] -> OSet a) -> c (OSet a)
forall b r. Data b => c (b -> r) -> c r
k (([a] -> OSet a) -> c ([a] -> OSet a)
forall r. r -> c r
z [a] -> OSet a
forall a. Ord a => [a] -> OSet a
fromList)
		Int
_ -> String -> c (OSet a)
forall a. HasCallStack => String -> a
error String
"gunfold"
	dataTypeOf :: OSet a -> DataType
dataTypeOf OSet a
_   = DataType
oSetDataType
	-- dataCast1 /must/ be eta-expanded in order to build on GHC 7.8.
	dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (OSet a))
dataCast1 forall d. Data d => c (t d)
f    = c (t a) -> Maybe (c (OSet a))
forall {k1} {k2} (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
       (a :: k2).
(Typeable t, Typeable t') =>
c (t a) -> Maybe (c (t' a))
gcast1 c (t a)
forall d. Data d => c (t d)
f

fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> String -> [String] -> Fixity -> Constr
mkConstr DataType
oSetDataType String
"fromList" [] Fixity
Prefix

oSetDataType :: DataType
oSetDataType :: DataType
oSetDataType = String -> [Constr] -> DataType
mkDataType String
"Data.Set.Ordered.Set" [Constr
fromListConstr]

-- | @'GHC.Exts.fromList' = 'fromList'@ and @'GHC.Exts.toList' = 'toList'@.
--
-- @since 0.2.3
instance Ord a => Exts.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 = OSet a -> [a]
OSet a -> [Item (OSet a)]
forall a. OSet a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

#if MIN_VERSION_base(4,9,0)
-- | @since 0.2
instance Ord a => Semigroup (Bias L (OSet a)) where Bias OSet a
o <> :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a)
<> Bias OSet a
o' = OSet a -> Bias L (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias (OSet a
o OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
|<> OSet a
o')
-- | @since 0.2
instance Ord a => Semigroup (Bias R (OSet a)) where Bias OSet a
o <> :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a)
<> Bias OSet a
o' = OSet a -> Bias R (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias (OSet a
o OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
<>| OSet a
o')
#endif

-- | Empty sets and set union. When combining two sets that share elements, the
-- indices of the left argument are preferred.
--
-- See the asymptotics of ('|<>').
--
-- @since 0.2
instance Ord a => Monoid (Bias L (OSet a)) where
	mempty :: Bias L (OSet a)
mempty = OSet a -> Bias L (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias OSet a
forall a. OSet a
empty
	mappend :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a)
mappend (Bias OSet a
o) (Bias OSet a
o') = OSet a -> Bias L (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias (OSet a
o OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
|<> OSet a
o')

-- | Empty sets and set union. When combining two sets that share elements, the
-- indices of the right argument are preferred.
--
-- See the asymptotics of ('<>|').
--
-- @since 0.2
instance Ord a => Monoid (Bias R (OSet a)) where
	mempty :: Bias R (OSet a)
mempty = OSet a -> Bias R (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias OSet a
forall a. OSet a
empty
	mappend :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a)
mappend (Bias OSet a
o) (Bias OSet a
o') = OSet a -> Bias R (OSet a)
forall (dir :: IndexPreference) a. a -> Bias dir a
Bias (OSet a
o OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
<>| OSet a
o')

infixr 5 <|, |<   -- copy :
infixl 5 >|, |>
infixr 6 <>|, |<> -- copy <>

(<|) , (|<)  :: Ord a =>      a -> OSet a -> OSet a
(>|) , (|>)  :: Ord a => OSet a ->      a -> OSet a

-- | /O(m*log(n)+n)/, where /m/ is the size of the smaller set and /n/ is the
-- size of the larger set.
(<>|) :: Ord a => OSet a -> OSet a -> OSet a

-- | /O(m*log(n)+n)/, where /m/ is the size of the smaller set and /n/ is the
-- size of the larger set.
(|<>) :: Ord a => OSet a -> OSet a -> OSet a

a
v <| :: forall a. Ord a => a -> OSet a -> OSet a
<| o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs)
	| a
v a -> OSet a -> Bool
forall a. Ord a => a -> OSet a -> Bool
`member` OSet a
o = OSet a
o
	| Bool
otherwise    = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Int -> Map a Int -> Map a Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v Int
t Map a Int
ts) (Int -> a -> Map Int a -> Map Int a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
t a
v Map Int a
vs) where
		t :: Int
t = Map Int a -> Int
forall a. Map Int a -> Int
nextLowerTag Map Int a
vs

a
v |< :: forall a. Ord a => a -> OSet a -> OSet a
|< OSet a
o = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Int -> Map a Int -> Map a Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v Int
t Map a Int
ts) (Int -> a -> Map Int a -> Map Int a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
t a
v Map Int a
vs) where
	t :: Int
t = Map Int a -> Int
forall a. Map Int a -> Int
nextLowerTag Map Int a
vs
	OSet Map a Int
ts Map Int a
vs = a -> OSet a -> OSet a
forall a. Ord a => a -> OSet a -> OSet a
delete a
v OSet a
o

o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs) |> :: forall a. Ord a => OSet a -> a -> OSet a
|> a
v
	| a
v a -> OSet a -> Bool
forall a. Ord a => a -> OSet a -> Bool
`member` OSet a
o = OSet a
o
	| Bool
otherwise    = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Int -> Map a Int -> Map a Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v Int
t Map a Int
ts) (Int -> a -> Map Int a -> Map Int a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
t a
v Map Int a
vs) where
		t :: Int
t = Map Int a -> Int
forall a. Map Int a -> Int
nextHigherTag Map Int a
vs

OSet a
o >| :: forall a. Ord a => OSet a -> a -> OSet a
>| a
v = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Int -> Map a Int -> Map a Int
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
v Int
t Map a Int
ts) (Int -> a -> Map Int a -> Map Int a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Int
t a
v Map Int a
vs) where
	t :: Int
t = Map Int a -> Int
forall a. Map Int a -> Int
nextHigherTag Map Int a
vs
	OSet Map a Int
ts Map Int a
vs = a -> OSet a -> OSet a
forall a. Ord a => a -> OSet a -> OSet a
delete a
v OSet a
o

OSet a
o <>| :: forall a. Ord a => OSet a -> OSet a -> OSet a
<>| OSet a
o' = OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
unsafeMappend (OSet a
o OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
\\ OSet a
o') OSet a
o'
OSet a
o |<> :: forall a. Ord a => OSet a -> OSet a -> OSet a
|<> OSet a
o' = OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
unsafeMappend OSet a
o (OSet a
o' OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
\\ OSet a
o)

-- assumes that ts and ts' have disjoint keys
unsafeMappend :: OSet a -> OSet a -> OSet a
unsafeMappend (OSet Map a Int
ts Map Int a
vs) (OSet Map a Int
ts' Map Int a
vs')
	= Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (Map a Int -> Map a Int -> Map a Int
forall k a. Ord k => Map k a -> Map k a -> Map k a
M.union Map a Int
tsBumped Map a Int
tsBumped')
	       (Map Int a -> Map Int a -> Map Int a
forall k a. Ord k => Map k a -> Map k a -> Map k a
M.union Map Int a
vsBumped Map Int a
vsBumped')
	where
	bump :: Int
bump  = case Map Int a -> Maybe Int
forall a. Map Int a -> Maybe Int
maxTag Map Int a
vs  of
		Maybe Int
Nothing -> Int
0
		Just Int
k  -> -Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
	bump' :: Int
bump' = case Map Int a -> Maybe Int
forall a. Map Int a -> Maybe Int
minTag Map Int a
vs' of
		Maybe Int
Nothing -> Int
0
		Just Int
k  -> -Int
k
	tsBumped :: Map a Int
tsBumped  = (Int -> Int) -> Map a Int -> Map a Int
forall a b. (a -> b) -> Map a a -> Map a b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int
bump Int -> Int -> Int
forall a. Num a => a -> a -> a
+) Map a Int
ts
	tsBumped' :: Map a Int
tsBumped' = (Int -> Int) -> Map a Int -> Map a Int
forall a b. (a -> b) -> Map a a -> Map a b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int
bump'Int -> Int -> Int
forall a. Num a => a -> a -> a
+) Map a Int
ts'
	vsBumped :: Map Int a
vsBumped  = (Int
bump Int -> Int -> Int
forall a. Num a => a -> a -> a
+) (Int -> Int) -> Map Int a -> Map Int a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
`M.mapKeysMonotonic` Map Int a
vs
	vsBumped' :: Map Int a
vsBumped' = (Int
bump'Int -> Int -> Int
forall a. Num a => a -> a -> a
+) (Int -> Int) -> Map Int a -> Map Int a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
`M.mapKeysMonotonic` Map Int a
vs'

-- | Set difference: @r \\\\ s@ deletes all the values in @s@ from @r@. The
-- order of @r@ is unchanged.
--
-- /O(m*log(n))/ where /m/ is the size of the smaller set and /n/ is the size
-- of the larger set.
(\\) :: Ord a => OSet a -> OSet a -> OSet a
o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs) \\ :: forall a. Ord a => OSet a -> OSet a -> OSet a
\\ o' :: OSet a
o'@(OSet Map a Int
ts' Map Int a
vs') = if OSet a -> Int
forall a. OSet a -> Int
size OSet a
o Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< OSet a -> Int
forall a. OSet a -> Int
size OSet a
o'
	then (a -> Bool) -> OSet a -> OSet a
forall a. Ord a => (a -> Bool) -> OSet a -> OSet a
filter (a -> OSet a -> Bool
forall a. Ord a => a -> OSet a -> Bool
`notMember` OSet a
o') OSet a
o
	else (a -> OSet a -> OSet a) -> OSet a -> Map Int a -> OSet a
forall a b. (a -> b -> b) -> b -> Map Int a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> OSet a -> OSet a
forall a. Ord a => a -> OSet a -> OSet a
delete OSet a
o Map Int a
vs'

-- | Intersection. (@/\\@ is meant to look a bit like the standard mathematical
-- notation for intersection.)
--
-- /O(m*log(n\/(m+1)) + r*log(r))/, where /m/ is the size of the smaller set,
-- /n/ the size of the larger set, and /r/ the size of the result.
(|/\) :: Ord a => OSet a -> OSet a -> OSet a
OSet Map a Int
ts Map Int a
vs |/\ :: forall a. Ord a => OSet a -> OSet a -> OSet a
|/\ OSet Map a Int
ts' Map Int a
vs' = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet Map a Int
ts'' Map Int a
vs'' where
	ts'' :: Map a Int
ts'' = Map a Int -> Map a Int -> Map a Int
forall k a b. Ord k => Map k a -> Map k b -> Map k a
M.intersection Map a Int
ts Map a Int
ts'
	vs'' :: Map Int a
vs'' = [(Int, a)] -> Map Int a
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList [(Int
t, a
v) | (a
v, Int
t) <- Map a Int -> [(a, Int)]
forall k a. Map k a -> [(k, a)]
M.toList Map a Int
ts'']

-- | @flip ('|/\')@
--
-- See asymptotics of '|/\'.
(/\|) :: Ord a => OSet a -> OSet a -> OSet a
/\| :: forall a. Ord a => OSet a -> OSet a -> OSet a
(/\|) = (OSet a -> OSet a -> OSet a) -> OSet a -> OSet a -> OSet a
forall a b c. (a -> b -> c) -> b -> a -> c
flip OSet a -> OSet a -> OSet a
forall a. Ord a => OSet a -> OSet a -> OSet a
(|/\)

empty :: OSet a
empty :: forall a. OSet a
empty = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet Map a Int
forall k a. Map k a
M.empty Map Int a
forall k a. Map k a
M.empty

member, notMember :: Ord a => a -> OSet a -> Bool
member :: forall a. Ord a => a -> OSet a -> Bool
member    a
v (OSet Map a Int
ts Map Int a
_) = a -> Map a Int -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.member    a
v Map a Int
ts
notMember :: forall a. Ord a => a -> OSet a -> Bool
notMember a
v (OSet Map a Int
ts Map Int a
_) = a -> Map a Int -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.notMember a
v Map a Int
ts

size :: OSet a -> Int
size :: forall a. OSet a -> Int
size (OSet Map a Int
ts Map Int a
_) = Map a Int -> Int
forall k a. Map k a -> Int
M.size Map a Int
ts

-- the Ord constraint is for compatibility with older (<0.5) versions of
-- containers
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 Map a Int
ts Map Int a
vs) = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet ((a -> Int -> Bool) -> Map a Int -> Map a Int
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
M.filterWithKey (\a
v Int
t -> a -> Bool
f a
v) Map a Int
ts)
                             ((Int -> a -> Bool) -> Map Int a -> Map Int a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
M.filterWithKey (\Int
t a
v -> a -> Bool
f a
v) Map Int a
vs)

delete :: Ord a => a -> OSet a -> OSet a
delete :: forall a. Ord a => a -> OSet a -> OSet a
delete a
v o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs) = case a -> Map a Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
v Map a Int
ts of
	Maybe Int
Nothing -> OSet a
o
	Just Int
t  -> Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Map a Int -> Map a Int
forall k a. Ord k => k -> Map k a -> Map k a
M.delete a
v Map a Int
ts) (Int -> Map Int a -> Map Int a
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Int
t Map Int a
vs)

singleton :: a -> OSet a
singleton :: forall a. a -> OSet a
singleton a
v = Map a Int -> Map Int a -> OSet a
forall a. Map a Int -> Map Int a -> OSet a
OSet (a -> Int -> Map a Int
forall k a. k -> a -> Map k a
M.singleton a
v Int
0) (Int -> a -> Map Int a
forall k a. k -> a -> Map k a
M.singleton Int
0 a
v)

-- | If a value occurs multiple times, only the first occurrence is used.
fromList :: Ord a => [a] -> OSet a
fromList :: forall a. Ord a => [a] -> OSet a
fromList = (OSet a -> a -> OSet a) -> OSet a -> [a] -> OSet a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' OSet a -> a -> OSet a
forall a. Ord a => OSet a -> a -> OSet a
(|>) OSet a
forall a. OSet a
empty

null :: OSet a -> Bool
null :: forall a. OSet a -> Bool
null (OSet Map a Int
ts Map Int a
_) = Map a Int -> Bool
forall k a. Map k a -> Bool
M.null Map a Int
ts

findIndex :: Ord a => a -> OSet a -> Maybe Index
findIndex :: forall a. Ord a => a -> OSet a -> Maybe Int
findIndex a
v o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs) = do
	Int
t <- a -> Map a Int -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
v Map a Int
ts
	Int -> Map Int a -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe Int
M.lookupIndex Int
t Map Int a
vs

elemAt :: OSet a -> Index -> Maybe a
elemAt :: forall a. OSet a -> Int -> Maybe a
elemAt o :: OSet a
o@(OSet Map a Int
ts Map Int a
vs) Int
i = do
	Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Map Int a -> Int
forall k a. Map k a -> Int
M.size Map Int a
vs)
	a -> Maybe a
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a) -> ((Int, a) -> a) -> (Int, a) -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, a) -> a
forall a b. (a, b) -> b
snd ((Int, a) -> Maybe a) -> (Int, a) -> Maybe a
forall a b. (a -> b) -> a -> b
$ Int -> Map Int a -> (Int, a)
forall k a. Int -> Map k a -> (k, a)
M.elemAt Int
i Map Int a
vs

-- | Returns values in ascending order. (Use 'toList' to return them in
-- insertion order.)
toAscList :: OSet a -> [a]
toAscList :: forall a. OSet a -> [a]
toAscList o :: OSet a
o@(OSet Map a Int
ts Map Int a
_) = ((a, Int) -> a) -> [(a, Int)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Int) -> a
forall a b. (a, b) -> a
fst (Map a Int -> [(a, Int)]
forall k a. Map k a -> [(k, a)]
M.toAscList Map a Int
ts)

-- | Convert an 'OSet' to a 'Set'.
--
-- /O(n)/, where /n/ is the size of the 'OSet'.
toSet :: OSet a -> Set a
toSet :: forall a. OSet a -> Set a
toSet (OSet Map a Int
ts Map Int a
_) = Map a Int -> Set a
forall k a. Map k a -> Set k
M.keysSet Map a Int
ts