{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  $header
-- Copyright   :  (c) Laurent P. René de Cotret
-- License     :  MIT-style
-- Maintainer  :  Laurent P. René de Cotret
-- Portability :  portable
--
-- This module contains the definition of 'Index', a sequence of /unique/ and /sorted/
-- keys which can be used to efficient index a 'Series'.


module Data.Series.Index.Definition (
    Index(..),

    -- * Creation and Conversion
    singleton,
    unfoldr,
    range,
    fromSet, toSet,
    fromList, toAscList,
    fromAscList, fromDistinctAscList,
    fromVector, toAscVector,
    fromAscVector, fromDistinctAscVector,
    -- ** Ad-hoc conversion with other data structures
    IsIndex(..),
    
    -- * Set-like operations
    null,
    member,
    notMember,
    union,
    intersection,
    difference,
    symmetricDifference,
    cartesianProduct,
    contains,
    size,
    take,
    drop,

    -- * Mapping and filtering
    map,
    mapMonotonic,
    filter,
    traverse,
    
    -- * Indexing
    findIndex,
    lookupIndex,
    elemAt,

    -- * Insertion and deletion
    insert,
    delete,
) where

import           Control.DeepSeq        ( NFData )
import           Control.Monad          ( guard )
import           Control.Monad.ST       ( runST )
import           Data.Coerce            ( coerce )
import qualified Data.Foldable          as Foldable
import           Data.Functor           ( ($>) )
import           Data.IntSet            ( IntSet )
import qualified Data.IntSet            as IntSet
import qualified Data.List              as List
import           Data.Sequence          ( Seq )
import qualified Data.Sequence          as Seq
import           Data.Set               ( Set )
import qualified Data.Set               as Set
import qualified Data.Traversable       as Traversable
import qualified Data.Vector            as Boxed
import           Data.Vector.Algorithms.Intro ( sortUniq )
import           Data.Vector.Generic    ( Vector )
import qualified Data.Vector.Generic    as Vector
import qualified Data.Vector.Generic.Mutable as M
import qualified Data.Vector.Unboxed    as Unboxed
import           GHC.Exts               ( IsList )
import qualified GHC.Exts               as Exts
import           GHC.Stack              ( HasCallStack )
import           Prelude                as P hiding ( null, take, drop, map, filter, traverse, product )

-- $setup
-- >>> import Data.Series.Index
-- >>> import qualified Data.Vector as Vector


-- | Representation of the index of a series.
-- An index is a sequence of sorted elements. All elements are unique, much like a 'Set'.
--
-- You can construct an 'Index' from a set ('fromSet'), from a list ('fromList'), or from a vector ('fromVector'). You can 
-- also make use of the @OverloadedLists@ extension:
--
-- >>> :set -XOverloadedLists
-- >>> let (ix :: Index Int) = [1, 2, 3]
-- >>> ix
-- Index [1,2,3]
--
-- Since keys in an 'Index' are always sorted and unique, 'Index' is not a 'Functor'. To map a function
-- over an 'Index', use 'map'.
newtype Index k = MkIndex (Set k)
    deriving (Index k -> Index k -> Bool
(Index k -> Index k -> Bool)
-> (Index k -> Index k -> Bool) -> Eq (Index k)
forall k. Eq k => Index k -> Index k -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall k. Eq k => Index k -> Index k -> Bool
== :: Index k -> Index k -> Bool
$c/= :: forall k. Eq k => Index k -> Index k -> Bool
/= :: Index k -> Index k -> Bool
Eq, Eq (Index k)
Eq (Index k) =>
(Index k -> Index k -> Ordering)
-> (Index k -> Index k -> Bool)
-> (Index k -> Index k -> Bool)
-> (Index k -> Index k -> Bool)
-> (Index k -> Index k -> Bool)
-> (Index k -> Index k -> Index k)
-> (Index k -> Index k -> Index k)
-> Ord (Index k)
Index k -> Index k -> Bool
Index k -> Index k -> Ordering
Index k -> Index k -> Index k
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 k. Ord k => Eq (Index k)
forall k. Ord k => Index k -> Index k -> Bool
forall k. Ord k => Index k -> Index k -> Ordering
forall k. Ord k => Index k -> Index k -> Index k
$ccompare :: forall k. Ord k => Index k -> Index k -> Ordering
compare :: Index k -> Index k -> Ordering
$c< :: forall k. Ord k => Index k -> Index k -> Bool
< :: Index k -> Index k -> Bool
$c<= :: forall k. Ord k => Index k -> Index k -> Bool
<= :: Index k -> Index k -> Bool
$c> :: forall k. Ord k => Index k -> Index k -> Bool
> :: Index k -> Index k -> Bool
$c>= :: forall k. Ord k => Index k -> Index k -> Bool
>= :: Index k -> Index k -> Bool
$cmax :: forall k. Ord k => Index k -> Index k -> Index k
max :: Index k -> Index k -> Index k
$cmin :: forall k. Ord k => Index k -> Index k -> Index k
min :: Index k -> Index k -> Index k
Ord, NonEmpty (Index k) -> Index k
Index k -> Index k -> Index k
(Index k -> Index k -> Index k)
-> (NonEmpty (Index k) -> Index k)
-> (forall b. Integral b => b -> Index k -> Index k)
-> Semigroup (Index k)
forall b. Integral b => b -> Index k -> Index k
forall k. Ord k => NonEmpty (Index k) -> Index k
forall k. Ord k => Index k -> Index k -> Index k
forall k b. (Ord k, Integral b) => b -> Index k -> Index k
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
$c<> :: forall k. Ord k => Index k -> Index k -> Index k
<> :: Index k -> Index k -> Index k
$csconcat :: forall k. Ord k => NonEmpty (Index k) -> Index k
sconcat :: NonEmpty (Index k) -> Index k
$cstimes :: forall k b. (Ord k, Integral b) => b -> Index k -> Index k
stimes :: forall b. Integral b => b -> Index k -> Index k
Semigroup, Semigroup (Index k)
Index k
Semigroup (Index k) =>
Index k
-> (Index k -> Index k -> Index k)
-> ([Index k] -> Index k)
-> Monoid (Index k)
[Index k] -> Index k
Index k -> Index k -> Index k
forall k. Ord k => Semigroup (Index k)
forall k. Ord k => Index k
forall k. Ord k => [Index k] -> Index k
forall k. Ord k => Index k -> Index k -> Index k
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
$cmempty :: forall k. Ord k => Index k
mempty :: Index k
$cmappend :: forall k. Ord k => Index k -> Index k -> Index k
mappend :: Index k -> Index k -> Index k
$cmconcat :: forall k. Ord k => [Index k] -> Index k
mconcat :: [Index k] -> Index k
Monoid, (forall m. Monoid m => Index m -> m)
-> (forall m a. Monoid m => (a -> m) -> Index a -> m)
-> (forall m a. Monoid m => (a -> m) -> Index a -> m)
-> (forall a b. (a -> b -> b) -> b -> Index a -> b)
-> (forall a b. (a -> b -> b) -> b -> Index a -> b)
-> (forall b a. (b -> a -> b) -> b -> Index a -> b)
-> (forall b a. (b -> a -> b) -> b -> Index a -> b)
-> (forall a. (a -> a -> a) -> Index a -> a)
-> (forall a. (a -> a -> a) -> Index a -> a)
-> (forall a. Index a -> [a])
-> (forall a. Index a -> Bool)
-> (forall a. Index a -> Int)
-> (forall a. Eq a => a -> Index a -> Bool)
-> (forall a. Ord a => Index a -> a)
-> (forall a. Ord a => Index a -> a)
-> (forall a. Num a => Index a -> a)
-> (forall a. Num a => Index a -> a)
-> Foldable Index
forall a. Eq a => a -> Index a -> Bool
forall a. Num a => Index a -> a
forall a. Ord a => Index a -> a
forall m. Monoid m => Index m -> m
forall a. Index a -> Bool
forall a. Index a -> Int
forall a. Index a -> [a]
forall a. (a -> a -> a) -> Index a -> a
forall m a. Monoid m => (a -> m) -> Index a -> m
forall b a. (b -> a -> b) -> b -> Index a -> b
forall a b. (a -> b -> b) -> b -> Index a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => Index m -> m
fold :: forall m. Monoid m => Index m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Index a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Index a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Index a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Index a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> Index a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Index a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Index a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Index a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Index a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Index a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Index a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Index a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> Index a -> a
foldr1 :: forall a. (a -> a -> a) -> Index a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Index a -> a
foldl1 :: forall a. (a -> a -> a) -> Index a -> a
$ctoList :: forall a. Index a -> [a]
toList :: forall a. Index a -> [a]
$cnull :: forall a. Index a -> Bool
null :: forall a. Index a -> Bool
$clength :: forall a. Index a -> Int
length :: forall a. Index a -> Int
$celem :: forall a. Eq a => a -> Index a -> Bool
elem :: forall a. Eq a => a -> Index a -> Bool
$cmaximum :: forall a. Ord a => Index a -> a
maximum :: forall a. Ord a => Index a -> a
$cminimum :: forall a. Ord a => Index a -> a
minimum :: forall a. Ord a => Index a -> a
$csum :: forall a. Num a => Index a -> a
sum :: forall a. Num a => Index a -> a
$cproduct :: forall a. Num a => Index a -> a
product :: forall a. Num a => Index a -> a
Foldable, Index k -> ()
(Index k -> ()) -> NFData (Index k)
forall k. NFData k => Index k -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall k. NFData k => Index k -> ()
rnf :: Index k -> ()
NFData)


instance Ord k => IsList (Index k) where
    type Item (Index k) = k
    fromList :: [k] -> Index k
    fromList :: [k] -> Index k
fromList = [k] -> Index k
forall k. Ord k => [k] -> Index k
fromList
    toList :: Index k -> [Exts.Item (Index k)]
    toList :: Index k -> [Item (Index k)]
toList = Index k -> [k]
Index k -> [Item (Index k)]
forall a. Index a -> [a]
toAscList


instance Show k => Show (Index k) where
    show :: Index k -> String
    show :: Index k -> String
show (MkIndex Set k
s) = String
"Index " String -> ShowS
forall a. [a] -> [a] -> [a]
++ [k] -> String
forall a. Show a => a -> String
show (Set k -> [k]
forall a. Set a -> [a]
Set.toList Set k
s)


-- | \(O(1)\)  Create a singleton 'Index'.
singleton :: k -> Index k
singleton :: forall k. k -> Index k
singleton = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> (k -> Set k) -> k -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Set k
forall a. a -> Set a
Set.singleton
{-# INLINE singleton #-}


-- | \(O(n \log n)\) Create an 'Index' from a seed value. 
-- Note that the order in which elements are generated does not matter; elements are stored
-- in order. See the example below.
--
-- >>> unfoldr (\x -> if x < 1 then Nothing else Just (x, x-1)) (7 :: Int)
-- Index [1,2,3,4,5,6,7]
unfoldr :: Ord a => (b -> Maybe (a, b)) -> b -> Index a
unfoldr :: forall a b. Ord a => (b -> Maybe (a, b)) -> b -> Index a
unfoldr b -> Maybe (a, b)
f = [a] -> Index a
forall k. Ord k => [k] -> Index k
fromList ([a] -> Index a) -> (b -> [a]) -> b -> Index a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> Maybe (a, b)) -> b -> [a]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
List.unfoldr b -> Maybe (a, b)
f
{-# INLINE unfoldr #-}


-- | \(O(n \log n)\) Create an 'Index' as a range of values. @range f start end@ will generate 
-- an 'Index' with values @[start, f start, f (f start), ... ]@ such that the largest element
-- less or equal to @end@ is included. See examples below.
--
-- >>> range (+3) (1 :: Int) 10
-- Index [1,4,7,10]
-- >>> range (+3) (1 :: Int) 11
-- Index [1,4,7,10]
range :: Ord a 
      => (a -> a) -- ^ Function to generate the next element in the index
      -> a        -- ^ Starting value of the 'Index'
      -> a        -- ^ Ending value of the 'Index', which may or may not be contained
      -> Index a
range :: forall a. Ord a => (a -> a) -> a -> a -> Index a
range a -> a
next a
start a
end 
    = (a -> Maybe (a, a)) -> a -> Index a
forall a b. Ord a => (b -> Maybe (a, b)) -> b -> Index a
unfoldr (\a
x -> Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
end) Maybe () -> (a, a) -> Maybe (a, a)
forall (f :: * -> *) a b. Functor f => f a -> b -> f b
$> (a
x, a -> a
next a
x)) a
start
{-# INLINE range #-}


-- | The 'IsIndex' typeclass allow for ad-hoc definition
-- of conversion functions, converting to / from 'Index'.
class IsIndex t k where
    -- | Construct an 'Index' from some container of keys. There is no
    -- condition on the order of keys. Duplicate keys are silently dropped.
    toIndex    :: t -> Index k

    -- | Construct a container from keys of an 'Index'. 
    -- The elements are returned in ascending order of keys.
    fromIndex  :: Index k -> t


instance IsIndex (Set k) k where
    -- | \(O(1)\) Build an 'Index' from a 'Set'.
    toIndex :: Set k -> Index k
    toIndex :: Set k -> Index k
toIndex = Set k -> Index k
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE toIndex #-}

    -- | \(O(1)\) Build an 'Index' from a 'Set'.
    fromIndex :: Index k -> Set k
    fromIndex :: Index k -> Set k
fromIndex = Index k -> Set k
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE fromIndex #-}


instance Ord k => IsIndex [k] k where
    -- | \(O(n \log n)\) Build an 'Index' from a list.
    toIndex :: [k] -> Index k
    toIndex :: [k] -> Index k
toIndex = [k] -> Index k
forall k. Ord k => [k] -> Index k
fromList
    {-# INLINE toIndex #-}

    -- | \(O(n)\) Convert an 'Index' to a list.
    fromIndex :: Index k -> [k]
    fromIndex :: Index k -> [k]
fromIndex = Index k -> [k]
forall a. Index a -> [a]
toAscList
    {-# INLINE fromIndex #-}


instance Ord k => IsIndex (Seq k) k where
    -- | \(O(n \log n)\) Build an 'Index' from a 'Seq'.
    toIndex :: Seq k -> Index k
    toIndex :: Seq k -> Index k
toIndex = [k] -> Index k
forall k. Ord k => [k] -> Index k
fromList ([k] -> Index k) -> (Seq k -> [k]) -> Seq k -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq k -> [k]
forall a. Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList
    {-# INLINE toIndex #-}

    -- | \(O(n)\) Convert an 'Index' to a 'Seq'.
    fromIndex :: Index k -> Seq k
    fromIndex :: Index k -> Seq k
fromIndex = [k] -> Seq k
forall a. [a] -> Seq a
Seq.fromList ([k] -> Seq k) -> (Index k -> [k]) -> Index k -> Seq k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index k -> [k]
forall a. Index a -> [a]
toAscList
    {-# INLINE fromIndex #-}


instance IsIndex IntSet Int where
    -- | \(O(n \min(n,W))\), where \W\ is the number of bits in an 'Int' on your platform (32 or 64).
    toIndex :: IntSet -> Index Int
    toIndex :: IntSet -> Index Int
toIndex = [Int] -> Index Int
forall k. [k] -> Index k
fromDistinctAscList ([Int] -> Index Int) -> (IntSet -> [Int]) -> IntSet -> Index Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toList
    {-# INLINE toIndex #-}
    
    -- | \(O(n)\) Convert an 'Index' to an 'IntSet.
    fromIndex :: Index Int -> IntSet
    fromIndex :: Index Int -> IntSet
fromIndex = [Int] -> IntSet
IntSet.fromDistinctAscList ([Int] -> IntSet) -> (Index Int -> [Int]) -> Index Int -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index Int -> [Int]
forall a. Index a -> [a]
toAscList
    {-# INLINE fromIndex #-}


instance (Ord k) => IsIndex (Boxed.Vector k) k where
    toIndex :: Boxed.Vector k -> Index k
    toIndex :: Vector k -> Index k
toIndex = Vector k -> Index k
forall (v :: * -> *) k. (Vector v k, Ord k) => v k -> Index k
fromVector
    {-# INLINE toIndex #-} 

    fromIndex :: Index k -> Boxed.Vector k
    fromIndex :: Index k -> Vector k
fromIndex = Index k -> Vector k
forall (v :: * -> *) k. Vector v k => Index k -> v k
toAscVector
    {-# INLINE fromIndex #-}


instance (Ord k, Unboxed.Unbox k) => IsIndex (Unboxed.Vector k) k where
    toIndex :: Unboxed.Vector k -> Index k
    toIndex :: Vector k -> Index k
toIndex = Vector k -> Index k
forall (v :: * -> *) k. (Vector v k, Ord k) => v k -> Index k
fromVector
    {-# INLINE toIndex #-} 

    fromIndex :: Index k -> Unboxed.Vector k
    fromIndex :: Index k -> Vector k
fromIndex Index k
ix = (forall s. ST s (Vector k)) -> Vector k
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Vector k)) -> Vector k)
-> (forall s. ST s (Vector k)) -> Vector k
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> k) -> ST s (MVector (PrimState (ST s)) k)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> a) -> m (v (PrimState m) a)
M.generate (Index k -> Int
forall a. Index a -> Int
size Index k
ix) (Int -> Index k -> k
forall k. HasCallStack => Int -> Index k -> k
`elemAt` Index k
ix) ST s (MVector s k)
-> (MVector s k -> ST s (Vector k)) -> ST s (Vector k)
forall a b. ST s a -> (a -> ST s b) -> ST s b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MVector s k -> ST s (Vector k)
Mutable Vector (PrimState (ST s)) k -> ST s (Vector k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
Vector.freeze
    {-# INLINE fromIndex #-}


-- | \(O(1)\) Build an 'Index' from a 'Set'.
fromSet :: Set k -> Index k
fromSet :: forall k. Set k -> Index k
fromSet = Set k -> Index k
forall t k. IsIndex t k => t -> Index k
toIndex
{-# INLINE fromSet #-}


-- | \(O(n \log n)\) Build an 'Index' from a list. Note that since an 'Index' is
-- composed of unique elements, the length of the index may not be
-- the same as the length of the input list:
--
-- >>> fromList ['c', 'a', 'b', 'b']
-- Index "abc"
--
-- If the list is already sorted, `fromAscList` is generally faster.
fromList :: Ord k => [k] -> Index k
fromList :: forall k. Ord k => [k] -> Index k
fromList = Set k -> Index k
forall k. Set k -> Index k
fromSet (Set k -> Index k) -> ([k] -> Set k) -> [k] -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Set k
forall a. Ord a => [a] -> Set a
Set.fromList
{-# INLINE fromList #-}


-- | \(O(n)\) Build an 'Index' from a list of elements in ascending order. The precondition
-- that elements already be sorted is not checked.
-- 
-- Note that since an 'Index' is composed of unique elements, the length of 
-- the index may not be the same as the length of the input list.
fromAscList :: Eq k => [k] -> Index k
fromAscList :: forall k. Eq k => [k] -> Index k
fromAscList = Set k -> Index k
forall t k. IsIndex t k => t -> Index k
toIndex (Set k -> Index k) -> ([k] -> Set k) -> [k] -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Set k
forall a. Eq a => [a] -> Set a
Set.fromAscList
{-# INLINE fromAscList #-}


-- | \(O(n)\) Build an 'Index' from a list of distinct elements in ascending order. The precondition
-- that elements be unique and sorted is not checked.
fromDistinctAscList :: [k] -> Index k
fromDistinctAscList :: forall k. [k] -> Index k
fromDistinctAscList = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> ([k] -> Set k) -> [k] -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Set k
forall a. [a] -> Set a
Set.fromDistinctAscList
{-# INLINE fromDistinctAscList #-}


-- | \(O(n \log n)\) Build an 'Index' from a 'Vector'. Note that since an 'Index' is
-- composed of unique elements, the length of the index may not be
-- the same as the length of the input vector:
--
-- >>> import Data.Vector as V
-- >>> fromVector $ V.fromList ['c', 'a', 'b', 'b']
-- Index "abc"
--
-- If the 'Vector' is already sorted, 'fromAscVector' is generally faster.
fromVector :: (Vector v k, Ord k) => v k -> Index k
fromVector :: forall (v :: * -> *) k. (Vector v k, Ord k) => v k -> Index k
fromVector v k
vs = v k -> Index k
forall (v :: * -> *) k. Vector v k => v k -> Index k
fromDistinctAscVector (v k -> Index k) -> v k -> Index k
forall a b. (a -> b) -> a -> b
$ (forall s. ST s (v k)) -> v k
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (v k)) -> v k) -> (forall s. ST s (v k)) -> v k
forall a b. (a -> b) -> a -> b
$ v k -> ST s (Mutable v (PrimState (ST s)) k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
v a -> m (Mutable v (PrimState m) a)
Vector.thaw v k
vs ST s (Mutable v s k)
-> (Mutable v s k -> ST s (Mutable v s k)) -> ST s (Mutable v s k)
forall a b. ST s a -> (a -> ST s b) -> ST s b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v s k -> ST s (Mutable v s k)
Mutable v (PrimState (ST s)) k
-> ST s (Mutable v (PrimState (ST s)) k)
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e, Ord e) =>
v (PrimState m) e -> m (v (PrimState m) e)
sortUniq ST s (Mutable v s k) -> (Mutable v s k -> ST s (v k)) -> ST s (v k)
forall a b. ST s a -> (a -> ST s b) -> ST s b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v s k -> ST s (v k)
Mutable v (PrimState (ST s)) k -> ST s (v k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
Vector.freeze
{-# INLINE fromVector #-}


-- | \(O(n \log n)\) Build an 'Index' from a 'Vector' of elements in ascending order. The precondition
-- that elements already be sorted is not checked. 
--
-- Note that since an 'Index' is composed of unique elements, 
-- the length of the index may not be the same as the length of the input vector:
--
-- >>> import Data.Vector as V
-- >>> fromAscVector $ V.fromList ['a', 'b', 'b', 'c']
-- Index "abc"
fromAscVector :: (Vector v k, Ord k) => v k -> Index k
fromAscVector :: forall (v :: * -> *) k. (Vector v k, Ord k) => v k -> Index k
fromAscVector = [k] -> Index k
forall k. Eq k => [k] -> Index k
fromAscList ([k] -> Index k) -> (v k -> [k]) -> v k -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v k -> [k]
forall (v :: * -> *) a. Vector v a => v a -> [a]
Vector.toList
{-# INLINE fromAscVector #-}


-- | \(O(n)\) Build an 'Index' from a 'Vector' of unique elements in ascending order. The precondition
-- that elements already be unique and sorted is not checked.
fromDistinctAscVector :: Vector v k => v k -> Index k
fromDistinctAscVector :: forall (v :: * -> *) k. Vector v k => v k -> Index k
fromDistinctAscVector = [k] -> Index k
forall k. [k] -> Index k
fromDistinctAscList ([k] -> Index k) -> (v k -> [k]) -> v k -> Index k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v k -> [k]
forall (v :: * -> *) a. Vector v a => v a -> [a]
Vector.toList
{-# INLINE fromDistinctAscVector #-}


-- | \(O(1)\) Convert an 'Index' to a 'Set'.
toSet :: Index k -> Set k
toSet :: forall k. Index k -> Set k
toSet = Index k -> Set k
forall t k. IsIndex t k => Index k -> t
fromIndex
{-# INLINE toSet #-}


-- | \(O(n)\) Convert an 'Index' to a list. Elements will be produced in ascending order.
toAscList :: Index k -> [k]
toAscList :: forall a. Index a -> [a]
toAscList (MkIndex Set k
s) = Set k -> [k]
forall a. Set a -> [a]
Set.toAscList Set k
s
{-# INLINE toAscList #-}


-- | \(O(n)\) Convert an 'Index' to a list. Elements will be produced in ascending order.
toAscVector :: Vector v k => Index k -> v k
toAscVector :: forall (v :: * -> *) k. Vector v k => Index k -> v k
toAscVector Index k
ix = (forall s. ST s (v k)) -> v k
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (v k)) -> v k) -> (forall s. ST s (v k)) -> v k
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> k) -> ST s (Mutable v (PrimState (ST s)) k)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> a) -> m (v (PrimState m) a)
M.generate (Index k -> Int
forall a. Index a -> Int
size Index k
ix) (Int -> Index k -> k
forall k. HasCallStack => Int -> Index k -> k
`elemAt` Index k
ix) ST s (Mutable v s k) -> (Mutable v s k -> ST s (v k)) -> ST s (v k)
forall a b. ST s a -> (a -> ST s b) -> ST s b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v s k -> ST s (v k)
Mutable v (PrimState (ST s)) k -> ST s (v k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
Vector.freeze
{-# INLINE toAscVector #-}


-- | \(O(1)\) Returns 'True' for an empty 'Index', and @False@ otherwise.
null :: Index k -> Bool
null :: forall a. Index a -> Bool
null (MkIndex Set k
ix) = Set k -> Bool
forall a. Set a -> Bool
Set.null Set k
ix
{-# INLINE null #-}


-- | \(O(n \log n)\) Check whether the element is in the index.
member :: Ord k => k -> Index k -> Bool
member :: forall k. Ord k => k -> Index k -> Bool
member k
k (MkIndex Set k
ix) = k
k k -> Set k -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set k
ix
{-# INLINE member #-}


-- | \(O(n \log n)\) Check whether the element is NOT in the index.
notMember :: Ord k => k -> Index k -> Bool
notMember :: forall k. Ord k => k -> Index k -> Bool
notMember k
k = Bool -> Bool
not (Bool -> Bool) -> (Index k -> Bool) -> Index k -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Index k -> Bool
forall k. Ord k => k -> Index k -> Bool
member k
k
{-# INLINE notMember #-}


-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Union of two 'Index', containing
-- elements either in the left index, right right index, or both.
union :: Ord k => Index k -> Index k -> Index k
union :: forall k. Ord k => Index k -> Index k -> Index k
union = Index k -> Index k -> Index k
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE union #-}


-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Intersection of two 'Index', containing
-- elements which are in both the left index and the right index.
intersection :: Ord k => Index k -> Index k -> Index k
intersection :: forall k. Ord k => Index k -> Index k -> Index k
intersection (MkIndex Set k
ix) (MkIndex Set k
jx) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> Set k -> Index k
forall a b. (a -> b) -> a -> b
$ Set k
ix Set k -> Set k -> Set k
forall a. Ord a => Set a -> Set a -> Set a
`Set.intersection` Set k
jx
{-# INLINE intersection #-}


-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Returns the elements of the first index 
-- which are not found in the second index.
--
-- >>> difference (fromList ['a', 'b', 'c']) (fromList ['b', 'c', 'd'])
-- Index "a"
difference :: Ord k => Index k -> Index k -> Index k
difference :: forall k. Ord k => Index k -> Index k -> Index k
difference (MkIndex Set k
ix) (MkIndex Set k
jx) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> Set k -> Index k
forall a b. (a -> b) -> a -> b
$ Set k -> Set k -> Set k
forall a. Ord a => Set a -> Set a -> Set a
Set.difference Set k
ix Set k
jx
{-# INLINE difference #-}


-- | \(O(n+m)\). The symmetric difference of two 'Index'.
-- The first element of the tuple is an 'Index' containing all elements which
-- are only found in the left 'Index', while the second element of the tuple is an 'Index' containing
-- all elements which are only found in the right 'Index':
--
-- >>> left = fromList ['a', 'b', 'c']
-- >>> right = fromList ['c', 'd', 'e']
-- >>> left `symmetricDifference` right
-- (Index "ab",Index "de")
symmetricDifference :: Ord k => Index k -> Index k -> (Index k, Index k)
symmetricDifference :: forall k. Ord k => Index k -> Index k -> (Index k, Index k)
symmetricDifference Index k
left Index k
right = (Index k
left Index k -> Index k -> Index k
forall k. Ord k => Index k -> Index k -> Index k
`difference` Index k
right, Index k
right Index k -> Index k -> Index k
forall k. Ord k => Index k -> Index k -> Index k
`difference` Index k
left)
{-# INLINE symmetricDifference #-}


-- | \(O(n m)\) Take the cartesian product of two 'Index':
--
-- >>> (range (+1) (1 :: Int) 2) `cartesianProduct` (range (+1) (3 :: Int) 4)
-- Index [(1,3),(1,4),(2,3),(2,4)]
cartesianProduct :: Index k -> Index g -> Index (k, g)
cartesianProduct :: forall k g. Index k -> Index g -> Index (k, g)
cartesianProduct (MkIndex Set k
xs) (MkIndex Set g
ys) 
    = Set (k, g) -> Index (k, g)
forall k. Set k -> Index k
MkIndex (Set (k, g) -> Index (k, g)) -> Set (k, g) -> Index (k, g)
forall a b. (a -> b) -> a -> b
$ Set k -> Set g -> Set (k, g)
forall a b. Set a -> Set b -> Set (a, b)
Set.cartesianProduct Set k
xs Set g
ys
{-# INLINE cartesianProduct #-}


-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\).
-- @(ix1 \'contains\' ix2)@ indicates whether all keys in @ix2@ are also in @ix1@.
contains :: Ord k => Index k -> Index k -> Bool
contains :: forall k. Ord k => Index k -> Index k -> Bool
contains (MkIndex Set k
ix1) (MkIndex Set k
ix2)= Set k
ix2 Set k -> Set k -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`Set.isSubsetOf` Set k
ix1
{-# INLINE contains #-}


-- | \(O(1)\) Returns the number of keys in the index.
size :: Index k -> Int
size :: forall a. Index a -> Int
size (MkIndex Set k
ix) = Set k -> Int
forall a. Set a -> Int
Set.size Set k
ix
{-# INLINE size #-}


-- | \(O(\log n)\). Take @n@ elements from the index, in ascending order.
-- Taking more than the number of elements in the index is a no-op:
--
-- >>> take 10 $ fromList [1::Int,2,3]
-- Index [1,2,3]
take :: Int -> Index k -> Index k
take :: forall k. Int -> Index k -> Index k
take Int
n (MkIndex Set k
ix) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Int -> Set k -> Set k
forall a. Int -> Set a -> Set a
Set.take Int
n Set k
ix)
{-# INLINE take #-}


-- | \(O(\log n)\). Drop @n@ elements from the index, in ascending order.
drop :: Int -> Index k -> Index k
drop :: forall k. Int -> Index k -> Index k
drop Int
n (MkIndex Set k
ix) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Int -> Set k -> Set k
forall a. Int -> Set a -> Set a
Set.drop Int
n Set k
ix)
{-# INLINE drop #-}


-- | \(O(n \log n)\) Map a function over keys in the index.
-- Note that since keys in an 'Index' are unique, the length of the resulting
-- index may not be the same as the input:
--
-- >>> map (\x -> if even x then 0::Int else 1) $ fromList [0::Int,1,2,3,4]
-- Index [0,1]
--
-- If the mapping is monotonic, see 'mapMonotonic', which has better performance
-- characteristics.
map :: Ord g => (k -> g) -> Index k -> Index g
map :: forall g k. Ord g => (k -> g) -> Index k -> Index g
map k -> g
f (MkIndex Set k
ix) = Set g -> Index g
forall k. Set k -> Index k
MkIndex (Set g -> Index g) -> Set g -> Index g
forall a b. (a -> b) -> a -> b
$ (k -> g) -> Set k -> Set g
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map k -> g
f Set k
ix
{-# INLINE map #-}


-- | \(O(n)\) Map a monotonic function over keys in the index. /Monotonic/ means that if @a < b@, then @f a < f b@.
-- Using 'mapMonononic' can be much faster than using 'map' for a large 'Index'.
-- Note that the precondiction that the function be monotonic is not checked.
--
-- >>> mapMonotonic (+1) $ fromList [0::Int,1,2,3,4,5]
-- Index [1,2,3,4,5,6]
mapMonotonic :: (k -> g) -> Index k -> Index g
mapMonotonic :: forall k g. (k -> g) -> Index k -> Index g
mapMonotonic k -> g
f (MkIndex Set k
ix) = Set g -> Index g
forall k. Set k -> Index k
MkIndex (Set g -> Index g) -> Set g -> Index g
forall a b. (a -> b) -> a -> b
$ (k -> g) -> Set k -> Set g
forall a b. (a -> b) -> Set a -> Set b
Set.mapMonotonic k -> g
f Set k
ix
{-# INLINE mapMonotonic #-}


-- | \(O(n)\) Filter elements satisfying a predicate.
--
-- >>> filter even $ fromList [1::Int,2,3,4,5]
-- Index [2,4]
filter :: (k -> Bool) -> Index k -> Index k
filter :: forall k. (k -> Bool) -> Index k -> Index k
filter k -> Bool
p (MkIndex Set k
ix) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> Set k -> Index k
forall a b. (a -> b) -> a -> b
$ (k -> Bool) -> Set k -> Set k
forall a. (a -> Bool) -> Set a -> Set a
Set.filter k -> Bool
p Set k
ix
{-# INLINE filter #-}


-- | \(O(\log n)\). Returns the integer /index/ of a key. This function raises an exception
-- if the key is not in the 'Index'; see 'lookupIndex' for a safe version.
--
-- >>> findIndex 'b' $ fromList ['a', 'b', 'c']
-- 1
findIndex :: HasCallStack => Ord k => k -> Index k -> Int
findIndex :: forall k. (HasCallStack, Ord k) => k -> Index k -> Int
findIndex k
e (MkIndex Set k
ix) = k -> Set k -> Int
forall a. Ord a => a -> Set a -> Int
Set.findIndex k
e Set k
ix 
{-# INLINE findIndex #-}


-- | \(O(\log n)\). Returns the integer /index/ of a key, if the key is in the index.
--
-- >>> lookupIndex 'b' $ fromList ['a', 'b', 'c']
-- Just 1
-- >>> lookupIndex 'd' $ fromList ['a', 'b', 'c']
-- Nothing
lookupIndex :: Ord k => k -> Index k -> Maybe Int
lookupIndex :: forall k. Ord k => k -> Index k -> Maybe Int
lookupIndex k
e (MkIndex Set k
ix) = k -> Set k -> Maybe Int
forall a. Ord a => a -> Set a -> Maybe Int
Set.lookupIndex k
e Set k
ix
{-# INLINE lookupIndex #-}


-- | \(O(\log n)\) Returns the element at some integer index. This function raises
-- an exception if the integer index is out-of-bounds.
elemAt :: HasCallStack => Int -> Index k -> k
elemAt :: forall k. HasCallStack => Int -> Index k -> k
elemAt Int
n (MkIndex Set k
ix) = Int -> Set k -> k
forall a. Int -> Set a -> a
Set.elemAt Int
n Set k
ix
{-# INLINE elemAt #-}


-- | \(O(\log n)\). Insert a key in an 'Index'. If the key is already 
-- present, the 'Index' will not change.
insert :: Ord k => k -> Index k -> Index k
insert :: forall k. Ord k => k -> Index k -> Index k
insert k
k (MkIndex Set k
ix) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> Set k -> Index k
forall a b. (a -> b) -> a -> b
$ k
k k -> Set k -> Set k
forall a. Ord a => a -> Set a -> Set a
`Set.insert` Set k
ix
{-# INLINE insert #-}


-- | \(O(\log n)\). Delete a key from an 'Index', if this key is present
-- in the index.
delete :: Ord k => k -> Index k -> Index k
delete :: forall k. Ord k => k -> Index k -> Index k
delete k
k (MkIndex Set k
ix) = Set k -> Index k
forall k. Set k -> Index k
MkIndex (Set k -> Index k) -> Set k -> Index k
forall a b. (a -> b) -> a -> b
$ k
k k -> Set k -> Set k
forall a. Ord a => a -> Set a -> Set a
`Set.delete` Set k
ix
{-# INLINE delete #-}


-- | \(O(n \log n)\). Map each element of an 'Index' to an applicative action, 
-- evaluate these actions from left to right, and collect the results.
--
-- Note that the data type 'Index' is not a member of 'Traversable'
-- because it is not a 'Functor'.
traverse :: (Applicative f, Ord b) => (k -> f b) -> Index k -> f (Index b)
traverse :: forall (f :: * -> *) b k.
(Applicative f, Ord b) =>
(k -> f b) -> Index k -> f (Index b)
traverse k -> f b
f = ([b] -> Index b) -> f [b] -> f (Index b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [b] -> Index b
forall k. Ord k => [k] -> Index k
fromList (f [b] -> f (Index b))
-> (Index k -> f [b]) -> Index k -> f (Index b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> f b) -> [k] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
Traversable.traverse k -> f b
f ([k] -> f [b]) -> (Index k -> [k]) -> Index k -> f [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index k -> [k]
forall a. Index a -> [a]
toAscList
{-# INLINE traverse #-}