{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE UndecidableInstances #-}
module Data.RandomAccessList.RelativizedMap (RelativizedMap (..))where

import Data.Word

import Data.RandomAccessList.Class qualified as RAL

import Data.IntMap.Strict qualified as IM
import GHC.Exts (IsList)

-- | A sequence implemented by a map from "levels" to values and a counter giving the "current"
-- level.
data RelativizedMap a = RelativizedMap (IM.IntMap a) {-# UNPACK #-} !Word64
    deriving stock (Int -> RelativizedMap a -> ShowS
[RelativizedMap a] -> ShowS
RelativizedMap a -> String
(Int -> RelativizedMap a -> ShowS)
-> (RelativizedMap a -> String)
-> ([RelativizedMap a] -> ShowS)
-> Show (RelativizedMap a)
forall a. Show a => Int -> RelativizedMap a -> ShowS
forall a. Show a => [RelativizedMap a] -> ShowS
forall a. Show a => RelativizedMap a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> RelativizedMap a -> ShowS
showsPrec :: Int -> RelativizedMap a -> ShowS
$cshow :: forall a. Show a => RelativizedMap a -> String
show :: RelativizedMap a -> String
$cshowList :: forall a. Show a => [RelativizedMap a] -> ShowS
showList :: [RelativizedMap a] -> ShowS
Show, RelativizedMap a -> RelativizedMap a -> Bool
(RelativizedMap a -> RelativizedMap a -> Bool)
-> (RelativizedMap a -> RelativizedMap a -> Bool)
-> Eq (RelativizedMap a)
forall a. Eq a => RelativizedMap a -> RelativizedMap a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => RelativizedMap a -> RelativizedMap a -> Bool
== :: RelativizedMap a -> RelativizedMap a -> Bool
$c/= :: forall a. Eq a => RelativizedMap a -> RelativizedMap a -> Bool
/= :: RelativizedMap a -> RelativizedMap a -> Bool
Eq)
    deriving (Int -> [Item (RelativizedMap a)] -> RelativizedMap a
[Item (RelativizedMap a)] -> RelativizedMap a
RelativizedMap a -> [Item (RelativizedMap a)]
([Item (RelativizedMap a)] -> RelativizedMap a)
-> (Int -> [Item (RelativizedMap a)] -> RelativizedMap a)
-> (RelativizedMap a -> [Item (RelativizedMap a)])
-> IsList (RelativizedMap a)
forall a. Int -> [Item (RelativizedMap a)] -> RelativizedMap a
forall a. [Item (RelativizedMap a)] -> RelativizedMap a
forall a. RelativizedMap a -> [Item (RelativizedMap a)]
forall l.
([Item l] -> l)
-> (Int -> [Item l] -> l) -> (l -> [Item l]) -> IsList l
$cfromList :: forall a. [Item (RelativizedMap a)] -> RelativizedMap a
fromList :: [Item (RelativizedMap a)] -> RelativizedMap a
$cfromListN :: forall a. Int -> [Item (RelativizedMap a)] -> RelativizedMap a
fromListN :: Int -> [Item (RelativizedMap a)] -> RelativizedMap a
$ctoList :: forall a. RelativizedMap a -> [Item (RelativizedMap a)]
toList :: RelativizedMap a -> [Item (RelativizedMap a)]
IsList) via RAL.AsRAL (RelativizedMap a)

instance RAL.RandomAccessList (RelativizedMap a) where
    type Element (RelativizedMap a) = a

    {-# INLINABLE empty #-}
    empty :: RelativizedMap a
empty = IntMap a -> Word64 -> RelativizedMap a
forall a. IntMap a -> Word64 -> RelativizedMap a
RelativizedMap IntMap a
forall a. Monoid a => a
mempty Word64
0
    {-# INLINABLE cons #-}
    cons :: Element (RelativizedMap a) -> RelativizedMap a -> RelativizedMap a
cons Element (RelativizedMap a)
a (RelativizedMap IntMap a
im Word64
l) = IntMap a -> Word64 -> RelativizedMap a
forall a. IntMap a -> Word64 -> RelativizedMap a
RelativizedMap (Int -> a -> IntMap a -> IntMap a
forall a. Int -> a -> IntMap a -> IntMap a
IM.insert (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
l) a
Element (RelativizedMap a)
a IntMap a
im) (Word64
lWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+Word64
1)
    {-# INLINABLE uncons #-}
    uncons :: RelativizedMap a
-> Maybe (Element (RelativizedMap a), RelativizedMap a)
uncons (RelativizedMap IntMap a
_ Word64
0) = Maybe (a, RelativizedMap a)
Maybe (Element (RelativizedMap a), RelativizedMap a)
forall a. Maybe a
Nothing
    uncons (RelativizedMap IntMap a
im Word64
l) = case IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey IntMap a
im of
        Maybe ((Int, a), IntMap a)
Nothing            -> Maybe (a, RelativizedMap a)
Maybe (Element (RelativizedMap a), RelativizedMap a)
forall a. Maybe a
Nothing
        Just ((Int
_, a
a), IntMap a
res) -> (a, RelativizedMap a) -> Maybe (a, RelativizedMap a)
forall a. a -> Maybe a
Just (a
a, IntMap a -> Word64 -> RelativizedMap a
forall a. IntMap a -> Word64 -> RelativizedMap a
RelativizedMap IntMap a
res (Word64
lWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1))
    {-# INLINABLE length #-}
    length :: RelativizedMap a -> Word64
length (RelativizedMap IntMap a
_ Word64
l) = Word64
l
    {-# INLINABLE indexZero #-}
    indexZero :: RelativizedMap a -> Word64 -> Maybe (Element (RelativizedMap a))
indexZero (RelativizedMap IntMap a
_ Word64
0) Word64
_  = Maybe a
Maybe (Element (RelativizedMap a))
forall a. Maybe a
Nothing
    indexZero (RelativizedMap IntMap a
im Word64
l) Word64
w =
        let maxIndex :: Word64
maxIndex = Word64
lWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1 in
            if Word64
w Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
> Word64
maxIndex then Maybe a
Maybe (Element (RelativizedMap a))
forall a. Maybe a
Nothing else Int -> IntMap a -> Maybe a
forall a. Int -> IntMap a -> Maybe a
IM.lookup (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
maxIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
- Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
w) IntMap a
im