{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DerivingStrategies #-}

module Data.Bytes.HashMap.Internal
  ( Map (..)
  ) where

import Data.Int (Int32)
import Data.Primitive (ByteArray, PrimArray, SmallArray)
import Data.Primitive.Unlifted.Array (UnliftedArray)

{- | A static perfect hash table where the keys are byte arrays. This
  table cannot be updated after its creation, but all lookups have
  guaranteed O(1) worst-case cost. It consumes linear space. This
  is an excellent candidate for use with compact regions.
-}
data Map v
  = Map
      !ByteArray -- top-level entropy
      !(UnliftedArray ByteArray) -- entropies
      !(PrimArray Int32) -- offset to apply to hash, could probably be 32 bits
      !(UnliftedArray ByteArray) -- keys
      !(SmallArray v) -- values
  deriving stock ((forall a b. (a -> b) -> Map a -> Map b)
-> (forall a b. a -> Map b -> Map a) -> Functor Map
forall a b. a -> Map b -> Map a
forall a b. (a -> b) -> Map a -> Map b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> Map a -> Map b
fmap :: forall a b. (a -> b) -> Map a -> Map b
$c<$ :: forall a b. a -> Map b -> Map a
<$ :: forall a b. a -> Map b -> Map a
Functor, (forall m. Monoid m => Map m -> m)
-> (forall m a. Monoid m => (a -> m) -> Map a -> m)
-> (forall m a. Monoid m => (a -> m) -> Map a -> m)
-> (forall a b. (a -> b -> b) -> b -> Map a -> b)
-> (forall a b. (a -> b -> b) -> b -> Map a -> b)
-> (forall b a. (b -> a -> b) -> b -> Map a -> b)
-> (forall b a. (b -> a -> b) -> b -> Map a -> b)
-> (forall a. (a -> a -> a) -> Map a -> a)
-> (forall a. (a -> a -> a) -> Map a -> a)
-> (forall a. Map a -> [a])
-> (forall a. Map a -> Bool)
-> (forall a. Map a -> Int)
-> (forall a. Eq a => a -> Map a -> Bool)
-> (forall a. Ord a => Map a -> a)
-> (forall a. Ord a => Map a -> a)
-> (forall a. Num a => Map a -> a)
-> (forall a. Num a => Map a -> a)
-> Foldable Map
forall a. Eq a => a -> Map a -> Bool
forall a. Num a => Map a -> a
forall a. Ord a => Map a -> a
forall m. Monoid m => Map m -> m
forall a. Map a -> Bool
forall a. Map a -> Int
forall a. Map a -> [a]
forall a. (a -> a -> a) -> Map a -> a
forall m a. Monoid m => (a -> m) -> Map a -> m
forall b a. (b -> a -> b) -> b -> Map a -> b
forall a b. (a -> b -> b) -> b -> Map 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 => Map m -> m
fold :: forall m. Monoid m => Map m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Map a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Map a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Map a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Map a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> Map a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Map a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Map a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Map a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Map a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Map a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Map a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Map a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> Map a -> a
foldr1 :: forall a. (a -> a -> a) -> Map a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Map a -> a
foldl1 :: forall a. (a -> a -> a) -> Map a -> a
$ctoList :: forall a. Map a -> [a]
toList :: forall a. Map a -> [a]
$cnull :: forall a. Map a -> Bool
null :: forall a. Map a -> Bool
$clength :: forall a. Map a -> Int
length :: forall a. Map a -> Int
$celem :: forall a. Eq a => a -> Map a -> Bool
elem :: forall a. Eq a => a -> Map a -> Bool
$cmaximum :: forall a. Ord a => Map a -> a
maximum :: forall a. Ord a => Map a -> a
$cminimum :: forall a. Ord a => Map a -> a
minimum :: forall a. Ord a => Map a -> a
$csum :: forall a. Num a => Map a -> a
sum :: forall a. Num a => Map a -> a
$cproduct :: forall a. Num a => Map a -> a
product :: forall a. Num a => Map a -> a
Foldable, Functor Map
Foldable Map
(Functor Map, Foldable Map) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> Map a -> f (Map b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Map (f a) -> f (Map a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Map a -> m (Map b))
-> (forall (m :: * -> *) a. Monad m => Map (m a) -> m (Map a))
-> Traversable Map
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Map (m a) -> m (Map a)
forall (f :: * -> *) a. Applicative f => Map (f a) -> f (Map a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Map a -> m (Map b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map a -> f (Map b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map a -> f (Map b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map a -> f (Map b)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Map (f a) -> f (Map a)
sequenceA :: forall (f :: * -> *) a. Applicative f => Map (f a) -> f (Map a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Map a -> m (Map b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Map a -> m (Map b)
$csequence :: forall (m :: * -> *) a. Monad m => Map (m a) -> m (Map a)
sequence :: forall (m :: * -> *) a. Monad m => Map (m a) -> m (Map a)
Traversable)